Lambda算子6a: SKI组合子(上)
接以前的
Y组合子。这篇帖子大致基于
Good Math Bad Math的
文章，穿插点花边。强烈推荐原文。
哈！I组合子完全没有必要。我们用S和K得出了I组合子的等价物！后面我们会看到，不用任何变量，仅用S和K就能组合出任何一个lambda表达式的等价表达。再进一步，每一个lambda表达式都可以被表达为二叉树，数的叶子就是S或K。
说SKI组合子前，不能不谈去年红得发紫的
Ruby On Rails。Rails里一大模块是
ActiveSupport。该模块实现了很多帮助函数，大幅降低了Rails框架的编程强度。有兴趣地话不妨读一下它的源代码。当然，拜Ruby强大的meta-programming支持所赐，
ActiveSupport里函数赏心悦目的程度，远远不是Java一个*Helper.java或者*Utils.java能比的。咳，咳，不好意思，一不小心就开始鄙视Java了。另外一个帮助函数库是
Ruby Facets，非常有用。Rails和SKI有乜关系呢？嗯，本来没有，可DHH和一位叫Mikael Brockman的老大聊过以后，于2005年3月在ActiveSupport里
加入了一段代码。于是就
发生关系老：
我们常常需要创建一个对象。比如说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，就是DHH在ActiveSupport里加的代码，让一个普通的创建函数变得更有Ruby的
风味。从俺自己的角度看，也更符合《重构》里强调的精神：减少代码间的依赖。去掉无关的中间变量。
实现returning的代码灰常简单：
15: class Kernel
16: def returning(value)
17: yield(value)
18: value
19: end
20: end
也就是说，定义的函数returning把接受的参数传给对应的block（ 隐含的第二个参数），再返回该参数。
返回该参数时，因为block的副作用，该参数已经被正确地更新。有了这个函数，我们可以实现而returning
函数的实现原理，就是SKI组合子里的老二，K组合子。
函数的实现原理，就是SKI组合子里的老二，K组合子。
组合子是
组合逻辑的基础构成。说到组合逻辑，不得不感叹一下它的命运多舛。1920年，Moses Schönfinkel还在哥廷根大学希尔伯特研究组（那个时代的数学系学生的口号是“打起背包，到哥廷根去吧”，可见哥廷根数学系的号召力之强）花差的时候，发明了组合逻辑。可惜1929年清洁工斯大林那B上台后，Moses就再没做过任何与组合逻辑有关的工作。他在二战爆发前夕回到苏联。1942年左右默默无闻地过世，卒月不详。俺强烈怀疑清洁工把他清洗了。后来同样是哥廷根出身的Haskell Curry读PhD时重新发现组合逻辑，并和他的学生Robert Feys着手把它发扬光大。可惜1933年优生学家希特勒上台，大搞不靠谱的雅利安人种净化运动。哥廷根数学系就此风流云散。犹太的非犹太的牛人们看到小布什那个原教旨红脖子还没上台，纷纷投奔新大陆。辉煌一时的欧洲数学中心开始慢慢转到美国。这是后话，扯远了。不世出的天才Alanzon Church隆重推出组合逻辑的函数化形式，Lambda算子理论，更是抢过组合逻辑的风头。直到上六七十年代理论计算机科学大热，组合逻辑才再次兴盛。
SKI三个组合子其实很简单。
- S: S是函数应用的组合子：
S = lambda x y z . (x z (y z)). - K: K 生成一个常数函数。当把生成的常数函数应用到任何一个参数上，都会得到K的第一个参数：
K = lambda x . (lambda y . x). - 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)
，用二叉树表示为：
<shapetype id="_x0000_t75" o:spt="75" o:preferrelative="t" path="[email protected]@[email protected]@[email protected]@[email protected]@5xe" filled="f" stroked="f" coordsize="21600,21600"><stroke joinstyle="miter"></stroke><formulas><f eqn="if lineDrawn pixelLineWidth 0"></f><f eqn="sum @0 1 0"></f><f eqn="sum 0 0 @1"></f><f eqn="prod @2 1 2"></f><f eqn="prod @3 21600 pixelWidth"></f><f eqn="prod @3 21600 pixelHeight"></f><f eqn="sum @0 0 1"></f><f eqn="prod @6 1 2"></f><f eqn="prod @7 21600 pixelWidth"></f><f eqn="sum @8 21600 0"></f><f eqn="prod @7 21600 pixelHeight"></f><f eqn="sum @10 21600 0"></f></formulas><path o:extrusionok="f" gradientshapeok="t" o:connecttype="rect"></path><lock v:ext="edit" aspectratio="t"></lock></shapetype><shape id="_x0000_i1025" style="WIDTH: 418.5pt; HEIGHT: 317.25pt" type="#_x0000_t75"><imagedata src="file:///C:%5CDOCUME~1%5Cdannyy%5CLOCALS~1%5CTemp%5Cmsohtml1%5C01%5Cclip_image001.png" o:title=""></imagedata></shape>
困了。下面的明天继续吧。