Lambda演算与科里化(Currying)
Lambda演算
早在现代计算机问世以前,Lambda演算(λ演算)已经由图灵的老师阿隆佐·邱奇(Alonzo Church)引入。这种演算可以用来清晰地定义什么是一个可计算函数。它包括一条变换规则(变量替换)和一条函数定义方式,Lambda 演算的通用性在于任何一个可计算函数都能用这种形式来表达和求值。因而,它等价于后来提出的图灵机。Lambda 演算对函数式编程语言有巨大的影响,比如 Lisp 语言、ML 语言和 Haskell 语言(后面还会提到Haskell这个人)。
简介
在Lambda演算中的每一个表达式都代表一个单输入(单参数)的函数,函数的输出(值)仍然是一个这样的函数。例如一个简单的增值函数 f(x) = x + 1在Lambda演算中我们可以这样表示:λx. x + 1。这里的x叫做这个Lambda表达式的参数。相应的f(2)可以表示为:(λx. x + 1)2。特别的这里的参数也可以是一个类似的函数,在Lambda演算中所有函数都是匿名函数,它们既可以是其他函数的返回值也可以是参数,下面来看一个稍微复杂一点的例子: (λ f. f 3)(λ x. x+1) 。这个表达式的意思是说要将f 3这个行为应用到我们先前定义的函数λ x. x+1上去。该表达式等价于(λ x. x + 2) 3 = 3+2。
Lambda演算的形式化定义
Lambda演算的过程是由若干个Lambda表达式构成的。一个Lambda表达式包含了一组变量v1, v2, …, vn,以及抽象符号‘λ’和‘( )’。这些Lambda表达式的集合Λ递归地定义如下:
如果 x 是一个变量, 则x ∈ Λ
如果 x 是一个变量且 M ∈ Λ, 则 (λx.M) ∈ Λ
如果M, N ∈ Λ, 则(M N) ∈ Λ
科里化(Currying)
科里化的概念最早由俄国数学家Moses Schönfinkel引入,而后由著名的数理逻辑学家哈斯格尔·科里(Haskell Curry)将其丰富和发展,Currying由此得名。它表示一种将一个带有N元组参数的函数转换成N个一元函数链的方法。前面提到的Lambda演算使用的都是1元函数,在有两个或者多个变量的情况下就要使用科里化了。
Currying的过程
Currying如何进行的呢?不妨来看一个直观的例子, 假设有如下函数:f(x, y, z) = x / y +z. 要求f(4,2, 1)的值。
首先,用4替换f(x, y, z)中的x,得到新的函数g(y, z) = f(4, y, z) = 4 / y + z
然后,用2替换g(y, z)中的参数y,得到h(z) = g(2, z) = 4/2 + z
最后,用1替换掉h(z)中的z,得到h(1) = g(2, 1) = f(4, 2, 1) = 4/2 + 1 = 3
很显然,如果是一个n元函数求值,这样的替换会发生n次,注意,这里的每次替换都是顺序发生的,这和我们在做数学时上直接将4,2,1带入x / y + z求解不一样。在这个顺序执行的替换过程中,每一步代入一个参数,每一步都有新的一元函数诞生,最后形成一个嵌套的一元函数链。这些一元函数和之前提到的Lambda演算中的单输入的函数是一回事。于是,通过Currying,我们可以对任何一个多元函数进行化简,使之能够进行Lambda演算。用C#来演绎上述Currying的例子就是:
<!--<br /><br />Code highlighting produced by Actipro CodeHighlighter (freeware)<br />http://www.CodeHighlighter.com/<br /><br />-->Func<int,Func<int,Func<int,int>>>func=x=>y=>z=>x/y+z;
Console.WriteLine(func(4)(2)(1));//显示3
偏函数应用
Currying的概念将函数式编程的概念和可变参数结合在一起,一个带n 个参数,科里化的函数固化第一个参数为固定参数,并返回另一个带n-1 个参数函数对象。这有点像我们求一个多元函数的偏导数的过程,这种函数将任意数量(顺序)的参数的函数转化成另一个带剩余参数的函数对象。这种行为也有个类似的名字---偏函数应用(Partial Function Applications)。
这里以Python 3.0中的PFA为例,要用到偏函数功能需要先导入functools模块。
当然,还可以让一个函数接收另一个函数作为参数,比如下面的求和函数:
<!--<br /><br />Code highlighting produced by Actipro CodeHighlighter (freeware)<br />http://www.CodeHighlighter.com/<br /><br />-->>>>defjustSum(func,L):
returnsum([func(item)foriteminL])
这样就可以用它来接收我们定义的任意函数,并对它们在L上的值求和了。比方说我们可以通过这样的方式来求平方和:
<!--<br /><br />Code highlighting produced by Actipro CodeHighlighter (freeware)<br />http://www.CodeHighlighter.com/<br /><br />-->>>>sqrsSum=partial(justSum,lambdax:x*x)
>>>sqrsSum([1,2,3,4,5])
55
C#中也有类似地实现,不过受委托强类型的限制,比较难看:-(,(见阅读资料[3])
阅读资料
[1]http://en.wikipedia.org/wiki/Lambda_calculus
[2] http://en.wikipedia.org/wiki/Currying
[3] http://blogs.msdn.com/wesdyer/archive/2007/01/29/currying-and-partial-function-application.aspx
黄季冬
2009年10月22日
分享到:
相关推荐
λ演算(lambda calculus)是一套用于研究函数定义、函数应用和递归的形式系统。它由阿隆佐·邱奇和他的学生斯蒂芬·科尔·克莱尼在20世纪30年代发明的。 λ演算可以被称为最小的通用程序设计语言。它包括一条变换...
个人收集的一些关于lambda演算的国内外资料和课件,请笑纳
lambda演算简介
λ演算的学习资料,英文版,可计算函数和lambda演算规则
详细演示lambda演算过程,最后给出Y组合字实现匿名递归
函数式编程入门概念之一,lambda演算是函数式编程的数学理论基础...
有关于lambada演算,程序设计原理、语义语法的文献
一个 lambda 演算的解释器实现
与以前的尝试不同(例如二进制lambda演算),它使用lambda项与输入上的ℕ之间的双射以及规范化的lambda项与输出上的ℕ之间的双射,因此任何数字/字符串都可以视为输入或输出。 例如,这意味着询问字符串的...
这里的目标是从lambda演算构建完整的函数式编程语言。 当前功能包括数字,运算符,字符串,列表和let语句。 该语言经过编译,并通过虚拟机进行评估。 即将推出的功能包括: 显式递归let语句 内置布尔 与守卫的模式...
无类型的lambda演算解释器 在ghci中运行 $ ghci > :l Lambda Lambda> main 要使用ghcjs编译并使用Node.js运行,请执行以下操作: $ ghcjs -o lambda Lambda $ node lambda.jsexe/all.js 抽象器是克拉符号^因此...
Lambda演算Lambda演算是一种非常小的编程语言,由Alonzo Church于1936年发明。 它的功能等效于PHP中的Turing Machine lambda-php Lambda演算解释器。 Lambda演算Lambda演算是一种非常小的编程语言,由Alonzo Church...
纯非类型化lambda演算和类型化lambda演算(FL)的解释器。 *当前,GUI键入模式暂时被禁用以进行维护。 该语言使用Typescript。 您可以将其与git clone一起使用,但也可以。 您现在可以做什么 可以处理纯的未类型化...
lambda演算解释器 什么: 用C ++编写的小型lambda演算解释器。 它支持α转换和β减少,以及精确跟踪替换和重命名的输出。 如何: 支持标准的lambda演算语法,例如: (λz.(((λx.(λy.x)) z) ((λx.(λy.x)) z)))...
Scala 中的类型级 lambda 演算 此存储库演示了 Scala 类型中 lambda 演算的实现。 无类型 lambda 演算 import lambda . _ case class Equals [ A > : B < : B , B ]() // this checks type equality type S = x ...
lambda演算解释器 这是lambda演算解释器lc的代码。 lc会按正常顺序(从最左到最先)减少beta和eta。 lc将重命名绑定变量以防止捕获变量。 建筑 我没有做GNU风格的autoconf脚本。 我确实编写了相当严格的ANSI C(我...
相依型Lambda演算此项目是对“”论文的源代码的重组。 这个项目的目标是使代码可读性和可理解性。 有兴趣的读者也可以查看。 该项目的目标是使代码的读取和导航尽可能简单。如何玩例子单纯型Lambda演算$ stack run ...
malc-制作Lambda演算 关于 Malc是用于以任何支持编程语言实现无类型的指南和规范。 λ演算有时被称为世界上最小的编程语言。 它是一个完全由功能和功能应用组成的符号。 甚至“原始值”也表示为组合器,即没有全局...
6 课:lambda 演算简介 [ ][ ][ ] 第 7 课:使用无类型 lambda 演算计算递归函数 [ ][ ][ td + 视频] 第8课:简单的lambda演算,教堂编码[ 视频] [ 注释] [ td + video ] 第 9 课:简单类型的 lambda 演算和笛卡尔...
天空lambda Haskell中的未类型化lambda演算该项目希望成为无类型lambda演算的简单但灵活的实现。它还将支持“模块”,这将使编写更大的程序变得容易得多。注意事项这仅是一个研究项目,而不是高效的编程语言!由于这...