Lisp Interpreter Using Python

Here i like to explain about small "interpreter of lisp  using python" . first lets go to language interpreter . its a process to convert a language into execution state
using syntax and semantics rules simply say compiler .
 a compiler have many parts but  we focus on  parsing and execution 
              Parsing means convert a program into sequence of characters based on syntax rules and  execution  means  internal representation then processed based on semantic rules .

                                    Representation of an interpreter

This is done in python and JavaScript  to see the code : click here

Before  explaining this we have to look at the working of the program for this

1:  >> program = "(begin (define r 3) (* 3.141592653 (* r r)))"  
2:  >>> parse(program)  
3:  ['begin', ['define', 'r', 3], ['*', 3.141592653, ['*', 'r', 'r']]]  
4:  >>> eval(parse(program))  
5:  28.274333877  

just look  parse section convert the lisp program into list of number and strings in python and evaluation gives the final output

execution :

                      Mainly have two parts evaluation and Environment .
Evaluation  means there are nine cases in lisp that is evaluated using function eval taking two argument that expression x,environment env.
 

1:  def eval(x, env=global_env):  
2:    "Evaluate an expression in an environment."  
3:    if isa(x, Symbol):       # variable reference  
4:      return env.find(x)[x]  
5:    elif not isa(x, list):     # constant literal  
6:      return x          
7:    elif x[0] == 'quote':     # (quote exp)  
8:      (_, exp) = x  
9:      return exp  
10:    elif x[0] == 'if':       # (if test conseq alt)  
11:      (_, test, conseq, alt) = x  
12:      return eval((conseq if eval(test, env) else alt), env)  
13:    elif x[0] == 'set!':      # (set! var exp)  
14:      (_, var, exp) = x  
15:      env.find(var)[var] = eval(exp, env)  
16:    elif x[0] == 'define':     # (define var exp)  
17:      (_, var, exp) = x  
18:      env[var] = eval(exp, env)  
19:    elif x[0] == 'lambda':     # (lambda (var*) exp)  
20:      (_, vars, exp) = x  
21:      return lambda *args: eval(exp, Env(vars, args, env))  
22:    elif x[0] == 'begin':     # (begin exp*)  
23:      for exp in x[1:]:  
24:        val = eval(exp, env)  
25:      return val  
26:    else:             # (proc exp*)  
27:      exps = [eval(exp, env) for exp in x]  
28:      proc = exps.pop(0)  
29:      return proc(*exps)  
30:  isa = isinstance  
31:  Symbol = str  

Environment
                     Environments are mappings of variable names (symbols) to the values (data objects) held by them
for a function definition there two section first definition second procedure call
when define a function  we have the output

1:  >> program = "(define area (lambda (r) (* 3.141592653 (* r r)))"  
2:  >>> parse(program)  
3:  ['define', 'area', ['lambda', ['r'], ['*', 3.141592653, ['*', 'r', 'r']]]]  
4:  >>> eval(parse(program))  
5:  None  

In this evaluation we take the branch if x[0] == 'define', under which Python sets var to 'area' and exp to ['lambda', ['r'], ['*', 3.141592653, ['*', 'r', 'r']]]. Python then modifies the env (which at this point is the global environment), adding a new variable, 'area', and setting it to the result of evaluating exp. To evaluate exp, we follow the elif x[0] == 'lambda' in eval, branch, assigning the three variables (_, vars, exp) to the corresponding elements of the list x (and signalling an error if x is not of length 3). We then create a new procedure that, when called, will evaluate the expression ['*', 3.141592653 ['*', 'r', 'r']], in the environment formed by binding the formal parameters of the procedure (in this case there is just one parameter, r) to the arguments supplied in the procedure call, and in addition using the current environment for any variables not in the parameter list (for example, the variable *). The value of this newly-minted procedure is then assigned as the value of area in global_env.

Now what happens when we evaluate (area 3)? Since area is not one of the special form symbols, this must be a procedure call (the last else: of eval), and the whole list of expressions is evaluated, one at a time. Evaluating area yields the procedure we just created; evaluating 3 yields 3. We then (according to the last line of eval) call the newly-created procedure with the argument list [3]. this means evaluating exp, which is ['*', 3.141592653 ['*', 'r', 'r']], in the environment where r is 3 and the outer environment is the global environment, and therefore * is the multiplication procedure.
           
