Csc 4330/6330, Programming Language Concepts (Summer 2020)

Data structure returned by parser

Here is a proposed data structure to hold the LISP and LISP expressions. It is strongly recommended that you use this. We shall use recursive lists as illustrated with examples below:

LISP Expression Python List
34 ['num',34]
x ['var','x']
(+ (* 2 x) 9) ['+',['*',['num',2],['var','x']],['num',9]]
(car (2 3)) ['car', [['num', 2.0], [['num', 3.0], []]]]
(let ((x 2)(y 4)) (+ x y)) ['let', [['x', ['num', 2.0]], ['y', ['num', 4.0]]], ['+', ['var', 'x'], ['var', 'y']]]

LIST Expression Python List
(1 2 x 4) [['num', 1.0], [['num', 2.0], [['var', 'x'], [['num', 4.0], []]]]]
(2 4 (+ 2 4) 8) [['num', 2.0], [['num', 4.0], [['+', ['num', 2.0], ['num', 4.0]], [['num', 8.0], []]]]]
(1 (car (2 3)) 4) [['num', 1.0], [['car', [['num', 2.0], [['num', 3.0], []]]], [['num', 4.0], []]]]
(cdr (10 20 30)) ['cdr', [['num', 10.0], [['num', 20.0], [['num', 30.0], []]]]]
(cons 2 (cdr (10 20 30))) [['num', 2.0], ['cdr', [['num', 10.0], [['num', 20.0], [['num', 30.0], []]]]]]

The data structure for a LIST expression is not the standard Python list we are used to. We use a structure borrowed from the implementation of functional programming languages such as LISP that stores the first item (referred to as the car) and a list of remaining items (referred to as cdr) in a Python list in a recursive manner as shown in the examples above. Also note that we go ahead and execute the "cons" operation while constructing the data structure itself.