通过翻译成 Python 来理解 lambda 演算？

Question

我正在尝试了解 lambda 演算的工作原理以及如何简化或扩展不同的语句。

鉴于示例语句 (λz.z) (λy.y y) (λx.x a) 我是否正确翻译和简化了该语句？

这是我的解决方案：

# (λz.z) (λy.y y) (λx.x a) 
#    F      G        H
# statement translates to -> F( G( H(x) ) )

f = lambda z: z
g = lambda y: (y, y)
h = lambda x: (x, 'a')

print(f(g(h('x')))) # -> (('x', 'a'), ('x', 'a'))

# so simplified statement = lambda x: (xa)(xa)

Answer 1

首先我们将翻译每个 lambda -

(λz.z) 变为 lambda z: z
(λy.y y) 变为 lambda y: y(y)
(λx.x a) 变为 lambda x: x(a)

接下来我们将对整个表达式求值。 === 突出显示每一步发生的替换 -

# (λz.z) (λy.y y) (λx.x a)
(lambda z: z) (lambda y: y(y)) (lambda x: x(a))
              ================     /     
          ___________/            /
         /                       /
(lambda z: z)          _________/
           =          /
     _____/          /
    /               /       
(lambda y: y(y)) (lambda x: x(a))
                 ================
         ________________/
        /
(lambda y: y(y)) 
           = =
    ______/   \______
   /                 \
(lambda x: x(a))((lambda x: x(a)))
                 ================
         _______________/
        /
(lambda x: x(a))
           =  \
     _____/    \
    /           \
(lambda x: x(a))(a)
                 =
         _______/
        /
(lambda x: x(a))
           = /
   _______/ /
  / _______/
 / /
a(a)

通过翻译成 Python 来理解 lambda 演算？

Understanding lambda calculus through translation into Python?

python

lambda-calculus