# -*- 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
        assert len(xs) == len(self.args)
        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]

def car(xs):
    return xs[0]

def cdr(xs):
    return xs[1:]

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

##
# macro table
def macro_define(tree):
    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

def macro_lambda(tree):
    assert len(tree) == 3
    return Lambda(tree[1], tree[2], e.scope)

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

def macro_let(tree):
    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

def macro_setx(tree):
    e.scope.setx(tree[1], evaluate(tree[2]))
    return UNDEF

def macro_define_macro(tree):
    macro_table[tree[1]] = lambda xs: Lambda(tree[2], tree[3], e.scope)(
        map(evaluate, cdr(xs)))

def macro_quote(tree):
    return tree

macro_table = {
    "define": macro_define,
    "lambda": macro_lambda,
    "if": macro_if,
    "let": macro_let,
    "set!": macro_setx,
    "define-macro": macro_define_macro,
    "quote": macro_quote,
}

def evaluate(tree):
    if tree == []: return []
    if isinstance(tree, list):
        car = tree[0]
        if car in macro_table:
            return macro_table[car](tree)
            
        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