Java 语言中的函数编程

呵呵，看来GEB都会涉及到的。

这下有福了:D

晚饭前和同学讨论一会儿
感觉自己以上的理解错了

下面是新的理解：


X其实可以理解为F的一种属性或性质
Y的作用就是在F中找出属性X
这种属性X的特征是在F作用其之前的状态和作用其之后的状态不变
即F的操作对X没有影响
反过来也就是说
X代表了F中的某种稳定的本质的东西
这对寻找和认识F有着关键的意义

因此Y作为找到X的钥匙就相当重要了
但这把钥匙该怎么找到呢？

Trustno1适合当老师，不会真是老师吧。呵，能把数学讲得如此生动，"可惜"了。

在开始新的课程之前，我公布一下上次那个查询table的答案
我们要求让CheckAge,CheckPostion,CheckGender能够传入参数，而不是hardcode.这里我们要用到的技术大体上和FP无关了。我们所需要做的就是overload Python类的()操作符__call__，让一个类看上去像一个函数。仅以CheckAge为例

class CheckAge：
    def __int__(self,age);:
           self.__age=age
      def __call__(Empee);: 
           if(Empee.Age< self.__age);: 
                return None 
          else 
               return Empee 

ca=CheckAge(20);
ca(Empee);
 

不动点定理，是20世纪50年代以来一个非常重要的数学发现，其影响可以说遍及整个数学界乃至与数学相关的其他交叉科学。最基本的不动点理论很简单使用高中数学就能理解，但是这个定理在拓扑上的推广却是很多科学的基石。例如我们耳熟能详的混沌理论，其理论基础沙可夫斯基定理就是从最基本的不动点定理经过简单的推广而得出的。好了请各位放松一下神经，我们今天不介入那么深奥的范畴。但是我们今天将试图从最基本的不动点定理关联到我们的Y Combinator，在课堂最后我们仍然会回来欣赏Eashor的那些作品。

一维布劳威尔不动点定理:
设f(x)是定义在[0，1]上的连续函数，且满足0≤f(x)≤1，则必存在x0∈[0，1]，使f(x0)=x0.
　　证 作函数 F(x)=f(x)-x．如F(0)＝0或F(1)=0，则0或1即为定理要求的x0，定理已成立(此时将有f(0)=0或f(1)=1)．由条件 0≤f(x)≤1知 F(0)＝f(0)≥0，F(1)＝f(1)-1≤0．故只需再在F(0)＞0和F(1)＜0的情形下证明定理．
　　由于f(x)是连续函数，故F(x)也是连续函数．因此当x由0出发变到1时，F(x)将从正值F(0)连续地变到负值F(1)，所以必至少有一点x0，使F(x0)＝0*．这正是f(x0)＝x0．

这个定理的证明足够简单吧。现在我们对这一定理作些说明．一个将某集A映到自身中的映射称为自映射．定理中的f是集合[0，1]上的自映射．称为f在A中的一个不动点．不动点不必唯一，如图中就画了三个，但是一个自映射的连续函数必然有一个不动点，这个就是一维布劳威尔不动点定理.现在回到我们的FP上来。上次的我给出的那个例子也是一个自映射，cfold1通过operator这个参数不断把自己作为参数，而输出的结果又是自己。当然这仅仅是和我们今天要讨论的Y Combinator在形式上一致，但是我们可以大致看清一个规律，那就是递归函数也是一种自映射。那么我们也能说递归函数也可能含有一个不动点。我们这个猜测是正确的，在Lambda calculus中也有一个不动点定理:
        
  这个定理用通俗的话来说就是任给一个Lambda 演算式Z，必定存在一个Lambda 演算式F使得FZ=Z(这里的lambda演算式可以理解为我们通常说的函数)。在Lambda calculus中的不动点定理基本的思想和一维布劳威尔不动点定理是一致的,但是他们又是不尽相同的.要说明清楚Lambda calculus中的不动点定理的证明需要非常多的预备知识，这里就不做展开了。我们只要明白这样一个基本规律，在自映射集合上的会存在不动点。
  好了和我们枯燥的数学说再见吧。我们如何在程序语言中表达这样一个神奇的不动点呢？因为Python和Lisp在语言表达上的限制，他们的Y Combinator过于的复杂。我们今天的大部分内容将采用Haskell这个新的语言进行表达。在Haskell中的Y Combinator 是这样表达的

 fix :: (a -> a); -> a
 fix f = f (fix (f););

