haskell - G-machine，(非)严格上下文 - 为什么 case 表达式需要特殊处理

Question

我正在阅读 Implementing functional languages: a tutorial由 SPJ 和我将在这个问题中提到的(子)章是 3.8.7(第 136 页)。

首先要说明的是，阅读本教程的读者尚未实现 ECase 表达式的 C 方案编译(即出现在非严格上下文中的表达式)。
提出的解决方案是转换核心程序，以便 ECase 表达式根本不会出现在非严格上下文中。具体来说，每个这样的事件都会创建一个新的 super 组合子，其中只有一个变量，该变量的主体对应于原始 ECase 表达式，并且该事件本身被替换为对该 super 组合子的调用。
下面我展示了一个来自 1 的这种转换的(略微修改的)示例。

t a b = Pack{2,1} ;
f x = Pack{2,2} (case t x 7 6 of
    <1> -> 1;
    <2> -> 2) Pack{1,0} ;
main = f 3

== transformed into ==>

t a b = Pack{2,1} ;
f x = Pack{2,2} ($Case1 (t x 7 6)) Pack{1,0} ;
$Case1 x = case x of
    <1> -> 1;
    <2> -> 2 ;
main = f 3

我实现了这个解决方案，它就像魅力一样，也就是说，输出是 Pack{2,2} 2 Pack{1,0} .
然而，我不明白的是——为什么要这么麻烦？我希望不只是我，但我解决问题的第一个想法是在 C 方案中实现 ECase 表达式的编译。我通过模仿 E 方案中的编译规则来做到这一点(1 中的第 134 页，但为了完整起见，我在这里展示了该规则):所以我使用了

E[[case e of alts]] p = E[[e]] p ++ [Casejump D[[alts]] p]

并写道

C[[case e of alts]] p = C[[e]] p ++ [Eval] ++ [Casejump D[[alts]] p]

我添加了 [Eval]因为Casejump需要以弱头范式(WHNF)在堆栈顶部的参数，而与 E 方案相反，C 方案不能保证这一点。

但随后输出变为神秘:Pack{2,2} 2 6 .
当我使用与 E 方案相同的规则时，这同样适用，即

C[[case e of alts]] p = E[[e]] p ++ [Casejump D[[alts]] p]

所以我想我的“明显”解决方案本质上是错误的——我可以从输出中看到这一点。但是我很难就为什么这种方法注定会失败提出正式的论点。
有人可以向我提供这样的论点/证据或一些直觉，说明为什么天真的方法不起作用吗？

Answer 1

C 方案的目的是不执行任何计算，而只是延迟一切直到 EVAL 发生(它可能会或可能不会)。你在为 case 提议的代码生成中做了什么？ ?你在调用 EVAL! C 的全部目的是不对任何东西调用 EVAL，所以你现在过早地评估了一些东西。

您可以直接为 case 生成代码的唯一方法在 C 方案中将添加一些新指令以在评估后执行案例分析。

但是我们(Thomas Johnsson 和我)认为去掉这样的表达式会更简单。但是，确切的历史细节会随着时间的流逝而丢失。 :)