文档章节

Lambda Calculus的简单理解

秋风醉了
 秋风醉了
发布于 2015/04/19 04:19
字数 2218
阅读 1292
收藏 27
点赞 0
评论 2

Lambda Calculus的简单理解

 

Lambda 演算

λ演算(英语:lambda calculus,λ-calculus)是一套用于研究函数定义、函数应用和递归的形式系统。它由阿隆佐·邱奇和他的学生斯蒂芬·科尔·克莱尼在20世纪30年代引入。邱奇运用λ演算在1936年给出判定性问题(Entscheidungsproblem)的一个否定的答案。这种演算可以用来清晰地定义什么是一个可计算函数。关于两个lambda演算表达式是否等价的命题无法通过一个“通用的算法”来解决,这是不可判定性能够证明的头一个问题,甚至还在停机问题之先。Lambda演算对函数式编程语言有巨大的影响,比如Lisp语言、ML语言和Haskell语言。

Lambda演算可以被称为最小的通用程序设计语言。它包括一条变换规则(变量替换)和一条函数定义方式,Lambda演算之通用在于,任何一个可计算函数都能用这种形式来表达和求值。因而,它是等价于图灵机的。尽管如此,Lambda演算强调的是变换规则的运用,而非实现它们的具体机器。可以认为这是一种更接近软件而非硬件的方式。

函数是通过λ表达式匿名地定义的,这个表达式说明了此函数将对其参数进行什么操作。例如,“加2”函数f(x)= x + 2可以用lambda演算表示为λx.x + 2 (或者λy.y + 2,参数的取名无关紧要)而f(3)的值可以写作(λx.x + 2) 3。函数的应用(application)是左结合的:f x y =(f x) y。

考虑这么一个函数:它把一个函数作为参数,这个函数将被作用在3上:λf.f 3。如果把这个(用函数作参数的)函数作用于我们先前的“加2”函数上:(λf.f 3)(λx.x+2),则明显地,下述三个表达式:

(λf.f 3)(λx.x+2) 与 (λx.x + 2) 3 与 3 + 2

是等价的。用js代码表达如下(应该不是那么严谨),

function f1(f) {
    return  f(3)
}

function f2() {
    return function (x) {
        return  x + 2;
    }
}


console.log(f1(f2()))

//=============或像下面这样写
console.log(f1((function () {
    return function (x) {
        return x + 2;
    }
})()));

有两个参数的函数可以通过lambda演算这么表达:一个单一参数的函数的返回值又是一个单一参数的函数(参见Currying)。例如,函数f(x, y) = x - y可以写作λx.λy.x - y。下述三个表达式:

(λx.λy.x - y) 7 2 与 (λy.7 - y) 2 与 7 - 2

也是等价的。js的代码表达如下,

//最普通的实现两个数相加的函数
function add0(x, y) {
    return x + y;
}

//使用函数的柯里化实现两个数相加
//也是js的闭包
function add1(num) {
    return function (numOther) {
        return num + numOther;
    }
}

console.log(add1(3)(2))

然而这种lambda表达式之间的等价性无法找到一个通用的函数来判定。

并非所有的lambda表达式都可以规约至上述那样的确定值,考虑

(λx.x x)(λx.x x)

(λx.x x x)(λx.x x x)

然后试图把第一个函数作用在它的参数上。 (λx.x x)被称为ω 组合子,((λx.x x)(λx.x x))被称为Ω,而((λx.x x x) (λx.x x x))被称为Ω2,以此类推。

若仅形式化函数作用的概念而不允许lambda表达式,就得到了组合子逻辑。

插播:关于λ项 

