haskell - 在惰性函数式语言的模板实例化求值器中实现 `case` 表达式有困难吗？

Question

我正在关注 "Implementing functional languages: a tutorial"由 SPJ，我坚持练习 2.18(第 70 页)，转载如下。这是关于书中描述的简单惰性函数式语言的模板实例化求值器的章节(类似于迷你 Miranda/Haskell):

Exercise 2.18. Why is it hard to introduce case expressions into the template instantiation machine?(Hint: think about what instantiate would do with a case expression.)

本教程接着介绍了几个不太通用的结构化数据解构版本的实现:if原始的，一个casePair原始的，和一个caseList原始。我还没有完成这部分的实现(第 2 章标记 5)，但我不明白为什么单独实现这些比实现单个 case 要容易得多。原始。

我能提供的唯一合理的解释是最通用的 case形式在备选方案数量(要匹配的标签数量)和元数(结构化数据的参数数量)方面都是可变的。以上所有原语都是固定数量的，并且具有已知数量的替代方案。但是，我不明白为什么这会使实现变得更加困难。

case 的实例化声明很简单:

1. 实例化监督者。
2. 实例化每个可选的 body 表情。 (如果我们替换未评估的分支，这可能会有些浪费。) (我现在注意到这可能是一个问题，将在答案中发布。)
3. 将结果封装在一个新的节点类型中，NCase ， 在哪里:

   data Node = NAp Addr Addr
             | ...
             | NCase [(Int, [Name], Addr)]
   

在操作上，减少了 case声明很简单。

1. 检查参数是否被评估。
   • 如果不是，则将其设为新堆栈并将当前堆栈插入转储。 (类似于评估任何原语的参数。)
2. 如果评估了参数，则搜索具有匹配标签的替代方案。
   • 如果没有找到具有匹配标签的备选方案，则抛出错误(不穷尽的案例分支)。
3. 使用结构化数据参数增强的环境实例化匹配备选方案的主体。 (例如，在 case Pack {0, 2} 3 4 in <0> a b -> a + b 中，使用环境 a + b 实例化 [a <- 3, b <- 4] )

对于包含备选方案列表的案例 ( NCase ) 可能必须引入新的节点类型，但这并不过分劝阻。

---

我找到了一个 GitHub 存储库 @bollu/timi这似乎也在本教程之后实现了一个模板实例化评估器。有一个名为 "Lack of lambda and case" 的部分，这归因于缺乏通用 case声明如下原因:

Case requires us to have some notion of pattern matching / destructuring which is not present in this machine.

但是，在本教程中没有模式匹配的概念；我们只是通过标签号(一个整数)进行匹配，所以我不确定这个解释是否有效。

---

_{除此之外，部分是为了我自己:a very similar question was asked关于特殊待遇case教程下一章中的语句(关于 G 机器而不是模板实例化)。}

Answer 1

我想我是在扩展我对问题的推理时弄清楚的。我会在这里发布以供后代使用，但如果有人有更易于理解的解释或能够纠正我，我会很乐意接受。

---

困难在于 instantiate step 执行所有变量替换，这与评估(step 函数)分开发生。问题是 as bollu says in the GitHub repository linked in the original question :在实例化时解构结构化数据并不容易。这使得很难实例化所有备选方案的主体。

为了说明这一点，考虑 let 的实例化表达式。这就像这样:

1. 实例化每个新的绑定(bind)表达式。
2. 使用新绑定(bind)增强当前环境。
3. 用增强的表情实例化 body 。

但是，现在考虑 case 的情况表达式。我们要做的是:

1. 实例化受检者。 (最终应该评估为 Pack {m, n} a0 a1 ... an 的形式)
2. 对于每个备选方案(每个备选方案都具有 <m> b0 b1 ... bn -> body 的形式)，使用新绑定(bind)( [b0 <- a0, b1 <- a1, ..., bn <- an] 然后实例化备选方案的主体。)扩充环境。

问题出在两个步骤之间:调用 instantiate在检查结果中实例化 Addr , 但我们不容易访问 a1 , a2 , ... an在实例化时增强环境。如果受检者是字面上的 Pack，这可能是可能的值，如果它需要进一步评估(例如，是调用 super 组合器的评估结果)，那么我们需要首先评估它。

---

为了巩固我自己的理解，我想回答一个额外的问题:原语如何if , casePair , 和 caseList避免这个问题？

if简单地避免了这个问题，因为 bool 值是无效的。 casePair和 caseList通过使用 thunk(s) 延迟变量绑定(bind)来避免这个问题；一旦 thunk 被调用， body 表达式就会被实例化，这是在审查者被评估之后。

---

可能的解决方案:

1. 我认为，如果我们在结构化数据对象上定义解构原语运算符，或许可以解决这个问题。即 (Pack {m, n} a0 a1 ... an).3将评估为 a3 .

   在这种情况下，我们可以做的是调用 instantiate scrut这会给我们地址 scrutAddr ，然后我们可以使用新的绑定(bind)来扩充环境 [b0 <- (NAp .0 scrut), b1 <- (NAp .1 scrut), ..., bn <- (NAp .n scrut)] .

2. 问题似乎在于实例化(替换)和求值是分开的。如果变量不是与评估分开实例化，而是在绑定(bind)/使用时添加到环境中/从环境中查找，那么这将不是问题。这就好像我们将 case 语句的主体放入 thunk 中，以便在评估受检者之后实例化，这类似于 casePair。和 caseList做。

我还没有研究过这些替代解决方案中的任何一个，也没有研究过它们会产生多少额外的工作。