Lisp Interpreter in Python with Code Generation tailored to Matrix manipulation

learnexp.el

(
	list
	(defun makefactor (n)
		(define q dict)
		(set! q.vars dict)
		(set! q.uS dict)
		(set! q.Jhg (gaussianc n))
		q
	)
	(define f1 (makefactor 2))
	(define f2 (makefactor 3))
	(set! f2.vars (list "A" "B" "C"))
	(set! f2.sw (sort (list "Z" "B" "C")))
	(set! f2.uS.w 10)
	(defun LinearGaussianFactor/ (f1 f2) 
		(if
			(== f1.uS f2.uS) 
			(- f1.Jhg f2.Jhg)
			(
				list
				(assert (== (sepSet f1.vars f2.vars) f1.vars))
				(assert (== (sepSet f1.vars f2.vars) f2.vars))
				(defconst oisfirst (var2index1 f2.uS f1.uS))
				(subop- f1.Jhg oisfirst f2.Jhg) 
			)
		)
	)
	(LinearGaussianFactor/ f1 f2)
	(collapse (quote (LinearGaussianFactor/ f1 f2)))
)

lisgen.py

################ Lispy: Scheme Interpreter in Python

## (c) Peter Norvig, 2010-14; See http://norvig.com/lispy.html

#Modified by Emanuele Ruffaldi for supporting:
# - string literals
# - procedure return
# - deffun
# - assign and get from entities with the dot operator
#
#Modified by Emanuele Ruffaldi for the code generation and constant folding
################ Types

from __future__ import division
import pprint

Symbol = str          # A Lisp Symbol is implemented as a Python str
List   = list         # A Lisp List is implemented as a Python list
Number = (int, float) # A Lisp Number is implemented as a Python int or float

################ Parsing: parse, tokenize, and read_from_tokens

def parse(program):
    "Read a Scheme expression from a string."
    return read_from_tokens(tokenize(program))

def tokenize(s):
    "Convert a string into a list of tokens." # TODO comments
    return s.replace('(',' ( ').replace(')',' ) ').split()

def read_from_tokens(tokens):
    "Read an expression from a sequence of tokens."
    if len(tokens) == 0:
        raise SyntaxError('unexpected EOF while reading')
    token = tokens.pop(0)
    if '(' == token:
        L = []
        while tokens[0] != ')':
            L.append(read_from_tokens(tokens))
        tokens.pop(0) # pop off ')'
        return L
    elif ')' == token:
        raise SyntaxError('unexpected )')
    else:
        return atom(token)

def atom(token):
    "Numbers become numbers; every other token is a symbol."
    try: return int(token)
    except ValueError:
        try: return float(token)
        except ValueError:
            return Symbol(token)

################ Environments
def doassert(x,q="unnamedassert"):
    if not x:
        print "failed assert",x

def subop_less(t,ii,x):
    print "subop_less cannot be evaluated"
    return None
def standard_env():
    "An environment with some Scheme standard procedures."
    import math, operator as op
    env = Env(name="global")
    env.update(vars(math)) # sin, cos, sqrt, pi, ...
    env.update({
        '+':op.add, '-':op.sub, '*':op.mul, '/':op.div, 
        '>':op.gt, '<':op.lt, '>=':op.ge, '<=':op.le, '=':op.eq, '==':op.eq,
        'abs':     abs,
        'append':  op.add,  
        'assert':  doassert,
        'apply':   apply,
        'begin':   lambda *x: x[-1],
        'car':     lambda x: x[0],
        'cdr':     lambda x: x[1:], 
        'cons':    lambda x,y: [x] + y,
        'eq?':     op.is_, 
        'equal?':  op.eq, 
        'length':  len, 
        'list':    lambda *x: list(x), 
        'list?':   lambda x: isinstance(x,list), 
        'map':     map,
        'max':     max,
        'min':     min,
        'sort':    lambda x: list(sorted(x)),
        'not':     op.not_,
        'null?':   lambda x: x == [], 
        'number?': lambda x: isinstance(x, Number),   
        'procedure?': callable,
        'round':   round,
        'symbol?': lambda x: isinstance(x, Symbol),

    })
    return env

class Env(dict):
    "An environment: a dict of {'var':val} pairs, with an outer Env."
    def __init__(self, parms=(), args=(), outer=None,name=""):
        self.update(zip(parms, args))
        self.outer = outer
        self.const = set()
        self.name = name
    def isconst(self,var):
        return var in self.const
    def setconst(self,var):
        self.const.add(var)
    def find(self, var):
        "Find the innermost Env where var appears."

        if (var in self):
            return self
        elif self.outer is None:
            return self
        else:
            return self.outer.find(var)

global_env = standard_env()

################ Interaction: A REPL

def repl(prompt='lis.py> '):
    "A prompt-read-eval-print loop."
    while True:
        val = eval(parse(raw_input(prompt)))
        if val is not None: 
            print(lispstr(val))

def lispstr(exp):
    "Convert a Python object back into a Lisp-readable string."
    if  isinstance(exp, list):
        return '(' + ' '.join(map(lispstr, exp)) + ')' 
    else:
        return str(exp)

################ Procedures

class Procedure(object):
    "A user-defined Scheme procedure."
    def __init__(self, parms, body, env,name):
        self.parms, self.body, self.env,self.name= parms, body, env,name
    def __call__(self, *args): 
        q = Env(self.parms, args, self.env,name=self.name)
        print "starting procedure",self.name,"with env",q.keys(),q.values()
        return eval(self.body, q)[-1]
    def __repr__(self):
        return "Procedure(%s,%d args)" % (self.name,len(self.parms))

