Skip to content

Instantly share code, notes, and snippets.

@cellularmitosis
Last active October 15, 2019 07:31
Show Gist options
  • Save cellularmitosis/074730ddde770f4ac694825ca3fbfaec to your computer and use it in GitHub Desktop.
Save cellularmitosis/074730ddde770f4ac694825ca3fbfaec to your computer and use it in GitHub Desktop.
Daily practice: trivial eval

Blog 2019/8/28

<- previous | index | next ->

Daily practice: trivial eval

Here's a trivial eval implementation which only knows how to do addition.

Note that the input is already in the form of an AST, as there isn't a lexer / parser (reader) implemented.

#!/usr/bin/env python
# today's coding practice: a trivial lisp-like interprer which only knows how to evaluate addition.
def first(l): # a.k.a. car
return l[0]
def rest(l): # a.k.a. cdr
return l[1:]
def is_atom(expr):
return not isinstance(expr, list)
def is_list(expr):
return isinstance(expr, list)
def is_symbol(expr):
return is_atom(expr) and expr["tag"] == "symbol"
def is_number(expr):
return is_atom(expr) and expr["tag"] == "number"
def is_string(expr):
return is_atom(expr) and expr["tag"] == "string"
def is_literal(expr):
return is_number(expr) or is_string(expr)
def lookup(expr, env):
return env[expr]
def add(a, b):
return a + b
def log(msg, indent=0):
print (" " * indent) + msg
def eval2(expr, env, indent=0):
log("eval2 %s" % expr, indent)
if is_literal(expr):
log("eval2: found literal", indent)
result = expr["content"]
elif is_symbol(expr):
log("eval2: found symbol", indent)
result = lookup(expr["content"], env)
elif is_list(expr):
log("eval2: found list", indent)
operator = eval2(first(expr), env, indent+1)
operands = [eval2(e, env, indent+1) for e in rest(expr)]
result = operator(*operands)
else:
raise Exception("Don't know how to evaluate '%s'" % expr)
log("eval2: returning %s" % result), indent
return result
def test0():
print "\ntest0:"
env = {}
# ast: 42
ast = {
"tag": "number",
"content": "42"
}
print eval2(ast, env)
def test1():
print "\ntest1:"
env = {
"+": add
}
# ast: [+ 1 2]
ast = [
{
"tag": "symbol",
"content": "+"
},
{
"tag": "number",
"content": 1
},
{
"tag": "number",
"content": 2
}
]
print eval2(ast, env)
def test2():
print "\ntest2:"
env = {
"+": add
}
# ast: [+ 1 [+ 2 3]]
ast = [
{
"tag": "symbol",
"content": "+"
},
{
"tag": "number",
"content": 1
},
[
{
"tag": "symbol",
"content": "+"
},
{
"tag": "number",
"content": 2
},
{
"tag": "number",
"content": 3
}
]
]
print eval2(ast, env)
if __name__ == "__main__":
test2()
test1()
test2()
$ ./eval2.py
test0:
eval2 {'content': '42', 'tag': 'number'}
eval2: found literal
eval2: returning 42
42
test1:
eval2 [{'content': '+', 'tag': 'symbol'}, {'content': 1, 'tag': 'number'}, {'content': 2, 'tag': 'number'}]
eval2: found list
eval2 {'content': '+', 'tag': 'symbol'}
eval2: found symbol
eval2: returning <function add at 0x1099508c0>
eval2 {'content': 1, 'tag': 'number'}
eval2: found literal
eval2: returning 1
eval2 {'content': 2, 'tag': 'number'}
eval2: found literal
eval2: returning 2
eval2: returning 3
3
test2:
eval2 [{'content': '+', 'tag': 'symbol'}, {'content': 1, 'tag': 'number'}, [{'content': '+', 'tag': 'symbol'}, {'content': 2, 'tag': 'number'}, {'content': 3, 'tag': 'number'}]]
eval2: found list
eval2 {'content': '+', 'tag': 'symbol'}
eval2: found symbol
eval2: returning <function add at 0x1099508c0>
eval2 {'content': 1, 'tag': 'number'}
eval2: found literal
eval2: returning 1
eval2 [{'content': '+', 'tag': 'symbol'}, {'content': 2, 'tag': 'number'}, {'content': 3, 'tag': 'number'}]
eval2: found list
eval2 {'content': '+', 'tag': 'symbol'}
eval2: found symbol
eval2: returning <function add at 0x1099508c0>
eval2 {'content': 2, 'tag': 'number'}
eval2: found literal
eval2: returning 2
eval2 {'content': 3, 'tag': 'number'}
eval2: found literal
eval2: returning 3
eval2: returning 5
eval2: returning 6
6
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment