科技行者

行者学院 转型私董会 科技行者专题报道 网红大战科技行者

知识库

知识库 安全导航

至顶网软件频道基础软件Lambda算子6a: SKI组合子(上)

Lambda算子6a: SKI组合子(上)

  • 扫一扫
    分享文章到微信

  • 扫一扫
    关注官方公众号
    至顶头条

组合子是组合逻辑的基础构成。我们可以实现而returning 函数的实现原理,就是SKI组合子里的老二,K组合子。

作者: g9 来源:CSDN 2008年2月6日

关键字: 组合子 SKI Lambda

  • 评论
  • 分享微博
  • 分享邮件
我们常常需要创建一个对象。比如说Person,一个Person对象有绰号,有电话号码。一般我们会用这样的工厂方法:
01: def create_person
02:   person = Person.new
03:   person.nick_name = "g9"
04:   person.phone = "12345"
05:   person
06: end
这样写挺好。不过好像Ruby味道不够。毕竟我们希望把和创建Person有关的逻辑约束到一块儿。而Ruby里最
常用的“块儿”,就是block了:
08: def create_person
09:   returning Person.new do |person|
10:     person.nick_name = "g9"
11:     person.phone = "12345"
12:   end
13: end
上面代码里的returning,就是DHHActiveSupport里加的代码,让一个普通的创建函数变得更有Ruby
风味。从俺自己的角度看,也更符合《重构》里强调的精神:减少代码间的依赖。去掉无关的中间变量。
实现
returning
的代码灰常简单:
15: class Kernel
16:   def returning(value)
17:     yield(value)
18:     value
19:   end
20: end
也就是说,定义的函数returning把接受的参数传给对应的block( 隐含的第二个参数),再返回该参数。
返回该参数时,因为block的副作用,该参数已经被正确地更新。有了这个函数,我们可以实现而returning
函数的实现原理,就是SKI组合子里的老二,K组合子。
 
 
组合子是组合逻辑的基础构成。说到组合逻辑,不得不感叹一下它的命运多舛。1920年,Moses Schönfinkel还在哥廷根大学希尔伯特研究组(那个时代的数学系学生的口号是“打起背包,到哥廷根去吧”,可见哥廷根数学系的号召力之强)花差的时候,发明了组合逻辑。可惜1929年清洁工斯大林那B上台后,Moses就再没做过任何与组合逻辑有关的工作。他在二战爆发前夕回到苏联。1942年左右默默无闻地过世,卒月不详。俺强烈怀疑清洁工把他清洗了。后来同样是哥廷根出身的Haskell Curry读PhD时重新发现组合逻辑,并和他的学生Robert Feys着手把它发扬光大。可惜1933年优生学家希特勒上台,大搞不靠谱的雅利安人种净化运动。哥廷根数学系就此风流云散。犹太的非犹太的牛人们看到小布什那个原教旨红脖子还没上台,纷纷投奔新大陆。辉煌一时的欧洲数学中心开始慢慢转到美国。这是后话,扯远了。不世出的天才Alanzon Church隆重推出组合逻辑的函数化形式,Lambda算子理论,更是抢过组合逻辑的风头。直到上六七十年代理论计算机科学大热,组合逻辑才再次兴盛。
 
SKI三个组合子其实很简单。
  1. S: S是函数应用的组合子:S = lambda x y z . (x z (y z)).
  2. K: K 生成一个常数函数。当把生成的常数函数应用到任何一个参数上,都会得到K的第一个参数:K = lambda x . (lambda y . x).
  3. I: I其实是一个恒等函数:I = lambda x . x
初看之下,这些定义相当诡异。特别是S,应用机制很古怪 - 它没有直接取两个参数x和y,然后把y应用到x上。相反,它接受两个函数x和y,以及第三个值z,然后把x应用于z。得到的结果再应用到把y应用于z得到的结果上。
 
不过前人选择这样的定义是有原因的。看看下面的推导。每一行都从上一行规约得来:
S K K x =
(K x) (K x) =
(lambda y . x) (lambda y . x) =
x


哈!I组合子完全没有必要。我们用S和K得出了I组合子的等价物!后面我们会看到,不用任何变量,仅用S和K就能组合出任何一个lambda表达式的等价表达。再进一步,每一个lambda表达式都可以被表达为二叉树,数的叶子就是S或K。
 
比如说,Y组合子有如下等式:

Y = S S K (S (K (S S (S (S S K)))) K)
,用二叉树表示为:
 

 
 
查看本文来源
    • 评论
    • 分享微博
    • 分享邮件
    邮件订阅

    如果您非常迫切的想了解IT领域最新产品与技术信息,那么订阅至顶网技术邮件将是您的最佳途径之一。

    重磅专题
    往期文章
    最新文章