在lambda演算中按值调用

Question

我正在通过类型和编程语言,而Pierce,通过降价策略调用,给出了该术语的示例id (id (?z. id z)).在将外部折射率降低到正常形式之前,将内部折射率id (?z. id z)减小到?z. id z第一次,id (?z. id z)作为第一次减少的结果?z. id z.

但是,按价值顺序调用被定义为"只有最外层的重新索引被减少",并且"仅当其右侧已经减少到某个值时,才会减少重新索引".在示例中id (?z. id z)出现在最外层redex的右侧,并且减少了.这与只有最外层的指数减少的规则相比如何？

"最外层"和"最内层"的答案仅仅是指lambda抽象吗？因此,对于一个长期t的?z. t,t不能减少,但在归约s t,t减少到一个值v,如果这是可能的,然后s v被降低？

Answer 1

简短回答:是的.你永远不能在一个lambda术语内减少你只能从右边开始减少术语.

lambda演算中的评估上下文按值定义如下:

E = [ ] | (?.t)E | Et

E是你可以珍惜的......

例如,在lambda演算中,评估上下文是:

E = [ ] | Et | fE

因为即使术语不是值,您也可以减少应用程序.例如(?x.x)(z ?x.x),通过值停留在呼叫中,但是在名称调用中它减少到(z ?x.x),这是正常形式.
在上下文中,语法f是一种常规形式(在名称调用中),定义为:

f = ?x.t | L  
L = x | L f

您可以在Pierce的第19.5.3章中看到上下文的另一个定义.