#!/usr/bin/python3
"Straightforward implementation of the core of Lisp in Python."

def Eval(sexp, env):
    return (env[sexp] if type(sexp) is str else
            specials[sexp[0]](sexp[1:], env) if type(sexp[0]) is str
                                            and sexp[0] in specials else
            Eval(sexp[0], env)([Eval(arg, env) for arg in sexp[1:]]))

def evcon(branches, env):
    for q, a in branches:
        if Eval(q, env): return Eval(a, env)

def evletrec(args, env):
    assignments, body = args[0], args[1]
    env = env.copy()
    for name, a, b in assignments: env[name] = closure(a, b, env)
    return Eval(body, env)

def closure(args, body, env):
    return lambda vals: Eval(body, augment(env, list(zip(args, vals))))

def augment(env, nvpairs):
    env = env.copy()
    for n, v in nvpairs: env[n] = v
    return env

specials = {
    'cond': evcon,
    'letrec': evletrec,
    'lambda': lambda args, env: closure(args[0], args[1], env),
    'quote': lambda args, env: args[0],
}

base_env = {
    'car': lambda args: args[0][0],
    'cdr': lambda args: args[0][1:],
    'cons': lambda args: [args[0]] + args[1],
    'atom': lambda args: type(args[0]) is str,
    'null': lambda args: not args[0],
    'equal': lambda args: args[0] == args[1],
    't': True,
}

example_prog = ['letrec', [['assoc', ['k', 'kvs'],
                            ['cond', [['equal', 'k', ['car', ['car', 'kvs']]],
                                      ['cdr', ['car', 'kvs']]],
                                     [['null', ['cdr', 'kvs']],
                                      ['quote', []]],
                                     ['t', ['assoc', 'k', ['cdr', 'kvs']]]]]],
                          ['assoc', ['quote', 'y'], ['quote',
                                                     [['x', 'a'],
                                                      ['y', 'b'],
                                                      ['z', 'c']]]]]

example2 = ['letrec',
             [['subst', ['f', 'd'],
               ['cond', [['atom', 'd'], ['f', 'd']],
                        [['null', 'd'], ['quote', []]],
                        ['t', ['cons', ['subst', 'f', ['car', 'd']],
                                       ['subst', 'f', ['cdr', 'd']]]]]],
              ['x', [], ['quote', 'X']]],
            ['subst', ['lambda', ['de'], ['cons', ['x'], ['cons', 'de',
                                                          ['quote', []]]]],
             ['quote', ['a', ['small', 'dog'], 'sat']]]]
    
if __name__ == '__main__':
    import cgitb
    cgitb.enable(format='text')
    print(Eval(example_prog, base_env))