-
Notifications
You must be signed in to change notification settings - Fork 1
/
mlisp.py
203 lines (155 loc) · 5.27 KB
/
mlisp.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
from operators import *
from typing import Callable
import re
import argparse
import sys
# environment, represents a variable scope
class Env(dict):
def __init__(self, params=(), args=(), outer=None):
super().__init__()
self.update(zip(params, args))
self.outer = outer
def __getitem__(self, key):
if key in self: return super().__getitem__(key)
return self.outer[key] if self.outer else None
# an anonymous function
class Lambda(Callable):
def __init__(self, params, body, env):
self.params = params
self.body = body
self.env = env
def __call__(self, *args):
# return another lambda if partially evaluated
if len(args) < len(self.params):
return Lambda(self.params[len(args):], self.body, Env(self.params[:len(args)], args, self.env))
# evaluate the whole lambda
lambda_env = Env(self.params, args, self.env)
eval_res = None
# there might be multiple statements in the body
for stmt in self.body:
eval_res = eval(stmt, lambda_env)
return eval_res
Symbol = str
Number = int
List = list
Exp = (Symbol, Number, List)
Arg = (bool, int, Lambda)
LETTER_REGEX = "[a-z]"
DIGIT_REGEX = "[0-9]"
SYMBOL_REGEX = f"{LETTER_REGEX}({LETTER_REGEX}|{DIGIT_REGEX}|-)*"
RESERVED_WORDS = ["mod", "and", "or", "not", "define", "fun", "if"]
def default_env() -> Env:
env = Env()
env.update({
"+": add,
"-": sub,
"*": mul,
"/": div,
"<": lt,
">": gt,
"=": eq,
"mod": mod,
"print-num": print_num,
"and": and_,
"or": or_,
"not": not_,
"print-bool": print_bool,
"#t": True,
"#f": False,
})
return env
def find_symbol(exp: Exp, env: Env):
if isinstance(exp, Number): return exp
if env[exp] is None:
raise SyntaxError(f"unknown symbol '{exp}'")
return env[exp]
def eval_if(args, env: Env):
predicate, consequence, alternative = args
bool_exp = eval(predicate, env)
if not type(bool_exp) is bool:
raise TypeError("if: predicate must be a boolean expression")
res = consequence if eval(predicate, env) else alternative
return eval(res, env)
def eval_define(args, env: Env):
symbol, exp = args
if symbol in RESERVED_WORDS:
raise SyntaxError(f"reserved word '{symbol}' in define statement")
if not re.fullmatch(SYMBOL_REGEX, symbol):
raise SyntaxError(f"unexpected symbol '{symbol}', id must be in lowercase letters or digits")
env[symbol] = eval(exp, env)
def eval_lambda(args, env: Env):
params, *body = args
return Lambda(params, body, env)
def eval(exp: Exp, env: Env):
if isinstance(exp, Symbol) or isinstance(exp, Number):
return find_symbol(exp, env)
# exp is an unevaluated expression, unwrap the expression
op, *args = exp
if isinstance(op, Number): return op # unwrap number
# keyword functions
if op == "if":
return eval_if(args, env)
elif op == "define":
return eval_define(args, env)
elif op == 'lambda' or op == 'fun':
return eval_lambda(args, env)
# function calls
func = eval(op, env)
if not isinstance(func, Callable):
raise SyntaxError(f"operator not found: '{op}'")
func_args = [eval(arg, env) for arg in args]
for param, evaluated in zip(args, func_args):
if not isinstance(evaluated, Arg):
raise SyntaxError(f"unexpected '{param}'")
return func(*func_args)
def tokenize(input_str: str) -> List:
return input_str.replace("(", " ( ").replace(")", " ) ").split()
def read_exp(tokens: List) -> Exp:
if len(tokens) == 0: raise SyntaxError("unexpected EOF")
token = tokens.pop(0)
if token == '(':
exp = []
while len(tokens) > 0 and tokens[0] != ')':
exp.append(read_exp(tokens))
if len(tokens) == 0: raise SyntaxError("unclosed bracket '('")
tokens.pop(0)
return exp
elif token == ')':
raise SyntaxError("unexpected ')'")
else:
return parse_literal(token)
def parse_program(input_str: str, verbose=False) -> Exp:
if verbose: print("Tokenized result:", tokenize(input_str))
return read_exp(tokenize(input_str))
def parse_literal(token: str):
try: return Number(token)
except ValueError: return Symbol(token)
def read_input():
input_lines = []
while True:
try:
line = input()
if line == "end":
break
elif line:
input_lines.append(line)
except EOFError:
break
return "".join(input_lines)
def run_interpreter(input_str: str, verbose=False):
program = parse_program(f"({input_str})", verbose)
if verbose: print("Parsed program:", program)
env = default_env()
for statement in program:
eval(statement, env)
def main():
sys.tracebacklimit = 0
parser = argparse.ArgumentParser()
parser.add_argument("-debug", dest="verbose", action="store_const", const=True, default=False, help="Debug mode")
args = parser.parse_args()
verbose = args.verbose
input_str = read_input()
if verbose: print("Input string:", input_str)
run_interpreter(input_str, verbose)
if __name__ == "__main__":
main()