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

Question

Я следующее лямбда-исчисление:

(λx. + (- x 1)) 9 3 

Право бета уменьшить это:

+ (- 9 1) 3 

Я сделал ошибку и взял вместо 9 число 3:

+ (- 3 1) 9 

и у меня тот же результат.

Я не понимал, что это было неправильно, пока не сравните его с решением.

Должен ли я взять ближайшую замену, в данном случае - 9?

Answer 1

Тот факт, что вы получили тот же ответ в этом арифметическом примере, - это совпадение, вызванное арифметикой, а не лямбда-исчислением.

Если вы написали больше пространства, чтобы термин структуру понятнее, было бы легче увидеть, что происходит на

(\x. + (- x 1)) 9 3 

средств, безвозмездными дополнительными скобки, показывая дерево разбора,

((\x. (+ (- x 1))) 9) 3 

потому что приложение ассоциировано слева («как мы все делали в шестидесятые годы» - Роджер Хиндли).

Таким образом, 3 не в том месте, где нужно заменить x. У нас есть только

((\x. (+ (- x 1))) 9) 3 
    = 
(+ (- 9 1)) 3 
    = 
(+ 8) 3 
    = 
11 

Answer 2

Да, вам всегда нужно применить лямбду к ее «первому» (левому) аргументу.

В теории нет такой вещи, как несколько аргументов, есть только применение одного аргумента. Тем не менее, принято писать f M N O для повторного применения (((f M) N) O). Обратите внимание, как f принимает в качестве аргумента M.

В общем случае вы не получите тот же результат, если вы используете приложение в другом порядке. Ваш пример был только инцидентом.