eval.py

import random
import ast


def generate_code(scope):
    stmts = []
    for _ in range(5):
        stmts.append(generate_statement(scope))
    stmts.append(random.choice(scope))
    return "\n".join(stmts)

def generate_expression(scope):
    terms = []
    for _ in range(5):
        if len(scope) > 0 and random.uniform(0, 1) < 0.5:
            terms.append(random.choice(scope))
        else:
            terms.append(str(random.randint(1, 10)))
    return "+".join(terms)

def generate_statement(scope):
    if len(scope) > 1 and random.uniform(0, 1) < 0.25:
        lhs = random.choice(scope)
    else:
        lhs = random.choice("abcde")
    rhs = generate_expression(scope)
    scope.append(lhs)            
    return "{} = {}".format(lhs, rhs)


def eval(node, env):
    """
    Tree-walking interpreter
    """
    if isinstance(node, ast.Module):
        for child in node.body:
            ret = eval(child, env)
        return ret
    elif isinstance(node, ast.Expr):
        return eval(node.value, env)
    elif isinstance(node, ast.Assign):
        node: ast.Assign
        name = node.targets[0].id
        env[name] = eval(node.value, env)
    elif isinstance(node, ast.BinOp):
        node: ast.BinOp
        left = eval(node.left, env)
        right = eval(node.right, env)
        return left + right
    elif isinstance(node, ast.Num):
        node: ast.Num
        return node.n
    elif isinstance(node, ast.Name):
        return env[node.id]
    else:
        raise Exception("No handler for node type {}".format(type(node)))

def compile(node, code):
    if isinstance(node, ast.Module):
        for child in node.body:
            compile(child, code)
    elif isinstance(node, ast.Expr):
        compile(node.value, code)
    elif isinstance(node, ast.Assign):
        node: ast.Assign
        name = node.targets[0].id
        compile(node.value, code)
        code.append(("STORE", name))
    elif isinstance(node, ast.BinOp):
        node: ast.BinOp
        compile(node.left, code)
        compile(node.right, code)
        code.append(("ADD",))
    elif isinstance(node, ast.Num):
        code.append(("PUSH", node.n))
    elif isinstance(node, ast.Name):
        code.append(("LOAD", node.id))
    else:
        raise Exception("No handler for node type {}".format(type(node)))    

def execute(code, env, stack):
    for op in code:
        if op[0] == 'PUSH':
            stack.insert(0, op[1])
        elif op[0] == 'ADD':
            a = stack.pop(0)
            b = stack.pop(0)
            stack.insert(0, a + b)
        elif op[0] == 'STORE':
            a = stack.pop(0)
            env[op[1]] = a
        elif op[0] == 'LOAD':
            stack.insert(0, env[op[1]])
    return stack[0]

test.py

from eval import *

for _ in range(25):
    
    scope = []
    source = generate_code(scope)

    env = {}
    result_interp = eval(ast.parse(source), env)

    # print("INTERPRETER:")
    # print("ENV", env)
    # print(result_interp)

    code = []

    compile(ast.parse(source), code)
    # print("\nBYTECODE:")
    # for op in code:
    #     print(op)

    env = {}
    stack = []

    result_exec = execute(code, env, stack)

    # print("ENV", env)
    # print("STACK", stack)
    
    assert result_exec == result_interp

    print(result_exec, " == ", result_interp)