第一行是fix这个函数的类型定义，这个定义说，fix这个函数的参数f 为一个函数这个函数的类型是接收一个类型为a的参数返回一个类型a，当fix接收到f以后将返回一个a。是不是像绕口令？对没有错，这就像我们一个笑话中说的那样，很久很久以前,山上有座庙，庙里有个老和尚，老和尚说:很久很久以前,山上有座庙，庙里有个老和尚说:..........
这个fix就是通过这种自映射来定义出来的。如果你觉得上面的说明令你头晕，没有关系我们用一个简单的例子将这个函数驱动起来。我们来看最简单的一个递归函数 计算阶乘

fact1 x | x<=1=1
       | x=x*(fact(x-1););

这是我们通常使用的阶乘，我们将其变化一下

 fact2 x = fix helper x
      where helper f x | x <= 1 = 1
                 helper f x = x * (f (x-1););

这里的where 相当于一种子函数的定义，这里的where块中定义了helper函数的。我们将其进行展开计算一个2的阶乘
fact 2 =
fix helper 2 =
helper (fix helper) 2 =
2 * (fix helper 1) =             
2 * 1 =
2
我们可以看到,通过fact和fix的复合作用完成了一次递归。问题是这样一种不动点有什么意义呢？我们再深入的问不动点定理的意义何在呢？请仔细的观察fact1和fact2两个函数。fact1是一个递归函数，而fact2不是一个递归函数(不要被f(x-1)迷惑了,f只是从外面传入的参数)。我想你一定在这样猜测，一个递归函数总是可以分解成为一个不动点和一个非递归函数。是的，Lambda calculus 就是这么说的:任给一个Lambda 演算式Z，必定存在一个F使得FZ=Z。在Lambda calculus 中一个lambda演算式只是类似Java中的一个表达式，他本身是不具备递归能力的。我们可以考察一下Python中的lambda函数

lambda x,y=x+y

这是一个函数，但是他没有名字因此无法实现递归。那么我们现在应该了解到，函数的递归性也就是可计算性是建立在不动点定理上的。我们在这里高谈阔论的各种语言，各种模式，各种软件都是由这个小小的fix point经过不断的自我复制而演算出来的。他就是计算机世界中的基因，是计算机世界中的上帝。如果没有这个定理，就不可能有计算机，程序，互联网，在座的各位也不大可能认识我。因此麻省理工学院的计算机系将其作为系徽是毫不夸张的。当然除了理论上的伟大之处外，在实际的应用中也有不少的妙用。我这里暂且说两个让大家开阔一下眼界。我们首先想象一下一个virtual Machine，例如c#或者java的VM，他们肯定要支持递归。但是我们知道任何递归都可以分解成一个fix point和一个非递归的表达式，那么也就是说你这个VM可以不用其他的算法支持递归，只要把这个fix point 编写到你的VM里去即可。另外我们知道递归函数的定义和van Nueman结构是冲突的，但是fix point的定义却可以很方便的在支持堆栈的计算机(也就是Van Nueman计算机)进行计算，也就是说fix point在FP和van Nueman结构之间架起了一座桥梁。至于更多的应用，如果以后有机会再深入下去的话我们再继续讲解。为了给大家一个思考上的锻炼，我把一个习题留给大家，在Python中我们同样也可以构造这样一个fix point,但是我们不能如haskell那样的定义。
因为haskell是lazy evaluation的，haskell的定义在python中将会引起一个infinit recursion。那么你们能够构造出一个相同的功能的Python fix point吗?
hints:我们还是可以从最简单的阶乘函数开始,我们知道像lambda x,y:x+y这种函数是无法实现递归的。但是有一种土方法，可以实现lambda递归:

def fact();:
    return lambda n:n and (n*(fact();(n-1););); or 1

