haskell - 共享由 monad Action 计算的信息

Question

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

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

类型检查器是一个读写状态 ( RWS ) monad:

阅读器，因为它使用由具有符号定义(符号及其类型的关联列表)的环境组成的上下文；

writer，因为它会生成错误消息列表；

稍后将需要 state 来实现名义类型等价，现在我只是在计算程序中定义了多少变量(仅作为其使用的演示)。

monad 返回的值是一个用类型(用于表达式)或环境(用于声明)注释的 ast。

函数 checker接收输入程序的 ast 并生成带有 RWS 注释的新 ast monad Action ，在运行时给出类型(如果 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

类型检查它将产生以下 ast:

                  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

用 RWS 递归注释单子(monad) Action 。

编译器的后期阶段将需要知道 ast 中的注释产生的信息(及其子级，递归地)。因此需要运行相应的操作来获取它。

根据语言规则，通过组合 child 的 Action 来构造根 Action 。

例如，为了获得根表达式的类型(一个 let 表达式)， action1必须运行，这将使 action2和 action3也要运行，因为当 action1已创建，它使用了 action2和 action3 .

当类型添加 1+x需要， action3必须运行才能得到它。

所以 Action 会重复运行。类型检查器的结构方式(使用 RWS monad Action )失去了对 ast 的每个节点的计算信息的共享。

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

Answer 1

听起来你的设计已经变成了一条死胡同。你向我们展示了它的外观。

I am studying compiler construction using Haskell.

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

The way the type checker is structured...loses sharing of the computed information for each node of the ast.

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

Is there any technique to recover this sharing, eliminating the need of recomputing actions?

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

也许每个 Action 都会从它的节点重新计算子树，包括它自己。 children 的行动被他们的结果(和重新计算的子树)所取代。

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