implementing lisp in Python

Question

First: yes, i have taken a very long look at Norvig's lispy. Second: I have reused part of his code.

On to my code, and my question. I am writing a really non-idiomatic lisp interpreter in Python, and I'm curious as to how I would write nested function definitions (e.g. (define square (lambda (x) (* x x))) then (define SoS (lambda (x y) (+ (square x) (square y))))) and currently that doesn't work. I'm a bit stuck. What can I do?

EDIT: Any tips about my coding style or improvements I could make would be greatly appreciated. Thank you!

"""

FIX NESTED DEFINITIONS!

(def square (lambda (x) (* x x)))
(def SoS (lambda x y) (+ (square x) (square y)))

DOES NOT WORK!

"""


#!/usr/bin/python
import readline, sys, shlex
userFuncs   = {}
userVars    = {}
stdOps      = "% * / - + set!".split()


def lispify(nested_lists):
    return str(nested_lists).replace('[','(').replace(']',')').replace(', ',' ').replace("'",'')

def mul_arr(array):
    tot = 1
    for i in array: tot *= i
    return tot

def div_arr(array):
    tot = array[0]
    for i in array[1:]: tot /= i
    return tot

def sub_arr(array):
    print array
    if len(array) > 1: tot = array[0]
    else: tot = 0-array[0]
    for i in array[1:]: tot -= i
    return tot

def atom(tok):
    try: return int(tok)
    except:
        try: return float(tok)
        except: return str(tok)

def pre_in(read):
    tempOp = read[0]
    body = read[1:]
    expr = []
    for i in range(len(body)-1):
        if not isinstance(body[i], list) and body[i] != " ":
            expr.append(str(body[i]))
            expr.append(tempOp)
        else:
            expr.append(str(pre_in(body[i])))
            expr.append(tempOp)
    try:
        if not isinstance(body[-1], list): expr.append(str(body[-1]))
        else: expr.append(str(pre_in(body[-1])))
    except: pass
    if expr != None: return "("+' '.join(expr)+")"

def tok(s):
    try: return shlex.split(s.replace('(',' ( ').replace(')',' ) '))
    except: return s.replace('(',' ( ').replace(')',' ) ').split()

def read_from(toks):
    if len(toks) == 0: raise SyntaxError('unexpected EOF')
    tok = toks.pop(0)
    if tok == "'":
        l = []
        toks.pop(0)
        while toks[0] != ")": l.append(read_from(toks))
        toks.pop(0)
        return lispify(l)
    if tok == '(':
        l = []
        while toks[0] != ')': l.append(read_from(toks))
        toks.pop(0)
        return l
    elif tok == ')': raise SyntaxError('unexpected \')\'')
    else: return atom(tok)

def total_eval(read):
    if isinstance(read, int):
        return read
    elif isinstance(read, str):
        if read not in stdOps:
            if read in userVars:
                return atom(userVars[read])
            else:
                return str(atom(read))
    elif isinstance(read, list):
        if read[0] in userFuncs:
            print read[0]+" = "+userFuncs[read[0]]
            exec(read[0]+" = "+userFuncs[read[0]])
            return eval(read[0]+str(tuple(read[1:])))
        elif read[0] == "+":
            return sum([float(total_eval(i)) for i in read[1:]])
        elif read[0] == "*":
            return mul_arr([float(total_eval(i)) for i in read[1:]])
        elif read[0] == "/":
            return div_arr([float(total_eval(i)) for i in read[1:]])
        elif read[0] == "-":
            return sub_arr([float(total_eval(i)) for i in read[1:]])
        elif read[0] == "set!" or read[0] == "setf":
            userVars[read[1]] = total_eval(read[2])
            return "ok"
        elif read[0] == "lambda":
            tempvars    = ','.join(i.replace(',','') for i in read[1])
            expr        = read[2]
            return "lambda "+str(tempvars)+": "+pre_in(expr)
        elif read[0] == "def" or read[0] == "define" or read[0] == "defun":
            funcName = read[1]
            funcBody = read[2]
            userFuncs[funcName] = total_eval(funcBody)
            return "ok"
        elif read[0] == "cons":
            body = read[1:]
            arr = body[0]
            to_push = body[1]
            if not isinstance(arr, list):
                arr = [arr]
            for i in to_push:
                arr.append(i)
            return lispify(arr)
        elif read[0] == "append":
            body = read[1:]
            main = body[0]
            tail = body[1:]
            for i in tail:
                if i != []:
                    main.append(i)
            #print main
            return lispify(main)
        elif read[0] == "list":
            return lispify(str([total_eval(read[1:][i]) for i in range(len(read[1:]))]))
        elif read[0] == "\'" or read[0] == "quote":
            return lispify(read[1:][0])
        elif read[0] == "print":
            return total_eval(read[1:][0])
        elif not isinstance(read[0], list):
            if read[0] in userFuncs:
                args = read[1:]
                exec(read[0]+" = "+userFuncs[read[0]])
                return eval(read[0]+str(tuple([float(i) for i in args])))
        else:
            if read[0][0] == "lambda":
                tempvars    = ','.join(i.replace(',','') for i in read[0][1])
                expr        = read[0][2]
                exec("temp = lambda "+str(tempvars)+": "+str(pre_in(expr)))
                args = read[1:] if len(read[1:]) > 1 else read[1]
                if isinstance(args, list): return eval("temp"+str(tuple([total_eval(i) for i in args])))
                else: return eval("temp("+str(float(args))+")")
"""
while 1:
    try:
        a = raw_input("lisp>   ")
        try:
            print tok(a)
            print read_from(tok(a))
            print total_eval(read_from(tok(a))),"\n"
        except:
            errorMsg = str(sys.exc_info()[1]).split()
            if errorMsg[0] == "list":
                print "ParseError: mismatched parentheses\n"
            else:
                print ' '.join(errorMsg)
                print
    except (EOFError, KeyboardInterrupt):
        print "\nbye!"
        break
"""
while 1:
    a = raw_input("lisp>   ")
    #print tok(a)
    #print read_from(tok(a))
    print total_eval(read_from(tok(a)))
    print
#"""

Answer 1

Have a look at the output of pre_in:

>>> pre_in(read_from(tok("(+ (square x) (square y))")))
'((x) + (y))'

That should be '(square(x) + square(y))'.

(By the way, your example code contains a syntax error. SoS should be defined as (lambda (x y) (+ (square x) (square y))).)