lambda 表达式的值和结合性

Question

谁能告诉我这些 lambda 表达式在替换 x=5 时的结果是什么？

a) λx. ((λx.x+1) x)

b) (λx. (λx.x+1)) x

这是我的想法。

a) λx。 (λx.x+1) x)5 = (λx.x+1) 5 = 6

b) (λx. (λx.x+1)) x 5 = (λx.x+1) x 5 = (λx.x+1) 5 = 6

Answer 1

第一个表达式：

  (λx. (λx. x + 1) x) 5
= (λx. (λy. y + 1) x) 5 -- alpha renaming
=      (λy. y + 1) 5    -- beta reduction
=           5 + 1       -- beta reduction
=           6

第二个表达式：

  ((λx. λx. x + 1) x) 5
= ((λx. λy. y + 1) z) 5 -- alpha renaming (z is a free variable)
= (     λy. y + 1   ) 5 -- beta reduction (z disappears because x is never used)
=           5 + 1       -- beta reduction
=           6

希望对您有所帮助。