Lisp in Python

I already discussed about Lisp in my previous post. I think you got an idea regarding Lisp Programming language. Now I almost completed my project "Design of a Lisp Interpreter with a web front-end". In this post I want to explore the development stages of my Lisp Interpreter.

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. During the study stage of my project I have searched for the existing Lisp interpreters, at that time I had found alot of standalone Lisp interpreters in different languages but I could not found any online lisp. Major advantage of this project is the online accessibility, I mean user can easily use this Lisp interpreter via internet.

    In this project web.py is the framework used for the web interface development. Three major files used in this project are app.py, lisp.py and lispio.py. Here app.py is the web application file, project execution also started from this file. Other two modules (lisp.py and lispio.py) used for lisp interpretation process.
    A language interpreter has two parts.

1. Parsing :The parsing component takes an input program in the form of a sequence of characters, verifies it according to the syntactic rules of the language, and translates the program into an internal representation.
2. Execution : The internal representation is then processed according to the semantic rules of the language, thereby carrying out the computation. 

Here is a picture of the interpretation process and an interactive session showing how parse and eval operate on a short program:

In this project parsing and execution are done by the lispio.py and lisp.py module respectively. Now I think you got an idea about what an interpreter actually do in its process stage.

Now we know that 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.

style="text-align: left;">hello
3455
(hello 34 (world 56))

As a web based application here user interaction is done with the browser. User can write their Lisp code in textarea field. After that they need to press the Evaluate button. Now I welcome you all to the code section.

lispio.py

I have already told that lispio.py module used for parsing. It imports other two modules are string and sys. It declare one variable 'inline' and assign it to null.

import string, sys
inline=""

This module have been built up on a number of simple functions, such as getSexp(), getToken(), nextChar(), getChar() and putSexp(). Next I want to explain the working of each functions.
First of all getSexp() used to read input from the user.  Here is the function

def getSexp () :       # get an S expression from the user
    "return and discard the next S expression, along with any nested ones in input" 
    a = getToken()
    if   a == "'" : return ['quote', getSexp()]
    elif a != '(' : return a
    a = []
    while 1 :
        b = getSexp()
        if b == ')' : return a
        a.append(b)

getSexp() used to input an S expression from the user and return the equivalent  python list. This function uses getToken function to extract symbols, numbers and special characters from the input provided by the user. It also uses itself to extract nested S expressions. getSexp() uses these tokens to generate the corresponding list in python and return this list back to the app.py module.

def getToken () :
    "return and discard the next symbol, number or special character in input"
    while nextChar() <= ' ': getChar()  # skip whitespace
    a = getChar()
    if a in ['(',')',"'"] : return a
    while nextChar() > ' ' and nextChar() not in ['(',')'] :
        a = a + getChar()
    try    : return float(a)   # if a number, make it a float
    except : return str(a)          # otherwise a string with the symbol name

GetToken() uses nextChar() to see if the next character is part of the token it is building and getChar() to grab it.

def nextChar() :
    """return (but don't discard) the next character in the input stream
       get more from the user if needed"""
    global inlin, data
    import app
    data=app.data1 
    if inline == ""
        inlin = data
        if inlin == "" : raise "EOF error"
    return inlin[0:1]

So nextChar() actually has to deal with getting input from the user. This function import app.py module, because user write their expressions on the textarea in web page not on the console. Userinput should assigned to a global variable 'data1' on app.py, nextChar() use these global variable  to access the userinput. This accessed data must be assigned to another global variable 'inline' . nextChar() then take one by one characters from this data. Here is the last function

def getChar() :
    """return and discard the next character in the input stream"""
    global inlin
    c = nextChar()
    inlin = inlin[1:]
    return c

getToken() uses this function to take one by one characters from the global variable inline.
Next we have to show the working of getToken()  and getSexp() a bit.
Note: Here I show the working of functions using terminal. Using existing code we cannot run it on terminal. since I want to show you the output of getToken() and getSexp(), for that i made some changes on the code. You can not run it on terminal, So you just need to look out the output of each functions and realize its working only. I am sure, following example provide more informations regarding the working of getSexp() and getToken() to you.

