Java 语言中的函数编程

对Trustno1简直敬仰得五体投地，这几天天天上来看有没有新的章节。
这下子又要出系列文章了，这真是造福人类的伟大事业啊，呵呵：）
谢谢Trustno1的无私奉献与耐心讲解。
兴奋的期待下文。

因为SCIP的内容很多，我不可能按照书照搬照抄，有些知识并不太重要或者大家都已经清楚。我每次罗列一下提纲，选择一些重要的内容作为必讲，一些内容作为选讲。大家可以在选讲的内容中选择一些感兴趣的告诉我。
第一课的预备提纲
1，递归,树形递归，尾递归
2，high order和函数抽象
3, Lambda演算式
选讲:
1.算法复杂度
2.一些有趣的算法，求幂，牛顿法，素数检测

上个星期刚把这些内容看了。这次又有机会用中文来理解一遍。太感谢了。

呵呵，不过这本也是用了（好像）25年的老教材了，虽说是第二版……

至少，还没有出现比他更经典的软件设计教材了。听说你们上学期用standford那本CS0081还是多少反正就是一本C++库设计上的很糟糕阿。

躲在这里给人上课倒是上得很起劲啊，你不介意我把这些内容整理之后转到 ABP 去吧？等你同意了，我再去问 robbin 。

不过我不同意你所说的 imperative 语言背离图灵机模型的说法，不知道你这么说的根据何在。图灵机是有状态的，根据纸带上的内容、机器当前状态和转移函数移动读写头、改写纸带、变换状态，从其工作方式来看，显然更加接近 imperative 语言的做法。相反，lambda 演算的计算能力虽然与图灵机等价，但是它们可是两种非常不同的计算模型，而所有的 functional 语言基本上都是披着语法糖衣的 lambda 演算。

按照我的理解，冯。诺依曼模型的特点主要在于“储存程序”和“通用计算机”两点之上。在那之前，计算机基本上都是专用的，一台计算机解决某种特定的问题，是冯。诺依曼第一个提出了允许计算机存储程序，从而可以解决不同问题的做法。

PS：你这个家伙引我关于图灵机计算能力的描述，居然也不打个招呼，哇咔咔咔咔！  

我是在引用前人的经验么，你看我这一引用你就成了和牛顿一样的前人了。该怎么感谢我？10月4号你帮我付帐吧。
  
我么，也就是搞搞科普工作。你是已经成为某神的选民，拥有算法助教进阶职业，研习<TACP>这种传奇魔法的，比我够班100倍阿100倍的强者，怎能和我计较这些呢？
那段话的确有些问题，不过我的的意思是说，Van Nueman和图林机最大的区别在于，Van Nueman体系是要区分数据和程序的，但是图林机是不区分的。当然从图林机的状态覆盖这点来说，的确要比Lambda演算更加接近imperative语言。但是在数据程序不区分这点上，imperative语言是和他们两者都是相背离的。Fortran和Lisp的一个最大的区别，不就是在函数是不是first class这点么？Van Nueman体系可以化成图林机但是它未必就是图林机。最多只能说和图林机等价，与图林机等价的模型很多，但是总不能都说是图林机。当然我说的不全对，大家还是可以继续讨论。
PS:你不觉得ABP网站的效率要比javaeye慢很多么？想想办法turning一下咯

再度更正，和Van Nueman结构没有太大的关系。Van Nueman结构在程序和数据的问题上和Turing Machine是一致的。要说有不同也只是c++/Java语言没有能够体现程序即数据的观念。
看来，还是基本功还给老师了，sigh.真没有面子


VON NEUMANN ARCHITECTURE

Definition: A computer architecture conceived by mathematician John von Neumann, which forms the core of nearly every computer system in use today (regardless of size). In contrast to a Turing machine, a von Neumann machine has a random-access memory (RAM) which means that each successive operation can read or write any memory location, independent of the location accessed by the previous operation.

A von Neumann machine also has a central processing unit (CPU) with one or more registers that hold data that are being operated on. The CPU has a set of built-in operations (its instruction set) that is far richer than with the Turing machine, e.g. adding two binary integers, or branching to another part of a program if the binary integer in some register is equal to zero (conditional branch).

