interpreter.lua

ARGINDEX_DEST = 2

Label = {}
Closure = {}
Parameter = {}

none = setmetatable({}, {
    __tostring = function () return "none" end
})

function evaluate(env, index, argument)
    if getmetatable(argument) == Parameter then
        -- We need to resolve a parameter to the value its bound to
        -- by walking up the environment tree.
        while env do
            if argument.label == env.label then
                return env.args[argument.index]
            end
            env = env.parent
        end
        error("unbound parameter encountered")
    elseif getmetatable(argument) == Label then
        -- Labels are captured in closures when passed as arguments
        if (index == ARGINDEX_DEST) then
            -- We're jumping to this label next, so no capturing neccessary
            return argument
        else
            return new_closure(env, argument)
        end
    else
        -- everything else is considered to be a constant
        return argument
    end
end

function apply_label(env, return_arg, label, ...)
    -- 1. Create a new child environment that maps a label to its arguments,
    -- providing us with a way to evaluate parameters to their value later on.
    env = { parent = env, label = label, args = { return_arg, ... } }

    -- 2. Using this new environment, build a new array of arguments from the
    -- body of the label, by resolving all parameters to the value they're
    -- bound to in the environment.
    local args = {}
    for i, argument in ipairs(label.body) do
        args[i] = evaluate(env, i, argument)
    end

    -- 3. Finally, execute the next instruction
    return apply(env, unpack(args))
end

function apply(env, return_arg, dest, ...)
    -- dispatch based on the type of dest
    if type(dest) == "function" then

        -- dest is a built-in function, just forward the call
        return dest(env, return_arg, dest, ...)

    elseif getmetatable(dest) == Label then

        -- dest is a label, we need to perform an evaluation
        return apply_label(env, return_arg, dest, ...)

    elseif getmetatable(dest) == Closure then

        -- dest is a closure, we forward with the new environment
        return apply(dest.env, return_arg, dest.label, ...)
    else
        error("illegal destination: " .. tostring(dest))
    end
end

function builtin_exit(env, return_arg, func)
    os.exit(0)
end

function builtin_print(env, return_arg, func, ...)
    print(...)
    return apply(env, none, return_arg)
end

function builtin_mul(env, return_arg, func, a, b)
    -- do the computation
    local result = a * b

    -- call return_arg with the result, and no return argument
    return apply(env, none, return_arg, result)
end

function new_closure(env, label)
    return setmetatable({env=env,label=label}, Closure)
end

function new_label(...)
    local self = setmetatable({}, Label)
    for i=1,select('#', ...) do
        local argname = select(i, ...)
        if argname ~= nil then
            local param = setmetatable({label=self,index=i}, Parameter)
            self[argname] = param
        end
    end
    return self
end

-- our program

-- define labels first
main = new_label()
pow3 = new_label("ret", "x")
pow3_2 = new_label(nil, "x")
print_result = new_label(nil, "x")

-- define label bodies
main.body = { print_result, pow3, 5 }
pow3.body = { pow3_2, builtin_mul, pow3.x, pow3.x }
pow3_2.body = { pow3.ret, builtin_mul, pow3.x, pow3_2.x }
print_result.body = { builtin_exit, builtin_print, print_result.x }

return apply(nil, none, main)