We have an Env class which gives appropriate value for variables

1:  class Env(dict):  
2:    "An environment: a dict of {'var':val} pairs, with an outer Env."  
3:    def __init__(self, parms=(), args=(), outer=None):  
4:      self.update(zip(parms,args))  
5:      self.outer = outer  
6:    def find(self, var):  
7:      "Find the innermost Env where var appears."  
8:      return self if var in self else self.outer.find(var)  

This process of looking first in inner environments and then in outer ones is called lexical scoping. Env.find finds the right environment according to lexical scoping rules.
some build in procedure is added to env

1:  def add_globals(env):  
2:    "Add some Scheme standard procedures to an environment."  
3:    import math, operator as op  
4:    env.update(vars(math)) # sin, sqrt, ...  
5:    env.update(  
6:     {'+':op.add, '-':op.sub, '*':op.mul, '/':op.div, 'not':op.not_,  
7:     '>':op.gt, '<':op.lt, '>=':op.ge, '<=':op.le, '=':op.eq,   
8:     'equal?':op.eq, 'eq?':op.is_, 'length':len, 'cons':lambda x,y:[x]+y,  
9:     'car':lambda x:x[0],'cdr':lambda x:x[1:], 'append':op.add,   
10:     'list':lambda *x:list(x), 'list?': lambda x:isa(x,list),   
11:     'null?':lambda x:x==[], 'symbol?':lambda x: isa(x, Symbol)})  
12:    return env  
13:  global_env = add_globals(Env())  

Parsing:parse and read
         
  parsing is two section : tokenized to separate into tokens   
  join token based on syntax rules and build internal structure
  

          

1:  >>> program = "(set! twox (* x 2))"  
2:  >>> tokenize(program)  
3:  ['(', 'set!', 'twox', '(', '*', 'x', '2', ')', ')']  
4:  >>> parse(program)  
5:  ['set!', 'twox', ['*', 'x', 2]]  

 now just  look at parsing function

1:  def read(s):  
2:    "Read a Scheme expression from a string."  
3:    return read_from(tokenize(s))  
4:  parse = read  
5:  def tokenize(s):  
6:    "Convert a string into a list of tokens."  
7:    return s.replace('(',' ( ').replace(')',' ) ').split()  
8:  def read_from(tokens):  
9:    "Read an expression from a sequence of tokens."  
10:    if len(tokens) == 0:  
11:      raise SyntaxError('unexpected EOF while reading')  
12:    token = tokens.pop(0)  
13:    if '(' == token:  
14:      L = []  
15:      while tokens[0] != ')':  
16:        L.append(read_from(tokens))  
17:      tokens.pop(0) # pop off ')'  
18:      return L  
19:    elif ')' == token:  
20:      raise SyntaxError('unexpected )')  
21:    else:  
22:      return atom(token)  
23:  def atom(token):  
24:    "Numbers become numbers; every other token is a symbol."  
25:    try: return int(token)  
26:    except ValueError:  
27:      try: return float(token)  
28:      except ValueError:  
29:        return Symbol(token)  

Finally we'll add a function, to_string, to convert an expression back into a Lisp-readable string, and a function repl, which stands for read-eval-print-loop, to form an interactive Lisp interpreter:

1:  def to_string(exp):  
2:    "Convert a Python object back into a Lisp-readable string."  
3:    return '('+' '.join(map(to_string, exp))+')' if isa(exp, list) else str(exp)  
4:  def repl(prompt='lis.py> '):  
5:    "A prompt-read-eval-print loop."  
6:    while True:  
7:      val = eval(parse(raw_input(prompt)))  
8:      if val is not None: print to_string(val)  

 Now we can check final output:

1:  >>> repl()  
2:  lis.py> (define area (lambda (r) (* 3.141592653 (* r r))))  
3:  lis.py> (area 3)  
4:  28.274333877  
5:  lis.py> (define fact (lambda (n) (if (<= n 1) 1 (* n (fact (- n 1))))))  
6:  lis.py> (fact 10)  
7:  3628800  
8:  lis.py> (fact 100)  
9:  9332621544394415268169923885626670049071596826438162146859296389521759999322991  
10:  5608941463976156518286253697920827223758251185210916864000000000000000000000000  
11:  lis.py> (area (fact 10))  
12:  4.1369087198e+13  
13:  lis.py> (define first car)  
14:  lis.py> (define rest cdr)  
15:  lis.py> (define count (lambda (item L) (if L (+ (equal? item (first L)) (count item (rest L))) 0)))  
16:  lis.py> (count 0 (list 0 1 2 3 0 0))  
17:  3  
18:  lis.py> (count (quote the) (quote (the more the merrier the bigger the better)))  
19:  4  