其实作为 Haskell 的核心,λ表达式是异常简洁的。下面是关于λ表达式 (λ Expression),也叫λ项 (λ Term) ,的定义:

  • 变元是λ项,通常用小写字母写出来,比如 x,y,z 等;

  • 如果 M 是λ项,那么 λx.M 也是;

  • 如果 M 和 N 都是λ项,那么 M N 也是。

  1. 变元 (variable) 形态的λ项很简单,就是 x 或者 y 或者 z 或者什么别的,我们通常用单个小写字母,有 时候也加上数字脚标,比如 x0, x1, x2 等,以示区分。

  2. 抽象 (abstraction) 形态的λ项,写出来就是先用λ这个符号本身作开头,后面跟一个变元,然后一个小点,然后跟一个任意的λ项。例如 λx.x 或 λx.y 或 λx.x x  等。

  3. 应用 (application) 形态的λ项,就是两个λ项写在一起,中间仅留一个空格做分隔。例如 f x 或者 x x。 写在前面的λ项通常叫函数(function),后面的叫参(argument)。比如在 x x 这个表达式里,就是把 x 这个函数作用于(apply to)它自己。

 

在实际书写抽象和应用两种λ项时,如果没有一定的标识,往往会产生歧义。所以通常是用括号来把一个λ项和它前后的符号区分开,比如 (λx.x) y 这个表达式,就是说函数 λx.x 作用在参数 y 上。 我们通常不认为括号本身是λ项的一部分,使用它们纯粹是为了书写。

 

括号的使用有时候也可以略去。约定俗成的习惯是在表达抽象时,小点后面整个式子(除非是遇到反括号) 都是与小点前面的变元对应的λ项。比如 λx.(λy.(x y)) 就可以简写为 λx.λy.x y;在表达应用时则向左结 合,比如 f x y 应该被理解为 (f x) y 而不是 f (x y)。

 

Lambda 演算的语法

先来看一下lambda表达式的基本语法(BNF):

<expr> ::= <identifier>

<expr> ::= lambda <identifier-list>. <expr>

<expr> ::= (<expr> <expr>) 

前两条语法用于生成lambda表达式(lambda函数),如:

lambda x y. plus x y

Lambda演算只有三类表达式:

  1. 函数定义:Lambda演算中的函数是一个表达式 ,写成:lambda x . body ,表示“一个参数为x的函数,它的返回值为body的计算结果”。 这时我们说:Lambda表达式绑定了参数 x

  2. 标识符引用(identifier reference):标识符引用就是一个名字,这个名字用于匹配函数表达式中的某个参数名

  3. 函数应用(function application):把要应用的值放到函数定义的后面,比如(lambda x . plus x x) y 

 

Lambda 表达式

“Lambda 表达式”(lambda expression)是一个匿名函数,Lambda表达式基于数学中的λ演算得名,直接对应于其中的lambda抽象(lambda abstraction),是一个匿名函数,即没有函数名的函数。Lambda表达式可以表示闭包(注意和数学传统意义上的不同)。——百科

自由变量和闭合

A particular instance of a variable is “free” in a lambda expression if it is not “bound” by a lambda. For example, x is free in the expressions 

x

and

λy. x 

but not in this expression

λx. x

Because variables can be repeated, care must be taken to know which variable one is referring to. 

For example, in this expression, the underlined occurrences of x are free, the others are not:

λy. x (λx. x x) x

A term is closed if it has no free variables; otherwise it is open.

lambda表达式如果没有自由变量,那么其是闭合的。

 

自由标识符(变量) vs 绑定标识符

闭包(closure)或者叫完全绑定(complete binding)

在对一个Lambda演算表达式进行求值的时候,不能引用任何未绑定的标识符。

如果一个标识符是一个闭合Lambda表达式的参数,我们则称这个标识符是(被)绑定的;如果一个标识符在任何封闭上下文中都没有绑定,那么它被称为自由变量。

lambda x . plus x y:在这个表达式中,y和plus是自由的,因为他们不是任何闭合的Lambda表达式的参数;而x是绑定的,因为它是函数定义的闭合表达式plus x y的参数。

lambda x y . y x :在这个表达式中x和y都是被绑定的,因为它们都是函数定义中的参数。

lambda y . (lambda x . plus x y):在内层演算lambda x . plus x y中,y和plus是自由的,x是绑定的。在完整表达中,x和y是绑定的:x受内层绑定,而y由剩下的演算绑定。plus仍然是自由的。

我们会经常使用free(x)来表示在表达式x中自由的标识符。

 

一个Lambda演算表达式只有在其所有变量都是绑定的时候才完全合法。但是,当我们脱开上下文,关注于一个复杂表达式的子表达式时,自由变量是允许存在的——这时候搞清楚子表达式中的哪些变量是自由的就显得非常重要了。

 

