Z组合器与按呼叫终止

Question

我正在尝试构建自己的λ-微积分解释器。到目前为止，它支持按Qual-Value和正常顺序。

我现在想通过固定点尝试递归。 $ y $ combinator与正常顺序合作，用教师函数 $$ \ text {fac}=lambda f 。\ lambda n。\ text {iszero} \，n \，1（\ text {mul} \，n \，（f（\ text {pred} \，n）））\ text {，} $$ 例如，我的解释器产生<跨度类=“math-container”> $ y \，\ text {fac} \，3 \ stactrel {\ text {no}} {\ lightarrow} 6 $ 。 （我将写入行为等同的教堂数字作为十进制数）

据我所知，对于按值，我将需要 $ z $ 组合器，而不是：

$$ z=lambda f。 （\ lambda x。f（\ lambda y.x x y））（\ lambda x。f（\ lambda y.x x y））\ text {，} $$

作为 $ y $ 将导致立即无限回归。

我的问题是，我未能了解 $ z \，\ text {fac} \，0 $ 应该终止。它也不会在我的翻译中终止，但我想首先手动理解它。

在一些步骤后，逐个值应该到达： $$ z \，\ text {fac} \，0 \\=lambda f。 （\ lambda x。f（\ lambda y.x x y））（\ lambda x。f（\ lambda y.x x y））\，\ text {fac} \，0 \\\ stactrel {\ text {cbv}}（\ lightarrow}（\ lambda x。\ text {fac}（\ lambda y.xxy））（\ lambda x。\ text {fac}（\ lambda y.xxy） ）\，0 \\\ stackrel {\ text {cbv}} {\ lightarrow} \ text {fac}（\ lambda y。（\ lambda x。\ text {fac}（\ lambda y'。xx y'））（\ lambda x 。\文本{fac}（\ lambda y.xx y'））y）\，0 \\\ stackrel {\ text {cbv}} {\ lightarrow} \ text {fac} \，f \，0 \ stackrel {\ text {cbv}} {\ lightarrow} \ text {iszero} \，0 \，1 \，a \ text {，} $$ < / span>

其中省略术语

$$ a=text {mul} \，0 \，0 \，（f \，（\ text {pred} \，0））$$ 包含< / p>

$$ f=lambda y。（\ lambda x。\ text {fac}（\ lambda y'.xxy'））（\ lambda x。\文本{fac }（\ lambda y'.xxy'））\，y $$ 再次。

现在， $ \ text {iszero} \，0 \ stackrel {\ text {cbv}} {\ lightarrow} \ lambda t。\ lambda ft $ ， st

$$ \ text {iszero} \，0 \，1 \，a \ stactrel {\ text {cbv}} {\ lightarrow}（\ lambda t。\ lambda ft ）\，1 \，a \ stackrel {\ text {cbv}} {\ lightarrow}（\ lambda f.1）\，a \ text {。} $$

如果我们的语言有一个分支构造，它将忽略 $ a $ 分支，但我们必须使用呼叫值来评估<跨越类=“数学容器”> $ a $ 到一个值，即抽象。

$ a=text {mul} \，0 \，（f \，（\ text {pred} \，0）$ 和 $ \ text {mul} \，0 $ 将是另一个抽象，所以接下来我必须减少 $ f \，（\ text {pred } \，0）$ 。

$ \ text {pred} \，0 \ stactrel {\ text {cbv}} {\ lightarrow} 0 $ ，所以我们减少 $ f \，0 $ 。

$$ f \，0=（\ lambda y。（\ lambda x。\ text {fac}（\ lambda y'.xxy'））（\ lambda x。 \ text {fac}（\ lambda y'.xxy'））\，y）\，0 \ stactrel {\ text {cbv}} {\ lightarrow}（\ lambda x。\ text {fac}（\ lambda y' .xxy'））（\ lambda x。\ text {fac}（\ lambda y'.xxy'））\，0 \ stactrel {\ text {cbv}} {\ lightarrow} \ text {fac} \，f \ ，0 $$

现在我们回到了广场。我做错了什么吗？

Answer 1

我不认为你正在减少错误，但问题不是z组合者。问题是 $ \ text {iszero} $ 。逐个值中的分支构造不能只需将每个分支的直接术语作为它们可以在呼叫名称（或类似）中的参数，因为无论测试如何，都将评估两个分支。这种情况清楚地与递归相互作用，但通常也是不希望的。

相反，呼叫中的分支构造应采取明确延迟的参数。所以类似的东西： $$ \ text {iszero} \n\（λ\ _。1）（λ\ _。\ text {mul} \n\（f \ text{pred} \ n））$$ 这种方式可以避免递归评估，除非实际是必要的。当然，您可以留下 $ \ text {iszero}$ 原样，始终以这种方式使用它，并提供额外的争论，但我认为通常会被定义为期望延迟参数。