Csc 4330/6330, Programming Language Concepts (Spring 2018)

Graduate Project (Due: April 29, Sunday)

Extend the LISP language of Homework 1 to include the following features:

1. Three new types of lisp-expressions:
   • A variable is a lisp expression (you may use the terminal VAR for this)
   • A let-expression is a lisp expression. let-expressions are of the form:

     (let name-value-pairs lisp-expression)
     

     where "let" is a keyword and name-value-pairs is a list of any number (at least one) of variable/value pairs, where value could be a lisp expression. Examples:

     (let ((x 2)(y 4)) (+ x y))
     (let ((x 10) (y (+ 25 (car (20 30)))) (z (+ 10 23)))  (+ x (car (y 20 z))) )
     

     An intuitive meaning of let-expressions is that they provide values for variables in the name-value-pairs, which are then substituted in the lisp-expression before evaluation.
   • A if-expression is a lisp expression. if-expressions are of the form:

     (if bool-exp lisp-expression lisp-expression)
     

     where "if" is a keyword and bool-exp is a boolean expression defined as follows: primitive boolean expressions are constructed using the comparison operators <, <=, >, >=, ^lt;>, and =, and more complicated boolean expressions are constructed using "and", "or", and "not". Here are some examples of boolean expressions:

     (> (+ 3 4) (<= 2 4))
     (= 3 (+ 1 2))
     (and (= 3 (+ 1 2)) (> (+ 3 4) (<= 2 4)) )
     (not (> (+ 3 4) (<= 2 4)) )
     

2. Two new types of list expressions:
   • cons-expression of the form (cons lisp-expression list-expression); examples include:

     (cons 24 (30 40 50))
     (cons (+ 3 4) ((+ 1 2) (* 1 2) (/20 2)))
     

     The cons operator adds one new element at the front of a given list.
   • list-expression of the form (list lisp-expression ... isp-expression); examples include:

     (list 2 3 4 5)
     (list (+ 2 3) 4 (* 5 6))
     

     The list operator forms a list out of given elements.

Some example LISP expressions with these new features are:

(+ x 4)
(car (2 3 x y))
(let ((x 10) (y (+ 25 (car (20 30)))) (z (+ 10 23)))  (+ x (car (y 20 z))) )
(let ((x 2)(y 4)) (if (> x y) 22 33));

The interpreter should accept all three types of expressions (numeric, list, and boolean) and evaluate them and show the answer. A sample run is shown below:

$ java LISP
LISP> (+ 2 3);

The value is 5.0

LISP> (if (> 2 3) 40 50);

The value is 50.0

LISP> (or (> 2 3) (> 3 2));

The value is true

LISP> (and (> 2 3) (> 3 2));

The value is false

LISP> (cdr (1 2 3 4));

The value is (2.0 3.0 4.0)

LISP> (cdr (cons (+ 2 3) (4 5 6)));

The value is (4.0 5.0 6.0)

LISP> (cdr (cdr (1 2 3 4)));

The value is (3.0 4.0)

LISP> (cdr (cdr (3 4)));

The value is ()

LISP> (cdr (cdr (3)));

EVALUATION ERROR - List Expression

LISP> (and (> 2 3) (> 3 2));

The value is false

LISP> (let ((x 10) (y (+ 25 (car (20 30)))) (z (+ 10 23)))  (+ x (car (y 20 z))) );

The value is 55.0

LISP> (let ((x 2)(y 3)) (+ (* x 4) (*y 3)));

The value is 17.0

LISP> (let ((x 2)(y 3)) (+ (* x 4) (*z 3)));

EVALUATION ERROR - Numeric Expression

LISP> (let ((x 2)(y 3)) (let ((x 10)(z 20)) (+ x (+ y z))));

The value is 33.0

LISP> (car (cdr (list 1 2 3 4)));

The value is 2.0