参考:http://cgnail.github.io/academic/lambda-1/

http://a.haskellcn.org/topic/4f9e4037edefd68d37010c8b

http://www.cs.yale.edu/homes/hudak/CS201S08/lambda.pdf

http://www.zhihu.com/question/20349066

http://zh.wikipedia.org/zh-cn/%E8%87%AA%E7%94%B1%E5%8F%98%E9%87%8F%E5%92%8C%E7%BA%A6%E6%9D%9F%E5%8F%98%E9%87%8F

http://zh.wikipedia.org/zh-cn/%CE%9B%E6%BC%94%E7%AE%97

http://blog.csdn.net/pongba/article/details/1336028

http://blog.csdn.net/g9yuayon/article/details/1062518

===========END===========

© 著作权归作者所有

共有 人打赏支持
秋风醉了
粉丝 223
博文 581
码字总数 411013
作品 0
东城
程序员
加载中

评论(2)

d
dandave

引用来自“datousir”的评论

不错,有意思,终于知道闭包还可以用lambda演算解释,回去好好研究一下lambda演算

说的很好
d
datousir
不错,有意思,终于知道闭包还可以用lambda演算解释,回去好好研究一下lambda演算
函数式编程基础思想

说明 网上有很多深入语言层次讲解函数式编程的应用,很多人无法理解,能用但是一头雾水,死记硬背,原因究其是核心思想不清楚。 我说的语言层次上的,例如 Spark MapReduce lambda Groovy Rx...

热血沸腾 ⋅ 2017/12/20 ⋅ 0

python做的lambda 演算示例

所有关于函数式编程的介绍中都指明 lambda演算是函数式编程的数学基础。死了不少脑细胞研究了一下维基百科上关于lambda演算的介绍文章。 参考:http://en.wikipedia.org/wiki/Lambdacalculus...

阿托 ⋅ 2014/07/04 ⋅ 0

利用 PHP 5.3 的 lambdas 和 closures

在过去的几年中,围绕着编程语言开展了很多活动。开发人员已经学习了 Ruby、Groovy 和 Clojure 这类语言 — 不仅是拓宽其销路,而且还拓宽其思维。这些语言的两个最精彩的特性已在 PHP 5.3 ...

红薯 ⋅ 2011/01/10 ⋅ 2

inspired by Lisp/Scheme

“不区分数据与操作”这句话说起来很简单,其实背后蕴含着一个重要的哲学问题,即“什么是时间”的问题。按照过程式编程的理念,“时间”是操作内部的一个变量,程序以局部变量的形式记录系统...

AdamWu ⋅ 2012/06/16 ⋅ 0

Scala之旅 4 Case Class

Scala支持Case Class的概念。Case Class是也是普通类,但其导出构造参数,并通过模式匹配提供递归分解机制。 下面实例包括一个抽象超类Term和三个实体类Var,Fun和App。 abstract class Ter...

开源中国驻成都办事处 ⋅ 2012/05/21 ⋅ 2

理解下函数式编程

Lambda calculus(Lambda演算)是一套形式系统,一套用于研究函数定义、函数应用和递归的形式系统。它由 Alonzo Church 和 Stephen Cole Kleene 在 20 世纪三十年代引入,可以证明它与图灵机...

开源中国驻成都办事处 ⋅ 2012/04/06 ⋅ 0

名词王国里的新政-解读Java8之lambda表达式

前几天在reddit上看到Java8 M8 Developer Preview版本已经发布了,不免想要尝鲜一把。Developer Preview版本已经所有Feature都完成了,Java8的特性可以在这里看到http://openjdk.java.net/p...

黄亿华 ⋅ 2013/09/15 ⋅ 11

函数式编程语言--F#

F#是由微软发展的为微软.NET语言提供运行环境的程序设计语言,是函数编程语言(FP,Functional Programming),函数编程语言最重要的基础是Lambda Calculus。它是基于OCaml的,而OCaml是基于...

匿名 ⋅ 2010/03/05 ⋅ 0

如何在6个月内学习深度学习(翻译)

