Read sections 3.1-3.6 (pages 69-98) and Appendix A (pages 345-358) of the textbook.
Study the parser and interpreter we developed in class this week.
Using this code as a starting point, add the primitive functions null?, cons, car, cdr, and list to the interpreter's initial environment, as well as the special constant nil bound to the empty list. Your list primitive should be able to handle any number of arguments, just like in Scheme. (Hint: you don't need to use Scheme's apply primitive for this.) Do you need to change the parser? Examples:
(evaluate '(cons 1 (cons 2 nil))) => (1 2) (evaluate '(car (cdr (list 3 4 5)))) => 4 (evaluate '(list 1 2 3 4 5)) => (1 2 3 4 5) (evaluate '(null? nil)) => #t
Suppose we would like let expressions to have the following concrete list-structure syntax:
(let <var> = <exp> {and <var> = <exp>}* in <exp>)
where * means "zero or more repetitions". For example, instead of writing
(let ((a 1) (b (2 + 3)) (c 4)) (a * (b + c)))
we would write
(let a = 1 and b = (2 + 3) and c = 4 in (a * (b + c)))
Modify the list-structure parser to support this new syntax. Do you need to change the interpreter?
Add support for unpack expressions to the list-structure parser, the string parser, and the interpreter. The concrete syntax of unpack looks like this:
List syntax: (unpack (<var> <var>*) = <exp> in <body>)
String syntax: unpack <var> {, <var>}* = <exp> in <body>
Unpack first evaluates exp, which should evaluate to a list whose length matches the number of variables to the left of the equals sign. If so, then the variables are bound to the corresponding elements of the list, otherwise an error occurs. For example, the programs below should both evaluate to 14:
List syntax: (unpack (x y z) = (cons 1 (list 2 (3 + 4))) in (y * z)) String syntax: unpack x, y, z = (cons 1 (list 2 [3 + 4])) in [y * z]
Add support for cond expressions to the list-structure parser, the string parser, and the interpreter, using the following concrete syntax:
List syntax: (cond (<test-expression> <expression>)* )
String syntax: cond {<test-expression> ==> <expression>}* end
where test-expression is either an expression that evaluates to a boolean, or the special symbol else. If no else clause is present and none of the tests succeed, an error should occur. Hint: define a new datatype called test-expression, with variants else-keyword and bool-exp.
Extend the list-structure version of unpack to handle more general types of pattern-matching. For example, the expression
(unpack ((a b) c) = (cons (list 1 2) (cons 3 nil)) in (list a b c))
might produce (1 2 3), based on matching the pattern ((a b) c) with the resulting list ((1 2) 3). You'll need to decide how to handle any ambiguity that might arise from nested lists. For example, should ((a b) c) match ((1 2) (3 4)) with c bound to (3 4), or cause an error?
Make sure to clearly explain your approach in a comment in your code, and give a few examples that show how your extended unpack works.
Name your files
and submit them using /common/cs/submit/cs131-submit. If you have questions about anything, just ask!