Operator overloading in Python

Operator overloading using class rational number .In this allowing classes to define their own behavior with respect to language operators .here is code for
a rational number which add and subtract 

1:  class RationalNumbe:  
2:    def __init__(self, numerator, denominator=1):  
3:      self.n = numerator  
4:      self.d = denominator  
5:    def __add__(self, other):  
6:      if not isinstance(other, RationalNumber):  
7:        other = RationalNumber(other)  
8:      n = self.n * other.d + self.d * other.n  
9:      d = self.d * other.d  
10:      return RationalNumber(n, d)  
11:    def __sub__(self,other):  
12:      if not isinstance(other,RationalNumber):  
13:       other = RationalNumber(other)  
14:      n = self.n * other.d + self.d * other.n  
15:      d = self.d * other.d  
16:      return RationalNumber(n, d)  
17:    def __str__(self):  
18:      return "%s/%s" % (self.n,self.d)  
19:    __rep__ = __str__  
20:  a = RationalNumber(3,2)  
21:  b = RationalNumber(3)  
22:  c=2 
 
23:  print b+c  
24:  print a+b  
25:  print a-b  

In this code we can redefine the existing operator using operator overloading.
that is look at the function add and subtract both function add two rational numbers .Now we can check the output

1:  addition with other 5/1  
2:  addtion 9/2  
3:  subtraction 9/2  

In the output we just get same result for addition and subtraction that is we can redefine existing language operator by class rational numbers

Tracing function call in Python

We know that function is a building part of a program in python so we need to pass a function as another functions argument this is done using higher order functions .Tracing a function call means find the number of times a function is called.  

                Higher order functions are functions which can take function as argument and returns new function from function call.Lets explain tracing function call using a Fibonacci function here is the code for Fibonacci.

1:  def fib(n):  
2:    if n is 0 or n is 1:  
3:      return 1  
4:    else:  
5:      return fib(n-1) + fib(n-2)  

This function is calling recursively now we trace how many times fib is called using the function trace

1:  def trace(f):  
2:    def g(x):  
3:      print f.__name__, x  
4:      value = f(x)  
5:      print 'return', repr(value)  
6:      return value  
7:    return g  
8:  f = trace(fib)  
9:  print f(3)     

The trace returns the output as:

1:  fib 3  
2:  fib 2  
3:  fib 1  
4:  return 1  
5:  fib 0  
6:  return 1  
7:  return 2  
8:  fib 1  
9:  return 1  
10:  return 3  
11:  3  

f= trace(fib) that means fib is replaced by f and f return the value of function   call before the actual call of fib.this is the way to how to trace a function call

 

Profile Function

"Profile function" which takes a function as argument and returns a new function, which behaves exactly similar to the given function, except that it prints the time consumed in executing it.

      We can explain this function in Python .The function is takes another function as argument and behaves exactly like the given function but it also gives the execution time of

given function

1:  import time  
2:  def fib(n):  
3:    if n is 0 or n is 1:  
4:      return 1  
5:    else:  
6:      return fib(n-1) + fib(n-2)  
7:  def profile(f):  
8:    cache={}  
9:    def g(x):  
10:     tim=0  
11:     if x not in cache:  
12:     start = time.time()  
13:     cache[x]=f(x)  
14:     tim=time.time()-start  
15:     return str(tim)+' sec'  
16:    return g  
17:  f= profile(fib)  
18:  print f(20)  

Now we can just go through this program first look for the core function "profile()"

 

    
1:  def profile(f):  
2:    cache={}  
3:    def g(x):  
4:     tim=0  
5:     if x not in cache:  
6:     start = time.time()  
7:     cache[x]=f(x)  
8:     tim=time.time()-start  
9:     return str(tim)+' sec'  
10:    return g  

Profile function takes a function and store  each execution in a cache and count the execution time using the library module "time" and finally returns the execution time of the given function

Now we can go through the output of the program which takes a "fib(20)" 
as function and returns its execution time as 0.00328707695007 seconds.
execution time is dipends  upon the hardware of the system where program is
running