haskell - 如何在 Haskell 中编写编译器？在 C# 中，我使用了很多状态

Question

我正在为一个学校项目用 C# 做一个编译器，我不禁想知道我将如何在 Haskell 中做到这一点。

例如:

我为 While 循环生成的代码是:

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();
    }

您可以看到我如何在方法的中间插入 jumpToTheEnd 的代码，但直到我知道跳转所在行的末尾才插入。幸运的是，我保留了指向该跳转的指针，并且可以轻松地在方法的最后设置其 whereToJump 属性。

你将如何在 Haskell 中做到这一点!
有什么推荐的教程吗？

Answer 1

我不知道。我不确定您是否想在 Haskell 中像这样构建代码生成阶段。但是假设你做了，你可以做的一件事就是把你的标签放在一个惰性状态单子(monad)和 tie the knot使用 mfix .

这是此技术的完整可运行示例。我们将有一个简单的 AST，只有 while 循环和不做任何事情的语句；和一个简单的指令类型，只有标签、跳转和不做任何事情的语句。我们的编译器将在某种状态下维护最新分配的标签。那么我猜你的问题是如何生成“向前”跳转到尚未分配的标签。

{-# 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

在 ghci 中，例如尝试 runCompiler (compile (While Rest Rest))举个最简单的例子。