Daily practice: trivial eval

README.md

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.

eval2.py

#!/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()

output.txt

$ ./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