Toy Lisp Interpreter

Read subroutine

<s-expression> --> ' <s-expression>
               --> <list>
               --> integer
               --> symbol

<list> --> ( <series> )
       --> ( <series> . <s-expression> )

<series> --> <s-expression> <series>
         -->

Eval subroutine

• INTS, PRIMS, COMPS, and SPECS evaluate to themselves.
• SYMs evaluate to the lisp objects to which they are bound.
• CONS cells (lists) are evaluated as follows. First, the car of the list is evaluated. If the result is a function (a PRIM or a COMP), then the remaining elements of the list are evaluated and the function is applied to them. If the result is a special form (a SPEC), then the function corresponding to the special form is applied to a two-element list whose first element contains the cdr of the original list and whose second element is the calling environment.

For example, consider a function f that takes two arguments. The s-expression "(f x y)" is evaluated by evaluating x and y to obtain arguments X and Y, and then applying the function named by f to these arguments to obtain the result.

In general, I will use lowercase letters to denote the elements of the list and uppercase letters to denote the results of evaluating these elements. For example, suppose we define symbols three and four:

--> (define three 3)
three
--> (define four 4)
four

Write subroutine

--> +
[primitive function]
--> (lambda x x)
[compound function]
--> quote
[special form]
--> (cons + quote)
([primitive function] . [special form])

Type CONS

A CONS cell is an ordered pair of lisp objects. The first lisp object is called the car of the CONS cell, and the second lisp object is called the cdr of the CONS cell. Note that the first or second lisp object may itself be a CONS cell, so lisp objects can be viewed as binary trees in which the non-terminal nodes are CONS cells and the terminal nodes are atoms (an atom is anything that is not a CONS cell).

Type INT

An INT is an integer.

Type SYM

A SYM is a symbol (also called a variable), and can be bound to another lisp object. A SYM can be thought of as naming the s-expression to which it is bound.

Type PRIM

A PRIM is a primitive function; that is, a function that is predefined by the lisp interpreter.

Type COMP

A COMP is a compound function; that is, a function that is built out of primitive functions and other compound functions.

Type SPEC

A SPEC is a special form; unlike a function, it does not evaluate all of its arguments.

Lists are subdivided into two classes: proper lists and improper lists. A list is said to be proper if it the empty list or if the cdr of the list is a proper list; otherwise the list is said to be improper.

Examples of proper lists: "(1 2 3)", "((1 2) 3)", "((1 . 2) 3)"

Examples of improper lists: "(1 2 . 3)"

Here are some examples that illustrate the difference between static and dynamic scoping. For static scoping,

--> (define bletch 1)
bletch
--> (define add-bletch (lambda (x) (+ x bletch)))
add-bletch
--> ((lambda (bletch) (add-bletch 3)) 5)
4

--> (define bletch 1)
bletch
--> (define add-bletch (lambda (x) (+ x bletch)))
add-bletch
--> ((lambda (bletch) (add-bletch 3)) 5)
8

--> (define bletch 1)
bletch
--> ((lambda (bletch) (define add-bletch (lambda (x) (+ x bletch)))) 7)
add-bletch
--> ((lambda (bletch) (add-bletch 3)) 5)
10

--> (define bletch 1)
bletch
--> ((lambda (bletch) (define add-bletch (lambda (x) (+ x bletch)))) 7)
add-bletch
--> ((lambda (bletch) (add-bletch 3)) 5)
8

--> ((special (lambda x x)) a b c)
((a b c) ())
--> (let ((bletch 42)) ((special (lambda x x)) a b c))
((a b c) ((bletch . 42)))

We can use "special" to define the "quote" special form as follows:

--> (define quote-new (special (lambda (sexp env) (car sexp))))
quote-new
--> (quote-new a)
a

We can use "special" to define the "cond" special form as follows:

--> (define eval-cond
  (lambda (sexp env)
    (if (null? sexp) ()
        (if (eval (first (first sexp)) env)
            (eval (second (first sexp)) env)
            (eval-cond (cdr sexp) env)))))
