我怎么会误解按需评估？
How am I misunderstanding call-by-need evaluation?
首先，我从来没有研究过这些东西或任何东西，所以我可能会问一些非常愚蠢的问题，我很抱歉，但请放轻松:)
我正在尝试实现 lambda 演算，并根据需要进行评估。我正在尝试关注 this paper 这个主题，其中相关位似乎是第 28 页上描述的自然语义。
无论如何，我对这种评估策略不了解的是，据我了解，实际替换仅在评估变量时发生。抽象评估自己，因为这些是值，应用程序只向缓存添加新条目。
但是考虑到这一点，如何评估像
这样的术语
(λx.λy.x y) λa.a
根据链接论文中描述的自然语义，第一个评估步骤是将条目 x -> λa.a 添加到缓存中，并在应用程序的 lhs 上评估抽象的主体，即 λy.x y。但这是一个值，所以评估结束。此时我们有一个未关闭的术语和一个非空堆。虽然我们确切地知道该术语的计算结果应为 λy.(λa.a) y.
我误会了什么？这在实际使用这种评估策略的语言中是如何工作的？
你的减法是对的。关键在于，该论文中提到的按需调用策略只是一种弱策略，因为它永远不会在 lambda 表达式下减少。这在图 1 中很明显，其中表达式 \x.M 是一个值。
归约结束后，如果想显式获取lambda term，还需要unwind cache（文献中常说environment），相当于把缓存中的associations替换到term中:
λy.x y [x -> λa.a] = λy.(λa.a) y
符合预期。
首先，我从来没有研究过这些东西或任何东西，所以我可能会问一些非常愚蠢的问题，我很抱歉，但请放轻松:)
我正在尝试实现 lambda 演算，并根据需要进行评估。我正在尝试关注 this paper 这个主题，其中相关位似乎是第 28 页上描述的自然语义。
无论如何，我对这种评估策略不了解的是，据我了解，实际替换仅在评估变量时发生。抽象评估自己，因为这些是值，应用程序只向缓存添加新条目。
但是考虑到这一点，如何评估像
这样的术语(λx.λy.x y) λa.a
根据链接论文中描述的自然语义，第一个评估步骤是将条目 x -> λa.a 添加到缓存中，并在应用程序的 lhs 上评估抽象的主体，即 λy.x y。但这是一个值，所以评估结束。此时我们有一个未关闭的术语和一个非空堆。虽然我们确切地知道该术语的计算结果应为 λy.(λa.a) y.
我误会了什么？这在实际使用这种评估策略的语言中是如何工作的？
你的减法是对的。关键在于，该论文中提到的按需调用策略只是一种弱策略，因为它永远不会在 lambda 表达式下减少。这在图 1 中很明显，其中表达式 \x.M 是一个值。
归约结束后，如果想显式获取lambda term，还需要unwind cache（文献中常说environment），相当于把缓存中的associations替换到term中:
λy.x y [x -> λa.a] = λy.(λa.a) y
符合预期。