fre*_*low 8 compiler-construction f# haskell functional-programming scala
在语法分析阶段,命令式编译器可以从已经包含在构造期间type设置的字段的节点构建AST null,然后在语义分析阶段,通过将声明/推断类型分配到类型来填充类型该type领域.
纯粹的函数式语言如何处理这个问题,在那里你没有分配的奢侈品？无类型AST是否映射到另一种类型丰富的AST？这是否意味着我需要为每个AST节点定义两种类型,一种用于语法阶段,一种用于语义阶段？
有没有纯函数式编程技巧可以帮助编译器编写这个问题？
我通常将源(或已经降低了几步)AST重写为新形式,用expression一对替换每个节点(tag, expression).
标签是唯一的数字或符号,然后由下一个传递使用,它从AST中导出类型方程.例如,a + b会产生类似{ numeric(Tag_a). numeric(Tag_b). equals(Tag_a, Tag_b). equals(Tag_e, Tag_a).}的东西.
然后解决类型方程(例如,通过简单地将它们作为Prolog程序运行),并且,如果成功,所有标记(这个程序中的变量)现在绑定到具体类型,如果不成功,它们将被保留为类型参数.
在下一步中,我们之前的AST再次被重写,这次用所有推断的类型信息替换标签.
整个过程是一系列纯重写,无需破坏性地替换AST中的任何内容.典型的编译管道可能需要几十次重写,其中一些会改变AST数据类型.
就像处理关系数据库的情况一样，在函数式编程中，最好不要将所有内容都放在单个数据结构中。
特别是，可能不存在“AST”的数据结构。
最有可能的是，会有表示解析表达式的数据结构。处理类型信息的一种可能方法是在解析过程中为树的每个节点分配一个唯一标识符（如整数），并使用一些合适的数据结构（如哈希映射）将这些节点 ID 与类型相关联。那么，类型推断过程的工作就是创建这个映射。