Lispy: Scheme Interpreter in Python (c) Peter Norvig, 2010-16; See http://norvig.com/lispy.html Launch the script and then type some basic Lisp code. Example:
(define fact (lambda (n) (if (<= n 1) 1 (* n (fact (- n 1))))))
(fact 10)
Should print 362880
Requires my “operator.py” script.
################ Lispy: Scheme Interpreter in Python ## (c) Peter Norvig, 2010-16; See http://norvig.com/lispy.html import math import operator as op ################ Types Symbol = str # A Lisp Symbol is implemented as a Python str List = list # A Lisp List is implemented as a Python list Number = (int, float) # A Lisp Number is implemented as a Python int or float ################ Parsing: parse, tokenize, and read_from_tokens def parse(program): "Read a Scheme expression from a string." return read_from_tokens(tokenize(program)) def tokenize(s): "Convert a string into a list of tokens." return s.replace('(',' ( ').replace(')',' ) ').split() def read_from_tokens(tokens): "Read an expression from a sequence of tokens." if len(tokens) == 0: raise SyntaxError('unexpected EOF while reading') token = tokens.pop(0) if '(' == token: L = [] while tokens[0] != ')': L.append(read_from_tokens(tokens)) tokens.pop(0) # pop off ')' return L elif ')' == token: raise SyntaxError('unexpected )') else: return atom(token) def atom(token): "Numbers become numbers; every other token is a symbol." try: return int(token) except ValueError: try: return float(token) except ValueError: return Symbol(token) ################ Environments def apply(object, *args, **kwargs): return object(*args, **kwargs) def standard_env(): "An environment with some Scheme standard procedures." env = Env() # env.update(vars(math)) # sin, cos, sqrt, pi, ... env.update({ 'acos': math.acos, 'acosh': math.acosh, 'asin': math.asin, 'asinh': math.asinh, 'atan': math.atan, 'atan2': math.atan2, 'atanh': math.atanh, 'ceil': math.ceil, 'copysign': math.copysign, 'cos': math.cos, 'cosh': math.cosh, 'degrees': math.degrees, 'erf': math.erf, 'erfc': math.erfc, 'exp': math.exp, 'expm1': math.expm1, 'fabs': math.fabs, 'floor': math.floor, 'fmod': math.fmod, 'frexp': math.frexp, 'gamma': math.gamma, 'isfinite': math.isfinite, 'isinf': math.isinf, 'isnan': math.isnan, 'ldexp': math.ldexp, 'lgamma': math.lgamma, 'log': math.log, 'log': math.log, 'log10': math.log10, 'log2': math.log2, 'modf': math.modf, 'pow': math.pow, 'radians': math.radians, 'sin': math.sin, 'sinh': math.sinh, 'sqrt': math.sqrt, 'tan': math.tan, 'tanh': math.tanh, 'trunc': math.trunc, 'e': math.e, 'pi': math.pi, }) env.update({ '+':op.add, '-':op.sub, '*':op.mul, '/':op.truediv, '>':op.gt, '<':op.lt, '>=':op.ge, '<=':op.le, '=':op.eq, 'abs': abs, 'append': op.add, 'apply': apply, '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, 'length': len, 'list': lambda *x: list(x), 'list?': lambda x: isinstance(x,list), 'map': map, 'max': max, 'min': min, 'not': op.not_, 'null?': lambda x: x == [], 'number?': lambda x: isinstance(x, Number), 'procedure?': callable, 'round': round, 'symbol?': lambda x: isinstance(x, Symbol), }) return env class Env(dict): "An environment: a dict of {'var':val} pairs, with an outer Env." def __init__(self, parms=(), args=(), outer=None): # self.update(zip(parms, args)) len_parms = len(parms) len_args = len(args) assert len_parms == len_args for i in range(len_parms): self.__setitem__(parms[i], args[i]) # self.outer = outer def find(self, var): "Find the innermost Env where var appears." return self if (var in self) else self.outer.find(var) global_env = standard_env() ################ Interaction: A REPL def repl(prompt='lisp> ', start_with_fact_example=True): "A prompt-read-eval-print loop." if start_with_fact_example: eval(parse("(define fact (lambda (n) (if (<= n 1) 1 (* n (fact (- n 1))))))")) # eval(parse("(fact 10)")) while True: try: val = eval(parse(input(prompt))) except: print("Done with the tinylisp.py REPL") if val is not None: print(lispstr(val)) def lispstr(exp): "Convert a Python object back into a Lisp-readable string." if isinstance(exp, List): return '(' + ' '.join(map(lispstr, exp)) + ')' else: return str(exp) ################ Procedures class Procedure(object): "A user-defined Scheme procedure." def __init__(self, parms, body, env): self.parms, self.body, self.env = parms, body, env def __call__(self, *args): return eval(self.body, Env(self.parms, args, self.env)) ################ eval def eval(x, env=global_env): "Evaluate an expression in an environment." if isinstance(x, Symbol): # variable reference return env.find(x)[x] elif not isinstance(x, List): # constant literal return x elif x[0] == 'quote': # (quote exp) (_, exp) = x return exp elif x[0] == 'if': # (if test conseq alt) (_, test, conseq, alt) = x exp = (conseq if eval(test, env) else alt) return eval(exp, env) elif x[0] == 'define': # (define var exp) (_, var, exp) = x env[var] = eval(exp, env) elif x[0] == 'set!': # (set! var exp) (_, var, exp) = x env.find(var)[var] = eval(exp, env) elif x[0] == 'lambda': # (lambda (var...) body) (_, parms, body) = x return Procedure(parms, body, env) else: # (proc arg...) proc = eval(x[0], env) args = [eval(exp, env) for exp in x[1:]] return proc(*args) def show_example(): print(""" You can use the following as an example, to check if Lis.py works: (define fact (lambda (n) (if (<= n 1) 1 (* n (fact (- n 1)))))) (fact 10) Should print 3628800 """) show_example() repl()