Small lisp implementation in Python
#!/usr/bin/env python3 | |
# Licensed under GPLv3: https://www.gnu.org/licenses/gpl.txt | |
# Commit history available here: https://github.com/clarete/wheelbarrow/blob/master/lispinho/main.py | |
# no dependencies, may also work with python2 | |
from __future__ import print_function | |
from pprint import pprint | |
import enum | |
import readline | |
import sys | |
# Python 2 portability | |
try: input = raw_input | |
except NameError: pass | |
__version__ = '0.0.1' | |
VALID_ATOM_CHARS = ('_', '-', '+', '*', '/', '>', '<') | |
class TokenType(enum.Enum): | |
(OPEN_PAR, | |
CLOSE_PAR, | |
QUOTE, | |
ATOM, | |
INTEGER, | |
FLOAT, | |
STRING, | |
DOT, | |
COLON, | |
END, | |
) = range(10) | |
class Token: | |
def __init__(self, _type, value=None): | |
self._type = _type | |
self.value = value | |
def __repr__(self): | |
return "Token({}, {})".format(self._type, repr(self.value)) | |
def __eq__(self, other): | |
return (isinstance(other, self.__class__) and | |
other._type == self._type and | |
other.value == self.value) | |
class Atom: | |
def __init__(self, name): | |
self.name = name | |
def __repr__(self): | |
return "Atom({})".format(repr(self.name)) | |
def __str__(self): | |
return self.name | |
def __eq__(self, other): | |
return (isinstance(other, self.__class__) and | |
other.name == self.name) | |
class Lambda: | |
def __init__(self, arglist, body): | |
self.arglist = arglist | |
self.body = body | |
def callBody(self, argEnv): | |
if isinstance(self.body, Nil): return nil | |
return car(_flattenCons(self.body, argEnv)) | |
def __call__(self, args, env): | |
assert(len(self.arglist) == len(args)) | |
argEnv = env.copy() | |
# No parameters, let's bail | |
if isinstance(self.arglist, Nil): | |
return self.callBody(argEnv) | |
i, head, tail = 0, car(self.arglist), cdr(self.arglist) | |
flattenArgs = _flattenCons(args, env) | |
while head != nil: | |
assert(isinstance(head, Atom)) | |
argEnv[head.name] = flattenArgs[i] | |
i += 1 | |
if tail == nil: break | |
head, tail = car(tail), cdr(tail) | |
return self.callBody(argEnv) | |
class Nil: | |
def __repr__(self): | |
return 'nil' | |
def __eq__(self, other): | |
return isinstance(other, self.__class__) | |
def __len__(self): | |
return 0 | |
nil = Nil() | |
def tokenize(code): | |
i = 0 | |
c = lambda n=0: (i+n) < len(code) and code[i+n] or None | |
while True: | |
if c() is None: break | |
elif c().isspace(): pass | |
elif c() == '.': yield Token(TokenType.DOT) | |
elif c() == '(': yield Token(TokenType.OPEN_PAR) | |
elif c() == ')': yield Token(TokenType.CLOSE_PAR) | |
elif c() == "'": yield Token(TokenType.QUOTE) | |
elif c().isdigit() or (c() == '-' and c(1) and c(1).isdigit()): | |
d = i | |
if c() == '-': i += 1 | |
_type = TokenType.INTEGER | |
while c() and (c().isdigit() or c() == '.'): | |
if c() == '.': _type = TokenType.FLOAT | |
i += 1 | |
yield Token(_type, (int(code[d:i]) | |
if _type == TokenType.INTEGER | |
else float(code[d:i]))) | |
continue | |
elif c() == '"': | |
i += 1; d = i; | |
while c() and c() != '"': i += 1 | |
yield Token(TokenType.STRING, code[d:i]); i += 1; | |
continue | |
elif c().isalpha() or c() in VALID_ATOM_CHARS: | |
d = i | |
while c() and (c().isalnum() or c() in VALID_ATOM_CHARS): i += 1 | |
yield Token(TokenType.ATOM, code[d:i]) | |
continue | |
elif c() == ';': | |
while c() != '\n': | |
i += 1 | |
else: | |
raise SyntaxError("Unexpected char `{}'".format(c())) | |
i += 1 | |
yield Token(TokenType.END) | |
class Parser: | |
def __init__(self, code): | |
self.code = code | |
self.token = None | |
self.tokens = tokenize(self.code) # Lazy | |
self.nextToken() | |
def nextToken(self): | |
try: self.token = next(self.tokens) | |
except StopIteration: return None | |
def testToken(self, _type): | |
return self.token._type == _type | |
def matchToken(self, _type): | |
if not self.testToken(_type): return False | |
self.nextToken() | |
return True | |
def returnCurrentAndMoveNext(self): | |
# This quietly converts atoms to Atom instances | |
value = (self.testToken(TokenType.ATOM) | |
and Atom(self.token.value) | |
or self.token.value) | |
self.nextToken() | |
return value | |
def parseCons(self): | |
if self.matchToken(TokenType.CLOSE_PAR): return None | |
a = self.parseValue() | |
if a is None: return None | |
if self.matchToken(TokenType.DOT): | |
b = self.parseValue() | |
if b: return [a, b] | |
else: return [a, nil] | |
b = self.parseCons() | |
if b is not None: return [a, b] | |
else: return [a, nil] | |
def parseValue(self): | |
if self.matchToken(TokenType.OPEN_PAR): | |
return self.parseCons() | |
if self.matchToken(TokenType.QUOTE): | |
return [Atom('quote'), [self.parseValue(), nil]] | |
elif self.testToken(TokenType.INTEGER): | |
return self.returnCurrentAndMoveNext() | |
elif self.testToken(TokenType.FLOAT): | |
return self.returnCurrentAndMoveNext() | |
elif self.testToken(TokenType.ATOM): | |
return self.returnCurrentAndMoveNext() | |
elif self.testToken(TokenType.STRING): | |
return self.returnCurrentAndMoveNext() | |
return None | |
def parse(self): | |
return self.parseValue() | |
def parse(tokens): | |
return Parser(tokens).parse() | |
def car(l): return l[0] | |
def cdr(l): return l[1] | |
def _flattenCons(v, env): | |
if isinstance(v, Nil): return [] | |
out = [evalValue(car(v), env)] | |
out.extend(_flattenCons(cdr(v), env)) | |
return out | |
def primSum(args, env): | |
return sum(_flattenCons(args, env)) | |
def primQuote(args, env): | |
return car(args) | |
def primCond(args, env): | |
head, tail = car(args), cdr(args) | |
while head != nil: | |
cond = evalValue(car(head), env) | |
if cond != nil: return evalValue(car(cdr(head)), env) | |
head, tail = car(tail), cdr(tail) | |
return nil | |
def primLabel(args, env): | |
assert(isinstance(car(args), Atom)) | |
value = evalValue(car(cdr(args)), env) | |
env[car(args).name] = value | |
return value | |
def primProgn(args, env): | |
return _flattenCons(args, env)[-1] | |
def primLambda(args, env): | |
if isinstance(args, Nil): return Lambda(nil, nil) | |
return Lambda(car(args), cdr(args)) | |
def primPrint(args, env): | |
printobj(evalValue(car(args), env)) | |
def primEval(args, env): | |
return evaluate(car(args), env) | |
def evalCons(v, env): | |
f = evalValue(car(v), env) | |
assert(callable(f)) | |
return f(cdr(v), env) | |
def lookup(env, name): | |
try: return env[name] | |
except KeyError: pass | |
raise NameError('Atom `{}\' is not defined'.format(name)) | |
def evalValue(v, env): | |
if isinstance(v, (int, float, str)): return v | |
elif isinstance(v, Atom): return lookup(env, v.name) | |
elif isinstance(v, list): return evalCons(v, env) | |
primFuncs = { | |
'nil': nil, | |
'+': primSum, | |
'quote': primQuote, | |
'cond': primCond, | |
'label': primLabel, | |
'progn': primProgn, | |
'lambda': primLambda, | |
'print': primPrint, | |
'eval': primEval, | |
} | |
def evaluate(code, env): | |
parser = Parser(code) | |
lastValue = None | |
while True: | |
expr = parser.parse() | |
if expr is None: break | |
lastValue = evalValue(expr, env) | |
return lastValue | |
def printlist(l, end=' '): | |
head, tail = car(l), cdr(l) | |
print('(', end='') | |
if not isinstance(tail, list): | |
printobj(head, end='' if tail == nil else ' ') | |
print('.', end=' ') | |
return printobj(tail, end=')') | |
while head != nil: | |
printobj(head, end='' if tail == nil else ' ') | |
if tail == nil: break | |
head, tail = car(tail), cdr(tail) | |
print(')', end=end) | |
def printobj(obj, end=''): | |
if isinstance(obj, list): printlist(obj, end) | |
else: print(obj, end=end) | |
def repl(): | |
env = primFuncs | |
env.update({'exit': lambda args, env: exit()}) | |
print('lispinho {}'.format(__version__)) | |
print('Type (exit) and hit enter to go back to the terminal') | |
while True: | |
userInput = input("> ") | |
if not userInput: continue | |
value = evaluate(userInput, env) | |
if value is not None: printobj(value) | |
print() | |
def evalFile(fileName, env=primFuncs): | |
return evaluate(open(fileName).read(), env) | |
def main(args=sys.argv[1:]): | |
if args: return evalFile(args[0]) | |
try: repl() | |
except EOFError: print() | |
def test_tokenizer(): | |
run = lambda c: list(tokenize(c)) | |
assert(run('1') == [Token(TokenType.INTEGER, 1), Token(TokenType.END, None)]) | |
assert(run('-1') == [Token(TokenType.INTEGER, -1), Token(TokenType.END, None)]) | |
assert(run('test') == [Token(TokenType.ATOM, 'test'), Token(TokenType.END, None)]) | |
assert(run('"test"') == [Token(TokenType.STRING, 'test'), Token(TokenType.END, None)]) | |
assert(run('3.141592653589793') == [Token(TokenType.FLOAT, 3.141592653589793), | |
Token(TokenType.END, None)]) | |
assert(run("'test") == [Token(TokenType.QUOTE, None), | |
Token(TokenType.ATOM, 'test'), | |
Token(TokenType.END, None)]) | |
assert(run('()') == [Token(TokenType.OPEN_PAR, None), | |
Token(TokenType.CLOSE_PAR, None), | |
Token(TokenType.END, None)]) | |
assert(run('(a b c)') == [Token(TokenType.OPEN_PAR, None), | |
Token(TokenType.ATOM, 'a'), | |
Token(TokenType.ATOM, 'b'), | |
Token(TokenType.ATOM, 'c'), | |
Token(TokenType.CLOSE_PAR, None), | |
Token(TokenType.END, None)]) | |
assert(run('(first (+ 2 3))') == [Token(TokenType.OPEN_PAR, None), | |
Token(TokenType.ATOM, 'first'), | |
Token(TokenType.OPEN_PAR, None), | |
Token(TokenType.ATOM, '+'), | |
Token(TokenType.INTEGER, 2), | |
Token(TokenType.INTEGER, 3), | |
Token(TokenType.CLOSE_PAR, None), | |
Token(TokenType.CLOSE_PAR, None), | |
Token(TokenType.END, None)]) | |
assert(run('(first (list 1 (+ 2 3) 9))') == [Token(TokenType.OPEN_PAR, None), | |
Token(TokenType.ATOM, 'first'), | |
Token(TokenType.OPEN_PAR, None), | |
Token(TokenType.ATOM, 'list'), | |
Token(TokenType.INTEGER, 1), | |
Token(TokenType.OPEN_PAR, None), | |
Token(TokenType.ATOM, '+'), | |
Token(TokenType.INTEGER, 2), | |
Token(TokenType.INTEGER, 3), | |
Token(TokenType.CLOSE_PAR, None), | |
Token(TokenType.INTEGER, 9), | |
Token(TokenType.CLOSE_PAR, None), | |
Token(TokenType.CLOSE_PAR, None), | |
Token(TokenType.END, None)]) | |
assert(run(' ( a \n\n\n\r\n b ) ') == [Token(TokenType.OPEN_PAR, None), | |
Token(TokenType.ATOM, 'a'), | |
Token(TokenType.ATOM, 'b'), | |
Token(TokenType.CLOSE_PAR, None), | |
Token(TokenType.END, None)]) | |
assert(run('(a . b)') == [Token(TokenType.OPEN_PAR, None), | |
Token(TokenType.ATOM, 'a'), | |
Token(TokenType.DOT, None), | |
Token(TokenType.ATOM, 'b'), | |
Token(TokenType.CLOSE_PAR, None), | |
Token(TokenType.END, None)]) | |
assert(run('; foo\n1') == [Token(TokenType.INTEGER, 1), | |
Token(TokenType.END, None)]) | |
assert(run("(1.2 3.4)") == [Token(TokenType.OPEN_PAR, None), | |
Token(TokenType.FLOAT, 1.2), | |
Token(TokenType.FLOAT, 3.4), | |
Token(TokenType.CLOSE_PAR, None), | |
Token(TokenType.END, None)]) | |
# pprint(run('(print 0)')) | |
assert(run('(print 0)') == [Token(TokenType.OPEN_PAR, None), | |
Token(TokenType.ATOM, 'print'), | |
Token(TokenType.INTEGER, 0), | |
Token(TokenType.CLOSE_PAR, None), | |
Token(TokenType.END, None)]) | |
def test_parser(): | |
run = lambda c: parse(c) | |
# pprint(run('1')) | |
assert(run('1') == 1) | |
# pprint(run('3.141592653589793')) | |
assert(run('3.141592653589793') == 3.141592653589793) | |
# pprint(run('"test"')) | |
assert(run('"test"') == 'test') | |
# pprint(run('atom')) | |
assert(run('atom') == Atom('atom')) | |
# pprint(run('(a)')) | |
assert(run('(a)') == [Atom('a'), nil]) | |
# pprint(run('(+ 2 (* 3 5))')) | |
assert(run('(+ 2 (* 3 5))') == [Atom('+'), [2, [[Atom('*'), [3, [5, nil]]], nil]]]) | |
# pprint(run('(+ 2 (* 3 5) (* -1))')) | |
assert(run('(+ 2 (* 3 5) (* -1))') == [Atom('+'), [2, [[Atom('*'), [3, [5, nil]]], | |
[[Atom('*'), [-1, nil]], nil]]]]) | |
# pprint(run('(first (list 1 (+ 2 3) 9))')) | |
assert(run('(first (list 1 (+ 2 3) 9))') == [Atom('first'), [[Atom('list'), | |
[1, [[Atom('+'), [2, [3, nil]]], | |
[9, nil]]]], nil]]) | |
# pprint(run("'test")) | |
assert(run("'test") == [Atom('quote'), [Atom('test'), nil]]) | |
# pprint(run('(1.2 3.4)')) | |
assert(run('(1.2 3.4)') == [1.2, [3.4, nil]]) | |
# pprint(run('(print 0)')) | |
assert(run('(print 0)') == [Atom('print'), [0, nil]]) | |
def test_evaluator(): | |
run = lambda c: evaluate(c, primFuncs) | |
# pprint(run('1')) | |
assert(run('1') == 1) | |
# pprint(run('"test"')) | |
assert(run('"test"') == 'test') | |
# TODO: Error handling | |
# pprint(run('atom')) | |
# assert(run('atom') == Atom('atom')) | |
# pprint(run('(+ 3 2)')) | |
assert(run('(+ 3 2)') == 5) | |
# pprint(run('(quote a)')) | |
assert(run('(quote a)') == Atom('a')) | |
# pprint(run("'a")) | |
assert(run("'an-atom") == Atom('an-atom')) | |
# pprint(run('(cond (nil 1) (nil 2) (1 3))')) | |
assert(run('(cond (nil 1) (nil 2) (1 3))') == 3) | |
# pprint(run('(label foo 1)')) | |
assert(run('(label foo 1)') == 1) | |
# pprint(run('(progn (label foo (lambda (x) (+ x 1)))' | |
# ' (foo 2))')) | |
assert(run('(progn (label foo (lambda (x) (+ x 1)))' | |
' (foo 2))') == 3) | |
# pprint(run('(progn (label foo (lambda (x y) (+ x y)))' | |
# ' (foo 2 3))')) | |
assert(run('(progn (label foo (lambda (x y) (+ x y)))' | |
' (foo 2 3))') == 5) | |
# pprint(run("(+ 1.2 3.4)")) | |
assert(run("(+ 1.2 3.4)") == 4.6) | |
# pprint(run("((lambda (x) (+ x 1)) 2)")) | |
assert(run("((lambda (x) (+ x 1)) 2)") == 3) | |
# pprint(run("((lambda ()))")) | |
assert(run("((lambda ()))") == nil) | |
def test(): | |
test_tokenizer() | |
test_parser() | |
test_evaluator() | |
if __name__ == '__main__': | |
test() | |
main() |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment