溶解lambda演算

Question

我有以下lambda演算:

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

正确的beta减少是:

+ (- 9 1) 3

我犯了一个错误,取而代之的是9号码:

+ (- 3 1) 9

而且我得到了相同的结果.

在与解决方案进行比较之前,我没有意识到这是错误的.

我是否必须采取最接近的替代,在这种情况下是9？

Answer 1

你在这个算术例子中得到相同答案的事实是由算术而不是lambda演算引起的巧合.

如果你写了更多的空格来使术语结构更清晰,那么就会更容易看出发生了什么

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

意思是,用无偿的额外括号显示解析树,

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

因为应用程序与左侧相关联("而不是像六十年代我们所做的那样" - Roger Hindley).

所以,3是在错误的地方替代x.我们只有

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