The CPU can interpret the contents of memory either as instructions or as data according to the fetch-execute cycle.

Von Neumann considered parallel computers but recognized the problems of construction and hence settled for a sequential system. For this reason, parallel computers are sometimes referred to as non-von Neumann architectures.

A von Neumann machine can compute the same class of functions as a universal Turing machine.

TURING MACHINE

Definition: A hypothetical machine defined in 1935-6 by Alan Turing and used for computability theory proofs. It consists of an infinitely long "tape" with symbols (chosen from some finite set) written at regular intervals. A pointer marks the current position and the machine is in one of a finite set of "internal states". At each step the machine reads the symbol at the current position on the tape. For each combination of current state and symbol read, a program specifies the new state and either a symbol to write to the tape or a direction to move the pointer (left or right) or to halt.

In an alternative scheme, the machine writes a symbol to the tape *and* moves at each step. This can be encoded as a write state followed by a move state for the write-or-move machine. If the write-and-move machine is also given a distance to move then it can emulate an write-or-move program by using states with a distance of zero. A further variation is whether halting is an action like writing or moving or whether it is a special state.

Without loss of generality, the symbol set can be limited to just "0" and "1" and the machine can be restricted to start on the leftmost 1 of the leftmost string of 1s with strings of 1s being separated by a single 0. The tape may be infinite in one direction only, with the understanding that the machine will halt if it tries to move off the other end.

All computer instruction sets, high level languages and computer architectures, including parallel processors, can be shown to be equivalent to a Turing Machine and thus equivalent to each other in the sense that any problem that one can solve, any other can solve given sufficient time and memory.

Turing generalised the idea of the Turing Machine to a "Universal Turing Machine" which was programmed to read instructions, as well as data, off the tape, thus giving rise to the idea of a general-purpose programmable computing device. This idea still exists in modern computer design with low level microcode which directs the reading and decoding of higher level machine code instructions.

A busy beaver is one kind of Turing Machine program.

Dr. Hava Siegelmann of Technion reported in Science of 28 Apr 1995 that she has found a mathematically rigorous class of machines, based on ideas from chaos theory and neural networks, that are more powerful than Turing Machines. Sir Roger Penrose of Oxford University has argued that the brain can compute things that a Turing Machine cannot, which would mean that it would be impossible to create artificial intelligence. Dr. Siegelmann's work suggests that this is true only for conventional computers and may not cover neural networks.

能否展示一些用来解决实际工程问题的例子？

我说怎么后背有点发冷呢，原来是有人想要折我的寿啊！就我这种差点在法师试炼中仆街的家伙，和你这样四处传播神的福音的正强者比起来，才是远未够班的废柴呀！况且 lambda 演算属于牧师神术，偶这种只懂一点点图灵机奥术的废柴法师，那是全然不能理解地 ……

程序既是数据这东西，怎么说呢，在我看来属于视角问题，无关于图灵机模型的本质。就图灵机而言，更接近我们平时所说的“程序”这一概念的东西并非是纸带上的内容，而是固化在图灵机本身内部的状态转移函数 —— 若是你也能遇到会在考试中让你构造完成乘法操作的图灵机的 BT 老师，相信你对此的体会一定更深（内心痛哭流涕）。因此，将一个图灵机直接视作一个机械化的算法会比较好，而构造一个图灵机其实就是写一个算法，或者通俗一些，写一段“程序”。受此影响，早期的计算机多数都是专用的，程序固化在计算机里面，而正是冯。诺依曼提出了“通用计算机”的概念，才促成了今天能够执行不同任务的计算机的出现。因此，lambda 演算我不敢妄言，但你要说图灵机模型具有“程序即数据”的性质，我是不以为然的。

至于你后面引的那一段描述，那是我们平时用来分析算法复杂度所使用的“RAM 模型”。这个模型比较贴近现实，用起来方便，而且和图灵机模型有多项式规约关系（是不是平方规约？），所以使用很广泛。不过我也不知道这东东还被称作“冯。诺依曼模型” …… 汗一个，孤陋了。

PS：你倒是同意不同意转载啊？
再 PS：我又不是 ABP 网站的管理员，找我有什么用？而且 ABP 的服务器在国外，估计再 turning 也快不到那里去。