泽民博客 ☰ Menu

lambda 演算中的布尔值和选择

Posted by 夏泽民 Mar 14, 2018

我们在lambda演算中引入了数字，只差两件事情就可以表达任意计算了：一个是如何表达选择（分支），另一个是如何表示重复。在这篇文章中，我将讨论布尔值和选择，下一篇将介绍重复和递归。

阅读全文

lambda Y组合子(y-combinator)

Posted by 夏泽民 Mar 14, 2018

lambda演算使用递归实现循环（递归的解释可以看这里）。 但是，由于在lambda演算里函数没有名字，我们得采取一些非常手段。这就是所谓的Y组合子，又名lambda不动点运算符。

阅读全文

lambda_Evaluation

Posted by 夏泽民 Mar 14, 2018

Peter Landin1965年在论文 A Correspondence between ALGOL 60 and Church’s Lambda-notation中指出的一样，面向过程的程序设计语言在λ演算模型的体系中是可以理解的，因为它提供了基本的过程抽象和程序应用机制。 匿名函数 以Lisp中的乘方函数为例,它可以使用lambda表达式表达为： (lambda (x) (* x x)) 以上是一个可以用作头等函数的例子。在这个表达式中，lambda创造了一个匿名函数并给予了它一个参数列表(x),虽然它只有一个参数，而(* x x)则是函数的主体。这个函数在Haskell中的实现是完全一样的。匿名函数有时候也被叫做lambda表达式。 再举个例子，Pascal和其它的命令式语言 长期以来都支持将通过函数指针的机制来将子程序 作为参数传递到其它子程序里面去。然而，函数指针并不是 函数成为头等函数类型的充分条件，因为一个头等数据类型必须要能够在运行时创建出一个它的实例。而支持运行时创建函数的语言有Smalltalk,Javascript,和最近的Scala,Eiffel,C#和C++11等。 归约策略 在编程语言的理论研究中，求值策略(Evaluation strategy)是一组用来确定程序设计语言中的表达式求值的规则。求值策略主要规定了在什么时候和用什么样的顺序给函数的实际参数求值，何时把参数代换入函数内，和用怎样的形式来进行代换。通常，人们使用λ演算模型中的归约策略来建模求值策略。 无论一个表达式是否为标准状态，将这个这个表达式化为标准型所需要的工作量很大程度上依赖于归约策略的使用。而归约策略的不同又和函数式编程中的及早求值还有惰性求值之间的不同有关。 1.完全β-归约 (Full β-reduction) 任何参数在任何时候都可以被归约，其实就是没有任何的归约策略，天知道会发生什么。 2.应用次序 (Applicative order) 最右边，最内部的表达式总是首先被归约，直观上可以知道，这意味着函数的参数总是在函数调用之前就被归约了。应用次序总是企图用标准形式去调用函数，即便在很多时候这是不可能的。 大多数的程序设计语言(包括Lisp,ML和命令式语言C和Java等)都被描述为严格类型语言，意思是使用了不正确形式参数的函数是形式不正确的。它们在实际上就是使用了应用次序和传值调用归约，但通常被成为及早求值策略。 3.正常次序 (Normal order) 最左边，最外部的表达式总是首先被归约，这也就意味着无论什么时候，参数都是再被归约之前就被替换进了抽象的函数体里面了。 4.传名调用 (Call by name) 和正常次序一样，但是不会在抽象的函数体中再进行归约，比如说，λx.(λx.x)x在这个策略中是正常形式, 虽然它包含了可归约的表达式(λx.x)x 5.传值调用 只有最外部的表达式被归约:一个表达式仅仅当它的右边已经被规约为一个值了才会被归约 6.传需求调用 “传需求调用”和传名调用类似，如果函数的实参被求值了，这个值就会被存储起来已备未来使用。它产生的结果和传名调用一样；但是如果函数的这个实参被调用了多次，那么传需求调用可以提高程序运行效率。它在现实语境中也被叫做惰性求值。 并行与并发 函数式编程在一开始就是面向并发处理的，这也得益于lambda的性质，lambda演算的Church-Rosser性质意味着归约(β归约)可以以任何顺序进行，甚至是并行来进行。这意味着各种不同的非确定性归约策略都是相近的。然而，lambda演算并不提供任何直接的并行结构。一个人可以添加像Futures结构体这样的并发结构体到lambda演算中去。相关的进程代数已经为了进程通信和并发而被研究了出来。 在λ-演算的基础上，发展起来的π-演算、χ-演算，成为近年来的并发程序的理论工具之一，许多经典的并发程序模型就是以π-演算为框架的。

阅读全文

从Lambda演算到组合子演算

Posted by 夏泽民 Mar 14, 2018
阅读全文

Lambda 演算

Posted by 夏泽民 Mar 14, 2018

计算机科学，尤其是编程语言，经常倾向于使用一种特定的演算：Lambda演算（Lambda Calculus）。这种演算也广泛地被逻辑学家用于学习计算和离散数学的结构的本质。Lambda演算伟大的的原因有很多，其中包括：

阅读全文

Search

Blog Categories

jekyll (35)
web (334)
technology (2)
php (201)
linux (415)
spark (51)
deep_learning (2)
storage (290)
golang (1081)
cryptology (15)
lang (74)
docker (100)
zookeeper (11)
elasticsearch (86)
java (7)
algorithm (134)
hadoop (2)
slug (1)
architect (46)
k8s (107)
node (82)
python (18)
mysql (42)
rust (4)
elasticSearch (1)
arch (1)
Javascript (1)
kafka (2)
nginx (7)

Popular posts

Anything in here will be replaced on browsers that support the canvas element

Recent posts

Tags

This blog is maintained by 夏泽民

Get in touch with me at 465474307@qq.com

Subscribe to our mailing list

* indicates required