为什么用函数语言编写编译器更容易?[关闭]

编译器经常与树一起工作。源代码被解析为语法树。然后,可以将该树转换为另一个具有类型注释的树来执行类型检查。现在,您可以将该树转换为只包含核心语言元素的树(将语法上类似于糖的符号转换为未经修饰的形式)。现在,您可以执行各种优化,这些优化基本上是树上的转换。之后,您可能会以某种正常形式创建一个树,然后在该树上迭代以创建目标(程序集)代码。

函数语言具有模式匹配和对高效递归的良好支持等特性,这使得使用树很容易,因此它们通常被认为是编写编译器的好语言。

许多编译器任务都是树结构上的模式匹配。

OCAML和Haskell都具有强大而简洁的模式匹配功能。

很难将模式匹配添加到命令式语言中,因为要匹配模式所需的任何值都必须是无副作用的。

需要考虑的一个重要因素是,任何编译器项目的一个重要部分都是当您可以自己托管编译器并“吃自己的狗食”时。因此,当您查看像ocaml这样专为语言研究设计的语言时,它们往往具有编译器类型问题的强大功能。

在我上一个类似编译器的工作中,我们使用ocaml正是因为这个原因,在操作C代码时,它只是任务中最好的工具。如果INRIA的人建立了具有不同优先级的OCAML,可能就不太合适了。

也就是说,函数语言是解决任何问题的最佳工具,因此从逻辑上讲,它们是解决这个特定问题的最佳工具。QED。

/M:爬回我的Java任务有点不快乐…

基本上,编译器是从一组代码到另一组代码的转换,从源代码到IR,从IR到优化的IR,从IR到汇编等等。这正是功能语言为“优化”而设计的类型。纯函数只是从一个事物到另一个事物的转换。命令式函数没有这种质量。虽然您可以用命令式语言编写这种代码,但是函数式语言是专门为它编写的。

也见

F# design pattern

对于编译器/解释器,fp按操作对事物进行分组,而oo按类型和操作对事物进行分组更为自然。

一种可能是编译器必须非常小心地处理大量的角情况。通过使用以与实现的规则并行的方式构造实现的设计模式,通常可以更容易地纠正代码的错误。通常是一个声明性(模式匹配,“where”)而不是命令式(排序,“when”)设计,因此更容易在声明性语言中实现(其中大多数是功能性的)。

似乎每个人都错过了另一个重要原因。为解析器编写一种特定于域的嵌入式语言(edsl)是非常容易的,它在普通代码中看起来很像(e)bnf。 解析器连接符 像parsec一样,使用高阶函数和函数组合,很容易用函数语言编写。不仅简单,而且非常优雅。

基本上,您只将最简单的通用解析器表示为函数,并且您有特殊的操作(通常是高阶函数),它允许您 组成 这些原语解析器将成为更复杂、更具体的语法解析器。

当然,这并不是实现Parer框架的唯一方法。