G机器,(非)严格的背景 - 为什么案例表达需要特殊处理

Question

我目前正在阅读实现函数式语言: SPJ的一个教程和我将在这个问题中引用的(子)章节是3.8.7(第136页).

第一个注意事项是,遵循本教程的读者尚未实现ECase表达式的C方案编译(即出现在非严格上下文中的表达式).
提出的解决方案是转换Core程序,以便ECase表达式根本不会出现在非严格的上下文中.具体来说,每次这样的事件都会创建一个新的超级组合器,其中只有一个变量,该变量的主体对应于原始的ECase表达式,并且该事件本身会被对该超级组合器的调用所替换.
下面我将介绍一个(略微修改过的)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方案中的编译规则来实现它(第134页,第1页,但我在这里提出了完整性规则):所以我用过

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)的堆栈顶部进行参数,而C方案不保证,与E方案相反.

但随后输出变为神秘: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方案中直接生成代码的唯一方法是在评估后添加一些新指令来执行案例分析.

但我们(托马斯约翰逊和我)认为解除这些表达方式更简单.但确切的历史细节会随着时间流逝而丢失.:)