Implement imperative return statement in interpreter

Question

I'm trying to implement simple imperative language in haskell.

Generally speaking my program is a list of statements (like arithmetic expression, if/then, block statement). My evaluator has simple state: stack of lexical scopes. Lexical scope is just map of variable name to value. I push lexical scope every time as control flow enters function or block and pop as control flow leaves function or block.

But I've encountered a problem while trying to implement evaluation of return statement. What I'm trying to do is to make a special case for return statement in main evaluating function(sources here):

evalStatements :: [Statement] -> Eval MaybeValue

-- nothing to evaluate
evalStatements [] = return Nothing

-- current statement is 'return expr', 
-- evaluate expr and skip the rest of statements
evalStatements (ret@(ReturnStatement _expr):_stmts) =
    leaveLexEnv -- leave current lexical scope
    evalStatement ret >>= return

-- this is last statement in function, eval it and leave lexical scope
evalStatements [stmt] = do
    res <- evalStatement stmt
    leaveLexEnv -- leave current lexical scope
    return res

evalStatements (st:stmts) =
    evalStatement st >> evalStatements stmts >>= return

evalStatement :: Statement -> MaybeValue
evalStatement (ExprStatemet expr) = ...
evalStatement (IfThenStatement expr stmt) = ...

But special case in evalStatements function looks ugly for me. And this approach doesn't work with BlockStatement, because return statement can be inside this block statement. Another problem is restoring stack of lexical scopes, when return statement is located inside multiple nested block statements.

I think I can solve this problem with storing some additional state in my evaluator, but this approach looks not very good. Something tells me that continuations can help me here. But I don't understand continuations very well yet.

What is best way to solve this problem? I need just an idea, general concept.

Thanks.

Answer 1

Continuations can work here, but they're way overkill. In fact, continuations are almost always overkill for solving any specific problem.

The simplest solution is to put the necessary logic into your Eval type. If you make Eval contain a constructor for "this computation returned early with this value", and then make your definitions of (>>) and (>>=) respect that, everything will work out automatically.