共享由monad操作计算的信息

Question

我正在使用Haskell研究编译器构造.我使用定点数据类型递归来表示抽象语法树(ast).

我正在研究如何为具有简单表达式(数字和逻辑常量,二进制操作和局部变量声明)的玩具语言编写类型检查器.

类型检查器是一个read-write-state(RWS)monad:

• 读者,因为它使用由具有符号定义的环境组成的上下文(符号的关联列表及其类型);
• writer因为它生成错误消息列表;
• 稍后将需要状态来实现名义类型等价,现在我只计算程序中定义了多少变量(就像它的使用演示一样).

monad返回的值是带有类型(用于表达式)或环境(用于声明)的注释.

该函数checker接收输入程序的ast并导致使用RWSmonad动作注释的新的ast ,当运行时,给出类型(如果ast是表达式)或环境(如果ast是声明).

例如,考虑输入程序

let x = 2 + 3 in 1 + x

与相应的ast:

                    Let                     
                     |                      
          -----------------------           
         |                      |           
     VarDec: x               Bin Add        
         |                      |           
         |                ------------      
         |                |          |      
      Bin Add          Num 1.0     Var x    
         |                                  
    -----------                             
   |          |                             
Num 2.0    Num 3.0

键入检查将产生以下内容:

                  action1
                    Let                     
                     |                      
          -----------------------           
         |                      |           
      action2                action3
     VarDec: x               Bin Add        
         |                      |           
         |                ------------      
         |                |          |      
      action4          action5    action6
      Bin Add          Num 1.0     Var x    
         |                                  
    -----------                             
   |          |                   
action7    action8      
Num 2.0    Num 3.0

使用RWSmonad动作递归注释.

编译器的后期阶段需要知道ast(及其子节点,递归)中的注释所产生的信息.因此,需要运行相应的操作才能获得它.

根据语言规则,通过组合孩子的动作来构建根动作.

例如,为了得到根表达的类型(let表达式),action1必须要运行,这将使action2并且action3要运行好了,因为当action1被创造了,它曾经action2和action3.

当1+x需要添加类型时,action3必须运行以获得它.

所以行动将反复进行.结构类型检查器的构造方式(使用RWSmonad动作)失去了ast的每个节点的计算信息的共享.

是否有任何技术可以恢复此共享,从而无需重新计算操作？

Answer 1

听起来你的设计已经走进了死胡同。您正在向我们展示它的一些外观。

我正在研究使用 Haskell 的编译器构造。

学习意味着您可以阅读其他人如何进行类型检查（例如 GHC 或Oleg的示例）。或者，这可能是你通过尝试发明来了解更多的手段。

类型检查器的构造方式...失去了 ast 的每个节点的计算信息的共享。

所以不要丢失信息。如果类型检查器在 monad 内运行，那么您最终可以将其设计为记住状态。

是否有任何技术可以恢复这种共享，从而消除重新计算操作的需要？

更具体地说，您希望在 actionX 运行后将其结果替换为它。这看起来非常非常像对惰性值的渴望：计算一次并记住结果（只是稍微有点棘手的错误）。

也许每个操作都会从其节点（包括其自身）重新计算子树。孩子们的行动被他们的结果（和重新计算的子树）所取代。

或者，如果你的 AST 是一个不可变的东西，那么状态也许应该是一个并行的 AST。