Приоритет операторов лямбда-исчисления

Question

У меня проблемы с пониманием приоритета операторов лямбда-исчисления.

Например, следующий код:

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

Куда в приведенном выше примере идут скобки?

Я знаю, что лямбда-приложение остается ассоциативным, но имеет значения лямбда иметь более высокий приоритет над приложениями?

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))))