Project 1

Due Friday Oct 1 2004 11:59 PM

TA in Charge: Steven

The latest version of the oracle.
Known bugs in the oracale: To keep this page from getting too cluttered I have moved the update section to a separate page. This takes the place of the Errata.txt file that Dan talked about in lecture.

Project Description

For this project you will be using the file ~cs61c/lib/lisp.c. This file contains an interpreter for a subset of Lisp. You will be modifying the file to add the use of structures to the language. The three functions you will be asked to write are:

Declaration

(1) (defstruct <structtype> <field1> <field2> ... <fieldn>)

This would define a structure of type structtype which has fields named field1, field2, ... fieldn. Additionally the functions defined in parts (2) and (3) should now exist. This function should return the symbol representing the name of the structtype.

E.g., (defstruct point x y) would define a structure of type point which has two fields: x and y. The return value of this statement should be the symbol point.

Instantiation

(2) (make-<structtype> <value1> <value2> ... <valuen>)

This would create and return a structure of type structtype with the fields set to the given values in correspondence order (the first field gets the first value, the second field gets the second value, etc.). The number of values here and the number of fields the structure must be the same. Note that the values can be anything, even other structures. The return value of this statement should be the structure which was just created. When a structure is printed to the screen, it looks like: #s(<structtype> <field1> <value1> ... <fieldn> <valuen>).

E.g., if we had defined the structure point as shown above, (make-point 1 2) would return a structure of type point which has the field x initialized to value 1 and y initialized to value 2. That return value would be printed as #s(point x 1 y 2) Note: make-<structtype> is the only way to make a <structtype> structure.

Getters

(3) (<structtype>-<fieldname> <struct>)

Procedures of this form should be automatically generated (when you declare the structure with defstruct) to access each of the fields of the structure you defined. The return value is the value of field in the given structure.

E.g., (point-x (make-point 1 2)) should return 1.

Example program runs

(the user typed the expressions in bold):

> (defstruct student sid gpa)
student
> (make-student 12345678 4)
#s(student sid 12345678 gpa 4)
> (student-sid (make-student 87654321 3))
87654321

and to make the binary tree

  is
 /  \
61c great
and be able to walk down to its right child and query its datum we would use:

> (defstruct binarytree datum left right)
binarytree
> (make-binarytree 'is 
                   (make-binarytree '61c   '() '())
                   (make-binarytree 'great '() '()) )
#s(binarytree datum is left #s(binarytree datum 61c left () right ()) right #s(binarytree datum great left () right ()))
> (binarytree-datum 
    (binarytree-right 
       (make-binarytree 'is 
                        (make-binarytree '61c   '() '())
                        (make-binarytree 'great '() '()) )))
great

Error Handling

You should handle at least the following error cases.

(1) You cannot use make-<structtype> or any of the accessor methods before doing the corresponding defstruct. In this case your interpreter should print "Unknown function" and return NIL.

(2) The arguments to defstruct must all be of type symbol. If this is not the case then your interpreter should print "Error: arguments must be of type symbol" and return NIL.

(3) The number of arguments passed to make-<structtype> must correspond to the declaration of <structtype>. If it does not then you should print "Error: incorrect number of arguments" and return NIL.

(4) The argument to any of the accessor functions should be a struct of the proper type. If it is not then you should print "Error: argument is of the wrong type" and return NIL.

Note: Don't worry too much about the case where one command has multiple errors. We won't be that sadistic.

Example program run

>(make-point 2 3)
Unknown function
()
>(point-x (+ 1 2))
Unknown function
()
>(defstruct point '() (+ 1 2) '(a b c d))
Error: arguments must be of type symbol
()
>(defstruct point x y z)
point
>(make-point 2 3)
Error: incorrect number of arguments
()
>(point-x (+ 1 2))
Error: argument is of the wrong type
()

Extra for Experts

Do not attempt this until you are done with the rest of the project. This is worth no extra credit points. Do this part only if you enjoy a good challenge and want the pride of a job well done.

Add the ability to read in a hard-coded structure from user input assuming that the type of structure has been previously defined. Recall that a structure is of the form #s(<structtype> <field1> <value1> ... <fieldn> <valuen>).

Example program run

>(defstruct house numwalls roof)
house
>(house-numwalls #s(house numwalls 4 roof true))
4

Author: CS61C