-
Notifications
You must be signed in to change notification settings - Fork 862
/
lis.py
212 lines (178 loc) · 6.26 KB
/
lis.py
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
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
#!/usr/bin/env python
################ Lispy: Scheme Interpreter in Python 3.9
## (c) Peter Norvig, 2010-18; See http://norvig.com/lispy.html
## Minor edits for Fluent Python, Second Edition (O'Reilly, 2021)
## by Luciano Ramalho, adding type hints and pattern matching.
################ Imports and Types
import math
import operator as op
from collections import ChainMap
from itertools import chain
from typing import Any, Union, NoReturn
Symbol = str
Atom = Union[float, int, Symbol]
Expression = Union[Atom, list]
################ Parsing: parse, tokenize, and read_from_tokens
def parse(program: str) -> Expression:
"Read a Scheme expression from a string."
return read_from_tokens(tokenize(program))
def tokenize(s: str) -> list[str]:
"Convert a string into a list of tokens."
return s.replace('(', ' ( ').replace(')', ' ) ').split()
def read_from_tokens(tokens: list[str]) -> Expression:
"Read an expression from a sequence of tokens."
if len(tokens) == 0:
raise SyntaxError('unexpected EOF while reading')
token = tokens.pop(0)
if '(' == token:
exp = []
while tokens[0] != ')':
exp.append(read_from_tokens(tokens))
tokens.pop(0) # discard ')'
return exp
elif ')' == token:
raise SyntaxError('unexpected )')
else:
return parse_atom(token)
def parse_atom(token: str) -> Atom:
"Numbers become numbers; every other token is a symbol."
try:
return int(token)
except ValueError:
try:
return float(token)
except ValueError:
return Symbol(token)
################ Global Environment
class Environment(ChainMap[Symbol, Any]):
"A ChainMap that allows changing an item in-place."
def change(self, key: Symbol, value: object) -> None:
"Find where key is defined and change the value there."
for map in self.maps:
if key in map:
map[key] = value # type: ignore[index]
return
raise KeyError(key)
def standard_env() -> Environment:
"An environment with some Scheme standard procedures."
env = Environment()
env.update(vars(math)) # sin, cos, sqrt, pi, ...
env.update({
'+': op.add,
'-': op.sub,
'*': op.mul,
'/': op.truediv,
'//': op.floordiv,
'>': op.gt,
'<': op.lt,
'>=': op.ge,
'<=': op.le,
'=': op.eq,
'abs': abs,
'append': lambda *args: list(chain(*args)),
'apply': lambda proc, args: proc(*args),
'begin': lambda *x: x[-1],
'car': lambda x: x[0],
'cdr': lambda x: x[1:],
'cons': lambda x, y: [x] + y,
'display': lambda x: print(lispstr(x)),
'eq?': op.is_,
'equal?': op.eq,
'filter': lambda *args: list(filter(*args)),
'length': len,
'list': lambda *x: list(x),
'list?': lambda x: isinstance(x, list),
'map': lambda *args: list(map(*args)),
'max': max,
'min': min,
'not': op.not_,
'null?': lambda x: x == [],
'number?': lambda x: isinstance(x, (int, float)),
'procedure?': callable,
'round': round,
'symbol?': lambda x: isinstance(x, Symbol),
})
return env
################ Interaction: A REPL
def repl(prompt: str = 'lis.py> ') -> NoReturn:
"A prompt-read-eval-print loop."
global_env = standard_env()
while True:
ast = parse(input(prompt))
val = evaluate(ast, global_env)
if val is not None:
print(lispstr(val))
def lispstr(exp: object) -> str:
"Convert a Python object back into a Lisp-readable string."
if isinstance(exp, list):
return '(' + ' '.join(map(lispstr, exp)) + ')'
else:
return str(exp)
################ Evaluator
def evaluate(exp: Expression, env: Environment) -> Any:
"Evaluate an expression in an environment."
if isinstance(exp, Symbol): # variable reference
return env[exp]
elif not isinstance(exp, list): # constant literal
return exp
elif exp[0] == 'quote': # (quote exp)
(_, x) = exp
return x
elif exp[0] == 'if': # (if test conseq alt)
(_, test, consequence, alternative) = exp
if evaluate(test, env):
return evaluate(consequence, env)
else:
return evaluate(alternative, env)
elif exp[0] == 'lambda': # (lambda (parm…) body…)
(_, parms, *body) = exp
if not isinstance(parms, list):
raise SyntaxError(lispstr(exp))
return Procedure(parms, body, env)
elif exp[0] == 'define':
(_, name_exp, *rest) = exp
if isinstance(name_exp, Symbol): # (define name exp)
value_exp = rest[0]
env[name_exp] = evaluate(value_exp, env)
else: # (define (name parm…) body…)
name, *parms = name_exp
env[name] = Procedure(parms, rest, env)
elif exp[0] == 'set!':
(_, var, value_exp) = exp
env.change(var, evaluate(value_exp, env))
else: # (proc arg…)
(func_exp, *args) = exp
proc = evaluate(func_exp, env)
args = [evaluate(arg, env) for arg in args]
return proc(*args)
class Procedure:
"A user-defined Scheme procedure."
def __init__(
self, parms: list[Symbol], body: list[Expression], env: Environment
):
self.parms = parms
self.body = body
self.env = env
def __call__(self, *args: Expression) -> Any:
local_env = dict(zip(self.parms, args))
env = Environment(local_env, self.env)
for exp in self.body:
result = evaluate(exp, env)
return result
################ command-line interface
def run(source: str) -> Any:
global_env = standard_env()
tokens = tokenize(source)
while tokens:
exp = read_from_tokens(tokens)
result = evaluate(exp, global_env)
return result
def main(args: list[str]) -> None:
if len(args) == 1:
with open(args[0]) as fp:
run(fp.read())
else:
repl()
if __name__ == '__main__':
import sys
main(sys.argv[1:])