DouKaku?

# -*- coding: cp932 -*-
# Scheme
# 文字列リテラルは作らない
# ドットリストのパースもしない

class Scope(object):
    def __init__(self, d, parent = None):
        self.d = d
        self.parent = parent
        #print "scope", d, parent
    def __getitem__(self, name):
        if self.d.has_key(name):
            return self.d[name]
        elif self.parent:
            return self.parent[name]

        raise "can't resolve name:", name

    def __setitem__(self, name, value):
        self.d[name] = value

    def setx(self, name, value):
        "impl. of set!"
        if self.d.has_key(name):
            self.d[name] = value
            return
        elif self.parent:
            return self.parent.setx(name, value)

        raise "can't resolve name:", name
        

class Lambda(object):
    def __init__(self, args, body, scope):
        self.args = args
        self.body = body
        self.scope = scope

    def __call__(self, xs):
#        print "Lambda", self.args, xs
        old_scope = e.scope
        e.scope = Scope(dict(zip(self.args, xs)), self.scope)
        result = evaluate(self.body)
        e.scope = old_scope
        return result

import re
_PAT_LEAF = re.compile(r"[^\s()]+|\(|\)")
def _tokenize(s):
    return re.findall(_PAT_LEAF, s)
    
def parse(s):
    tokens = _tokenize(s)
    result = []
    stack = [result]
    for t in tokens:
        if t == "(":
            stack.append([])
        elif t == ")":
            stack[-2].append(stack[-1])
            del stack[-1]
        else:
            stack[-1].append(t)

    return result[0]

def add(xs):
    return sum(xs)

def mul(xs):
    from operator import mul
    return reduce(mul, xs)

def sub(xs):
    if len(xs) == 1: return -xs[0]
    return xs[0] - sum(xs[1:])

def begin(xs):
    return xs[-1]

def expt(xs):
    return xs[0] ** xs[1]

def equal(xs):
    return xs[0] == xs[1]

def div(xs):
    return xs[0] / xs[1]

def lt(xs):
    return xs[0] < xs[1]

def display(xs):
    print xs[0]
    return xs[0]

scope = Scope({"+": add, "*": mul, "-": sub, "=": equal, "/": div, "<": lt}, globals())
UNDEF = "#<undef>"

def evaluate(tree):
    if isinstance(tree, list):
        car = tree[0]
        if car == "define":
            # special form
            if isinstance(tree[1], str): # symbol
                e.scope[tree[1]] = evaluate(tree[2])
            else:
                func_name = tree[1][0]
                args = tree[1][1:]
                e.scope[func_name] = Lambda(args, tree[2], e.scope)
            return UNDEF
        
        if car == "lambda":
            assert len(tree) == 3
            return Lambda(tree[1], tree[2], e.scope)

        if car == "if":
            assert len(tree) == 4
            cond = evaluate(tree[1])
            if cond:
                return evaluate(tree[2])
            else:
                return evaluate(tree[3])

        if car == "let":
            assert len(tree) == 3
            d = dict([(k, evaluate(v)) for (k, v) in tree[1]])
            old_scope = e.scope
            e.scope = Scope(d, e.scope)
            result = evaluate(tree[2])
            e.scope = old_scope
            return result

        if car == "set!":
            e.scope.setx(tree[1], evaluate(tree[2]))
            return UNDEF
            
        car = evaluate(car)
        cdr = tree[1:]
        cdr = map(evaluate, cdr)
        return car(cdr) 
    else:
        if tree[0] in "0123456789":
            return int(tree) # int leteral
        else:
            return e.scope[tree]
   
e = evaluate
e.scope = scope