未来先生的三个投影

这是关于 Futamura 三投影的介绍,以机械类机器为例解释了部分求值或特化这一编程技术的应用,包含以下主要内容:

  • 引言:Futamura 三投影是部分求值技术的应用序列,比前一个更令人费解。将以非程序员也能理解的方式解释,这种自指推理可能会伤脑,这里以机械类机器代替计算机程序,机器有输入和输出槽,能获取无限原材料且可复制物品。
  • 造币:简单机器可将空白物制成新硬币,更有趣的是有两个输入槽可输入硬币描述的通用机器,类似计算机的解释器,能根据描述制造不同硬币。还可制作将硬币描述转化为制造该硬币的专用机器的编译器,解释器和编译器的概念如下:

    • 解释器:接受描述或指令并据此制造事物。
    • 编译器:接受描述或指令并制造用于制造该事物的专用机器,从指令集制造这样的机器的过程称为编译。
  • 特化:需要特化这一概念,对于有两个输入槽的机器,若某一输入槽的输入固定,可对机器进行优化,类似造币中专用造币机比通用造币机更专业,基于此对机器进行定制的过程称为特化或部分求值。还可制作自动特化机器设计的特化机。
  • 第一投影:特化过程类似专用造币机,可将解释器的设计输入特化机,再输入要制造的硬币描述,特化机输出专门制造该硬币的机器,即编译器,这是 Futamura 第一投影,无需制作编译器,可制作特化机,如商业产品可将代码特化为在特定架构上运行。
  • 第二投影:特化机的第一个输入是双输入机器的描述,将特化机的描述输入自身第一个输入可对其进行特化,使其与特定解释器配合工作,输出的机器内置了解释器,能接受描述并输出执行该指令的机器,即编译器,这是 Futamura 第二投影。
  • 第三投影:特化机可接受特化机的描述作为第一个输入,将其输入特化机两次可得到专门用于将解释器转换为编译器的机器,即专用解释器到编译器转换器,这是 Futamura 第三投影,有了特化机无需再制作编译器,可设计可自动转换为编译器的解释器,便于程序员编写优化编译器。
  • 总结:三投影分别是将特定程序编译为专用机器、从解释器制作用于编译的专用机器、制作将解释器转换为编译器的专用机器,还有很多变体,如使用不同语言描述、不同优化的特化机等,Futamura 投影提供了有趣的组合方式,相关理论与写自引用程序的理论相关,还有传闻中的第四投影。
  • 附录:用 Haskell 类型检查器来明确上述陈述,定义了表示图片、机器等类型,以及运行机器、特化机等函数,解释了各投影在 Haskell 中的表示,第一投影是作为编译器的通用机器,第二和第三投影是专用机器。
阅读 8
0 条评论