lambda calculus

  • 从外往里
    \beta reduction order
    image.png
  • normal order
    M N P
    left to right 先直接把N给M
  • applicative order
    M N P
    left to right
    先把M 和N 内部可以reduce的先reduce

如果一个lambda expression 可以被reduce，那么normal order一定可以reduce到最简单的模式，applicative order不一定可以

\alpha convention
M N
(λx.xy)(λk.kx)
= (λt.ty)(λk.kx)
=kxy
bound variable in the left side = free variable in the right side

image.png
©著作权归作者所有,转载或内容合作请联系作者
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

推荐阅读更多精彩内容