你们要做的工作就是把fact从lambda中消除，而且不损失这个函数的递归性。
好了，在结束我们的课程之前。我们在回过来欣赏荷兰艺术家Escher的作品。在他的作品中，我们能够清楚地看到自映射的美妙之处，那幅<互绘的双手>里面到底是左手画出了右手，还是右手画出了左手？或许我们永远没有答案。或许我们的计算机本身也可以用这种方式来建立一个模型，请想象一下:最小的物理开关元件在量子力学里建模，量子力学用一组微分方程进行描述，微分方程的可以用一系列值进行逼近，这种数值又由计算机程序所描述，计算机程序的组成........。是不是很有趣？但是有趣的背后却是各种各样的困扰。这种自映射的作用最先深入到数学中，著名的哥德尔不完备性定理把好几代数学家追求完美的美梦打了个粉碎。在歌德尔之前，数学家们认为数学即是相容的，又是完备的。但是歌德尔的工作让数学家们要么选择完备性要么选择相容性。自映射让数学好像是建立在一个乌龟壳上的大厦。(关于歌德尔和数学的更多的问题可以参考上次庄表卫推荐的<确定性的丧失>一书。)当自映射影响到数学以后，他的影响就像他本身的特性一样迅速的扩散到任何与数学相关的领域。例如很多物理学家都认为，整个世界都是由一个小小的自映射作用发展出来的。著名的混沌理论就是这个方面前沿科学。但是根据自映射的奇怪特性让我们哭笑不得，我们有可能的确知道世界的本原的确来自一个小小的自映射，但是我们却可能永远无法发现他们。就像<互绘的双手>，我们的确知道这两只手的确是自映射的产物，但是我们永远无法找到他最原始的形态。因此，霍金断言基于自映射的超弦理论是不可能存在的，同样英国剑桥大学的彭罗斯也断言在目前基于自映射的语言符号体系下AI也是不可能的。好了，让这些扰人的理论问题留给物理学家和哲学家们吧。我们还是来欣赏一下自映射在巴洛克时期的复调音乐中的辉煌成就。所谓的复调音乐，就是有两个以上的声部各自独立组成旋律的音乐。和我们现在听到的主调音乐不同，主调音乐只有一个声部形成旋律其他声部作为打节拍的伴奏而存在。复调音乐最重要的形式就是赋格和卡农，在这一形式中成就最高的就是Bach。我们先来听一段大家都很熟悉的<勃兰登堡协奏曲第3号>BWV1048，G大调.在这首作品中Bach用了三把小提琴、三把中提琴、三把大提琴以及一把低音大提琴 将他们分为3个声部，分别各自模仿竞奏。在音乐开始的时候请你仔细的听第一个小节。你就会发现Bach使用的音乐材料及其简单:一个先下行再上行的音型，仅仅由三个音符构成,但是在Bach精湛的对位法下3个声部轮流出现，反复自我模进，放大，缩小，逆行，倒影，最终构成一个辉煌的音乐宫殿。
ftp://trustno1:trustno1@yyftp.vicp.net/Music/Karl_Richter__Bach__Brandenburg_Concertos_No3_1.mp3
另外一段是著名的<D大调卡农>，它是Bach同时期的音乐家帕和贝尔的作品。
如果大家看过<我的野蛮女友>就应该对这段卡农有些影响，全智贤独奏的那段就是这首<Cannon in D major>。所谓的卡农，简单的说就是，由一个声部先开始，随后声部模仿这个声部在另外一个声部出现，形成一种互相追逐的情况。
此声部间赋格式的模仿进行常是一模一样的就好像在唱轮唱曲一样。今天带来的是卡拉扬1983的柏林爱乐版，乐团的规模编制很大，有一种稳中而发木的感觉，缺少了巴洛克音乐的华丽轻快。但是很慢的时值，却能让你能够听出声部之间是如何自我模仿的。
[url]ftp://trustno1:trustno1@yyftp.vicp.net/Music/Cannon in D major.mp3[/url]
最后一段是Bach的巅峰之作<赋格艺术>。所谓的赋格和卡农一样也是一种巴洛克时期的音乐样式。Fugu原来是拉丁文意思是逃遁。一般来说赋格的总是首先在第一声部呈现主题，然后音乐家根据一种称为对位法的音乐技巧在第二声部上以不同的音高重复主题，称为“答句”（answer），此时第一声部配合审句的进行称为“对句”（countersubject），对句部分常常与原来主题形成对比。第二声合演奏主题后进入对句，第三声部重复呈示主题，如此互相模仿重复，构成整个音乐作品。Bach的<赋格艺术>是整个巴洛克时期的最高音乐成就，一般人们认为这部作品Bach旨在体现音乐中如同数学公式般的的抽象表现力。所以Bach在乐谱上没有指定使用任何乐器，因为他认为这部作品的抽象表现力足以适合所有的乐器(haha,是不是想到OO,interface,这些东西了？)。所以演绎这部作品有很多不同的乐器版本。我今天给大家带来的是科隆古乐团的古乐版本。如果由于音乐素养的关系，你不能听出前面两首作品中的自映射。那么这首bwv1080 一定能最清晰的表达出音乐中的自映射的魅力所在。
[url]ftp://trustno1:trustno1@yyftp.vicp.net/Music/001.The Art of Fugue (BWV 1080) - Contrapunctus 1.MP3[/url]

