Lambda微积分运算符优先

Question

我在理解lambda演算运算符优先级时遇到了问题.

例如,以下代码:

lambda x.x z lambda y.x y

将是:

lambda x. (x (z lambda y. x y))

要么

lambda x. ((x z) (lambda y. x y))

？

更复杂的例子:

(lambda x.x z) lambda y.w lambda w.w x y z

在上面的例子里,括号去了哪里？

我知道lambda应用程序是左关联的,但lambda值是否优先于应用程序？

Answer 1

应用程序具有比抽象更高的优先级.连同应用程序是左关联和抽象是右关联的事实,这导致以下结果:

lambda x.x z lambda y.x y

是

lambda x. ( (x z) (lambda y. (x y)) )

和

(lambda x.x z) lambda y.w lambda w.w x y z

是

(lambda x. (x z)) (lambda y. (w (lambda w. (((w x) y) z))))