simple.py

primitives = {
    "+" : sum
}

def step(program):

    # For convenience, not necessity
    program[0][1] = dict(program[0][1])

    def get(path):
        current = program
        for element in path:
            current = current[element]
        return current

    def set(path, value):
        get(path[:-1])[path[-1]] = value

    def env(name):
        return program[0][1][name]

    if len(program[0][0]) == 0:
        print("END")
        return

    # Need to remember last path?
    # When going upwards, have to apply primitive functions
    path = program[0][0].pop()
    current = get(path)

    print("current", current)
    if isinstance(current, int):
        pass
    elif isinstance(current, str):
        set(path, env(current))
    elif isinstance(current, list) and len(current)>0 and isinstance(current[0], str):
        if current[0] in primitives:
            # Primitives evaluate without evaluating arguments
            # This prevents the control paths from carrying extra fields that specify application
            # Actually, that's problematic because ["+", 1, ["test", 1, 2], 3] would fail brutally
            # wait, wait, wait. if all are defined as "test", can it ever happen?
            set(path, primitives[current[0]](current[1:]))
        else:
            # Some expression. Have to evaluate until only primitive operations are left
            program[0][0].append(path)
            for index in range(len(current)-1, -1, -1):
                program[0][0].append(path+[index])

    program[0][1] = list(program[0][1].items())
    print(program)
    return program


program = [[[[1]], [["test", "+"]]], ["+", 1, ["test", 1, 2], 3]]
print(program)
for i in range(20):
    program = step(program)
    if program is None:
        break