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

Homework 1 (Due: 27 January (Thursday))

Hints

Using PLY, write an interpreter for the language of "LISP expressions".

A LISP expression is defined as follows:

1. A number (integer as well as fractional) is a LISP expression.
2. if E1 and E2 are LISP expressions then so are (+ E1 E2), (- E1 E2), (* E1 E2), and (/ E1 E2).
3. if L is a LIST expression (defined below) then (car L) is a LISP expression.
4. if B is a BOOLEAN expression and E1 and E2 are LISP expressions then (if B E1 E2) is a LISP expression.

A LIST Expression is defined as follows:

1. if E1, E2, ..., En are LISP expressions where n>=0 then (E1 E2 ... En) is a LIST expression.
2. if L is a LIST expression then (cdr L) is a LIST expression.
3. if E is a LISP expression and L is a LIST expression then (cons E L) is a LIST expression.

A BOOLEAN expression is defined as follows:

1. True and False are BOOLEAN expressions.
2. if E1 and E2 are LISP expressions then (> E1 E2), (>= E1 E2), (< E1 E2), (<= E1 E2), (= E1 E2), and (<> E1 E2) are BOOLEAN expressions.
3. if B1 and B2 are BOOLEAN expressions then so are (not B1), (and B1 B2), and (or B1 B2).

Here are examples of valid LISP expressions:

34
True
(20 30 40)
(+ 20 30)
(* (+ 1 2) (/ 8 4))
(* (car (2 4 (+ 2 4) 8)) (/ 27 9))
(+ (car (2 3 4)) (car (cdr (cdr (9 8 7 6)))))
(if (> 2 3) 40 50)
(and (> 2 3) (> 3 2))
(cdr (cons (+ 2 3) (4 5 6)))

Here is a sample run:

Mac-mini:hw1 raj$ python3 LISP.py
LISP: 34;
34.0
LISP: (+ 20 30);
50.0
LISP: (/ 9 (- 2 2));
DIVIDE BY ZERO!
LISP: (* (+ 1 2) (/ 8 4));
6.0
LISP: (* (car (2 4 (+ 2 4) 8)) (/ 27 9));
6.0
LISP: (+ (car (2 3 4)) (car (cdr (cdr (9 8 7 6)))));
9.0
LISP: (+ 2 3 4);
Syntax error in input!
LISP: (* (car 4) 22);
Syntax error in input!
LISP: (+ 3 (car (cdr (cdr (cdr (1 2))))));
Cannot CDR on an empty list!
LISP: (if (> 2 3) 40 50);
50.0
LISP: (or (> 2 3) (> 3 2));
True
LISP: (and (> 2 3) (> 3 2));
False
LISP: (cdr (1 2 3 4));
(2.0 3.0 4.0)
LISP: (cdr (cons (+ 2 3) (4 5 6)));
(4.0 5.0 6.0)
LISP: (cdr (cdr (1 2 3 4)));
(3.0 4.0)
LISP: (cdr (cdr (3 4)));
()
LISP: (cdr (cdr (3)));
Cannot CDR on an empty list!
LISP: (car (cdr (1 2 3 4)));
2.0
LISP: exit;
Mac-mini:hw1 raj$

WHAT TO SUBMIT?

LISP.py, LISPLexer.py, LISPParser.py. If you chose to implement the expression tree using LISPNode, then you must submit LISPNode.py as well.