您好、欢迎来到现金彩票网!
当前位置:神州彩票app下载 > 公理语义 >

简单λ演算

发布时间:2019-08-05 20:55 来源:未知 编辑:admin

  在 20 世纪三十年代引入,Church 运用 lambda 演算在 1936 年给出(Entscheidungsproblem) 的一个否定的答案。这种演算可以用来清晰地定义什么是一个。关于两个 lambda 演算表达式是否等价的命题无法通过一个通用的算法来解决,这是不可判定性能够证明的头一个问题,甚至还在

  λ-演算可以说是最简单、最小的一个形式系统。它是在二十世纪三十年代由Alonzo ChurchStephen Cole Kleene发明的。至今,在欧洲得到了广泛的发展。可以说,欧洲的计算机科学是从λ-演算开始的,而现在仍然是欧洲计算机科学的基础,首先它是函数式程序理论的基础,而后,在λ-演算的基础上,发展起来的π-演算、χ-演算,成为近年来的并发程序的理论工具之一,许多经典的并发程序模型就是以π-演算为框架的。

  Lambda 演算可以被称为最小的通用程序设计语言。它包括一条变换规则 (变量替换) 和一条函数定义方式,Lambda 演算之通用在于,任何一个可计算函数都能用这种形式来表达和求值。因而,它是等价于图灵机的。尽管如此,Lambda 演算强调的是变换规则的运用,而非实现它们的具体机器。可以认为这是一种更接近软件而非硬件的方式。 Lambda演算表达了两个计算机计算中最基本的概念“代入”和“置换”。“代入”我们一般理解为函数调用,或者是用实参代替函数中的形参;“置换”我们一般理解为变量换名规则。后面会讲到,“代入”就是用lambda演算中的β-归约概念。而“替换”就是lambda演算中的α-变换。

  最开始,Church 试图创制一套完整的形式系统作为数学的基础,当他发现这个系统易受罗素悖论的影响时,就把 lambda 演算单独分离出来,用于研究可计算性,最终导致了他对判定性问题的否定回答。

  在 lambda 演算中,每个表达式都代表一个只有单独参数的函数,这个函数的参数本身也是一个只有单一参数的函数,同时,函数的值是又一个只有单一参数的函数。函数是通过 lambda 表达式匿名地定义的,这个表达式说明了此函数将对其参数进行什么操作。例如,“加 2”函数f(x) =x+ 2 可以用 lambda 演算表示为 λx.x+ 2 (λy.y+ 2 也是一样的,参数的取名无关紧要) 而f(3) 的值可以写作 (λx.x+ 2) 3。函数的作用 (application) 是左结合的:fxy= (fx)y。考虑这么一个函数:它把一个函数作为参数,这个函数将被作用在 3 上:λf.f3。如果把这个 (用函数作参数的) 函数作用于我们先前的“加 2”函数上:(λf.f3) (λx.x+2),则明显地,下述三个表达式:

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

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

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

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

  1.    标识符 (identifier) 的:{ x1,x2,x3,…}变元(变元的数量是无穷的,不能在有限步骤内穷举,这个很重要,后面有定理是根据这一点证明的)

  4.    λ,(,)  (辅助工具符号,一共有三个,λ和左括号右括号)

  λ-项在一些文章中也称为λ表达式(lambda expression),它是由上面字母表中的合法字符组成的表达式,合法的表达式组成规则如下:

  则所有的 lambda 表达式可以通过下述以BNF范式表达的上下文无关文法描述:

  说明1:通常,lambda 抽象 (规则 2) 和函数作用 (规则 3) 中的括号在不会产生歧义的情况下可以省略。如下假定保证了不会产生歧义:

  说明2:(λx.M)这样的λ-项被称为函数抽象,原因是它常常就是一个函数的定义,函数的参数就是变量x,函数体就是M,而函数名称则是匿名的。用一个不恰当的比喻来说,我们通常认为的函数f(x)=x+2,可以被表达为λx.x+2。因为+是未定义的,所以这个比喻只是为了方便理解而已。

  说明3:MN这样的λ-项被称为函数应用,原因是它表达了将M这个函数应用到N这个概念。沿用上面的例子f(x)=x+2,那么f(2)=2+2;同样的λx.x+2表达了f(x)的概念,那么(λx.x+2)2表达了f(2)的概念。其中M=λx.x+2,N=2,所以MN=(λx.x+2)2。

  说明4:注意说明3只是为了方便理解,但是还存在很多与直观理解不符合的地方。例如xy也是一个合法的λ-项,它们也是MN形式的,不过x和y都仅仅是一个变量而已,谈不上函数代入。

  说明4:这里的另一难点就是要区分变量和元变量,如:M=λx.x,这里x为变量,是我们在语法系统中定义了的,而M为元变量,没有在语法系统中定义,是我们用来表示的助记符。我们必须根据上下文来区分谁是变量,谁是元变量。

  上面是λ-项的形式化定义,有一些是可以与函数理论直观联系的,而另一些只是说明这个λ-项是合法的,不一定有直观的字面意义。

  类似 λ x. (x y) 这样的 lambda 表达式并未定义一个函数,因为变量 y 的出现是自由的,即它并没有被绑定到表达式中的任何一个 λ 上。在一个λ-项中,变量要么是自由出现的,要么是被一个λ符号绑定的。还是以函数的方式来理解变量的自由出现和绑定。例如f(x)=xy这个函数,我们知道x是和函数f相关的,因为它是f的形参,而y则是和f无关的。那么在λx.xy这个λ-项中,x就是被λ绑定的,而y则是自由出现的变量。

  直观的理解,被绑定的变量就是作为某个函数形参的变量,而自由变量则是不作为任何函数形参的变量。

  1.   在表达式x中,如果x本身就是一个变量,那么x就是一个单独的自由出现。

  2.   在表达式λ x. E中,自由出现就是E中所有的除了x的自由出现。这种情况下在E中所有x的出现都称为被表达式中x前面的那个λ所绑定。

  3.   在表达式(MN )中,变量的自由出现就是M和N中所有变量的自由出现。

  为什么要花大力气来给出变量自由出现的规则,是因为后面的很多地方要用到变量的自由出现的概念。例如α-变换和β-归约。

  一个不含自由变量的项称为封闭项;封闭项也称为组合子。最简单的组合子,称为恒等函数:id=λx.x

  来看两个λ-项,λx.xx和λx.(xx)有何不同?根据左结合的法则,λx.xx=(λx.x)x,其中第一个x是被λ绑定的,而第二个x则是自由出现的。而λx.(xx)中两个x都是被λ绑定的。这表明了两个λ-项中λx的控制域是不同的。

  α-变换规则表达的是,被绑定变量的名称是不重要的。比如说 λx.x和 λy.y是同一个函数。因此,将某个函数中的所有约束变量全部换名是可以的。尽管如此,这条规则并非像它看起来这么简单,关于被绑定的变量能否由另一个替换有一系列的限制需要遵循。

  首先是一个说明:如果M,N是λ-项,x在M中有自由出现,若以N置换M中所有x的自由出现(M中可能含有x的约束出现),我们得到另一个λ-项,记为M[x/N]。

  λx.M≌λy.M[x/y]  如果y没有在M中自由出现,并且只要y替换M中的x,都不会被M中的一个λ绑定。即:替换的变元不能在M中自由出现,并且也只替换M中的自由变元

  注意:M[x/N]定义出来只是一种记号,它不等于α-变换。既M!≌ M[x/y]

  α-变换主要用来表达函数中的变量换名规则,需要注意的是被换名的只能是M(函数体)中变量的自由出现。

  β-归约表达的是函数应用或者函数代入的概念。前面提到MN是合法的λ-项,那么MN的含义是将M应用到N,通俗的说是将N作为实参代替M中的约束变量,也就是形参。β-归约的规则如下:

  (λx.M)N à M[x/N] 如果N中所有变量的自由出现都在M[x/N]中保持自由出现

  β-归约是λ演算中最重要的概念和规则,它是函数代入这个概念的形式化表示。

  在 lambda 表达式的集合上定义了一个等价关系(在此用  标注),“两个表达式其实表示的是同一个函数”这样的直觉性判断即由此表述,这种等价关系是通过所谓的“alpha-变换规则”和“beta-归约规则”得到的。

  关系被定义为满足上述规则的最小等价关系 (即在这个等价关系中减去任何一个映射,它将不再是一个等价关系)。

  前两条规则之后,还可以加入第三条规则,η-变换,来形成一个新的等价关系。η-变换表达的是外延性的概念,在这里外延性指的是,两个函数对于所有的参数得到的结果都一致,当且仅当它们是同一个函数。

  下面说明了为何这条规则和外延性是等价的:(即由η-变换可以证明外延等价,相反由外延等价也可以证明η-变换)

  faga对所有的 lambda 表达式a成立,则当取a为在f中不是自由出现的变量x时,我们有fxgx,因此 λx.fxλx.gx,由 η-变换fg。所以只要 η-变换是有效的,会得到外延性也是有效的。

  相反地,若外延性是有效的,则由β-归约,对所有的y有 (λx.fx)yfy,可得 λx.fxf,即 η-变换也是有效的

  如果一个λ-项M中不含有任何形为((λx.N1)N2)的子项,则称M是一个范式,简记为n.f.。如果一个λ-项M通过有穷步β-归约后,得到一个范式,则称M有n.f.,没有n.f.的λ-项称为n.n.f.。

  通俗的说法是,将一个λ-项进行β-归约,也就是进行实参代入形参的过程,如果通过有穷步代入,可以得到一个不能够再进行代入的λ-项,那么这就是它的范式。如果无论怎样代入,总存在可以继续代入的子项,那么它就没有范式。

  一般的把一个λ-项规约为范式的过程称为求值,范式也叫做值。在《类型和程序设计语言》一书中,作者给出了λ-演算中的几种不同的求值策略。每个策略确定一个项在下一步求值中激活哪一个约式或几个约式。

  注意到在求值的过程中是左结合,并且当且仅当左边以是值了才能对右边的项进一步求值

  13.M≌N = MàN 如果y没有在M中自由出现,并且只要y替换M中的x,都不会被M中的一个λ绑定。

  如果某一公式MàN或者M N可以用以上的公理推出,则记为λ├MàN和λ├M N。

  证明是非常巧妙的,对于每个F,构造出的这个ww刚好是可以通过一次β-归约得到F(ww)=FM,如果再归约一次就得到F(FM),这样可以无限次的归约下去得到F(F(F(F…(FM)…)))。

  这两个定理告诉我们这样一个事实:如果M有一个n.f.,则这个n.f.是唯一的,任何β-归约的路径都将终止,并且终止到这个n.f.。

  Church-Rosser定理:如果λ├M N,则对某一个Z,λ├MàZ并且λ├NàZ。

  推论:MàN1,MàN2 且N1,N2都是范式 则N1≌N2 (范式在α-变换下的唯一性)

  关系被定义为满足上述两条规则的最小等价关系 (即在这个等价关系中减去任何一个映射,它将不再是一个等价关系)。

  对上述等价关系的一个更具操作性的定义可以这样获得:只允许从左至右来应用规则。不允许任何 beta 归约的 lambda 表达式被称为范式。并非所有的 lambda 表达式都存在与之等价的范式,若存在,则对于相同的形式参数命名而言是唯一的。此外,有一个算法用来计算范式,不断地把最左边的形式参数替换为实际参数,直到无法再作任何可能的规约为止。这个算法当且仅当 lambda 表达式存在一个范式时才会停止。Church-Rosser 定理说明了,当且仅当两个表达式等价时,它们会在形式参数换名后得到同一个范式。

  在 lambda 演算中有许多方式都可以定义自然数,但最常见的还是邱奇数,下面是它们的定义:

  以此类推。直观地说,lambda 演算中的数字n就是一个把函数f作为参数并以f的n次幂为返回值的函数。换句话说,Church 整数是一个高阶函数-- 以单一参数函数f为参数,返回另一个单一参数的函数。

  (注意在 Church 原来的 lambda 演算中,lambda 表达式的形式参数在函数体中至少出现一次,这使得我们无法像上面那样定义 0) 在 Church 整数定义的基础上,我们可以定义一个后继函数,它以n为参数,返回n+ 1:

  PLUS 可以被看作以两个自然数为参数的函数,它返回的也是一个自然数。你可以试验证

  在《类型和程序设计语言》一书中作者对于数和各种运算的编码描述得比较清晰,强烈建议看以下,并且作者还介绍了直接基于原始的布尔类型和数型的系统,简称为λNB,并给出了这两套系统之间的转换。

  习惯上,下述两个定义 (称为 Church 布尔值) 被用作 TRUE 和 FALSE 这样的布尔值:

  断言是指返回布尔值的函数。最基本的一个断言 ISZERO,当且仅当其参数为零时返回真:

  递归是一种以函数自身迭代自身变元的算法,一般是通过函数自身来定义函数的方式实现。表面看来 lambda 演算不允许递归,其实这是一种对递归的误解。考虑阶乘函数f(n) 一般这样递归地定义:

  这一节我也没分析透彻,只能原本引用,并且以上的内容也只能当作一个不严格的了解,暂时还不知道其有没有错,不过一点可以肯定的是上面定义的Y-组合子只能用于按名调用的情况,在按值调用的形式中是无用的,因为对任何g,表达式Yg发散。想要深入理解还是参看一下《类型和程序设计语言》这本书,不过书中也没深入的具体分析按值和按名调用的作用方式。其实这涉及到不同的操作语义的定义。想要在这里弄透还得找找论文看看。

  现在时兴讲函数式编程,弄得如果不会写两句λ表达式你都不好意思跟人说自己是敲代码的。所以我也就趁着这阵风头,琢磨琢磨了这个函数式编程。怎么算来,也有个三年两载了,出师还不敢说,将将入门估计还算凑合。朋友...博文来自:四纪启悟 · 数据科学

  λ演算时下函数式程序设计风格甚是流行,新出的语言,比如F#、golang天然支持;旧的语言c++、c#等则在不断添加对它们的支持。函数式程序设计的主要特点就是:值(value)是不变量;函数(func...博文来自:zdarks的专栏

  此系列文章是我学习lambda演算过程的总结与复习,着重于探讨“为什么(Why)”与“怎么做(How)”,也希望能对看到它的人学习了解这个形式系统有些微帮助。由于之前看了不少wiki、tutorial...博文来自:weixin_33721344的博客

  这一段接触代码多了,对各种的编程方法也有一些深入的理解。尤其是学习了LISP,稍稍有些心得。像LISP,使用最简单的语法,进行函数式的编程。按我的猜测,LISP来源于λ演算(从λ演算的3个原则派生为7...博文

  学习函数式编程的大图(bigmap)/鸟瞰图博文来自:yqj2065的博客

  摘录自:CIPS2016中文信息处理报告《第一章词法和句法分析研究进展、现状及趋势》P8-P11CIPS2016中文信息处理报告下载链接:博文来自:素质云笔记/Recorder...

  可计算性的概念是一个非常重要和美丽的数学观念。它又是相当近代的,具有这样基本性质的事体进入数学的王国是本世纪三十年代的事。这个观念已经渗透到数学的所有领域中去(虽然这一点确实是真的,但是大多数数学家...博文来自:对用语句构建世界的迷恋,以及对世界背后的话语的追索

  作者:离散梦欢迎大家给出宝贵的建议! 命题逻辑等值演算 一、等值式定义1设A,B是两个命题公式,若A,B构成的等价式为重言式,则称A与B是等值的,记作。 16组常用的重要等值式模式:1.双重否定律:2...博文来自:离散梦

  一个条状的计算器。 现有的计算器往往做的很炫、很复杂,但其实我们在进行绘图、统计分析等工作时,计算只是一件随手进行的辅助性工作。我们往往不希望计算器太过复杂、喧宾夺主。 这个小计算器只在屏幕右下角显示一个条形输入条,不遮挡主工作界面。而且...

  λ-演算的语法和语义.pdf λ-演算的语法和语义.pdf λ-演算的语法和语义.pdf

  算法流程1.计算中的set中每一个点与Xt的距离。2.按距离增序排。3.选择距离最小的前k个点。4.确定前k个点所在的label的出现频率。5.返回频率最高的label作为测试的结果。实现python...博文来自:Soul Joy Hub

  由简入深,适时复习,温故知新。λ演算基于最简单的定义函数的思想:一为函数抽象λx.E,由λ说明的x在函数体E中出现均为形参变元。E是一个λ表达式。一为函数应用(λx.E)(a),即E中的x均由a置换变...博文来自:housir的专栏

  一个前人写的有关Lambda演算的项目,里面包含了一个完整的关于Lambda演算的起源和讲解的pdf文件,还有能在不同平台下运行的解释器。Lambda演算是一套用于研究函数定义、函数应用和递归的形式系...博文来自:weixin_34342578的博客

  DNC是一种基于最小加代数的确定性排队分析理论,基于DNC可以分析数据流在网络传输过程中流量积压和传输延迟的上界,DNC分析的是最坏情况下的网络性能,使得通常情况下,网络资源的利用率都不高。SNC通过...博文来自:NgSunng的博客

  数据库中存储了大量的关系(表)之后,要对其进行增删查改等操作,其一般通过SQL类语言来实现,而语言实现的基础就是对关系进行一定的集合(关系代数)或逻辑处理(关系演算、域演算),然后返回处理结果。1、关...博文来自:Airuio的博客

  lambda演算根据维基百科,lambda演算(英语:lambdacalculus,λ-calculus)是一套从数学逻辑中发展,以变量绑定和替换的规则,来研究函数如何抽象化定义、函数如何被应用以及递...博文来自:zwvista的专栏

  一概念函数式编程(英语:Functionalprogramming),又称泛函编程,是一种编程范型,它将电脑运算视为数学上的函数计算,并且避免状态以及可变数据。函数编程语言最重要的基础是 λ演算(la...博文来自:crazyhacking的专栏

  lambda演算可说是函数式编程的基石,实际上已和函数式语言浑然一体了。不过聊起来可太数学了,反正已经证明lambda演算和图灵机等效了,不用去我们去操心了。现在java,c++,c#等语言要引进这些...博文来自:KISS

  定义5.1 设A,B是两个谓词公式,如果AB是永真式,则称A与B等值,记作AB,并称AB是等值式 基本等值式 第一组命题逻辑中16组基本等值式的代换实例以及推理定律的代换实例 第...博文来自:lyhan1998的博客

  关系演算可分为元组演算与域演算关系演算是基于元组进行操作而域演算是基于一列中的每个值进行演算,域演算的过程性较差域演算有QBE语言...博文来自:zrz0258的博客

  前言因为最近在学习组合范畴文法,也就是CCG(combinatorycategorialgrammar)。这种文法在表达语义的过程中使用到一些关于lambda演算的一些知识,所以在网上找到一些资料错略...博文来自:neuTblue的专栏

  λ演算维库,知识与思想的自由文库 Jumpto:navigation,search页面分类(2):计算理论递归论λ演算是一套用于研究函数定义、函数应用和递归的形式系统。它由AlonzoChurch...博文来自:Lu_ming的专栏

  上一篇我们已经建好了lambda演算大厦的地基,接下来需要了解的就是如何在此基础上构造用于计算的一些通用工具了,比如自然数、布尔值、基本运算和布尔运算等等。丘奇数(ChurchNumerals)在介绍...博文来自:weixin_33924770的博客

  域关系演算原子公式有两种形式: ⑴ R(x1…xk),R是一个k元关系,每个xi是常量或域变量; ⑵ xθy,其中x,y是常量或域变量,但至少有一个是域变量,θ是算术比较符。             ...博文来自:兜里有包包

  2.5关系演算关系演算是以数理逻辑中的谓词演算为基础的。按谓词变元的不同,关系演算可分为元组关系演算和域关系演算。本节先介绍元组关系演算,然后简单简绍域关系演算。......博文来自:iteye_3748的博客

  本书主要内容包括张量基本概念、张量的代数运算和微分学、Riemann流形上的张量分析和微分算子。除此之外,本书用很大的篇幅讲授张量在连续介质力学和物理学中的应用。特别是有许多内容是作者20多年来应用张量分析工具,建立相关力学、数学模型,发...

  first-order and higher-order paradigms.pdf

  pi演算作者当年的博士论文,值得一看!详细地介绍了pi-演算!pi演算作者当年的博士论文,值得一看!详细地介绍了pi-演算!pi演算作者当年的博士论文,值得一看!详细地介绍了pi-演算!

  导读1.元组演算2.域演算3.QBE语言4.关系演算的安全性5.三种演算的比较博文来自:hala22的博客

  u011244821:我发现一个奇怪的现象,报道中经常会出现苹果、谷歌因热更新机制而下架App,但是,却很少出现国内应用商店因热更新机制下架App的新闻。对于热更新,有人称之为病毒,陷用户于危险之中,难道这就是苹果、谷歌禁止热更新的原因吗?那为什么国内不禁止呢? 以上种种,都是我最近在的关于热更新机制文章中的疑惑,看到您发表的有关热更新技术的文章,能跟您请教一些问题吗? 为什么谷歌、苹果会禁止使用热更新功能? 据了解,苹果不是完全禁止热更新,React-Native 热更新机制是允许的。为什么它被允许,其他却被禁止? 谷歌在禁止力度上是比苹果还严吗? 国内有哪些App使用热更新技术?有哪些可看见的现象,像游戏打开时的更新,还有其他吗? 热更新技术的好处除了可以在不打扰用户的状态下达到bug修复,更新内容,方便快捷,还有什么其他优势? 有声音表示,热更新技术会被用来做恶,现实中有这样的例子吗? 国内有哪些应用商店会禁止热更新机制?是不是对热更新的态度比较宽松?

http://39-5963.net/gongliyuyi/700.html
锟斤拷锟斤拷锟斤拷QQ微锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷微锟斤拷
关于我们|联系我们|版权声明|网站地图|
Copyright © 2002-2019 现金彩票 版权所有