为什么用函数式语言编写编译器更容易？

Question

为什么用函数式语言编写编译器更容易？

wvd*_*wvd 85 compiler-construction ocaml haskell functional-programming

我一直在考虑这个问题,但实际上无法在Google上找到答案以及Stackoverflow上的类似问题.如果有重复,我很抱歉.

许多人似乎都说,在函数式语言(如OCaml和Haskell)中编写编译器和其他语言工具比使用命令式语言编写它们更有效,更容易.

这是真的？如果是这样的话 - 为什么用函数式语言而不是像C这样的命令式语言来编写它们是如此高效和容易？另外 - 在一些函数式语言中,语言工具不是像C这样的低级语言吗？

Answer 1

通常,编译器会对树进行大量工作.源代码被解析为语法树.然后可以将该树转换为具有类型注释的另一个树以执行类型检查.现在,您可以将该树转换为仅包含核心语言元素的树(将类似糖的符号转换为未加工的形式).现在,您可以执行基本上在树上进行转换的各种优化.之后,您可能会以某种正常形式创建一个树,然后遍历该树以创建目标(程序集)代码.

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

@WarrenP:"携带证据的代码"概念来自静态类型的函数语言.我们的想法是你以这样的方式使用类型系统,这样一个函数只有在它正确时才能进行类型检查,所以代码编译的事实就是正确性的证明.当然,这并不是完全可能的,同时保持语言turing-complete和typechecking可判定.但是类型系统越强,你就越接近这个目标. (3认同)
这个概念主要在功能社区中流行的原因是,在具有可变状态的语言中,您还必须编码有关类型中何时何地发生状态更改的信息.在您知道函数的结果仅取决于其参数的语言中,在类型中编码证明要容易得多(手动证明代码的正确性也更容易,因为您不必考虑哪个全局状态是可能以及它将如何影响函数的行为).然而,这些都与编译器没有特别的关系. (3认同)
在我看来,最重要的一个特征是模式匹配.使用模式匹配优化抽象语法树非常简单.没有模式匹配这样做通常会令人沮丧. (3认同)

Answer 2

Pet*_*ham 38

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

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

向命令式语言添加模式匹配更加困难,因为正在评估或提取的任何值以匹配模式必须是无副作用的.

@camccann:如果语言标准保证tco(或者至少保证某种形式的递归函数永远不会导致堆栈溢出或内存消耗的线性增长),我会考虑一种语言特性.如果标准不能保证,但编译器无论如何都会这样做,那就是编译器功能. (3认同)

Answer 3

Ukk*_*kko 15

需要考虑的一个重要因素是,任何编译器项目的一个重要部分就是当你可以自我托管编译器并"吃掉你自己的狗粮"时.因此,当您查看OCaml等语言研究语言时,它们往往具有编译器类型问题的强大功能.

在我上一次编译器式的工作中,我们在操作C代码时正是出于这个原因使用OCaml,它只是该任务的最佳工具.如果INRIA的人们已经建立了具有不同优先级的OCaml,那么它可能不是那么合适.

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

/ me:快点回到我的Java任务......

@Andrei Krotkov:今天的一句话就是发音:发音:\fə-sē-shəs\功能:形容词词源:法语中的facetieux,来自facetie jest,来自拉丁语facetia日期:1599 1:经常不恰当地开玩笑或开玩笑:waggish <just facetious> 2:意思是幽默或有趣:不严肃的<a facetious remark>同义词见诙谐除了错过笑话之外,你的逻辑仍然存在缺陷.你假设所有人都是理性的演员,我担心,这不是一个公平的假设. (15认同)
@Andrei:使用你的*argumentum ad populum*:"如果理性比情感无知更好,我们都会在任何地方使用它." (13认同)
我想我错过了这个笑话,因为我知道现实生活中的人会说完全相同的事情,除非完全认真.我想是爱伦坡的法则.http://tvtropes.org/pmwiki/pmwiki.php/Main/PoesLaw (5认同)
-1表示"功能语言是解决任何问题的最佳工具".如果这是真的,我们都会在各处使用它们.;) (4认同)

Answer 4

Chu*_*uck 9

基本上,编译器是从一组代码到另一组代码的转换 - 从源到IR,从IR到优化的IR,从IR到汇编等.这正是函数式语言设计的类型 - 纯函数是只是从一件事转变为另一件事.势在必行的功能没有这种品质.虽然您可以用命令式语言编写这种代码,但函数式语言是专门用于它的.

Answer 5

Bri*_*ian 6

也可以看看

F#设计模式

FP通过"操作"对事物进行分组,而OO按类型对事物进行分组,而"按操作"则对编译器/解释器更自然.

这与在某些程序设计语言理论界所谓的"表达问题"有关.例如,请参阅[this question](http://stackoverflow.com/questions/2807629/),其中我演示了一些真正可怕的Haskell代码,它以"可扩展类型"的方式执行.相反,迫使OOP语言进入"可扩展操作"风格往往会激发访问者模式. (3认同)

Answer 6

BCS*_*BCS 6

一种可能性是编译器倾向于非常谨慎地处理一大堆极端情况.通过使用以与其实现的规则相似的方式构造实现的设计模式,通常可以更轻松地获得正确的代码.通常最终会成为声明性(模式匹配,"何处")而不是命令式(排序,"何时")设计,因此更容易在声明性语言中实现(并且大多数都是功能性的).

归档时间：	15 年，7 月前
查看次数：	11203 次
最近记录：	13 年，4 月前