6

我目前正在阅读实现功能语言：SPJ 的教程，我将在这个问题中提到的（子）章节是 3.8.7（第 136 页）。

首先要注意的是，阅读本教程的读者尚未实现 ECase 表达式的 C 方案编译（即出现在非严格上下文中的表达式）。
提出的解决方案是转换核心程序，以便 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 方案中的编译规则来做到这一点（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）的堆栈顶部的参数，而 C 方案不能保证这一点，而不是 E 方案。

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

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

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

4

1 回答 1

7

The purpose of the C scheme is to not perform any computation, but just delay everything until an EVAL happens (which it might or might not). What are you doing in your proposed code generation for case? You're calling EVAL! And the whole purpose of C is to not call EVAL on anything, so you've now evaluated something prematurely.

The only way you could generate code directly for case in the C scheme would be to add some new instruction to perform the case analysis once it's evaluated.

But we (Thomas Johnsson and I) decided it was simpler to just lift out such expressions. The exact historical details are lost in time though. :)

于 2014-12-30T20:29:22.613 回答