-
Notifications
You must be signed in to change notification settings - Fork 39
Expand file tree
/
Copy pathlis.py
More file actions
executable file
·272 lines (226 loc) · 8.66 KB
/
lis.py
File metadata and controls
executable file
·272 lines (226 loc) · 8.66 KB
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
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
#!/usr/bin/env python3
################ lis.py: Scheme Interpreter in Python 3.10
## (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 collections.abc import MutableMapping
from typing import Any, TypeAlias
from exceptions import (
UnexpectedCloseParen, UnexpectedEndOfSource, UndefinedSymbol,
InvalidSyntax, EvaluatorException,
)
Symbol: TypeAlias = str
Number: TypeAlias = int | float
Atom: TypeAlias = int | float | Symbol
Expression: TypeAlias = Atom | list
TCO_ENABLED = True
class Environment(ChainMap):
"A ChainMap that allows updating 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
return
raise KeyError(key)
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.definition_env = env
def application_env(self, args: list[Expression]) -> Environment:
local_env = dict(zip(self.parms, args))
return Environment(local_env, self.definition_env)
def __call__(self, *args: Expression) -> Any:
env = self.application_env(args)
for exp in self.body:
result = evaluate(exp, env)
return result
################ global environment
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,
'quotient': op.floordiv,
'>': op.gt,
'<': op.lt,
'>=': op.ge,
'<=': op.le,
'=': op.eq,
'abs': abs,
'append': op.add,
'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,
'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
################ parse, tokenize, and read_from_tokens
def parse(source: str) -> Expression:
"Read a Scheme expression from a string."
return read_from_tokens(tokenize(source))
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 UnexpectedEndOfSource()
token = tokens.pop(0)
if '(' == token:
exp = []
while tokens and tokens[0] != ')':
exp.append(read_from_tokens(tokens))
if not tokens:
raise UnexpectedEndOfSource()
tokens.pop(0) # discard ')'
return exp
elif ')' == token:
raise UnexpectedCloseParen()
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)
################ interaction: a REPL
def repl(prompt: str = 'lis.py> ') -> None:
"A prompt-read-evaluate-print loop."
global_env: Environment = standard_env()
while True:
val = evaluate(parse(input(prompt)), 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)
################ special forms
def cond_form(clauses: list[Expression], env: Environment) -> Any:
"Special form: (cond (test exp)* (else eN)?)."
for clause in clauses:
match clause:
case ['else', *body]:
for exp in body:
result = evaluate(exp, env)
return result
case [test, *body] if evaluate(test, env):
for exp in body:
result = evaluate(exp, env)
return result
def or_form(expressions: list[Expression], env: Environment) -> Any:
"Special form: (or exp*)"
value = False
for exp in expressions:
value = evaluate(exp, env)
if value:
return value
return value
def and_form(expressions: list[Expression], env: Environment) -> Any:
"Special form: (and exp*)"
value = True
for exp in expressions:
value = evaluate(exp, env)
if not value:
return value
return value
################ eval
KEYWORDS_1 = ['quote', 'if', 'define', 'lambda']
KEYWORDS_2 = ['set!', 'cond', 'or', 'and', 'begin']
KEYWORDS = KEYWORDS_1 + KEYWORDS_2
# Quantifiers in syntax descriptions:
# * : 0 or more
# + : 1 or more
# ? : 0 or 1
def evaluate(exp: Expression, env: Environment) -> Any:
"Evaluate an expression in an environment."
while True:
match exp:
case int(x) | float(x): # number literal
return x
case Symbol(var): # variable reference
try:
return env[var]
except KeyError as exc:
raise UndefinedSymbol(var) from exc
case ['quote', exp]: # (quote exp)
return exp
case ['if', test, consequence, alternative]: # (if test consequence alternative)
if evaluate(test, env):
exp = consequence
else:
exp = alternative
case ['define', Symbol(var), value_exp]: # (define var exp)
env[var] = evaluate(value_exp, env)
return
case ['set!', Symbol(var), value_exp]: # (set! var exp)
env.change(var, evaluate(value_exp, env))
return
case ['define', [Symbol(name), *parms], *body # (define (name parm*)) body+)
] if len(body) > 0:
env[name] = Procedure(parms, body, env)
return
case ['lambda', [*parms], *body] if len(body) > 0: # (lambda (parm*) body+)
return Procedure(parms, body, env)
case ['cond', *clauses]: # (cond (t1 e1)* (else eN)?)
return cond_form(clauses, env)
case ['or', *expressions]: # (or exp*)
return or_form(expressions, env)
case ['and', *expressions]: # (and exp*)
return and_form(expressions, env)
case ['begin', *expressions]: # (begin exp+)
for exp in expressions[:-1]:
evaluate(exp, env)
exp = expressions[-1]
case [op, *args] if op not in KEYWORDS: # (proc exp*)
proc = evaluate(op, env)
values = [evaluate(arg, env) for arg in args]
if TCO_ENABLED and isinstance(proc, Procedure):
exp = ['begin', *proc.body]
env = proc.application_env(values)
else:
try:
return proc(*values)
except TypeError as exc:
msg = (f'{exc!r}\ninvoking: {proc!r}({args!r}):'
f'\nsource: {lispstr(exp)}\nAST: {exp!r}')
raise EvaluatorException(msg) from exc
case _:
raise InvalidSyntax(lispstr(exp))
if __name__ == '__main__':
repl()