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
150
151
152
153
154
155
156
157
158
|
"""
null -> None
pair -> <use tuples>
boolean (true/false) -> True/False
number -> number
identifier/symbol -> string
const (atomic values)
lambda
quote (s-expr "one level down")
identifier (a symbol to be looked up in the context)
cond (conditional expression)
"""
def is_atom(x):
return x is () or type(x) not in (None, tuple, list, dict)
def is_boolean(x):
return x in (True, False)
def is_number(x):
return type(x) in (int, float, long)
def is_zero(x):
return x == 0
def is_null(x):
return x is ()
def is_eq(a, b):
return a == b
def is_builtin(x):
return x in ('lambda', 'quote', 'cond', 'else', 'cons', 'car', 'cdr',
'null?', 'eq?', 'atom?', 'zero?', 'number?',
'+', '-', '*', '/')
# because python does not allow circular function definitions, and action
# functions call out to meaning(), which depends on some actions, we'll use an
# "action lookup table" to handle function references ourself.
# A more "pythonic" way to do this might be to use an object.
actions = dict()
def meaning(x, ctx):
action = None
if is_atom(x):
if is_number(x) or is_boolean(x) or is_builtin(x):
action = actions['identity']
else: # an identifier
action = actions['lookup']
elif type(x) is tuple:
if x[0] is 'quote':
action = actions['quote']
elif x[0] is 'cond':
action = actions['cond']
elif x[0] is 'lambda':
action = actions['lambda']
elif type(x[0]) is tuple:
action = actions['apply']
else: # some other identifier, either builtin or not
action = actions['apply']
else:
raise ValueError("Unexpected expression: %s" % x)
return action(x, ctx)
def meaning_list(l, ctx):
return tuple([meaning(x, ctx) for x in l])
def identity_action(x, ctx):
return x
actions['identity'] = identity_action
def lookup_action(x, ctx):
if not x in ctx:
ValueError("Unknown identifier: %s" % x)
else:
return ctx[x]
actions['lookup'] = lookup_action
def quote_action(x, ctx):
if len(x) != 2:
ValueError("Improper quote usage: %s" % x)
return x[1]
actions['quote'] = quote_action
def cond_action(x, ctx):
for line in x[1:]:
if line[0] == 'else':
return meaning(line[1], ctx)
elif meaning(line[0], ctx):
return meanint(line[1], ctx)
else:
# "unspecified"
return None
actions['cond'] = cond_action
def lambda_action(x, ctx):
return ('procedure', x[1], x[2:], ctx.copy())
actions['lambda'] = lambda_action
def apply_action(x, ctx):
if is_builtin(x[0]):
args = meaning_list(x[1:], ctx)
if x[0] is 'cons':
return (args[0], ) + args[1]
elif x[0] is 'car':
return args[0][0]
elif x[0] is 'cdr':
return args[0][1]
elif x[0] is 'null?':
return is_null(args[0])
elif x[0] is 'eq?':
return is_eq(args[0], args[1])
elif x[0] is 'atom?':
return is_atom(args[0])
elif x[0] is 'zero?':
return is_zero(args[0])
elif x[0] is 'number?':
return is_number(args[0])
elif x[0] is '+':
return args[0] + args[1]
elif x[0] is '-':
return args[0] - args[1]
elif x[0] is '*':
return args[0] * args[1]
elif x[0] is '/':
return args[0] / args[1]
else:
raise Exception("Unexpected builtin: %s" % x[0])
elif type(x[0]) is tuple:
proc = meaning(x[0], ctx)
if proc[0] is not 'procedure':
raise Exception("Not applicable: %s" % str(proc))
variables = proc[1]
body = proc[2]
closure = proc[3].copy()
args = meaning_list(x[1:], ctx)
for i in range(len(variables)):
closure[variables[i]] = args[i]
for expr in body:
ret = meaning(expr, closure)
return ret
else:
raise Exception("Unexpected... thing...: %s" % str(x[0]))
actions['apply'] = apply_action
def value(x):
return meaning(x, dict())
def test():
# ((lambda (x) (+ 1 x)) 5) ; 6
v = value( (('lambda', ('x',), ('+', 1, 'x')), 5) )
assert(v is 6)
return True
if __name__=='__main__':
print(test())
|
