Skip to content

Instantly share code, notes, and snippets.

Last active April 20, 2022 20:42
What would you like to do?
Reference implementation of the original tinylisp language
#!/usr/bin/env python3
whitespace = " \t\n\r"
symbols = "()"
# Shortcut function for print without newline
write = lambda x: print(x, end="")
def scan(code):
i = 0
code += " "
while i < len(code):
char = code[i]
if char in whitespace:
elif char in symbols:
yield char
a = i
while code[i+1] not in whitespace + symbols:
i += 1
yield code[a:i+1]
i += 1
def parse(code):
tree = []
if type(code) is str:
code = scan(code)
for token in code:
if token == "(":
elif token == ")":
return tree
elif token.isdigit():
return tree
# Note: disp and load are in the reference implementation for convenience;
# submissions do not need to implement them as tinylisp builtins
builtins = {"tl_cons": "c",
"tl_car": "h",
"tl_cdr": "t",
"tl_subt2": "s",
"tl_less2": "l",
"tl_eq2": "e",
"tl_eval": "v",
"tl_disp": "disp",
# The following four are macros:
"tl_def": "d",
"tl_if": "i",
"tl_quote": "q",
"tl_load": "load"}
# Decorators for member functions that implement builtins
def macro(pyFn):
pyFn.isMacro = True
return pyFn
def function(pyFn):
pyFn.isMacro = False
return pyFn
class Program:
def __init__(self):
self.names = [{}]
self.depth = 0
for name in dir(self):
# Go through the member functions and put the ones that implement
# tinylisp functions or macros into the top-level symbol table
# under their abbreviated names
if name in builtins:
tlName = builtins[name]
self.names[0][tlName] = getattr(self, name)
def call(self, function, args, fname):
if type(function) is not list or not 2 <= len(function) <= 3:
print("Error: object is not callable", function)
return []
elif len(function) == 2:
# Regular function: evaluate all the arguments
macro = False
argnames, code = function
args = [self.tl_eval(arg) for arg in args]
elif len(function) == 3:
# Skip first element of macro list, and don't evaluate
# the arguments
macro = True
argnames, code = function[1:]
self.depth += 1
while True:
if type(argnames) is list:
if len(argnames) == len(args):
for name, val in zip(argnames, args):
self.names[self.depth][name] = val
print("Error: wrong number of arguments")
result = []
# Single name, bind entire arglist to it
self.names[self.depth][argnames] = args
# Tail-call elimination
returnExpr = code
while type(returnExpr) is list and returnExpr[:1] == ["i"]:
test = self.tl_eval(returnExpr[1])
if test == 0 or test == []:
returnExpr = returnExpr[3]
returnExpr = returnExpr[2]
if (type(returnExpr) in (str, int, type(self.tl_eval))
or returnExpr == []):
result = self.tl_eval(returnExpr)
head = self.tl_eval(returnExpr[0])
if type(head) is list and 2 <= len(head) <= 3:
# Swap out the args from the original call for the updated
# args, the function for the new function (which might be
# the same function), and loop for the recursive call
if len(head) == 2:
macro = False
argnames, code = head
args = [self.tl_eval(arg) for arg in returnExpr[1:]]
elif len(function) == 3:
macro = True
argnames, code = head[1:]
args = returnExpr[1:]
self.names[self.depth] = {}
result = self.tl_eval(returnExpr)
del self.names[self.depth]
self.depth -= 1
return result
def tl_car(self, lyst):
if len(lyst) == 0:
return []
return lyst[0]
def tl_cdr(self, lyst):
if len(lyst) == 0:
return []
return lyst[1:]
def tl_cons(self, head, tail):
if type(tail) is not list:
print("Error: cannot cons to non-list in tinylisp")
return []
return [head] + tail
def tl_def(self, name, value):
if name in self.names[0]:
print("Error: name already in use")
self.names[0][name] = self.tl_eval(value)
return name
def tl_disp(self, value, end="\n"):
if value == []:
elif type(value) is list:
self.tl_disp(value[0], end="")
for item in value[1:]:
write(" ")
self.tl_disp(item, end="")
elif type(value) is type(self.tl_disp):
write("<built-in function>")
return []
def tl_eq2(self, arg1, arg2):
return +(arg1 == arg2)
def tl_eval(self, code, depth=None):
if depth is None:
depth = self.depth
if type(code) is list:
if code == []:
return []
if type(code[0]) is str:
fname = code[0]
fname = None
function = self.tl_eval(code[0])
if type(function) is list:
# User-defined function or macro
return, code[1:], fname)
elif type(function) is type(self.tl_eval):
# Builtin function or macro
if function.isMacro:
args = code[1:]
args = (self.tl_eval(param) for param in code[1:])
return function(*args)
# ?!
print("Error: %s is not a function or macro" % function)
return []
elif type(code) is int or code.isdigit():
# Integer literal
return int(code)
# Atom = name, look up its value
if code in self.names[depth]:
return self.names[depth][code]
elif code in self.names[0]:
return self.names[0][code]
print("Error: referencing undefined name", code)
return []
def tl_if(self, cond, trueval, falseval):
# A macro, so arguments are not pre-evaluated
cond = self.tl_eval(cond)
if cond == 0 or cond == []:
return self.tl_eval(falseval)
return self.tl_eval(trueval)
def tl_less2(self, arg1, arg2):
return +(arg1 < arg2)
def tl_subt2(self, arg1, arg2):
return arg1 - arg2
def tl_quote(self, quoted):
return quoted
def tl_load(self, filename):
if not filename.endswith(".tl"):
filename += ".tl"
with open(filename) as f:
libraryCode =
except IOError:
print("Error: could not load", filename)
run(libraryCode, self)
return None
def run(code, env=None):
if type(code) is str:
code = parse(code)
if env is None:
env = Program()
for expr in code:
result = env.tl_eval(expr)
if result is not None:
def repl():
print("(welcome to tinylisp)")
environment = Program()
instruction = input("tl> ")
while instruction != "(quit)":
if instruction == "(restart)":
environment = Program()
run(instruction, environment)
instruction = input("tl> ")
if __name__ == "__main__":
import sys
if len(sys.argv) > 1:
# User specified a filename--run it
filename = sys.argv[1]
run("(load %s)" % filename)
# No filename specified, so...
Copy link

ePaul commented Sep 1, 2021

Hi, I found a bug in this reference implementation:

The two expressions

(e (q 1) 1)
(e 1 1)

are supposed to both do the same thing (compare 1 with 1, and return 1), but currently the reference implementation is returning 0 in the first example.

The reason for this is that the scanner leaves 1 as a string (aka symbol), and only at its first evaluation it is converted into an integer. In the (q 1) example, it is never evaluated. The e builtin then compares a string with an integer, which returns false (0).

Revision 7 of my fork fixes this.

(I've also added some more commits with other improvements, feel free to take them too.)

Copy link

Thanks for bringing this up @ePaul . Turns out I had noticed and fixed this bug in the tinylisp interpreter here (by changing the parser rather than the scanner), so I used that version.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment