lisp.py

class Reader:
    def __init__(self, form):
        self.form = form
        self.index = 0

    def seek_char(self):
        if self.index >= len(self.form):
            return None
        return self.form[self.index]

    def unread_char(self):
        self.index -= 1

    def read_char(self):
        if self.index >= len(self.form):
            return None
        self.index += 1
        return self.form[self.index-1]

    def read_token(self):
        ch = self.read_char()
        if ch == '(':
            return '('
        elif ch == ')':
            if self.seek_char() == ' ':
                self.read_char()
            return ')'
        else:
            buf = ''
            while ch != ' ' and ch != None:
                if ch == ')':
                    self.unread_char()
                    return buf
                else:
                    buf += ch
                    ch = self.read_char()

            return buf

def read_list(reader):
    result = []
    token = reader.read_token()
    while token:
        if token == '(':
            result.append(read_list(reader))
        elif token == ')':
            return result
        else:
            result.append(token)
        token = reader.read_token()

    return result

def read_atom(reader):
    return reader.read_token()

def read(reader):
    # ch = reader.seek_char()
    ch = reader.read_char()
    if ch == '(':
        return read_list(reader)
    return read_atom(reader)

# --------------------------------------------------------

def quote(e):
    return e

def car(e):
    assert isinstance(e, list)
    return e[0]

def cdr(e):
    assert isinstance(e, list)
    return e[1:]

def cons(e1, e2):
    if isinstance(e2, list):
        return [e1] + e2
    return [e1, e2]

def equal(e1, e2):
    return e1 == e2

def atom(e):
    return not isinstance(e, list)

def cond(*cases):
    for case in cases:
        if eval_(case[0]) is not None:
            for expr in cdr(case)[:-1]:
                eval_(expr)
            return eval_(case[-1])
    return None

def lambda_(args, *exprs):
    def fn(*arg_vals):
        fn_env = {k:v for (k, v) in zip(args, arg_vals)}
        fn_env['parent_env'] = env

        for expr in exprs[:-1]:
            eval_(expr, fn_env)
        return eval_(exprs[-1], fn_env)
    return fn

def label(name, lambda_exp, *exprs):
    func = eval_(lambda_exp)
    label_env = {'parent_env': env}
    label_env[name] = func

    for exp in exprs[:-1]:
        eval_(exp, label_env)
    return eval_(exprs[-1], label_env)

def defun(name, args, *exprs):
    env[name] = lambda_(args, *exprs)

env = {'quote': quote,
       'car': car,
       'cdr': cdr,
       'cons': cons,
       'equal': equal,
       'atom': atom,
       'cond': cond,
       'lambda': lambda_,
       'label': label,
       'defun': defun}

def search_in_env(env, key):
    # print "searching:", key
    val = env.get(key)
    if val:
        return val
    if env.has_key('parent_env'):
        return search_in_env(env['parent_env'], key)
    raise KeyError(key)

def eval_(exp, env=env):
    # print "evaluating: %s" % str(exp)
    if isinstance(exp, list):
        if isinstance(exp[0], list):
            op = eval_(exp[0])
        else:
            op = search_in_env(env, exp[0])

        if op in [quote, cond, lambda_, label, defun]:
            return apply(op, exp[1:])
        return apply(op, [eval_(e, env) for e in exp[1:]])

    return search_in_env(env, exp)

def eval_from_string(string):
    return eval_(read(Reader(string)))

def expr_repr(expr):
    if isinstance(expr, list):
        return '(' + ' '.join([expr_repr(e) for e in expr]) + ')'
    elif isinstance(expr, bool):
        if expr:
            return 'T'
        return 'nil'
    return str(expr)

def repl():
    while True:
        try:
            input = raw_input("> ")
            print expr_repr(eval_(read(Reader(input))))
        except (KeyboardInterrupt, EOFError):
            return

if __name__ == '__main__':
    repl()

lisp_test.py

import unittest

from lisp import *

class TestLisp(unittest.TestCase):

    def test_quote(self):
        r = expr_repr(eval_from_string("(quote a)"))
        self.assertEqual(r, "a")

    def test_car(self):
        r = expr_repr(eval_from_string("(car (quote (a b c)))"))
        self.assertEqual(r, "a")

    def test_cdr(self):
        r = expr_repr(eval_from_string("(cdr (quote (a b c)))"))
        self.assertEqual(r, "(b c)")

    def test_cons(self):
        r = expr_repr(eval_from_string("(cons (quote a) (quote (b c)))"))
        self.assertEqual(r, "(a b c)")

    def test_equal(self):
        r = expr_repr(eval_from_string("(equal (car (quote (a b))) (quote a))"))
        self.assertEqual(r, 'T')

    def test_atom(self):
        r1 = expr_repr(eval_from_string("(atom (quote (1 2)))"))
        r2 = expr_repr(eval_from_string("(atom (quote a))"))
        self.assertEqual(r1, 'nil')
        self.assertEqual(r2, 'T')

    def test_cond(self):
        r = expr_repr(eval_from_string("(cond ((atom (quote a)) (quote b)) (quote t) (quote c)))"))
        self.assertEqual(r, 'b')

    def test_lambda(self):
        r = expr_repr(eval_from_string(
            "((lambda (x y) (cons (car x) y)) (quote (a b)) (cdr (quote (c d))))"))
        self.assertEqual(r, '(a d)')

    def test_label(self):
        r = expr_repr(eval_from_string(
            "(label ff (lambda (x) (cons (quote a) x)) (ff (quote (b c d))))"))
        self.assertEqual(r, '(a b c d)')

    def test_defun(self):
        eval_from_string("(defun fun1 (a b c) (cons (cons (car a) (car (cdr b))) c))")
        r = expr_repr(eval_from_string("(fun1 (quote (1 2)) (quote (a b c d)) (quote e))"))
        self.assertEqual(r, "((1 b) e)")

if __name__ == '__main__':
    unittest.main()