class Gaussian(object):
    "Gaussian in moment form - real or abstract"
    def __init__(self,size=None,value=None,ismoment=False):
        self.size = size
        self.value = value
        self.ismoment = ismoment
    def isabstract(self):
        return self.value is None
    def asmoment(self):
        if self.ismoment:
            return self
        else:
            if self.value is not None:
                print "UNIMPLEMENTED FLIP"
                return Gaussian(self.size,None,True)
            else:
                return Gaussian(self.size,None,True)
    def ascanonical(self):
        if not self.ismoment:
            return self
        else:
            if self.value is not None:
                print "UNIMPLEMENTED FLIP"
                return Gaussian(self.size,None,False)
            else:
                return Gaussian(self.size,None,False)
    def __repr__(self):
        return "Gaussian(size=%d,%s,%s)" % (self.size,self.ismoment and "moment" or "canonical",self.value is None and "abstract" or "real")

################ eval

def collapse(x,env=global_env):
    print "collapse ",
    pprint.pprint(x)
def isconst(x,env=global_env):
    pass

def gencpp(x,env=global_env):
    pass

def var2index1(a,b):
    r = []
    for x in a:
        r.append(b.find(x))
    return r

global_env.update(
{
        'isconst': isconst,
        # special custom
        'subop-': subop_less,
        'gaussianm': lambda x: Gaussian(size=x,value=None,ismoment=True),
        'gaussianc': lambda x: Gaussian(size=x,value=None,ismoment=False),
        'sepSet': lambda x,y: list(set(x)-set(y)),
        'collapse': collapse,
        'var2index1': var2index1
    })

def eval(x, env=global_env):
    "Evaluate an expression in an environment."
    if isinstance(x, Symbol):      # variable reference
        if x[0] == "\"":
            return x[1:-1]
        else:
            # We use Env for storing structure 
            if(x == "dict"):
                return Env()
            else:
                #print "lookup of",x,"in env with keys:",env.keys()
                a = x.split(".")
                w = env.find(a[0])[a[0]]
                for y in a[1:]:
                    w = w[y]
                return w
    elif not isinstance(x, List):  # constant literal
        return x                
    elif x[0] == 'quote':          # (quote exp)
        (_, exp) = x
        return exp
    elif x[0] == 'print':
        for y in x[1:]:
            print eval(y,env),
        print "\n",
    elif x[0] == 'if':             # (if test conseq alt)
        print "processing if ",x
        (_, test, conseq, alt) = x
        exp = (conseq if eval(test, env) else alt)
        print "!!!selected",exp
        w = eval(exp, env)
        print "return of if is ",w[-1]
        return w[-1]
    elif x[0] == 'define':         # (define var exp)
        (_, var, exp) = x
        r = eval(exp,env)
        print "definition",var,"value",r
        env[var] =r
    elif x[0] == 'defun':         # (defun var (var...) body) == (define var (lambda (vars...) body))
        (_, var, parms) = x[0:3]
        #TODO
        body = x[3:]
        body = ["list"] + body
        env[var] = Procedure(parms, body, env,name=var)
    elif x[0] == 'defconst':         # (defun var (var...) body) == (define var (lambda (vars...) body))
        (_, var, exp) = x
        env[var] = eval(exp, env)  # TODO MARK CONST
        env.setconst(var)
    elif x[0] == 'setconst':           # (set! var)
        (_, var) = x
        a = x[1].split(".")
        var = a[0]
        tenv = env.find(var)
        if len(a) > 1:
            # w must exist
            if not var in tenv:
                print "missing ",var,"somewhere,cannot assign"
            else:
                tenv = tenv[var]
                for y in a[1:-1]:
                    if not y in tenv:
                        print "missing ",var,"in part",x
                    else:
                        tenv = tenv[y]
                tenv.setconst(a[-1])
        else:
            tenv.setconst(var)
    elif x[0] == 'set!':           # (set! var exp)
        (_, var, exp) = x
        a = x[1].split(".")
        var = a[0]
        tenv = env.find(var)
        r = eval(exp,env)
        print "writing to",x[1],"in",env.name
        if len(a) > 1:
            # w must exist
            if not var in tenv:
                print "missing ",var,"somewhere,cannot assign"
            else:
                tenv = tenv[var]
                for y in a[1:-1]:
                    if not y in tenv:
                        print "missing ",var,"in part",x
                    else:
                        tenv = tenv[y]
                tenv[a[-1]] = r
        else:
            tenv[var] = r         
    elif x[0] == 'lambda':         # (lambda (var...) body)
        (_, parms, body) = x
        return Procedure(parms,body, env,name="lambda")
    else:                          # (proc arg...)
        print "evaluating something",x[0],"in ",env.name,"with",len(x)-1,"args"
        proc = eval(x[0], env)
        args = [eval(exp, env) for exp in x[1:]]
        return proc(*args)


if __name__ == "__main__":
    import sys
    #defs = set(global_env.keys())
    qenv = Env(outer=global_env,name="sub")

    q = parse(open(sys.argv[1],"rb").read())
    pprint.pprint(q)
    eval(q,qenv)
    print "printing final"
    for k in qenv: #set(global_env.keys())-defs:
        print k,qenv[k]

#;(subassign f1.Jhg oisfirst (- (subref f1.Jhg oisfirst) f2.Jhg) )
#;(LinearGaussianFactor/ f1 f2)
#; q should be local

# TODO: implement the constantness of the expression (const traverse) === constexpr of C++
# TODO: implement the folding (using recursive replacement)
# TODO: implement code generation