1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
# -*- 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