原文链接:如何在6个月内学习深度学习(翻译) 微信公众号:机器学习养成记 搜索添加微信公众号:chenchenwings 机器学习工程师Bargava的文章《How to learn Deep Learning in 6 months》介绍了...

小沁_3ca9 ⋅ 04/09 ⋅ 0

Common Lisp 函数 require 和 provide 源代码分析

Common Lisp 函数 require 和 provide 源代码分析 涉及文件:l1-files.lispl1-init.lisp作者:FreeBlues2013-08-19 目录 0) 1) 2) 2.1) 2.2) 2.3) 0 概述(id:0) require 使用场景, 使用 quickl......

FreeBlues ⋅ 2013/08/19 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

vim编辑模式、命令模式

编辑模式 vim要从一般模式进入编辑模式只要按字母 i 、I、a、A、o、O键就可以了 要从编辑模式回到一般模式按键盘上的Esc键即可。 按键 作用 i 在当前字符前插入 I 在光标所在行的行首插入 o ...

黄昏残影 ⋅ 25分钟前 ⋅ 0

OSChina 周五乱弹 —— 如果有一天不当程序员了

Osc乱弹歌单(2018)请戳(这里) 【今日歌曲】 @guanglun :分享off的单曲《我唱情歌给你听》 《我唱情歌给你听》- off 手机党少年们想听歌,请使劲儿戳(这里) @小小编辑 :#如果不做程序...

小小编辑 ⋅ 32分钟前 ⋅ 4

从 Confluence 5.3 及其早期版本中恢复空间

如果你需要从 Confluence 5.3 及其早期版本中的导出文件恢复到晚于 Confluence 5.3 的 Confluence 中的话。你可以使用临时的 Confluence 空间安装,然后将这个 Confluence 安装实例升级到你现...

honeymose ⋅ 今天 ⋅ 0

Java8新增的DateTimeFormatter与SimpleDateFormat的区别

两者最大的区别是,Java8的DateTimeFormatter也是线程安全的,而SimpleDateFormat并不是线程安全。 在并发环境下使用SimpleDateFormat 为了能够在多线程环境下使用SimpleDateFormat,有这三种...

人觉非常君 ⋅ 今天 ⋅ 0

多线程如何控制执行顺序

线程的生命周期说明: 当线程被创建并启动以后,它既不是一启动就进入了执行状态,也不是一直处于执行状态,在线程的生命周期中,它要经过新建(New)、就绪(Runnable)、运行(Running)、...

MarinJ_Shao ⋅ 今天 ⋅ 0

用ZBLOG2.3博客写读书笔记网站能创造今日头条的辉煌吗?

最近两年,著名的自媒体网站今日头条可以说是火得一塌糊涂,虽然从目前来看也遇到了一点瓶颈,毕竟发展到了一定的规模,继续增长就更加难了,但如今的今日头条规模和流量已经非常大了。 我们...

原创小博客 ⋅ 今天 ⋅ 0

MyBatis四大核心概念

本文讲解 MyBatis 四大核心概念(SqlSessionFactoryBuilder、SqlSessionFactory、SqlSession、Mapper)。 MyBatis 作为互联网数据库映射工具界的“上古神器”,训有四大“神兽”,谓之:Sql...

waylau ⋅ 今天 ⋅ 0

以太坊java开发包web3j简介

web3j(org.web3j)是Java版本的以太坊JSON RPC接口协议封装实现,如果需要将你的Java应用或安卓应用接入以太坊,或者希望用java开发一个钱包应用,那么用web3j就对了。 web3j的功能相当完整...

汇智网教程 ⋅ 今天 ⋅ 0

2个线程交替打印100以内的数字

重点提示: 线程的本质上只是一个壳子,真正的逻辑其实在“竞态条件”中。 举个例子,比如本题中的打印,那么在竞态条件中,我只需要一个方法即可; 假如我的需求是2个线程,一个+1,一个-1,...

Germmy ⋅ 今天 ⋅ 0

Django第一期

安装Django 去https://www.djangoproject.com/download/ 下载最新版的Django,然后解压放到Anaconda\Lib\site-packages目录下,然后cmd进入此目录,输入安装命令: python setup.py install ...

大不了敲一辈子代码 ⋅ 今天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部