Modify A LISP Interpreter Written in Python
factorial.expected
GLOBAL -------------------- fact : Procedure -------------------- n : 4 -------------------- GLOBAL -------------------- fact : Procedure -------------------- n : 3 -------------------- GLOBAL -------------------- fact : Procedure -------------------- n : 2 -------------------- GLOBAL -------------------- fact : Procedure -------------------- n : 1 -------------------- GLOBAL -------------------- fact : Procedure -------------------- n : 0 -------------------- 24 GLOBAL -------------------- fact : Procedure x : 0 sub1 : Procedure sub3 : Procedure -------------------- x : 2 -------------------- GLOBAL -------------------- fact : Procedure x : 0 sub1 : Procedure sub3 : Procedure -------------------- x : 2 -------------------- -------------------- GLOBAL -------------------- fact : Procedure x : 0 sub1 : Procedure sub3 : Procedure -------------------- -------------------- 0
factorial.lisp
; This is a comment - your code should ignore these ; A recursive program (define fact (lambda (n) ; Computes n! (if (< n 1) ; then 1 ; else (* n (fact (- n 1))) ); end if ); end lambda ); end fact (fact 4) ; Problem 5.6 converted to scheme (define x 0) (define sub1 (lambda (x) ( ; this open paren is to _call_ sub2 (lambda () ; this lambda function is sub2 (sub3) ; this calls sub3 ) ; this ends sub2 ) ; this close paren ends the _call_ to sub2 ) ;end the lambda for sub1 ) ; end the define for sub1 (define sub3 (lambda () x)) ; returns x, whatever that is (sub1 2)
lisp.py
import sys import math import operator as op import re class Env(dict): def __init__(self, params=(), args=(), outer=None): self.update(dict(zip(params, args))) self.outer = outer # TODO: If outer is not None, then print the outer environment and then this one. # It outer is None, then print GLOBAL # Look at factorial.expected def find(self, var): return self if (var in self) else self.outer.find(var) global_env = Env() global_env.update({k:v for k, v in vars(math).items() if not k.startswith('_')}) global_env['+'] = op.add global_env['-'] = op.sub global_env['/'] = op.truediv global_env['*'] = op.mul global_env['<'] = op.lt global_env['>'] = op.gt global_env['>='] = op.ge global_env['<='] = op.le global_env['='] = op.eq global_env['display'] = print def tokenize(source): # Will not work for comments in strings, but that is ok source = re.sub(r';.*$', ' ', source, flags=re.MULTILINE) return source.replace('(', ' ( ').replace(')', ' ) ').split() def parse_expr(tokens): if len(tokens) == 0: raise SyntaxError("EOF") token = tokens.pop(0) if token == '(': thelist = [] while tokens[0] != ')': subexpr = parse_expr(tokens) thelist.append(subexpr) tokens.pop(0) return thelist else: try: return int(token) except ValueError: try: return float(token) except ValueError: return token class Procedure(object): def __init__(self, parms, body, env): self.parms= parms self.body= body self.env = env def __call__(self, *args): local_env = Env(self.parms, args, self.env) return eval_expr(self.body, local_env) def eval_expr(exp, env=global_env): if isinstance(exp, str): env = env.find(exp) return env[exp] elif not isinstance(exp, list): return exp op, *args = exp # Special symbols (quote, if, define, lambda) if op == 'quote': # (quote (1 2 3)) ==> (1 2 3) return args[0] elif op == 'if': # conditional (if test conseq alt) => only eval the correct branch test, conseq, alt = args exp = conseq if eval_expr(test, env) else alt return eval_expr(exp, env) elif op == 'define': # definition symbol, exp = args env[symbol] = eval_expr(exp, env) return None elif op == 'lambda': # procedure parms, body = args return Procedure(parms, body, env) else: proc = eval_expr(op, env) eargs = [eval_expr(arg, env) for arg in args] return proc(*eargs) if __name__ == '__main__': filename = sys.argv[1] source = open(filename).read() tokens = tokenize(source) while len(tokens) > 0: expr= parse_expr(tokens) print(">>>", expr) print(eval_expr(expr, global_env))
demo_lisp.py
import sys import math import operator as op import re class Env(dict): def __init__(self, params=(), args=(), outer=None, printme=True): self.outer = outer self.update(dict(zip(params, args))) # Print the env if printme: self.print() def print(self): #TODO # # # # # # # pass def find(self, name): if name in self: return self else: return self.outer.find(name) class Procedure: def __init__(self, params, body, env): self.params = params self.body = body self.env = env def __call__(self, *args): local_env = Env(self.params, args, outer=self.env) return eval_expr(self.body,local_env) def __repr__(self): return "Procedure" builtin_env = Env(printme=False) builtin_env.update({k:v for k, v in vars(math).items() if not k.startswith('_')}) builtin_env['+'] = op.add builtin_env['-'] = op.sub builtin_env['/'] = op.truediv builtin_env['*'] = op.mul builtin_env['<'] = op.lt builtin_env['>'] = op.gt builtin_env['>='] = op.ge builtin_env['<='] = op.le builtin_env['='] = op.eq builtin_env['display'] = print builtin_env['version'] = '0.0.0' global_env = Env(outer=builtin_env, printme=False) def tokenize(source): # https://regex101.com/ source = re.sub(';.*$', ' ', source, flags=re.MULTILINE) return source.replace('(', ' ( ').replace(')', ' ) ').split() def parse_expr(tokens): if len(tokens) == 0: raise SyntaxError("EOF") token = tokens.pop(0) if token == '(': thelist = [] while tokens[0] != ')': subexpr = parse_expr(tokens) thelist.append(subexpr) tokens.pop(0) return thelist else: try: return int(token) except ValueError: try: return float(token) except ValueError: return token def eval_expr(expression, env=global_env): if isinstance(expression, str): name = expression declaring_scope = env.find(name) return declaring_scope[name] elif not isinstance(expression, list): return expression # Expression is alist op, *args = expression if op == 'define': name, value = args global_env[name] = eval_expr(value, env) return None elif op == 'if': test, thenpart, elsepart = args evaluated_test = eval_expr(test, env) return eval_expr(thenpart, env) if evaluated_test else eval_expr(elsepart, env) elif op == 'quote': # (quote hello) ==> hello return args[0] elif op == 'lambda': params, body = args return Procedure(params, body, env) else: proc = eval_expr(op, env) evaluated_args = [eval_expr(arg, env) for arg in args] result = proc(*evaluated_args) return result if __name__ == '__main__': source = open(sys.argv[1]).read() tokens = tokenize(source) while len(tokens) > 0: expr= parse_expr(tokens) print(">>>", expr) result = eval_expr(expr, global_env) if result is not None: print(result)