Lisp in Python

Why Lisp?

Even though we are already programming in Python, which has many of the features of Lisp, it is instructive to look at the original Lisp evaluation mechanism. At the heart of the Lisp language is an recursive interplay between evaluating expressions, which means applying functions to arguments. But that requires further evaluation of the functions arguments and internal expressions. The result is an extremely elegant piece of code.

When I was a student of computer science at the University of Oregon in 1971, I took a course in Artificial Intelligence. We got exposed to some of the classic Lisp programs but, unfortunately, had no way of running them. So our projects were written in Fortran and were not very impressive.

So when I came across "Lisp in Lisp" taking up most of page 13 of the Lisp 1.5 Users Manual I had a stronger motivation than just esthetics to do something with it. I figured that if I could translate just that much Lisp into Fortran, then I would have the means to run other Lisp programs. It was much easier said than done. Fortran did not support recursion and this was an example of true "functional programming". There was not a single GOTO or variable assignment. Each function call and return had to done in Fortran with computed GOTO's, first pushing or popping information on stacks implemented with Fortran arrays. It was very messy. Later I did a version in PDP-11 Assembler and, still later, one in Pascal which was pretty clean.

This Lisp implemented in Python is mostly a translation of the original Lisp. If you have a chance to look at the original Lisp in Lisp, I think you'll agree with me that the Python code is much easier to get your head around. Like the original it is very short and, except for input of S expressions, completely functional. That basically means no variable assignments or explicit loops. Where we would normally use a "for" or "while" loop, you will see tail recursion.

I made a few small changes in this design. Lisp supports both lists and binary trees. In fact lists in Lisp are simply a special form of tree. Our Python Lisp supports only lists. In addition I added two small commands that will let us use the program interactively.

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.

