(click your browser's refresh button to ensure that you have the most recent version)
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 that 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.
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. It is understood that some of the exercises in this programming assignment require extremely little code and will not require extensive comments. Nevertheless, comments for things such as each branch of a cond form are required, as well as comments for "helper" functions if any.
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.
The overall objective of this assignment is for you to gain some hands-on experience with Common Lisp. The first four problems are simple exercises that require very little code, the intent being to provide a "warm up" for the main exercise. Problems #5 and #6 require you to write a more complicated program that will use more advanced features of Lisp like higher order functions and lambda forms. Finally the extra-credit problem is really not that difficult, but requires a careful recursion.
The instructions for submission of your assignment may be found at the bottom of this page of this document. It is a good idea to start this assignment early; Lisp programming, while not inherently difficult, often seem somewhat foreign at first, particularly when it comes to recursion and list manipulation.Important: Note that some questions ask you to write programs that use recursion rather than iteration. For these questions, programs that use iteration will receive no credit.
So as not to make the code overly long, it is not required that you deal with user errors: you can assume that the user always types valid commands (e.g., if a function is supposed to take an atom as input, you do not have to check whether the input is instead a list and throw an error). Note that the Common Lisp interpreter catches a good number of user errors anyway.
Write a Common Lisp function called my-remove that takes an atom and a list in input, and returns a list that is identical to the input list, but with elements equal to the input atom removed, if any. Examples of the function in operation are shown below (user input is in red):
CL-USER(1): (my-remove 'b '(a b c b d))
(a c d)
CL-USER(2): (my-remove 'b '(a c d e f))
(a c d e f)
CL-USER(3): (my-remove 'a '(b (a d) a d))
(b (a d) d)
CL-USER(4): (my-remove 'a '())
nil
Requirements:
Hints:
Write a Common Lisp function called my-recursive-remove that takes an atom and a list in input, and returns a list that is identical to the input list, but with all occurrences of the input atom removed, if any. Examples of the function in operation are shown below (user input is in red):
CL-USER(1): (my-recursive-remove 'a '(a b c d))
(b c d)
CL-USER(2): (my-recursive-remove 'a '((a b) a (c d e a) (a a) b))
((b) (c d e) nil b))
CL-USER(3): (my-recursive-remove 'a '((((a)))))
(((nil)))
Requirements:
Write a Common Lisp function called palindromep that takes a list as input and returns 't' is the list is a palindrome, and 'nil' otherwise. Examples of the function in operation are shown below (user input is in red):
CL-USER(1): (palindromep '(a b b a))
t
CL-USER(2): (palindromep '(a b c b a))
t
CL-USER(3): (palindromep '(a b c))
nil
CL-USER(4): (palindromep '(a (d e) b (d e) a))
t
CL-USER(5): (palindromep '(a (d e) b (e d) a))
nil
Note in the 4th and 5th examples above that we do not look into sublists, meaning that matching sublists in both sides of the palindrome must be identical rather than the reverse of each other.
Requirements:
Hint:
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 and empty lists have been removed). Examples of the function in operation (user input is in red):
CL-USER(1): (flatten '(a b c d))
(a b c d)
CL-USER(2): (flatten '(a () b (c d)))
(a b c d)
CL-USER(3): (flatten '(a (())))
(a)
CL-USER(4): (flatten '(a (b c) (d e (f) ((((((g)))) h)) i) j (k) l))
(a b c d e f g h i j k l)
Requirements:
CL-USER(1): (infix '(+ 2 3))
(2 + 3)
CL-USER(2): (infix '(+ 2 x (* y 3)))
(2 + x + (y * 3))
CL-USER(3): (infix '(+ 2 x (* y (- z 3) 4)))
(2 + x + (y * (z - 3) * 4))
Requirements:
In this assignment you will write a database to keep track of bugs (real bugs, not bugs in a program). The database will make it possible to add new bugs, to do "select" queries, and to do "update" queries. Basically, the functionality is equivalent to a useful subset of SQL. You do not need to make the code robust to any kind of user mistakes and errors.
Although this is simple and at first glance not very interesting, you will see that this assignments is a great demonstration of the power of Common Lisp. In particular of the way in which lists can be used to store structured data, and more importantly how lambda forms can be created on-the-fly for increased flexibility and expressivity. This assignment does not require a lot of code writing: my solution to all the questions below amounts to only 90 lines of nicely formatted and commented Common Lisp code. Information about how to test your code is available there.
Each bug in the data base is characterized by the following six fields (types and example values are given):
| Field | Type | Meaning | Example Value |
| legs | integer ≥ 0 | number of legs | 34 |
| eyes | integer ≥ 0 | number of eyes | 12 |
| eyecolor | string | color of the eyes | "green" |
| wings | integer ≥ 0 | number of wings | 0 |
| color | string | color of the bug | "red" |
| length | float > 0 | length in inches | 0.3 |
(That's right, you can have a 20-inch green bug with no legs, no eyes, no wings, and 200 red eyes.)
The database is stored as a list of records, where each record is itself a plist (this is Lisp after all). It is assumed that there is a global (special) variable, *db*, that contains the database. In other words, before any of the database-related function is used, the user should place the following defvar call:
CL-USER(1): (db_makebug 6 2 "red" 2 "black" 0.4)
(:legs 6 :eyes 2 :eyecolor "red" :wings 2 :color "black" :length 0.4)
CL-USER(1): (db_insert (db_makebug 6 2 "red" 2 "black" 0.4))
1
CL-USER(2): (db_insert (db_makebug 102 2 "green" 0 "brown" 5))
2
CL-USER(3): (db_insert (db_makebug 8 0 "none" 0 "black" 1))
3
CL-USER(1): (db_print)
legs: 6
eyes: 2
eye color: red
wings: 2
color: black
length: 0.4
-------------------------
legs: 102
eyes: 2
eye color: green
wings: 0
color: brown
length: 5
--------------------------
legs: 8
eyes: 0
eye color: none
wings: 0
color: black
length: 1
-------------------------
3
The format above is used as a guideline for what your function should print to screen and it is not necessary to match it exactly as long as your output is in the same spirit.
CL-USER(1): (keep-if-true #'(lambda (x) (= (mod x 2) 0)) '(2 3 5 8 7 4 2))
(2 8 4 2)
Requirements:
Although we could write specific select functions for each bug attribute (e.g., (select_by_color "red")), we want to have only a single function, db_select, to select entries in the database. This will be easier for the user, and will also be easier to extend if the database changes.
We will implement a db_select function that takes only one argument. This argument is a function, which we'll call a "selector function". db_select returns a list of the bugs in the database for which the selector function evaluates to true.
We wish to dynamically create the selector function to be passed to db_select, rather than have the user have to define and pass selector functions him/herself. To this end, we will use a function color_selector to create selector functions to do selection on, say, bug color. color_selector takes a string as a argument and returns a selector function. This selector function returns 't' when applied to a database record whose color is equal to the string argument that was passed to color_selector.
Implement db_select and color_selector. db_select returns a list of records. Here is an example:
CL-USER(1): (db_select (color_selector "black"))
((:LEGS 6 :EYES 2 :EYECOLOR "red" :WINGS 2 :COLOR "black" :LENGTH 0.4)
(:LEGS 8 :EYES 0 :EYECOLOR "none" :WINGS 0 :COLOR "black" :LENGTH 1))
While the db_select we wrote in Step #5 is somewhat generic, we still have to write color-selector, legs-selector, eyes-elector, etc. This leads to a lot of code and requires a new function to be implement each time a new attribute is added to the bug database schema.
What we really want is a where function (for those of you who know a bit of SQL it shouldn't be a surprising name), so that we can do selection in the following way:
CL-USER(1): (db_select (where :color "black" :eyes 0))
((:LEGS 8 :EYES 0 :EYECOLOR "none" :WINGS 0 :COLOR "black" :LENGTH 1)
The where function supports an arbitrary specification of attributes and corresponding values for the selection. It takes at most 6 arguments, which are named after the bug attributes: legs, eyes, eyecolor, wings, color, and length. The example above uses only the color and the eyes arguments, and the other arguments are set to nil by default. We discussed in class how to define functions with optional arguments and with default argument values (using the &key keyword).
The where function returns a function that does the conjunctions (i.e., logical AND) of the specified selection criteria. Note in the example above that the list returned by db_select contains the only bug that is both black and with no eyes.
Implement the where function as described above.
Like in Step #6 for the where function, you will need to define db_update so that it takes optional arguments with default values.CL-USER(1): (db_update (where :color "black") :legs 12 :wings 2)
2
CL-USER(2): (db_select (where :color "black"))
((:LEGS 12 :EYES 2 :EYECOLOR "red" :WINGS 2 :COLOR "black" :LENGTH 0.4)
((:LEGS 12 :EYES 0 :EYECOLOR "none" :WINGS 2 :COLOR "black" :LENGTH 1)
Hints:
where we say that this bug is ugly, crunchy, and rare. There is no limit to which symbols can be put in there, but database users would most likely agree on some (potentially) large number of accepted symbols. When doing a selection, on wishes to return bugs that possess all the facts specified in the where clause. Note that these bugs may possess other facts not specified in the where clause. For instance, assuming that one has created a bug as above, one would have:CL-USER(1): (db_insert (db_makebug 6 2 "red" 2 "black" 0.4 '(ugly crunchy rare)))
1
CL-USER(1): (db_select (where :facts '(ugly rare) :color "black"))
((:LEGS 6 :EYES 2 :EYECOLOR "red" :WINGS 2 :COLOR "black" :LENGTH 0.4 '(ugly crunchy rare)))
Also, we slightly change the semantic of db_update for the facts attribute. If a list is passed to update (after the :facts keyword), the the bug's facts are replaced by the list. However, if a symbol is passed to update (after the :facts keyword), then the symbol is added to the bug's facts. For instance:
will add the symbol ugly to the list stored in the facts attribute of all bugs with green eyes. Note that the above may add ugly to a bug's facts while that bug's facts already contained ugly (in fact, this is what would happen in our example so far). You must ensure that, for each bug, the facts list does not contain any duplicates.CL-USER(1): (db_update (where :eyecolor "red") :facts 'ugly)
Finally, one also wishes to be able to query the database based on the number of distinct facts for a bug. For instance:
will return all bugs that have exactly three facts. Modify your program from Problem #6 to extend the database to contain the facts attribute, and all modify all functions as necessary to provide the capabilities described above. Examples to test your code are available there.CL-USER(1): (db_select (where :facts 3 :color "black"))
Your functions/programs must compile and/or run on a UNIX 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.
Examples for testing your programs for Problem #5 and Problem #6 are available here and there.
Your answers to this assignment will be stored in separate files under a directory called <LastName>_<FirstName>_cse130_pa1/. For instance, I would create a directory called Casanova_Henri_cse130_pa1. The directory hierarchy should appear as follows:
<LastName>_<FirstName>cse130_pa1/
problem1.lisp
problem2.lisp
problem3.lisp
problem4.lisp
problem5.lisp
problem6.lisp
problem7.lisp
For example, as indicated above, in the <LastName>_<FirstName>_cse130_pa1 directory, you should have a file named problem1.lisp, which will contain the documented Common Lisp source code to implement the functions specified in Problem #1 of this assignment, a file named problem2.lisp, which will contain the documented Common Lisp source code to implement the functions specified in Problem #2, and so on.Assuming the directory hierarchy above, populated with the problem solutions as described, you should create a tar file called <LastName>_<FirstName>_cse130_pa1.tar by running the tar command in the directory where the <LastName>_<FirstName>_cse130_pa1 directory resides. If you don't know anything about tar, I strongly suggest you learn about it as it is very useful (the man page is rather lengthy, but you can find a gentler introduction there). For example, in the directory containing the above directory, I would run the command
tar -cvf Casanova_Henri_cse130_pa1.tar Casanova_Henri_cse130_pa1
which would create the desired tar file (in this case, named Casanova_Henri_cse130_pa1.tar) from the directory named Casanova_Henri_cse130_pa1.
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 I am in the directory where I've created the Casanova_Henri_cse130_pa1.tar file, I would simply run the turnin command as follows:
turnin -c cs130s -p pa1 Casanova_Henri_cse130_pa1.tar
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.