5

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

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

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

  • 阅读器，因为它使用由具有符号定义（符号及其类型的关联列表）的环境组成的上下文；
  • writer，因为它会生成错误消息列表；
  • 稍后将需要 state 来实现名义类型等价，现在我只是在计算程序中定义了多少变量（仅作为其使用的演示）。

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

该函数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

类型检查它将产生以下 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 动作递归注释的。

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

根据语言规则，通过组合孩子的动作来构造根动作。

例如，为了获得根表达式的类型（一个 let 表达式），action1必须运行，这将使得action2andaction3也被运行，因为当action1它被创建时，它使用了action2and action3。

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

所以动作会重复运行。类型检查器的结构方式（使用RWSmonad 操作）失去了对 ast 的每个节点的计算信息的共享。

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

4

2 回答 2

1

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

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

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

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

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

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

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

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

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

于 2012-05-18T08:17:24.730 回答
0

动作应该总是给出类型，有时修改环境。词法环境本身可以直接在 monad 中携带，作为一个词法框架的堆栈（或列表），每个框架捕获一个范围，并包含标识符到类型的映射。如果你正在做统一，那么让你的类型要么是实际类型，要么只是打开类型变量，然后指向另一个从类型变量到类型的映射。（这方面为您提供了一个可变存储。）如果该映射中的类型变量没有值，则该类型仍然是打开的。一旦确定了类型统一到什么，然后将该统一作为关联添加到地图中。（当然，统一两个类型变量意味着创建一个新类型变量并将其他类型变量统一到该变量上——这实际上是基本统一的唯一“技巧”）。

无论如何，您可能想查看 wren 的统一库以获取一些实现技术的指针：http: //hackage.haskell.org/package/unification-fd。请注意他如何拥有一个STVar使用真正可变性的后端，以及一个在IntVar后台使用不可变映射的后端（这有点像上面描述的）。

编辑：我还想到，如果每个动作都在 RWS 之后，那么根据定义，它们之间就无法共享！AST 的递归固定点很棒，但我知道将 monad 向下“推”到每个级别没有任何优势，除非您明确想要创建实际上试图避免的“不共享”行为。

编辑：要在每个级别使用类型注释 AST，然后只需将typecheckfrom的类型更改Expr () -> m Type为Expr -> m (Expr Type)expr 在某种注释上参数化的位置！您当前没有用类型注释 AST，而是用可以产生类型的计算来注释它！因此，只需运行计算即可...

于 2012-05-18T12:32:52.677 回答