Certain forms of S expressions may be evaluated. For example "(+ 5 4)" would apply the primitive function '+' to the arguments (5 and 4) and return the number 9, which is also an S expression. All function calls list 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
(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

Notice that we used (car '(a b c)) instead of (car (a b c)). The quote is necessary to keep (a b c) from another layer of evaluation. This will be clearer as we proceed.

When eval is called it is passed the S expression and also an association list. The above evaluations did not need the association list (alist for short) because we were evaluating either constants or functions whose arguments are constants.

Here is an example alist.

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

It pairs the variables 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

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 is true (not nil). Then the second element of that pair is evaluated and that value is returned as the value of the cond. The remaining pairs are not evaluated. Generally the last pair has t for its first element which makes it work like an else. For example with the alist above

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

Another special form is used for user defining functions. It is easiest to provide an example and explain it. The following is a function definition to square a number.

(lambda (x) (* x x))

The symbol lambda introduces this form. It is followed by an S expression with the function parameters, and an S expression which is the body of the funciton. It may be applied to arguments just like any primitive function. Again, assuming we have the alist above ...

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

In evaluation the argument a is evaluated (yields 2). Then the lambda expression is applied to 2. The parameter x is paired with 2 on the alist which now 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 primitive function "*" is applied yielding 4.

I added one special form not in the original code. (def x y) will bind a name x to an S expression y. The alist is saved in a global variable when these definitions are made and therefore remain for later evaluations. This form is especially useful to bind names to functions. For example

(def square (lambda (x) (* x x)))
(sq 4)

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']].

Tail Recursion

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

Lets look at an example. A call to assoc(x,alist) walks down the name/value pairs in the alist until it finds a pair whose 1st element matches x. Then it returns the 2nd 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]
   raise "Lisp error"

With tail recursion the function looks like

def assoc (x, alist) :
   if   not alist        : raise "Lisp error"
   elif alist[0][0] == x : return alist[0][1]
   else                  : return assoc(x,alist[1:])

There are 3 possibilities. If the first pair on the alist is the one we want, return its 2nd element. If there is no 1st element, raise an error. Or simply search the rest of the alist recursively. Eventually either the right pair will be found or an error will be raised.

Walking through the Code.

At this point you will probably 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

In the module lispio.py we have a function getSexp to input an S expression from the user and return the equivalent Python list. We also the have a function putSexp to convert a Python list (representing an S expression) to a string in Lisp.

The function getSexp uses getToken to extract symbols, numbers and special characters from the input provided by the user. It also uses itself to extract nested S expressions. In turn, getToken uses nextChar to see if the next character is part of the token it is building and getChar to grab it. So at the bottom of the food chain is nextChar which actually has to deal with getting input from the user.

Lets play with getToken a bit.

>>> import lispio
>>> while 1 :
...     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
>>> while 1 :
...     print lispio.getSexp()
...
Lisp>(car '(a b))
['car', ['quote', ['a', 'b']]]
Lisp>(eq a 5)
['eq', 'a', 5.0]
Lisp>

Notice that there are 2 versions of the function nextChar. One just uses raw_input which means the user must type everything in. The other uses the userInput module letting us put programs in files and running them thru the indirect file mechanism. For more information on the UserInput module click here .

The main functions in lisp.py are apply and eval. Each is a set of if/elif/else statements that handle the various options discussed above. The handling is done with the Python list operators. The other functions, pairlis, assoc, evcon, and evlis are just auxillary functions. The names are the same as in the original Lisp code. You will notice that they are tail recursive.

The function pairlis adds pairs to the alist (returning an expanded alist) and assoc finds values for variables in the alist passed. The function 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.

The lisp main function interacts with the user. As long as the user inputs an S expression to evaluate, it is passed to eval and the result printed. If lispio.nextchar is using the userInput module then the S expressions may be loaded from a file. This is generally used to define functions.

There are two extra commands handled in eval. def allows us to set variables or define functions by adding a pair onto the global Alist. And the special symbol alist is permanently set to the global Alist letting us view it easily. When the user enters a new S expression to evaluate, we start out with this preloaded alist.

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 one so that each call of eval and apply will be printed.

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>(sq a)
--Eval--- (sq a)  alist= ((sq (lambda (x) (* x x))) (a 6.0))
--Eval--- a  alist= ((sq (lambda (x) (* x x))) (a 6.0))
--Apply-- sq  Args= (6.0)  alist= ((sq (lambda (x) (* x x))) (a 6.0))
--Eval--- sq  alist= ((sq (lambda (x) (* x x))) (a 6.0))
--Apply-- (lambda (x) (* x x))  Args= (6.0)  alist= ((sq (lambda (x) (* x x))) (a 6.0))
--Eval--- (* x x)  alist= ((x 6.0) (sq (lambda (x) (* x x))) (a 6.0))
--Eval--- x  alist= ((x 6.0) (sq (lambda (x) (* x x))) (a 6.0))
--Eval--- x  alist= ((x 6.0) (sq (lambda (x) (* x x))) (a 6.0))
--Apply-- *  Args= (6.0 6.0)  alist= ((x 6.0) (sq (lambda (x) (* x x))) (a 6.0))
36.0
Lisp>

Setting debug back to 0 will enable a more natural, if less informative, interaction.

We can prepare a function definition in a file and invoke its definition. 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 parens either on the same line or vertically.

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

This function is another example of tail recursion. It counts one for the first element of a list and adds that to the length of the rest of the list. An empty list returns zero.

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?

Dynamic Scope

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

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

The function b is able to see the value for x even though x is not an argument. In fact the function b doesn't take arguments. But since the value of x is determined by a simple search of the alist, its setting from the calling function a is found.

Some Ideas for Projects.

You can extend this program in many ways. Extra primitives like turning the debug flag on and off, or providing access to user input would be useful. The system could also be expanded with functions written in Lisp (like length) that are loaded at input. A more complete system could be a combination of Python and Lisp. For the ambitious, the Python code could be translated back to Lisp and then you could run Lisp in Lisp in Python. Compare its speed to just Lisp in Python and then to a regular interpreter like Scheme.

Copyright © 2003-2015 Chris Meyers

.