minivm.lua

local function do_compile(expr, output, i)
	if expr.type == "constant" then
		output[i] = {type = "constant", value = expr.value}
		return i + 1
	elseif expr.type == "builtin_function" then
		for _, arg in ipairs(expr.args) do
			i = do_compile(arg, output, i)
		end
		output[i] = {type = "builtin_function", func = expr.func, arity = #expr.args, no_ret = expr.no_ret}
		return i + 1
	elseif expr.type == "function" then
		for _, arg in ipairs(expr.args) do
			i = do_compile(arg, output, i)
		end
		output[i] = {type = "function", func = expr.func}
		return i + 1
	elseif expr.type == "localvar_get" then
		output[i] = {type = "localvar_get", varname = expr.varname}
		return i + 1
	elseif expr.type == "globalvar_get" then
		output[i] = {type = "globalvar_get", varname = expr.varname}
		return i + 1
	elseif expr.type == "localvar_set" then
		i = do_compile(expr.value, output, i)
		output[i] = {type = "localvar_set", varname = expr.varname}
		return i + 1
	elseif expr.type == "globalvar_set" then
		i = do_compile(expr.value, output, i)
		output[i] = {type = "globalvar_set", varname = expr.varname}
	elseif expr.type == "if" then
		i = do_compile(expr.condition, output, i)
		local j = do_compile(expr.then_branch, output, i + 1)
		output[i] = {type = "jump_if_false", destination = j + 1}
		local k = do_compile(expr.else_branch, output, j + 1)
		output[j] = {type = "jump", destination = k}
		return k
	elseif expr.type == "while" then
		local j = do_compile(expr.condition, output, i)
		local k = do_compile(expr.loop_body, output, j + 1)
		output[j] = {type = "jump_if_false", destination = k + 1}
		output[k] = {type = "jump", destination = i}
		return k + 1
	elseif expr.type == "return" then
		i = do_compile(expr.value, output, i)
		output[i] = {type = "return"}
		return i + 1
	elseif expr.type == "seq" then
		for _, code in ipairs(expr.instrs) do
			i = do_compile(code, output, i)
		end
		return i
	end
end

local function compile_expr(expr)
	local output = {}
	do_compile(expr, output, 1)
	return output
end

local function compile_all(functions)
	local compiled = {}
	for fct_name, fct in pairs(functions) do
		compiled[fct_name] = {code = compile_expr(fct.code), args = fct.args}
	end
	return compiled
end

-------------------------------------------

local function run_step(compiled, state)
	local instr = compiled[state.current_function].code[state.pc]
	state.pc = state.pc + 1
	if not instr then
		return false
	end
	if instr.type == "constant" then
		state.stack_index = state.stack_index + 1
		state.stack[state.stack_index] = instr.value
	elseif instr.type == "builtin_function" then
		state.stack_index = state.stack_index - instr.arity
		local args = {}
		for i = 1, instr.arity do
			args[i] = state.stack[state.stack_index + i]
			state.stack[state.stack_index + i] = nil
		end
		local result = instr.func(unpack(args))
		if not instr.no_ret then
			state.stack_index = state.stack_index + 1
			state.stack[state.stack_index] = result
		end
	elseif instr.type == "function" then
		local arity = #compiled[instr.func].args
		state.stack_index = state.stack_index - arity
		local args = {}
		for i = 1, arity do
			args[compiled[instr.func].args[i]] = state.stack[state.stack_index + i]
			state.stack[state.stack_index + i] = nil
		end
		state.call_stack_index = state.call_stack_index + 1
		state.call_stack[state.call_stack_index] =
			{func = state.current_function, pc = state.pc, localvars = state.localvars}
		state.current_function = instr.func
		state.pc = 1
		state.localvars = args
	elseif instr.type == "localvar_get" then
		state.stack_index = state.stack_index + 1
		state.stack[state.stack_index] = state.localvars[instr.varname]
	elseif instr.type == "globalvar_get" then
		state.stack_index = state.stack_index + 1
		state.stack[state.stack_index] = state.globalvars[instr.varname]
	elseif instr.type == "localvar_set" then
		local v = state.stack[state.stack_index]
		state.stack[state.stack_index] = nil
		state.stack_index = state.stack_index - 1
		state.localvars[instr.varname] = v
	elseif instr.type == "globalvar_set" then
		local v = state.stack[state.stack_index]
		state.stack[state.stack_index] = nil
		state.stack_index = state.stack_index - 1
		state.globalvars[instr.varname] = v
	elseif instr.type == "jump" then
		state.pc = instr.destination
	elseif instr.type == "jump_if_false" then
		local v = state.stack[state.stack_index]
		state.stack[state.stack_index] = nil
		state.stack_index = state.stack_index - 1
		if not v then
			state.pc = instr.destination
		end
	elseif instr.type == "return" then
		--local v = state.stack[state.stack_index]
		--state.stack[v] = nil
		--state.stack_index = state.stack_index - 1
		local frame = state.call_stack[state.call_stack_index]
		state.call_stack_index = state.call_stack_index - 1
		state.current_function = frame.func
		state.pc = frame.pc
		state.localvars = frame.localvars
		--state.stack_index = state.stack_index + 1
		--state.stack[state.stack_index] = v
	end
	return true
end

local function run_n_steps(compiled, state, n)
	local count = n
	while count > 0 do
		if not run_step(compiled, state) then
			break
		end
		count = count - 1
	end
end

local function run_all(compiled, state)
	while run_step(compiled, state) do
	end
end

local function make_init_state(compiled)
	return {
		call_stack = {},
		call_stack_index = 0,
		stack = {},
		stack_index = 0,
		pc = 1,
		current_function = "main",
		localvars = {},
		globalvars = {}
	}
end

--------------------------------------------

-- Demo

-- builtins
local function add(x, y) return x + y end
local function mul(x, y) return x * y end
local function cmp(x, y) return x < y end

--[[
function f(i)
  return i * i
end

function main()
	i = 0
	s = 0
	while i < 30 do
	  s = s + f(i)
	  i = i + 1
	  print(s)
	end
end
]]

local functions = {
	f = {
		code = {
			type = "return",
			value = {
				type = "builtin_function",
				func = mul,
				args = {
					{type = "localvar_get", varname = "i"},
					{type = "localvar_get", varname = "i"}
		}}},
		args = {"i"}
	},
	main = {
		code = {
			type = "seq",
			instrs = {
				{type = "localvar_set", varname = "i", value = {type = "constant", value = 0}},
				{type = "localvar_set", varname = "s", value = {type = "constant", value = 0}},
				{type = "while",
				 condition = {
					 type = "builtin_function",
					 func = cmp,
					 args = {
						 {type = "localvar_get", varname = "i"},
						 {type = "constant", value = 30}
					 }
				 },
				 loop_body = {
					 type = "seq",
					 instrs = {
						 {type = "localvar_set", varname = "s", value = {
								type = "builtin_function",
								func = add,
								args = {
									{type = "localvar_get", varname = "s"},
									{type = "function", func = "f", args = {{type = "localvar_get", varname = "i"}}}
								}
						 }},
						 {type = "localvar_set", varname = "i", value = {
								type = "builtin_function",
								func = add,
								args = {
									{type = "localvar_get", varname = "i"},
									{type = "constant", value = 1}
								}
						 }},
						 {type = "builtin_function", func = print, no_ret = true,
							args = {{type = "localvar_get", varname = "s"}}
						 }
					 }
				 },
				}
			}
		},
		args = {}
	}
}

local compiled = compile_all(functions)
local state = make_init_state(compiled)
run_n_steps(compiled, state, 100)
print("Pause after 100 steps")
run_n_steps(compiled, state, 100)
print("Pause after 200 steps")
run_all(compiled, state)