Haskell 中二村投影的证明

Question

我在 The Three Projections of Doctor Futamura 上阅读了 Dan Piponi 的精彩博客 post。在文章末尾，他有一个附录，其中包含 Haskell 中二村预测的证明。但是，我发现他的文章缺少有关所涉及语言的信息。为了使 Futamura 投影起作用，专业化程序的源语言、目标语言和对象语言必须是什么？例如，如果我在 Haskell 中将 Haskell 写入 LLVM 专家，Futamura 预测是否有效？如果您编写了一个 Haskell 程序来证明这一点，就像 Dan Piponi 在他的文章中所做的那样，那将会很有帮助。

Answer 1

是的，当且仅当专业化程序的源语言和目标语言相同时，Futamura 投影才有效。这是因为只有用它可以阅读的相同语言编写的专业化程序才能应用于自身。但是，专业化程序的目标语言独立于其他两种语言。这会产生重要的后果，我将在稍后的回答中讨论。

为了证明我的假设，我将引入一种新的符号来粗略地描述基于 tombstone diagrams. A tombstone diagram (or T-diagram) is a pictorial representation of compilers and other related metaprograms 的程序。它们用于说明和推理程序从源语言（T 的左侧）到目标语言（T 的底部）中实现的目标语言（T 的右侧）的转换。让我们扩展 T 图的概念以适用于所有程序：

α → β : ℒ -- A program is a function from α to β as implemented in language ℒ.

在元程序的情况下 α 和 β 本身就是程序：

(α → β : ) × α → β :  -- An interpreter for language  as implemented in .
(α → β : ) → (α → β : ) :  -- A compiler from  to  as implemented in .
(ι × α → β : ) × ι → (α → β : ) :  -- A self-hosting specializer from  to .
(ι × α → β : ) → (ι → (α → β : ) : ) :  -- A compiler compiler from  to .

这种表示法可以直接转换成Haskell中的类型定义。有了这个，我们现在可以在 Haskell 中写出关于语言的 Futamura 投影的证明：

{-# LANGUAGE RankNTypes #-}

module Futamura where

newtype Program a b language = Program { runProgram :: a -> b }

type Interpreter source object = forall a b.       Program (Program a b source, a) b object
type Compiler    source target = forall a b.       Program (Program a b source) (Program a b target) target
type Specializer source target = forall input a b. Program (Program (input, a) b source, input) (Program a b target) source
type Partializer source target = forall input a b. Program (Program (input, a) b source) (Program input (Program a b target) target) target

projection1 :: Specializer object target -> Interpreter source object -> Program a b source -> Program a b target
projection1 specializer interpreter program = runProgram specializer (interpreter, program)

projection2 :: Specializer object target -> Interpreter source object -> Compiler source target
projection2 specializer interpreter = runProgram specializer (specializer, interpreter)

projection3 :: Specializer source target -> Partializer source target
projection3 specializer = runProgram specializer (specializer, specializer)

我们使用 RankNTypes 语言扩展来隐藏类型级机制，使我们能够专注于所涉及的语言。对自身应用特化器也是必要的。

在上面的程序中，第二个投影特别有趣。它告诉我们，给定一个自托管 Haskell 的 LLVM 专用程序，我们可以将它应用到任何用 Haskell 编写的解释器，用于某些源语言以获得 LLVM 编译器。这意味着我们可以用高级语言编写一个解释器，并用它来生成一个以低级语言为目标的编译器。如果专门化程序有任何好处，那么生成的编译器也会相当不错。

另一个值得注意的细节是自托管专用程序与自托管编译器非常相似。如果您的编译器已经执行了部分评估，那么将它变成专业化程序应该不会有太多工作。这意味着实施二村预测比最初认为的要容易得多，也更有回报。我还没有对此进行测试，所以请对它持保留态度。

Haskell 中二村投影的证明

Proof of the Futamura projections in Haskell

compiler-construction

interpreter

haskell