anoop@anoop-laptop:~$ python
Python 2.6.5 (r265:79063, Apr 16 2010, 13:09:56) 
[GCC 4.4.3] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> import lispio
>>> while 1:
...     print lispio.getToken()
... 
Lisp>(+ a b)
(
+
a
b
)
Lisp>(car '(a b))
(
car
'
(
a
b
)
)
Lisp>

Here first i gives an S expression (+ a b) to getToken(), after processing this function returns the corresponding tokens. Next i gives another S expression (car ' (a b)) it also returns the corresponding tokens. getToken() returns these tokens back to the getSexp(). Next we have to see how lisp S expressions are converted to Python lists

anoop@anoop-laptop:~$ python
Python 2.6.5 (r265:79063, Apr 16 2010, 13:09:56) 
[GCC 4.4.3] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> import lispio
>>> while 1:
...     print lispio.getSexp()
... 
Lisp>(cdr '(a b))
['cdr', ['quote', ['a', 'b']]]
Lisp>(= 5 6)
['=', 5.0, 6.0]
Lisp>

getSexp() returns the corresponding list of S expressions. Above examples shows all working of getToken() and getSexp(). 
putSexp() is also included in this module. The main purpose of this function is to provide result back in the proper manner. Here is the function

def putSexp (s):
    "return string form of an S expression"
    if type(s) == type([]) :
        if 0 and len(s) and s[0] == 'quote' : return "'" + putSexp(s[1:])
        else : return '(' + string.join(map(putSexp,s)) + ')'
    else : return str(s) 

You can download the full code of lispio.py from here
lisp.py 

The main functions in lisp.py are eval and apply. Each is a set of if/elif/else statements. The other functions, pairlis, assoc, evcon, and evlis are just auxillary functions. You will notice that they are tail recursive.

Tail Recursion

We should talk about tail recursion a bit. It is used in our python code although sometimes we could 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 first element matches x. Then 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]
     raise "Lisp error"

With tail recursion the function look like this

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.

After getting the result back from the getSexp(), app.py module calls the eval() of lisp.py. An important term used in this module is the 'alist' (association list). It is permanently set to the global variable. It is used to hold the value of variables in alist, so we can hold many variables and their values in list, also we can access these values in various situation during the execution process. 
 

Functions in lisp.py:

eval() and apply() are the main functions in this module. First of all I want to discuss other simple functions used here, then only I can explain this main functions efficiently.

pairlis()

def pairlis (x,y,alist) :
    """push symbols in x along with respective values in y onto the alist"""
    if not x : return alist
    else : return [[x[0],y[0]]] + pairlis(x[1:],y[1:],alist)

pairlis() adds pairs to the alist (returning an expanded list). When we define a variable or a function ( I will explain it latter) eval() calls the pairlis(). Arguments (x, y, alist), here x and y are two list's and 'alist' is a global variable. After processing return alist back to the calling function.

assoc()

def assoc (x, alist) :
    "look up x on the alist and return its value"
    if   not alist        : raise "Lisp error"
    elif alist[0][0] == x : return alist[0][1]
    else                  : return assoc(x,alist[1:])

I have already explained it above this document. This function used to find the value of variable x in the given alist.

Power() 

def power(x,y):
    if y==0:
        return 1
    elif x==0:
        return 0
    elif y==1:
        return x
    elif y%2==0:
        var_even=power(x,y/2)
        return var_even*var_even
    else:
        var_odd=power(x,(y-1)/2)   
        return x*var_odd*var_odd

This function used to find the power of a number. I think all of you are familiar  with this code.

ifcon()

def ifcon(s,alist):
    if eval(s[0],alist) == 't':
        return eval(s[1],alist)
    else:
        return eval(s[2],alist)

This function used to implement the if/else condition. It recursively calls the eval() to check the condition is true or false.

evcon() and evlis()

def evcon (c, alist) :
    "evaluate cond. Note just the pairs passed in c"
    if   len(c) == 0           : return []
    elif eval (c[0][0], alist) : return eval (c[0][1],alist)
    else                       : return evcon(c[1:],  alist)

def evlis (l, alist) :
    "evaluate all elements in a list, returning list of the values"
    if not l : return []
    else     : return [eval(l[0], alist)] + evlis(l[1:], alist)

evcon() is special for handling condition expressions. evlis() similar to the python map(). It evaluates each item in the list passed and returns a list of the values.

Two other simple functions are,

def isSymbol(x) : return type(x) == type('')  
def isNumber(x) : return type(x) == type(0.0)  

These functions return boolean values.

Important functions:
eval()

def eval (exp, alist) :
    "evaluate an S expression using the alist"
    global Alist
    if debug : print "--Eval---", sxp(exp), " alist=",sxp(alist)
    if   exp == 't'     : return 't'      # true evaluates to itself
    elif exp == 'nil'   : return 'nil'       # symbol nil same as a null list
    elif exp == 'alist' : return Alist    # special command to examine alist
    elif isNumber(exp)    : return exp      # numbers eval to themselves
    elif isSymbol(exp)    : return assoc(exp,alist)  # look up variables
    else :               # check for special forms
        if   exp[0] == 'quote' : return exp[1]
        elif exp[0] == 'def' : # special extra. Let user define functions that stick
            alist = Alist = pairlis([exp[1]],[exp[2]],alist)
            return exp[1]         # return function name
    elif exp[0] == 'if'   : return ifcon(exp[1:],alist)
        elif exp[0] == 'cond'  : return evcon(exp[1:], alist)
        else :
            x = evlis(exp[1:], alist)
            return apply (exp[0],x , alist) 

After getting result (list) from the getSexp(), calls the eval(). List and alist are the arguments passed to it.

def eval (exp, alist) :

'exp' contain list representation of S expression and 'alist' means global variable.

if   exp == 't'     : return 't'      # true evaluates to itself
    elif exp == 'nil'   : return 'nil'       # symbol nil same as a null list
    elif exp == 'alist' : return Alist    # special command to examine alist

If the given expression is 't', 'nil' and 'alist' means the function returns 't', 'nil' and 'alist' respectively. 't' means true, 'nil' means false and 'alist' means the current values in the alist. 

elif isNumber(exp)    : return exp      # numbers eval to themselves
elif isSymbol(exp)    : return assoc(exp,alist)  # look up variables

If the given expression is a number, then function returns the same number. If it is a symbol, then call assoc() to retrieve the current value of that symbol and return that value back to calling function.

else :               # check for special forms
        if   exp[0] == 'quote' : return exp[1]
        elif exp[0] == 'def' :    # special extra. Let user define functions that stick
            alist = Alist = pairlis([exp[1]],[exp[2]],alist)
            return exp[1]         # return function name
        elif exp[0] == 'if'   : return ifcon(exp[1:],alist)
        elif exp[0] == 'cond'  : return evcon(exp[1:], alist)
        else :
            x = evlis(exp[1:], alist)
            return apply (exp[0],x , alist)

If exp[0] contain 'quote' then it returns the content of exp[1]. For example

(quote charlie)    yields  charlie
(quote (a b c))     yields (a b c)  

'def' allows us to set variables or define functions by adding a pair on to the global Alist. Also returns exp[1]. For example

Note: Here I shows the examples using terminal, using existing code we canot run it on terminal. Just try to realize its working.

Lisp>(def a 7)       # here assign 7 to variable 'a'
a
Lisp>a         # display the value of a
7.0
Lisp>(def a (lambda (x) (b)))    # Define a function 'a'
a

If exp[0] contain 'if' , then calls the ifcon() to evaluate the condition to return result. For example.

(if (> 4 5) (+ 4 3)(- 6 7))    It means if 4>5 then 4+3 else 6-7. here function return -1.
(if (< 4 5) (+ 4 3)(- 6 7))    function return 7

If all these conditions are false, then eval() calls the apply().

Apply()

def apply (fn,args,alist) :
    "apply a function fn to its arguments in args"
    if debug : print "--Apply--", sxp(fn), " Args=",sxp(args), " alist=",sxp(alist)
    if isSymbol(fn) :   # name of a function
        if   fn == 'atom' : return [[],'t'][type(args[0]) != type([])]
        elif fn == 'car'  : return args[0][0]   # first element of 1st arg
        elif fn == 'cdr'  : return args[0][1:]  # tail of 1st arg
        elif fn == '+'    : return args[0]+args[1]
        elif fn == '*'    : return args[0]*args[1]
        elif fn == '-'    : return args[0]-args[1]
        elif fn == '/'    : return args[0]/args[1]
        elif fn == '^'    : return power(args[0],args[1])
        elif fn == '<'   : return ['nil','t'][args[0] < args[1]]
        elif fn == '<='   : return ['nil','t'][args[0] <= args[1]]
        elif fn == '>'   : return ['nil','t'][args[0] > args[1]]
        elif fn == '>='   : return ['nil','t'][args[0] >= args[1]]
        elif fn == '='   : return ['nil','t'][args[0] == args[1]]
        elif fn == 'not'  : return [[],'t'][args[0] == []]
        elif fn == 'cons' :
            if type(args[1]) != type([]) : args[1] = [args[1]]
            return [args[0]] + args[1]
        else : return (apply(eval(fn,alist),args,alist))
    elif fn[0] == 'lambda' : # a function definition
        return eval (fn[2], pairlis(fn[1],args,alist))
    else                   : raise "Lisp error"

Arguments passed to it is the function name, arguments and alist. Based on the function name perform arithmetic functions such as addition, subraction, multiplication, division. Also perform <, <=, >, >=, = operations. We can also find the power of a number.

Examples:

(+ 1 (+ 2 (+ 3 4))) is the same as (+ 1 (+ 2 7)) is the same as (+ 1 9) which yields 10, 
(+ (+ 1 2) (+ 3 4)) is the same as (+ 3 7) which yields 10, 
(- 10 7) yields 3, 
(- 7 10) yields 0, 
(+ (* 3 4) (* 5 6)) is the same as (+ 12 30) which yields 42, 
(^ 2 10) yields 1024, 
(< (* 10 10) 101) is the same as (< 100 101) which yields true, 
(= (* 10 10) 101) is the same as (= 100 101) which yields false.

elif fn == 'car'  : return args[0][0]   # first element of 1st arg
elif fn == 'cdr'  : return args[0][1:]  # tail of 1st arg

If the function name is 'car', then it returns the first element of the first argument. If the function name is 'cdr', then it returns the tail of the first argument. For example

(car ' (a b c)) yields a, 
(cdr ' (a b c)) yields (b c), 
(car ' ((a) (b) (c))) yields (a), 
(cdr ' ((a) (b) (c))) yields ((b) (c)), 
(car ' (a)) yields a, 
(cdr ' (a)) yields (), 

elif fn == 'cons' : 
if type(args[1]) != type([]) : args[1] = [args[1]]
            return [args[0]] + args[1] 

If the function name is 'cons', then it combines the arguments to make a new list. For example.

(cons ' a ' (b c)) yields (a b c), 
(cons ' (a) ' ((b) (c))) yields ((a) (b) (c)), 
(cons ' a ' ()) yields (a), 

elif fn[0] == 'lambda' : # a function definition
        return eval (fn[2], pairlis(fn[1],args,alist))

Another special form 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 function. It may be applied to arguments just like any primitive function.

((lambda (x) (* x x)) 2)     evaluates to 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)))
(square 4)                   evaluates to 16

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))))
      )
   )
)
(length '(a b c d e f g))   yields 7

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.

We can define a function , that find the factorial of a number.

(def fact (lambda (n) (if (< n 1) 1 (* n (fact (- n 1))))))
(fact 9)
             Evaluates to  362880
(def fact (lambda (n) (if (<= n 1) 1 (* n (fact (- n 1))))))
(fact -5)    Evaluates to 1

This is the structure of my project. I think you are satisfied with this explanation. You can download the lisp.py module from here