Lisp in Python

---

Why Lisp?

Introduction to Lisp

The basis for both programs and data in Lisp is the S (symbolic) expression. An S-expression may be a symbol, a number, or a series of S-expressions in parentheses. Here are some examples.

george
54
(george 54 (sue 48))

As you can see S-expressions may be nested.

Symbols like george are not variables. They are atoms. Python does not have atoms, so we must internally represent george as a string "george". In our Lisp implementation, numbers are also atoms. Symbols may be bound to a value on the association list (coming up). In the course of a recursive computation, a symbol may be bound to a different value at each level of recursion.

Certain forms of S-expressions may be evaluated. A number evaluates to itself. The function call "(+ 5 4)" would apply the primitive function '+' to the arguments (5 and 4) and evaluate to 9. All function calls use prefix notation which lists the function name first, followed by the arguments.

Here are some more examples of S-expression evaluation.

S-expression        Evaluation   Comments

234                 234          numbers evaluate to themselves
(* (+ 72 4) 5)      380.0        Addition done before the multiplication
(quote charlie)     charlie      quote stops further evaluation
(quote (a b c))     (a b c)      quote stops further evaluation
'charlie            charlie      'x is shorthand for (quote x)
t                   t            symbol for "true"
nil                 nil          symbol for "false" same as ()
(eq 5 5)            t            eq returns t or nil
(eq 5 6)            nil
(car '(a b c))      a            car returns 1st item in a list
(cdr '(a b c))      (b c)        cdr returns rest of a list
(cons 'a '(b c))    (a b c)      cons combines args to make a new list

One possibly point of confusion is the “quote” operator. Above (quote charlie) which also has a syntactic sugar form ’charlie means the symbol charlie is not to be evaluated. This is how data is passed around in the Lisp program. Also the S-expresion ’(a b c) keeps its form. Without the quote (with sugar or without) Lisp would treat a as a function to apply with b and c (evaluated) as arguments.

Association Lists (alist)

When the built-in Lisp eval() function is called, it is passed an S-expression and an association list (alist for short). The alist binds symbols to values. The above evaluations did not need the alist because we were evaluating either constants or predefined functions whose arguments were constants

Here is an example alist.

((a 2) (b 6) (c (george 45)))

It pairs the symbols a to 2, b to 6, and c to (george 45). Here are some more sample evaluations assuming this alist.

S-expression  Evaluation  Comments

c             (george 45) variables are looked up in the alist
(eq a 2)      t           arguments to a function are evaluated first
(eq a b)      nil
(car c)       george

Special Forms of S-expressions

Finally, there are a few special forms of S-expressions. These are not functions even though the look like function calls. Their arguments are not evaluated before processing. One we've already seen is quote.

Another is the conditional, cond, which is very much like a case or switch statement in other languages, or like a Python if, elif, ... else. It takes the following form.

(cond  A B ...)

where A, B, etc. are lists of two elements each. The first element of each pair is evaluated until one returns true (not nil). At that point the second element of the pair is evaluated and its value is returned as the value of the cond. The remaining pairs are not evaluated. Generally the last pair t (True) for its first element so it works like a Python else. Again with the alist: ((a 2) (b 6) (c (george 45)))

(cond ((eq a 1) (cdr george)) (t 3))   would return *3*
(cond ((eq a 2) (cdr george)) (t 3))   would return a list *(45)*

Another special form is used for user defined functions. It is easiest to explain with an example. The following is a lambda-expression to square a number.

(lambda (x) (* x x))

The symbol lambda introduces the form. It is followed by an S-expression with the function parameters, and finally an S-expression which is the body of the function. It may be applied to arguments just like a built-in function. Again, assuming we have the alist above ...

((lambda (x) (* x x)) a)     evaluates to *4*.

The evaluation of the argument a yields 2. Then the lambda expression is applied to 2. The parameter x is paired with 2 and prepended to the alist. Now the alist looks like...

((x 2) (a 2) (b 6) (c (george 45)))

Finally, (* x x) is evaluated. x is replaced with 2 from the alist and the built-in function multiply is applied yielding 4. Returning from the lambda pops the (x 2) off the alist.

I added one special form not in the original code. (def x y) will bind a name, x, to an S-expression, y, on the current alist and to the Alist. The alist grows and shrinks and is passed between recursive calls to eval() and apply(). The Alist is a global variable that maintains definitions of functions and constants. Yes, a non-functional hack.

(def square (lambda (x) (* x x)))
(square 4) evaluates to 16.0

Representing S-expressions in Python.

Python lists are convenient to store S-expressions. Nested S-expressions can be handled simply with nested lists. Strings may be used for symbols and numbers can represent themselves. So our S-expression (lambda (x) (* x x)) would be ['lambda', ['x'], ['*','x','x']].

Recursion everywhere

We should talk about recursion a bit. It is used in our Python code although at times we could have used a for or while loop instead. However if you want to create Lisp functions then you must use recursion because we are not providing any other means of iteration!

Lets look at an example. The Python function, assoc(key, list), walks down a list of key/value pairs until it finds a pair whose first element matches the key, at which point it returns the second element (the value).

Here is how to write assoc using a for loop.

def assoc (x, alist) :
   for pair in alist :
      if pair[0] == x : return pair[1]
   scream ("variable %s not bound" % x)

With recursion the function looks like

def assoc (key, alist) :
   if   not alist        : scream ("variable %s not bound" % x)
   elif alist[0][0] == x : return alist[0][1]
   else                  : return assoc(key,alist[1:])

Walking through the Code. I/O

At this point you may want to bring up the code in a separate window, or just print it out. It's a couple of pages. The two modules are lisp.py and lispio.py. Let's look at lispio first.

lispio.py connects the internal computation with the outside world. S-expressions must be converted from the internal format (lists and python atoms (which are strings and numbers)) to the Lisp notation and vice-versa.

Let's start with output.

Function putSexp() is a recursive pretty-print. It accepts an S-expression in the form of a Python list, and returns a string representation of the Lisp code. Atoms, (both symbols and values), are formatted with str() (line 15) and assembled into Lisp lists with join() (line 14). We also translate quote expressions with the single-quote character (’). (line 13).

10 def putSexp (s):
11     # return string form of an S-expression
12     if type(s) == type([]) :
13         if 0 and len(s) and s[0] == 'quote' : return "'" + putSexp(s[1:])
14         else : return '(' + ' '.join(map(putSexp,s)) + ')'
15     else : return str(s)
16

To process input in Lisp format, we use getSexp() . It uses getToken() to extract symbols, numbers and special characters from a string and builds the internal Python (nested) list. getSexp() also calls itself to extract nested S-expressions. Here recursion guarantees that parentheses will balance correctly.

17 def getSexp () :       # get an S-expression from the user
18     # return and discard the next S-expression,
19     #   along with any nested ones in input
20     a = getToken()
21     if   a == "'" : return ['quote', getSexp()]
22     elif a != '(' : return a
23     a = []
24     while 1 :
25         b = getSexp()
26         if b == ')' : return a
27         a.append(b)
28

getToken() is our lexical analyzer. It uses getChar() and nextChar() which buffer and return characters from the keyboard or from files (perhaps nested).

29 def getToken () :
30     # return and discard the next symbol,
31     #   number or special character in input
32     while nextChar() <= ' ': getChar()  # skip whitespace
33     a = getChar()
34     if a in ['(',')',"'"] : return a
35     while nextChar() > ' ' and nextChar() not in ['(',')'] :
36         a = a + getChar()
37     try    : return float(a)   # if a number, make it a float
38     except : return a          # otherwise a string with the symbol name
39
            

getFile() reads the file contents and normally returns it as a single string. However an inner file may be requested on its own line starting with the ‘@’ char. The inclusion of other files may be taken to any depth.

nextChar() returns characters input from the keyboard or from a file opened with the @ convention.

getChar() retrieves a single character from the buffer filled by the functions above.

  40 def getFile(fname) :
  41     output = []
  42     lines = open(fname).readlines()
  43     for line in lines :
  44         line = line.rstrip()
  45         if line[0:1] == '@' :
  46             output.append(getFile(line[1:]))
  47         else :
  48             output.append(line)
  49     return '\n'.join(output)
  50
  51 def nextChar() :
  52     # return (but don't discard) the next character in the input stream
  53     #   get more from the user if needed
  54     global inlin, inputter
  55     if inlin == "" :
  56         inlin = raw_input("Lisp>")
  57         if inlin == "" : sys.exit()
  58         if inlin[0] == '@' :
  59             inlin = getFile(inlin[1:])
  60     return inlin[0:1]
  61
  62 def getChar() :
  63     # return and discard the next character in the input stream
  64     global inlin
  65     c = nextChar()
  66     inlin = inlin[1:]
  67     return c

Let's play with all of this a bit. We'll start with getToken

$ python
>>> import lispio
>>> while True :
...     print(lispio.getToken())
...
Lisp>a b
a
b
Lisp>(car '(a b))
(
car
'
(
a
b
)
)
Lisp>

Now let's play with getSexp to see how Lisp S-expressions are converted to Python lists.

>>> import lispio                # python code to peek under the hood
>>> while True :
...     print lispio.getSexp()
...
Lisp>(car '(a b))
['car', ['quote', ['a', 'b']]]
Lisp>(eq a 5)
['eq', 'a', 5.0]
Lisp>

The Main Module

Now we're ready to look at the heart of it all - the code expressed in a meta-lisp at the start of the MIT Lisp 1.5 User Manual, 8th edition 1973. We'll start with a handful of small auxiliary functions that are pretty easy and then work into the main functions eval() and apply().

pairlis() adds pairs to the alist (returning an expanded alist) and assoc() finds values for variables in the alist parameter.

13 def pairlis (x,y,alist) :
14     "push symbols in x along with respective values in y onto the alist"
15     if not x : return alist
16     else : return [[x[0],y[0]]] + pairlis(x[1:],y[1:],alist)
17
18 def assoc (x, alist) :
19     "look up x on the alist and return its value"
20     if   not alist        : raise "Lisp error"
21     elif alist[0][0] == x : return alist[0][1]
22     else                  : return assoc(x,alist[1:])
23

evcon() is special for handling cond expressions as described above. evlis() is similar to the Python map function. It evaluates each item in the list passed and returns a list of the values.

67 def evcon (c, alist) :
68     "evaluate cond. Note just the pairs passed in c"
69     if   len(c) == 0           : return []
70     elif eval (c[0][0], alist) : return eval (c[0][1],alist)
71     else                       : return evcon(c[1:],  alist)
72
73 def evlis (l, alist) :
74     "evaluate all elements in a list, returning list of the values"
75     if not l : return []
76     else     : return [eval(l[0], alist)] + evlis(l[1:], alist)
77

apply() gives meaning to the built-ins. We have only a minimal set. With a little study it should make sense. Notice how cons sews lists together (line 41). And how a lambda expression first adds arguments to the alist and then evaluates the body of the function (line 45).

24 def apply (fn,args,alist) :
25     "apply a function fn to its arguments in args"
26     if debug :
27         print("--Apply-- %s  Args=%s" % (sxp(fn),sxp(args)))
28         printAlist(alist)
29
30     if isSymbol(fn) :   # name of a function
31         if   fn == 'atom' : return [[],'t'][type(args[0]) != type([])]
32         elif fn == 'car'  : return args[0][0]   # first element of 1st arg
33         elif fn == 'cdr'  : return args[0][1:]  # tail of 1st arg
34         elif fn == '+'    : return args[0]+args[1]
35         elif fn == '-'    : return args[0]-args[1]
36         elif fn == '*'    : return args[0]*args[1]
37         elif fn == '/'    : return args[0]/args[1]
38         elif fn == 'eq'   : return [[],'t'][args[0] == args[1]]
39         elif fn == 'not'  : return [[],'t'][args[0] == []]
40         elif fn == 'cons' :
41             if type(args[1]) != type([]) : args[1] = [args[1]]
42             return [args[0]] + args[1]
43         else : return (apply(eval(fn,alist),args,alist))
44     elif fn[0] == 'lambda' : # a function definition
45         return eval (fn[2], pairlis(fn[1],args,alist))
46     else                   : scream("Can't apply %s" % fn)
47

eval() handles constants like numbers, true/nil and the special keywords quote, def and cond (lines 58-62). At line 64 the magic happens. The expression to evaluate is a function call. The arguments are evaluated and added to the alist (line 60) and then apply() is called. When apply() returns, the extra additions to the alist disappear.

48 def eval (exp, alist) :
49     "evaluate an S expression using the alist"
50     global Alist
51     if debug : print("--Eval--- %s" %  sxp(exp)); printAlist(alist)
52     if   exp == 't'     : return 't'      # true evaluates to itself
53     elif exp == 'nil'   : return []       # symbol nil same as a null list
54     elif exp == 'alist' : return Alist    # special command to examine alist
55     elif isNumber(exp)  : return exp      # numbers eval to themselves
56     elif isSymbol(exp)  : return assoc(exp,alist)  # look up variables
57     else :               # check for special forms
58         if   exp[0] == 'quote' : return exp[1]
59         elif exp[0] == 'def' :            # user define functions
60             alist = Alist = pairlis([exp[1]],[exp[2]],alist)
61             return exp[1]                 # return function name
62         elif exp[0] == 'cond'  : return evcon(exp[1:], alist)
63         else :
64             x = evlis(exp[1:], alist)
65             return apply (exp[0],x , alist)
66

The special command def adds a name/func pair to the alist and to Alist. It should only be from the command prompt.

Using our Pythonic Lisp

The lisp main function interacts with the user. As long as the user inputs an S-expression to evaluate. Indirect files may be used. If the user types @filename, the file read and used just as if the user had typed the contents manually. And indirect files may be nested in turn.

Lets use the interactive mode to evaluate some expresssions. Here we use def to set the variable a to 6 on the alist.

>>> import lisp
>>> lisp.main()
Lisp>(def a 6)
a
Lisp>alist
((a 6.0))
Lisp>

Next we'll do an addition. The global "debug" is set to True so that each call of eval() and apply() will be printed.

Lisp>debug
Lisp>(+ a 7)
--Eval--- (+ a 7.0)
Alist
  (a 6.0)
--Eval--- a
Alist
  (a 6.0)
--Eval--- 7.0
Alist
  (a 6.0)
--Apply-- +  Args=(6.0 7.0)
Alist
  (a 6.0)
13.0

Next we'll define a function sq to square a number and then use it to calculate a**2.

Lisp>(def sq (lambda (x) (* x x)))
--Eval--- (def sq (lambda (x) (* x x)))  alist= ((a 6.0))
sq
Lisp>debug       # toggle debug off
Lisp>(sq a)
36.0
Lisp>

We can prepare a function definition in a file and load it. Here is a definition for the function length which returns the number of S-expressions in a list. I used an indentation style that matches left and right parentheses either on the same line or that separates groups of ‘)’ with a space when matching ‘(’ are on previous lines.

(def length
   (lambda (x)
      (cond
         ((not x) 0)
         (   t   (+ 1 (length (cdr x)))) ) ) )

Lisp>@length.lsp
length
Lisp>(length '(a b c d e f g))
7.0
Lisp>(length length)
3.0

Can you explain why the length of length is 3?

The Factorial Function

This is the code from the file, fact.lsp. We recursively multiply x by the factorial of x-1 until x is zero. The expression (+ x -1) is used since no subtraction operator was defined for the simpler (- x 1).

1 (def fact
2    (lambda (x)
3       (cond
4          ((eq x 0) 1)
5          ( t       (* x (fact (+ x -1)))) ) ) )
6

Lisp>@fact.lsp
fact
Lisp>(fact 5)
120.0
Lisp>

If we had toggled debug on we would have seen a great deal of output as all evals() and applys() are shown along with the current alist. Here is a peek at the alist at the deepest point in the recursion.

--Eval--- 1.0
Alist
  (x 1.0)
  (x 2.0)
  (x 3.0)
  (x 4.0)
  (x 5.0)
  (fact (lambda (x) (cond ((eq x 0.0) 1.0) (t (* x (fact...

Five bindings of x on the alist. The returns start at this point. With each return a binding is popped off and a multiply done. At the bottom of the alist is the definition of our fact() function.

Dynamic Scope

An interesting property in this language emerges from using the alist to hold values. Consider the following.

Lisp>(def x 5)
x
Lisp>(def b (lambda () (+ x x)))
b
Lisp>(b)
10.0

The function b() is able to see the value for x even though x is not an argument for b(). But this happens simply because the value of x is determined by a simple search through the alist.

Early versions of Lisp used this "dynamic" scoping. It let you set "global" values by simply defining them first. It fell out of favor over time. The norm is now "lexical" scoping and there is an excellent reason for this. Functional progamming demands that a function called repeatably with the same inputs must yield the same results. Dynamic typing can violate that rule just like the careless use of global variables.

You can download the zip file for the project here.

If you have comments or suggestions You can email me at mail me

Copyright © 2003-2021 Chris Meyers and Fred Obermann

…