variables = {}
functions = {}



function evaluate(expr, varlevel)
	assert(varlevel)
	if expr.type == "function" then
		local retval,nvarlevel = evaluate(expr.body, varlevel)
		assert((type(retval) == "nil" and expr.returntype == "void") or
		       (type(retval) == "number" and expr.returntype == "int"), "incorrect return type "..type(retval).." for function returning "..expr.returntype)
		return retval,varlevel
	elseif expr.type == "stmtlist" then
		for k,v in pairs(expr.body) do
			local retval
			retval,varlevel = evaluate(v, varlevel)
			if not varlevel then	-- we've taken a 'return'
				return retval,nil
			end
		end
		return nil,varlevel
	elseif expr.type == "variable" then
		varlevel = varlevel + 1
		variables[varlevel] = { name = expr.name, type = expr.vtype, value = expr.initializer }
		return nil,varlevel
	elseif expr.type == "expression" then
		return evaluate(expr.value, varlevel), varlevel
	elseif expr.type == "while" then
		while evaluate(expr.expression, varlevel) ~= 0 do
			local retval,donevarlevel = evaluate(expr.chunk, varlevel)
			if donevarlevel == nil then
				return retval, nil
			end
		end
		return nil,varlevel
	elseif expr.type == "if" then
		if evaluate(expr.expression, varlevel) ~= 0 then
			local retval,donevarlevel = evaluate(expr.chunk, varlevel)
			if donevarlevel == nil then
				return retval, nil
			end
		end
		return nil,varlevel
	elseif expr.type == "operator" then
		local lhs = evaluate(expr.left, varlevel)
		local rhs = evaluate(expr.right, varlevel)
		if not (expr.value == "=" and lhs == nil) then	-- This case is OK.
			assert(type(lhs) == type(rhs), "operator "..expr.value.." on two different types: "..type(lhs).." and "..type(rhs))
		end
		if expr.value == "+" then
			return lhs + rhs
		elseif expr.value == "-" then
			return lhs - rhs
		elseif expr.value == "*" then
			return lhs * rhs
		elseif expr.value == "/" then
			return lhs / rhs
		elseif expr.value == ">" then
			return lhs > rhs and 1 or 0
		elseif expr.value == "<" then
			return lhs < rhs and 1 or 0
		elseif expr.value == "==" then
			return lhs == rhs and 1 or 0
		elseif expr.value == "=" then
			-- blah
			assert(expr.left.type == "identifier", "lvalue of operator '=' must be an identifier")
			for k=varlevel,1,-1 do
				if variables[k].name == expr.left.value then
					assert(variables[k].type == "int")
					variables[k].value = rhs
					return rhs
				end
			end
			error("unknown identifier "..expr.left.value.." in varlevel "..varlevel)
		else
			error("unknown operator "..expr.value.." in evaluate")
		end
	elseif expr.type == "number" then
		return expr.value
	elseif expr.type == "identifier" then
		for k=varlevel,1,-1 do
			if variables[k].name == expr.value then
				return variables[k].value
			end
		end
		error("unknown identifier "..expr.value)
	elseif expr.type == "funccall" then
		if not functions[expr.name] then
			error("unknown function "..expr.name)
		end
		assert(table.getn(expr.args) == table.getn(functions[expr.name].args), "wrong number of args for function "..expr.name)
		
		local orig_varlevel = varlevel
		local vars_to_move = {}
		for k,v in pairs(expr.args) do
			assert(functions[expr.name].args[k].type == "int", "wrong type for argument #"..k.." to function "..expr.name)
			varlevel = varlevel + 1
			vars_to_move[varlevel] = { type = v.type, name = functions[expr.name].args[k].name }
			vars_to_move[varlevel].value = evaluate(v.value, orig_varlevel)
		end
		for k,v in pairs(vars_to_move) do
			variables[k] = vars_to_move[k]
		end
		
		if functions[expr.name].native then
			return functions[expr.name].native(expr, varlevel), orig_varlevel
		else
			local retval, varlevel = evaluate(functions[expr.name].body, varlevel)
			assert(not varlevel)
			return retval, orig_varlevel
		end
	elseif expr.type == "return" then
		local retval = nil
		if expr.expression then
			retval = evaluate(expr.expression, varlevel)
		end
		return retval,nil
	else
		error("unknown type "..expr.type.." in evaluate")
	end
	error("fell through? type was "..expr.type)
end

functions["printint"] = { returns = "void", args = { { type = "int", name = "toprint" } },
			native = function(expr, varlevel)
				print("NATIVE CALL: printint("..variables[varlevel].value..")")
			end }

function backend(parsetree, outfn)
	for k,v in pairs(parsetree) do
		if v.type == "variable" then
			table.insert(variables, { name = v.name, type = v.vtype, value = v.initializer })
		elseif v.type == "function" then
			functions[v.name] = v
		else
			error("invalid type in global deparse")
		end
	end
					
	local retval,varlevel = evaluate(functions["main"], table.getn(variables))
	print("main returned "..retval)
end