CSE 130 - Programming Assignment #3

Common Lisp and (a Bit of) Java

Must be turned in no later than 11:59:59 PM on Thursday, 29 May
(see submission instructions below)

(click your browser's refresh button to ensure that you have the most recent version)

Code Documentation

Code for all programming assignments should be well documented.  A working program with no comments will receive only partial credit.  Documentation entails writing a description of each function/method, class/structure, as well as comments throughout the code to explain the program logic.  Comments in Common Lisp begin with a semicolon (;) and are terminated by a newline/carriage return.

While few programming assignments pretend to mimic the "real" world, they may, nevertheless, contain some of the ambiguity that exists outside the classroom.  If, for example, an assignment is amenable to differing interpretations, such that more than one algorithm may implement a correct solution to the assignment, it is incumbent upon the programmer to document not only the functionality of the algorithm (and more broadly his/her interpretation of the program requirements), but to articulate clearly the reasoning behind a particular choice of solution.

Integrity of Scholarship

University rules on integrity of scholarship will be strictly enforced.  By completing this assignment, you implicitly agree to abide by the UCSD Policy on Integrity of Scholarship described beginning on page 62 of the Academic Regulations section (PDF) of the 2002-2003 General Catalog, in particular, "all academic work will be done by the student to whom it is assigned, without unauthorized aid of any kind."

You are expected to do your own work on this assignment; there are no group projects in this course.  You may (and are encouraged to) engage in general discussions with your classmates regarding the assignment, but specific details of a solution, including the solution itself, must always be your own work.  Incidents which violate the University's rules on integrity of scholarship will be taken seriously.

In addition to receiving a zero (0) on the assignment, students may also face other penalties, up to and including, expulsion from the University.  Should you have any doubt about the moral and/or ethical implications of an activity associated with the completion of this assignment, please see the instructors.

Assignment Overview

The overall objective of this assignment is for you to gain some hands-on experience with problem solving using Common Lisp and contrast it with the approach encouraged by the use of Java.  The first three questions are simple exercises that require very little code, the intent being to provide a "warm up" for the main exercise.  Questions 4 and 5 require you to write programs in Common Lisp and Java, respectively.  The instructions for submission of your assignment may be found at the end of this document.  Please start this assignment early; Lisp programming, while not inherently difficult, can seem somewhat foreign at first, particularly when it comes to recursion and list manipulation.

Problem #1 - Return the last element of a list

Part A (10 points)

Write a Common Lisp function called my-last that returns a list containing the last top-level element of a list.  Examples of the function in operation (user input is in red):

CL-USER(1): (my-last '(1 2 3 4))
(4)
CL-USER(2): (my-last '())
NIL
CL-USER(3): (my-last '(1 2 (3 4)))
((3 4))

Requirements:

• You must implement your function without using last, length, or related standard Common Lisp functions.
• You must implement your function using recursion, not iteration.

Hints:

• Note that, with this and the following Lisp problems, it may be helpful to consider Lisp's internal representation of lists (i.e., cons cells, as discussed in class) in order to arrive at the appropriate implementation.  Specifically, think about what the various test functions (e.g., null, atom, listp, etc.) and list manipulation functions (e.g. car, cdr, cons, etc.) do when applied to cons cells.
• When expressed in terms of cons cells, the operation of my-last is to return the last cons cell at the top-level of a list (recall that, in Lisp's internal representation, the elements in a list are not atoms, symbols, etc., but rather cons cells which point to atoms, symbols, etc.).
• You may wish to compare the behavior of your my-last function with that of the standard Common Lisp function last to ensure that you've covered all argument cases.

Part B (15 points)

Write a Common Lisp function called recursive-last that returns a list containing the last atom anywhere in a list, whose elements may also be lists.  Examples of the function in operation (user input is in red):

CL-USER(1): (recursive-last '(1 2 3 4))
(4)
CL-USER(2): (recursive-last '())
NIL
CL-USER(3): (recursive-last '(1 2 (3 4)))
(4)
CL-USER(4): (recursive-last '(1 2 (3 4) (5 (6 7))))
(7)

Requirements:

• You must implement your function without using last, length, or related standard Common Lisp functions.
• You must implement your function using recursion, not iteration.

Hint:

• Recursively defined, this function returns the last cons cell, of the last cons cell, of the last cons cell (and so on) in a given list.

Problem #2 - Reverse a list

Part A (10 points)

Write a Common Lisp function called my-reverse that reverses the top-level elements of a list.  Examples of the function in operation (user input is in red):

CL-USER(1): (my-reverse '(1 2 3 4))
(4 3 2 1)
CL-USER(2): (my-reverse '(1 2 (3 4)))
((3 4) 2 1)
CL-USER(3): (my-reverse '(1 () (3 4)))
((3 4) NIL 1)

Requirements:

• You must implement your function without using reverse or related standard Common Lisp functions.
• You must implement your function using recursion, not iteration.

Hint:

• You may wish to compare the behavior of your my-reverse function with that of the standard Common Lisp function reverse to ensure that you've covered all argument cases.

Part B (15 points)

Write a Common Lisp function called recursive-reverse that reverses the elements of a list whose elements may be either atoms or lists.  If an element is a list, then its elements should also be reversed (and so on, recursively).  Examples of the function in operation (user input is in red):

CL-USER(1): (recursive-reverse '(1 2 3 4))
(4 3 2 1)
CL-USER(2): (recursive-reverse '(1 2 (3 4)))
((4 3) 2 1)
CL-USER(3): (recursive-reverse '(1 (((2 7) 3) (4 5)) 6))
(6 ((5 4) (3 (7 2))) 1)

Requirements:

• You must implement your function without using reverse or related standard Common Lisp functions.
• You must implement your function using recursion, not iteration.

Problem #3 - Flatten a list (20 points)

Write a Common Lisp function called flatten that takes a list that may have embedded lists, and returns a flattened version of it (i.e., a list whose elements are only atoms).  Examples of the function in operation (user input is in red):

CL-USER(1): (flatten '(1 2 3 4))
(1 2 3 4)
CL-USER(2): (flatten '(1 2 (3 4)))
(1 2 3 4)
CL-USER(3): (flatten '(1 (2 3) (4 5 (6) ((((((7)))) 8)) 9) 10 (11) 12))
(1 2 3 4 5 6 7 8 9 10 11 12)

Requirement:

• You must implement your function using recursion, not iteration.

Problem #4 - Common Lisp Matchmaker (30 points)

You have recently been hired as the new head programmer at the Match-o-Matic dating service.  The CEO of the company, Heinrich Neuhaus, has decided that it's time to drag his company into the computer age, and thus find a replacement for the 3x5 index cards which have been the mainstay of Match-o-Matic for generations.  Herr Neuhaus has tasked you with the implementation of a prototype automated matchmaking system.  While not caring about the implementation details, his design criteria are that the input should be the characteristics describing two people plus a function specifying some compatibility metric to compute from those characteristics, and the output should be a number from 0 to 100 inclusive indicating the likelihood of a match.  In addition, he would like to expand beyond just dating, and have a flexible solution that will allow the matching of people in a variety of scenarios.

For example, if the only criterion for friendship (i.e., the compatibility function associated with that elusive concept known as "friendship") is having the same hair color, then if two persons have the same hair color, the output of the compatibility function is 100, while the value would be 0 if the two people in question have different colors of hair (Herr Neuhaus has a Weltanschauung that admits no shades of grey, so to speak).

Knowing that matchmaking is as much art as science, and recalling with great clarity the lessons learned in CSE 130, you remember that Common Lisp is not only well suited to Artificial Intelligence but permits the programmer great flexibility in the design and implementation of solutions in fuzzy problem domains.  An initial analysis shows that a reasonable approach is to consider the characteristics of individuals as lists of features, and the compatibility metric as a list of functions to be applied, as appropriate, to the features of the individuals being matched.  For example, consider the following:  Say that Jack and Jill both have brown hair, and the metric for friendship is as described above; in list form this information might look like

Jack's feature list:
     (("hair-color" "brown"))

Jill's feature list:
     (("hair-color" "brown"))

If the sole compatibility function for friendship is the following (that the hair-color of person A equals the hair-color of person B)
     (defun hair-color-metric (a b)
       (cond ((equal a b) 100)
       (t 0)))

then the complete list of functions for computing friendship would be
     (("hair-color" hair-color-metric))

The application of hair-color-metric to the hair-color features of Jack and Jill would produce a score of 100.  Note in the last list the pairing of the string representing the name of a feature with the name of the function that computes the metric associated with the feature; more on this below.

The general requirements of the system you are to build for Herr Neuhaus are as follows:

• Write a Common Lisp function named compatibility which takes three arguments: (1) a list of features associated with a person, (2) a list of features associated with a person, (3) a list of lists consisting of pairs of feature names (strings) and functions which operate on the corresponding features.
• The list of features associated with a person consists of a list of lists.  The first element of each sublist is a string representing the name of a feature, while the second element is an atom or list representing the values associated with a feature.
• Each constituent function of the overall compatibility metric (i.e., the list of feature/function pairs) will take arguments appropriate to corresponding feature and produce a number from 0 to 100 inclusive.
• The value returned by the compatibility function will be the arithmetic mean of the scores resulting from the application of all of the functions which make up any given compatibility metric.

Consider the example feature lists

(defparameter *person-A*
  '(("hair-color" "brown")
    ("eye-color" "hazel")
    ("age" 32)
    ("favorite-movies" ("The Matrix" "Bambi Meets Godzilla"))))

(defparameter *person-B*
  '(("hair-color" "black")
    ("eye-color" "brown")
    ("age" 27)
    ("favorite-movies" ("Terminator 2" "The Matrix"))))

the feature comparison functions

(defun hair-color-metric (a b)
  (cond ((equal a b) 100)
  (t 0)))

(defun eye-color-metric (a b)
  (cond ((equal a b) 100)
        ((or (and (equal a "blue") (equal b "green"))
             (and (equal a "green") (equal b "blue")))
         75)
        ((or (equal a "hazel")
             (equal b "hazel"))
         50)
        (t 0)))

(defun age-metric (a b)
  (cond ((<= (abs (- a b)) 5) 100)
        ((<= (abs (- a b)) 7) 50)
        (t 0)))

(defun movie-metric (a b)
  (* (/ (length (intersection a b :test 'equal))
        (length (union a b :test 'equal)))
     100.0))

and the compatibility metric

(defvar *dating*
  '(("hair-color" hair-color-metric)
    ("eye-color" eye-color-metric)
    ("age" age-metric)
    ("favorite-movies" movie-metric)))

The application of the compatibility function as

(compatibility *person-A* *person-B* *dating*)

would return a value of 45.833336, possibly meaning that persons A and B, if currently dating, may wish to consider trying out *just-friends* instead (assuming such a compatibility metric exists, of course).

Requirements:

• You may use any standard Common Lisp functions in your implementation, but you must implement the compatibility function (and any ancillary functions) using recursion, not iteration.

Hints:

• In keeping with the spirit of the A.I. problem space, note that your task is to write a general purpose driver function which will take arguments as specified above, but has no prior knowledge of the nature of the arguments beyond the expected format (e.g., a list of lists with keywords of type string corresponding to the names of features).  In other words your compatibility function should work on all input forms which meet the format criteria.
• Common Lisp supports higher order functions, namely the ability to pass functions as parameters and return them as the result of function invocation.  In order to make such features useful, Common Lisp has two functions, apply and funcall, which provide a means of calling the function objects passed as arguments.  For example, given the function definition
  
       (defun do-apply (f l)
         (apply f l))
  
  the function call
  
            (do-apply 'eye-color-metric '("blue" "green"))
  
  is equivalent to
  
            (eye-color-metric "blue" "green")
   
• Another often useful feature of Common Lisp is the ability to create "anonymous" function definitions, i.e., Lisp forms which specify functionality without binding it to a name.  To represent the definition of a function, we use what is known as a lambda expression.  For example, the lambda expression corresponding to the hair-color-metric function above would be
  
       (lambda (a b)
         (cond ((equal a b) 100)
               (t 0)))
  
  Formatted for a single line, but otherwise unchanged, this anonymous function definition can then be passed as an argument to the do-apply function defined above:
  
       (do-apply (lambda (a b) (cond ((equal a b) 100) (t 0))) '("brown" "brown"))
  
  In the context of this assignment, note the potential utility of being able to pass the operational specification of a function without ever having to define the function itself.  Why is this useful?  Simple:  If at runtime you do not have access to the Lisp interpreter to define functions with defun (i.e., in order to associate a function definition with a symbolic name), you can still pass the definitions of functions to the compatibility function as lambda expressions.  This provides the ability to incorporate new functionality into existing code at runtime.
• Common Lisp is a complex language, with many useful features; be sure to consult the online resources referenced at the bottom of the main class web page.

Problem #5 - Java Matchmaker

Part A (20 points)

Much to your dismay, Herr Neuhaus has paid a visit to the JavaSoft web site and is totally enamored of Java and the object-oriented programming paradigm.  His "executive summary" understanding of Java does not match your ability to compare in depth the relative merits of two very different programming paradigms: functional (or applicative) programming in the form of Common Lisp, and object-oriented programming in the form of Java.  Prepare a design document describing how you would implement the same functionality from Problem #4 but using Java, and based on that design specification compare and contrast the suitability of the two different paradigms for the implementation of a solution to the generalized pattern matching domain.

Part B (extra credit) (20 points)

Sadly, Herr Neuhaus is not convinced by your erudite analysis of Part A, so you decide on the brute force approach of implementing in Java exactly the functionality of the Common Lisp solution to Problem #4.  Present your pointy haired boss with the source code for your Java solution, as well as a thorough analysis of any differences in difficulty and/or complexities encountered in the Java implementation as compared with the Common Lisp implementation.

For the purposes of your Java implementation, assume that the driver program is called as

java Driver <input_file_1> <input_file_2> <input_file3>

where <input_file_1> is the name of the file containing the feature list of person 1, <input_file_2> is the name of the file containing the feature list of person 2, and <input_file_3> is the name of the file containing the specification of the compatibility function (i.e., the definitions of the constituent functions).

The format of the feature list of a person (i.e., the format for the first two input files) is one feature name/feature list combination per line.  For example, the feature list of *person-A* above might appear as follows in the input file:

hairColor "brown"
eyeColor "hazel"
age 32
favoriteMovies "The Matrix" "Bambi Meets Godzilla"

The format of the file containing the constituent functions (i.e., the format of the third input file) consists of pairs of feature names and Java method definitions, with the feature name appearing on a line by itself, followed on one or more subsequent lines specifying the associated method definition.  Feature name/method definition pairs are separated by a single blank line.  For example, the first two constituent functions for *dating* above might appear in the input file as

hairColor
int hairColorMetric(String a, String b) {
    if (a.equals(b))
        return 100;
    else
        return 0;
}

eyeColor
int eyeColorMetric(String a, String b) {
    if (a.equals(b))
        return 100;
    else if (a.equals("blue") && b.equals("green"))
        return 75;
    else if (a.equals("green") && b.equals("blue"))
        return 75;
    else if (a.equals("hazel") || b.equals("hazel"))
        return 50;
    else
    return 0;
}

The file would have similar feature name/method definition pairs for age and favoriteMovies (these are omitted here for the sake of brevity).  Note that, as with the Common Lisp implementation,  the names of the individual features are arbitrary, but should be consistent among all three input files.  The names associated with the method definitions are arbitrary as long as your driver program has an internal mapping from each feature name to the corresponding method definition.

Submission Guidelines/Instructions

Testing

Your functions/programs must compile and/or run on an ACS machine, as this is where the verification of your solutions will occur.  While you may develop your code on any system, ensure that your code runs as expected on an ACS machine prior to submission.  Code which does not compile and/or produce the desired results on the testing machine will receive little or no credit.  You should test your code in the directories from which the tar file (see below) will be created, as this will approximate the environment used for grading the assignment.

Creating the tar file for submission

Your answers to this assignment will be stored in subdirectories corresponding to each of the five problems specified above.  The directory hierarchy should appear as follows:

<username>_cse130_pa3/
     problem1/
          problem1.lisp
     problem2/
          problem2.lisp
     problem3/
          problem3.lisp
     problem4/
          problem4.lisp
     problem5/
          part_a.txt, and optionally a Makefile, Java source files, and part_b.txt

<username> is your CSE 130 account username (i.e., your login name).  For example, as indicated above, in the problem1 subdirectory of the main <username>_cse130_pa3 directory, you should have a single file named problem1.lisp, which will contain the documented Common Lisp source code to implement the functions specified in Problem #1 of this assignment.  In the problem5 subdirectory, the write up for Part A should be in a text file named part_a.txt.  If you choose to do the optional Part B, in addition to the write up in a file named part_b.txt, you should also place in this subdirectory all of the documented Java source code files, plus a makefile such that the program will compile when a user types make, and run when the user types

java Driver <input_file_1> <input_file_2> <input_file_3>

where the input files are as described above in Part B of Problem #5..

Assuming the directory hierarchy above, populated with the problem solutions as described, you should create a tar file called <username>_cse130_pa3.tar by running the tar command in the directory where the <username>_cse130_pa3 directory resides.  For example, if the directory containing the answers to your assignment is located in the current directory and your account is cs130szz, running the command

tar cf cs130szz_cse130_pa3.tar cs130szz_cse130_pa3

will create the desired tar file (in this case, named cs130szz_cse130_pa3.tar) from the directory named cs130szz_cse130_pa3.

Submitting the program via the turnin program

Once you've created the tar file containing all of your answers to the assignment questions, you will use the turnin program to submit this file for grading.  Using the turnin program is straightforward.  Assuming you are in the directory where you've created the <username>_cse130_pa3.tar file, simply run the turnin command as follows:

turnin -c cs130s <username>_cse130_pa3.tar

remembering to replace <username> with your CSE 130 account username (i.e., login name).  The turnin program will provide you with a confirmation of the submission process; make sure that the size of the file indicated by turnin matches the size of your tar file.  See the ACS web page on turnin for more information on the operation of the program.