大作啊！受益匪浅。回头还要多多请教。

不过这好像已经不是java中的函数编程，而变成音乐中的函数编程了？

[为整体理解帖子顺畅，将本人无关言论删除]

如果对Python不熟悉，请参看这个Python的简明教程
http://www.chinesepython.org/pythonfoundry/limodoupydoc/dive/html/toc.html
一般来说，语法问题1个小时就能搞定，剩下的就是查reference的工作了，sigh现在的技术也大都如此。
至于Haskell么？我不太推荐你去看，上面几篇文章中的haskell是很简单清晰的。如果你有问题可以问我。
至于那些music,我也无能为力。你难道不能访问FTP么？只能用http?

我觉得这样零零散散的讲FP，总是不是个事儿，一来不系统说了后面要回过去说前面，二来大家总是没有概念，FP好在哪里，用在那里？俺打算根据MIT 6001的内容，做一些系列的文章。为何我推荐MIT 6001，因为我觉得这本书基本上囊括了中国大学四年所有的课程。对于这个坛子上好多半路出家的，或者本科学的稀里糊涂DX们来说绝对是一个很好的教材。这是其一，其二我觉得正像这本书
的作者harold abelson 在序言里面说到的那样"设计这门课的基础是我们的一种信念，"计算机科学"并不是一门科学，而且其重要性也与计算机本身没有关系。计算机革命是有关我们如何去思考的方式，以及我们如何去表达自己思考的一个革命。"。当我最初读到这本书的第二章数据抽象的时候，我真的很震惊。虽然只是薄薄80页的内容，但是囊括了我们大学一个学期的数据结构的过程。但是我震惊的不只是这些处理数据结构的方法。在整个第二章，我看到STL的数据与算法分离的思想，看到现在流行于OO的面向接口的编程，看到了现在Spring里面的IOC依赖注入。孔子他老人家说:"复习旧的知识就能掌握新的知识".。对比我大学里的那些数据结构的教材，它不仅仅是在教会你几个算法几个结构，当你阅读这些数据结构和算法的时候，你能够感觉到它是在传授你很多新的思想和方法。我当时就想，如果我大学里面就上这门课程我绝对不会为那些所谓的新技术一惊一咋。就如我的朋友Tut说的那样:"这个世界上本没有什么新鲜事情"。
这本书对于这里习惯于Java的朋友来说有两个障碍，一个是Scheme，这个语言
虽然很简单一天就能搞定，但是毕竟和大家的经验上的语言有很大的区别。一个是很难把这种抽象的函数式语言和我们平常工作使用的OO联系在一起。
所以，我就想把我看书以后的一些想法根据他的课程安排串联起来，同时使用python这个即有FP特性，又有OO特性的语言来讲解。这样大家即不会被语法
所困扰，又能够联系到我们的实际工作。当然Python在FP方面相比Lisp还是有一些小小的差距。所以有可能当Python无法表达的时候，我会采用scheme来进行一些描述。我想整个教程会分为这几块:
1.Procedure-Recursion-High order Function
2.Data Abstraction
3.Object,State,Module
4.Intepreter
5.Compiler

:o 天上真的掉馅饼啦!