The Paradoxical Operator.

说起来我对院士好像一直没有什么好印象，唔，这么说似乎FQ了点，那至少当偶知道给偶们上离散的老师是传说中的院士+副院长的时候，偶的第一感觉是~寒=。=~

注意我的语气~按照套路作文写到这个地方就应该话锋一转：但是^^云云~没错~我就是会这么写……= =周二的离散课多多少少改变了我的这个印象，那个看上去完全想象不出他笑是什么样子的陈老头讲课的时候也可以笑得很自然嘛…喜欢说无厘头的笑话让我仿佛又回到了王殿军同学的课上~~~Anyway，希望偶的Discrete Math也能95哈~~~

设计Pandaria的时候偶然遇到匿名函数的递归这么个问题，就在离散上课前用教室的电脑随便Google了一下，居然读到了一些无比好玩的关于Lambda Calculus的文章~~记得以前接触这个还是在一本Programmer上，函数的Fix-point和递归的关系什么什么的，尽管现在看来这篇文章有点扯（Programmer上有点CS意味的文章一贯如此），当时还是勾起了我很多想法= =，呵呵，所以才会买那本The structure & interpretation of computer programs~~~唔，很美好的感觉^_^

Y = lambda G. (lambda g. G(g g)) (lambda g. G(g g))

The Paradoxical Operator. 

For example, a factorial program can be written with no recursive declarations, in fact with no declarations at all. First note that YF=F(YF); YF is a fixed-point of F.

    Y F
=   (lambda G. (lambda g.G(g g)) (lambda g.G(g g))) F
--> (lambda g. F(g g)) (lambda g. F(g g))
--> F( (lambda g. F(g g)) (lambda g. F(g g)) )
/*notice this step is also a beta-reduction...cool*/
=   F( Y F )

Using this observation it is possible to evaluate factorial(3) as follows.

let F = lambda f. lambda n. if n=0 then 1 else n*f(n-1)
in  Y F 3

--> Y (lambda f. lambda n. if n=0 then 1 else n*f(n-1)) 3

--> F(Y F) 3

=   (lambda f.lambda n.if n=0 then 1 else n*f(n-1)) (Y F) 3

--> (lambda n. if n=0 then 1 else n*(Y F)(n-1)) 3
                                                     
--> if 3=0 then 1 else 3*( (Y F 2) )

--> 3*( Y F 2 )
...
--> 6

太酷了