eval-cond
--> (define cond (special eval-cond))
cond
--> (cond (#f 1) (#t 2))
2

(+ x1 ... xn) : X1, ..., Xn must be of type INT

Return the sum of X1, X2, ..., Xn. Examples:

--> (+ 7 5)
12
--> (+ 1 2 3)
6
--> (+ 3)
3

(- x1 ... xn) : X1, ..., Xn must be of type INT

Return X1 minus the sum of X2, ..., Xn. Examples:

--> (- 7 5)
2
--> (- 1 2 3)
-4
--> (- 3)
3

(* x1 ... xn) : X1, ..., Xn must be of type INT

Return the product of X1, ..., Xn. Examples:

--> (* 7 5)
35
--> (* 2 3 4)
24
--> (* 3)
3

(= x y) : X and Y must be of type INT

If X and Y are equal then return #t, otherwise return #f. Examples:

--> (= 42 42)
#t
--> (= 0 42)
()

(car list) : LIST must be of type CONS

Return the first element of LIST. Examples:

--> (car '(1 2 3))
1
--> (car '(a . b))
a

(cdr list) : LIST must be of type CONS

Return the list that is obtained by removing the first element from LIST. Examples:

--> (cdr '(1 2 3))
(2 3)
--> (cdr '(a . b))
b
--> (cdr '(1))
()

(cons x y)

Return a CONS cell whose first element is X and whose second element is Y. Examples:

--> (cons 1 2)
(1 . 2)
--> (cons 'a '(1 2 3))
(a 1 2 3)

(eval x env) : ENV must be an association list

Evaluate X in environment ENV and return the result. Examples:

--> (eval 'bletch '((bletch . 42)))
42
--> (eval '(lambda quote quote) (list (cons 'lambda *) (cons 'quote 3)))
9

(apply f list) : F must be a function, LIST must be a list of arguments for F

Apply F to LIST and return the result. Example:

--> (apply + '(1 2 3))
6

(assoc key alist) : KEY must be an atom, ALIST must be an association list

Compare KEY with each dotted pair in alist in sequence, starting with the first. If KEY matches the first element of a dotted pair then return that dotted pair, otherwise return the empty list. Examples:

--> (assoc 'b '((a . 1) (b . 2) (c . 3)))
(b . 2)
--> (assoc 'z '((a . 1) (b . 2) (c . 3)))
()
--> (assoc 'a '((a . 1) (a . 2) (a . 3)))
(a . 1)

(eqv? x y)

If X and Y are the same lisp object then return #t, otherwise return #f. Examples:

--> (eqv? 'a 'a)
#t
--> (eqv? 12 (+ 7 5))
#t
--> (eqv? '(1 2) '(1 2))
()

(type-of x)

Return the type code of X, where CONS cells, INTS, SYMS, PRIMS, COMPS, and SPECS are assigned type codes 0, 1, 2, 3, 4, and 5, respectively. Examples:

--> (type-of '(1 2 3))
0
--> (type-of 42)
1
--> (type-of 'bletch)
2
--> (type-of ())
2
--> (type-of #t)
2
--> (type-of #f)
2
--> (type-of +)
3
--> (type-of (lambda (x y) (* x y)))
4
--> (type-of quote)
5
--> (type-of (special cons))
5

(special f): F must be a function that takes two arguments

Return a special form. The special form is evaluated by applying F to a two-element list whose first element is a list of the unevaluated arguments and whose second element is the calling environment. Examples:

--> ((special (lambda x x)) (+ 1 2) cons)
(((+ 1 2) cons) ())
--> ((lambda (a b) ((special (lambda x x)) bletch foo)) 1 2)
((bletch foo) ((a . 1) (b . 2)))

(quote x)

Return x. Examples:

--> '(1 2 3)
(1 2 3)
--> (quote (1 2 3))
(1 2 3)
--> 'bletch
bletch

(lambda args x) : args must be either a SYM or a list of SYMs

Return a function. Examples:

--> ((lambda (x y) (* x y)) 3 4)
12
--> ((lambda x x) 1 2 3)
(1 2 3)

(if x y z)

If X is true then return Y, otherwise return Z.

(define name x) : name must be a SYM

Bind name to X, return name.

:q

Quit the program.

:e

Print out the current environment.

:t

Toggle trace mode; this shows the individual steps taken by the lisp interpreter in evaluating lambda expressions.

:m

Print the total number of objects that have been generated.

:n

Print out the list of SYMS.

(let ((fact-helper (lambda (f n) (if (= n 0) 1 (* n (f f (- n 1)))))))
  (let ((fact (lambda (n) (fact-helper fact-helper n))))
    (fact 5)))

((lambda x (apply (car x) x))
 (lambda (f n) (if (= n 0) 1 (* n (f f (- n 1))))) 5)

John McCarthy defined a special form called "label" that makes it much simpler to define recursive local functions. Here is how "label" can be used to define "fact" as a recursive local function:

((label fact (lambda (n) (if (= n 0) 1 (* n (fact (- n 1)))))) 5)

The problem can be trivially solved by simply binding "fixed-point" to itself:

--> (define fixed-point 'fixed-point)
fixed-point
--> (eval-top fixed-point)
fixed-point

Define a symbol "diag" as follows:

--> (define diag '(lambda (x) (list x (list (quote quote) x))))
diag

(eval-top ((eval-top diag) f)) = ((eval-top f) f),

--> (eval-top ((eval-top diag) 'list))
(list)
--> (list 'list)
(list)

--> (eval-top ((eval-top diag) '(lambda (x) (cons x x))))
((lambda (x) (cons x x)) lambda (x) (cons x x))
--> ((lambda (x) (cons x x)) '(lambda (x) (cons x x)))
((lambda (x) (cons x x)) lambda (x) (cons x x))

(eval-top ((eval-top diag) diag)) = ((eval-top diag) diag).

--> (define fixed-point ((eval-top diag) diag))
fixed-point
--> fixed-point
((lambda (x) (list x (list (quote quote) x))) (quote (lambda (x) (list x (list (quote quote) x)))))
--> (eval-top fixed-point)
((lambda (x) (list x (list (quote quote) x))) (quote (lambda (x) (list x (list (quote quote) x)))))