How to write a compiler in Haskell? In C# I use a lot of state

Question

I'm doing a compiler in C# for a school project and I can't stop wondering how I would do that in Haskell.

For example:

My code generation for a While loop is:

public override void generateCode(Compiler compiler)
    {
        int jumpToTheBeginningInstructionIndex = compiler.getIndexOfNextActionInCurrentFunction();
        MachineInstructions.JMP jumpTotheBeginning = new MachineInstructions.JMP(jumpToTheBeginningInstructionIndex);
        MachineInstructions.JMPF jumpToTheEnd = new MachineInstructions.JMPF();

        booleanExpression.generateCode(compiler);

        //I insert the jump to the end here:
        compiler.addAction(jumpToTheEnd);

        foreach(IAction action in this.thenActions)
        {
            action.generateCode(compiler);
        }
        compiler.addAction(jumpTotheBeginning);

        //...But is here where I know where should it jump to:
        jumpToTheEnd.whereToJump = compiler.getIndexOfNextActionInCurrentFunction();
    }

You can see how I insert the code for the jumpToTheEnd at the very middle of the method, but is not until the end where I know the line where the jump jumps. Fortunately, I keep a pointer to that jump and I'm easily able to set its whereToJump attribute at the very end of the method.

How would you do that in Haskell!? Any recommended tutorial?

Answer 1

I dunno. I'm not sure you'd want to structure the code-gen phase quite like this in Haskell. But under the assumption that you did, one thing you can do is put your labels in a lazy state monad and tie the knot using mfix.

Here's a complete runnable example of this technique. We'll have a simple AST with just while-loops and statements that don't do anything; and a simple instruction type with just labels, jumps, and statements that don't do anything. Our compiler will maintain the latest-allocated label in some state. Then I guess your question is how to generate "forward" jumps to labels that haven't been allocated yet.

{-# LANGUAGE FlexibleContexts #-}
import Control.Monad.State
import Control.Monad.Writer

data Instruction = Nop | Jump Int | Label Int deriving (Eq, Ord, Show, Read)
data AST = While AST AST | Rest               deriving (Eq, Ord, Show, Read)
type Compiler = StateT Int (Writer [Instruction])

generateLabel :: Compiler Int
generateLabel = do
    v <- get
    put (v+1)
    tell [Label v]
    return v

compile :: AST -> Compiler ()
compile Rest = tell [Nop]
compile (While b c) = do
    start <- generateLabel
    compile b
    mfix $ \end -> do
        tell [Jump end] -- here we generate a forward jump
        compile c
        tell [Jump start]
        generateLabel   -- here we allocate the label we're forward-jumping to
    return ()

runCompiler :: Compiler () -> [Instruction]
runCompiler = execWriter . flip evalStateT 0

In ghci, try for example runCompiler (compile (While Rest Rest)) for the simplest example.