1.不同编程风格的函数怎么定义？

指令式编程中对于函数的定义已经远离了我们一般函数概念。我们一般的函数概念是不同集合之间的映射规则[Rules of Mapping]，然而指令式编程严格地把对一个函数的描述划分为参数表，函数主体以及返回值。这是由于指令式编程最根本的内容是对地址的操作，因此指令式编程的函数定义基于一系列的赋值操作，最终植根于地址和值。然而函数式编程则是以函数本身为主体的。简单地说，它的基础是一组抽象的数据结构。输入的信息最终会转化成这种抽象的数据结构，输出的信息也是依赖于这种数据结构产生。关键问题在於，它不是地址和值，虽然它最终在硬件层面上也是依靠地址和值表示的。总之，事实上你不知道它是什么，因此它是抽象的。不同的语言中它有不同的表述方法。比如在Mathematica中它叫做表达式，而在LISP和Scheme中它就叫做表。但是无论在哪种语言中，它都可以解释为某种容器，以尽可能接近数学上集合的概念。那么在函数式编程中的函数便是基于这种结构的一种映射，或者更通俗地讲，叫做替换。

接下来我们再描述一次不同语言中的函数是如何实现的。一般来说，指令式编程风格程序的编译过程大概是这样，首先进行文法分析(Lexical analysis)，找到所有的符号(包括变量、函数名以及built-in标识符)，为那些需要安排内存的地方安排个住处。接下来就要将这些代码编译为汇编指令并进行代码优化。在汇编完成之后就要开始link。这个时候就要为程序代码按顺序记入内存中。程序执行时如果遇到函数，那么就把对应的参数按照形式参数的顺序带入函数中，接下来就从这个函数的地方继续运行下去。因此有按值传递和按地址(引用)传递一说。

关于按值传递和按引用传递的例子：
今天晚上关于下一周考试的题目 终于流传到了我们宿舍，我复印(copy)了一份，而老二直接拿着别人的。现在我和老二都要对小抄进行修改，那么就把这个小抄当成参数，而我和老二均可看作函数。我们上考场答的考卷则可看作函数返回值。然而，函数返回值此时不是我们关注的焦点，我们关注的是。但是我并没有对外层参数的值进行修改，我在处理时产生的新的变量，我复印的这个值最后没用了，交由垃圾回收机构处理，并且我将借的小抄还回去时仍和原来一样。而老二和别人用的是同一个小抄，因此这个改动就会保存下 来。很明显，所谓按值传递，就是在子程序应用参数时产生了一个新的等值变量，而按引用传递，则是子程序应用参数时指向了那个参数的地址。

事实上，目前所有的在指令式编程中出现的函数概念，严格地都应该叫做“子程序”。因为它无论从我们应用程序代码对它的描述还是实质，都是一系列对于实际值的搬运，而并不是抽象的规则。因此即使从程序的角度上讨论它也并不能叫做“函数”。

函数式编程的函数的理论基础是基于之前所提到的Lambda演算，之前提到过数学方面的定义和描述，现在需要讨论它在内存中如何工作。当一个Lambda函数生成时，它只是被解释成一系列的指令序列，这个指令序列在用时生成，一旦用完就立刻在内存中被标记为可以被抹去了。事实上，Lambda函数使得程序执行的效率大大变低了。首先，Lambda函数最终的实现方法还是子程序。但是由于Lambda函数引入了很多递归的性质，使得它在以子程序实现的时候引入了很多不必要的内容。换句话说，它没有子程序灵活，同时也无法像指令式编程一样对代码按照CPU的指令集进行进一步的优化。然而，从软件工程的角度上来说，过于灵活的语言势必造成代码的冗长，最终影响到了程序的开发时间。如果为了追求程序的运行效率而牺牲了更多的程序开发的效率，这样是很不划算的。

出于大型软件开发的目的，我不推荐Mathematica。它适合开发Prototype，但是对于那些要构筑永垂不朽的金字塔的同志们来说，我们仍然要拾起C++或Java。

2. 注记形式和数学

事实上，认真回顾一下数学的本质，主要是两个内容。

1)按照一定规则表示某些内容
这就是所谓的格式规则。比如我们记录一个n进制m位的数字的记法，代数式的记法，矩阵的记法，树、图的记法等等。它们本身没有意义。因为确切地说，它们就是将一个符号集合中的某些元素以某种方式排列而已。符号的写法区别的意义仅在于区分，单个的符号没有任何意义。

2)按照一定规则改变所表示的内容
这就是所谓的变换规则。变换规则通常和表示规则相对应。比如标量运算表达式和向量运算表达式在记法上的区别意味着它们将采用不同的运算规则。改变表示的顺序又可分为插入、删除两种操作，基于这两种操作又可以实现替换和交换顺序等等。沿用之前谈到的环缀表达式记法，两个对数相乘可以记作Plus[Log[a], Log[b]]，根据我们人为的定义，可以写为Log[Times[a, b]]。还有更为高深的如柏松括号这样麻烦的定义。

根据奥卡姆剃刀定律，把简单的事情搞复杂很简单，把复杂的事情搞简单很复杂。数学家此时正沉湎于manipulating各种复杂的符号，但是忘记了如何能够以一种非常简单的方式将它表达出来。就比如我们经常说的有效数字，譬如我们读最小刻度为1毫米的的刻度尺需要估读下一位，但是估读位后面的我们就认为是无效的了。假如测量值为3.1416m，那么这个数字就可以表示为

List[3, Dot, 1, 4, 1, 6, Indeterminate]

最后的Indeterminate代表后面的都不确定。Mathematica号称能够表示任意精度的数字，就是应用了这种注记形式。用这种注记形式的目的是为了统一。在Mathematica中做到了非常好的一点，就是化简了大部分的符号，使得各种表达式能够以简单有限的记号的组合来表示。这同SW本人所信奉的哲学也是类似的。我想这也是很多人觉得Mathematica不好用的原因之一，因为很多人期望的数学软件就是能用他们习惯的方法得到他们习惯的结果，但是Mathematica再尝试探索更简单的形式。

Speed my Mathematica up! by 陶悦 is licensed under a Creative Commons 署名-非商业性使用 2.5 中国大陆 License.

此文的绝大多数内容是基于Ted Ersek老师的Programming for Speed一文写成，我的贡献仅为翻译和“建立查找表”中关于动态规划的使用。如Preface中所说，Verbeia.com中还有很多很多有用的东西。

Mathematica效率编程

这是整个教程中最精华的部分，尽管它并不长。我们通过它养成一个好的写代码的习惯，使得我们Mathematica代码既有牛逼的功能又有迅捷的速度。这一章包含好风格的形成，以及在好风格的基础上如何将代码进一步优化。

1.建立查找表

公认的最快的计算方法就是寻找已经算出来的结果，无论是硬件层次的汇编语言还是高级的软件开发都认可这一点。而根据上一章执行流程的介绍，符号所具有的OwnValues在第三步就会执行，并且不再顾及后面的DownValues，也就是说尽可能用”=”赋值会使得程序运行更迅速。比如，虽然我定义了f[x_]:=BlahBlah[x]，但是在我的程序中大量出现f[1]，f[2]和另外几个特殊的值，那么就把这两个值单独列出来，于是执行器不会进行到后面的步骤，以及判断f的属性然后将啥啥啥规则带入进行计算。显然，这会节省大量时间。此外需要说明的是，在Mathematica中常用到的是这样一种形式：

f[x_PatternX]:=f[x]=BlahBlah[x]

它表示的意思是，当匹配PatternX类型的某个x的值出现时，执行BlahBlah[x]同时把执行结果存入f[x] (此处的x均指相应的某个值)。如果需要进行大量重复性的操作，那么它就可以实现一边运行一边建立查找表。这个技巧最伟大的实现就是动态规划。动态规划的核心思想就是在遍历的时候建立一个备忘录。举个比较容易的例子，就是去做一个数字三角形，从哪条路径由顶端至底端累计数字之和最少，题目见Project Euler[我目前这台机子上不了，很抱歉]：

Blah[i_, j_]:=Blah[i, j]=If[i==1, Initial[i, j], Min[Blah[i, j+1], Blah[i+1, j]]]

动态规划基本原则就是空间换时间。由于Mathematica的Kernel本身就维护着一个存有搜索路径的List，所以不需要我们重新建立一个这样的表了。不过要注意，在递归运行的时候会产生大量中间数据，所以当处理步数和搜索规模较大时，慎用。

2.应用FP工具

Mathematica的函数编程工具最大的优点就是不会破坏原有的数据结构。至于破坏原有数据结构会有什么问题会在以后讨论。函数编程的工具主要有这么几类：

并行操作: Map, Apply, Thread, Inner Outer … [省略了很多Map族的函数如MapIndexed, MapThread之类的] 具体用法请参考相关文档。并行操作的基本原理可以简单地描述为对原有表达式树形结构的结点插入、结点改写以及结点层次顺序交换。

迭代操作:Nest, FixedPoint, Fold, Scan … [省略了Nest族和Fold族的其他函数，Scan虽然关系不大，但是其定义是按轮次执行表中内容，故也放进了迭代操作类中] 迭代操作的基本原理是按要求把同一种操作不断叠加在同一个对象上，和高阶函数基本是一个意思。

3.应用匿名函数 (纯函数)

纯函数是直接定义的高效率的变换规则，它要比应用由”=”及”:=”定义的规则快很多，我认为也许是在引用的时间上得到了节约。

4.Checkpoint:切莫割裂原有的数据结构

1.避免使用AppendTo[] 以及PrependTo[]
如果需要追加元素，可以采取直接赋值的方式如ListBla={ListBla, ApElement}，或者ListBla=Join[ListBla, {ApElement}]，在整个追加工作完毕后应用Flatten。当然这要求ApElement最好别是List。如果是的话就改一下ApElement的Head，避免需要的括号也被Flatten掉，等到括号都推干净了再换回来就是了。事实上，对于几乎所有不涉及Dynamic[]的问题，完全可以一开始就把基础的数据结构整体地建立起来，而没有必要在后面才一个一个地追加。

2.某些场合避免使用Part[] ([[]])
这里涉及到两种用法，首先，提取元素的时候，能用First, Rest, Last, Most就不要用Take, Drop，而能用Take, Drop就不要使用Part[]。其次，比如两个表Blax, Blay的内积，Sum[Blax[[i]]×Blay[[i]], {i,1, Length[Blax]}]显然比Dot[Blax, Blay]要傻很多。

我们之前提到的在这里再提一次，表达式结构尽可能维持一个整体，如果数据结构被拆开，即意味着它在以后不会回到原来的整体了。

5.表达式越简单越快

1.简单的方法比复杂的方法快，如
Range[10^6]比Table[i, {i, 1, 10^6}]快

2.同样的方法，简单的写法比复杂的写法快，如
Table[{10^6}]比Table[i, {i, 1, 10^6}]快

3.同样的目标，语句少的比语句多的快，如
Norm[x_, y_]:=Sqrt[x^2+y^2]; Apply[Norm, RandomInteger[{-10, 10}, {10^6, 2}]]，就不如
Apply[Sqrt[#1^2+#1^2], RandomInteger[{-10, 10}, {10^6, 2}]]快

4.如果有一个Built-in函数能够实现其他Built-in函数的组合，那么前者不一定更快，如
有两个等长的List，Blax和Blay，进行的操作是把Blay的第i个元素插到Blax的第i个元素后面并构成一个新表，可以这样实现:
Flatten@Transpose[{Blax, Blay}]
也可以用6的新方法:
Riffle[Blax, Blay]
看起来有了这个新方法能实现专一的功能，但事实上前者比后者快！
[其实我原来一直认为后者比前者快，但是不保险实验了一下，结果发现我的直觉是错误的。事实上Mathematica中有很多种方法能够实现相同的目的，但是有的时候函数简单并不意味着效率高，所以如果有时间，还是要多试试其他方法。我觉得这也是Mathematica的乐趣之一。]

注意：通常我们测试用的计时器是Timing，它显示的是CPU时间，这有可能和我们感觉不太一样。事实上有更好的计时器，AbsoluteTiming，它和我们感觉上的时间更为接近。

6.优化代码

1.能用带有精度的实数，就不要用精确的数字
精确的数字就是表达式，比如Sqrt[2]就是Sqrt[2]，只有你输入N@Sqrt[2]它才会变成1.414…。后者在存储时结构更为简单，故速度更快。能在最开始化为实数的运算，就不要留到最后再化。这样能快很多。

2.善于利用Compile[]和Dispatch[]
前者能将数值函数编译为二进制码，并且忽略掉一些对数值函数没有影响的默认选项，使得运行速度更快。[这个答案是我问了Wolfram Technical Support得到的]。后者在上面提到过，但是具体工作方式并不清楚。

7.关于内存

ClearSystemCache[]
有的时候会出现提示，称MathKernel没有足够的内存进行工作，那么此时首先要做的就是把你之前工作留在内存里面的东西都清除掉。

Mathematica Hacking by 陶悦 is licensed under a Creative Commons 署名-非商业性使用 2.5 中国大陆 License.

探索Mathematica Kernel   [下文将简称为MathKernel]

如果在运行Mathematica的时候打开进程管理器，就可以看到除了一个Mathematica.exe之外还有一个MathKernel.exe。前者掌控着界面、notebook的格式以及代码高亮等等，而后者才是真正处理我们工作的部分。接下来我们就了解一下它是如何工作的。

[这部分内容由一名叫David Withoff的Wolfram内部高层人士写的。此人主管Kernel部分的开发，并且写过一本书，叫做Power Programming with Mathematica: The Kernel。虽然这本书是基于版本3写的，但我想对于现在来说仍然很有意义。在Wolfram的会议记录上有过一次关于MathKernel的讨论，原版是ps的，我把它弄成PDF了，上这儿看。以下内容主要就是基于这个文档写的。]

初始化MathKernel

1.创建List, String和Symbol这样的基本符号

虽然他们用来描述数据类型，但是他们自己本身也是Symbol类型的符号。它们是基础的抽象数据结构，详细请参考Computer Science with Mathematica书中的第十一章。

2.创建主要的符号表(symbol table)，所有在内存中的符号都位于这个表中，而这个表本身就是一个List

3.创建标准上下文(Context)，System`和Global`

Context:所谓context其实并不难理解，就好象C++的namespace，或者更熟悉的例子就是windows文件夹。换句话说，context是Mathematica存储变量的路径，这样同样名称的函数或者package出现在不同的context中不会引起冲突。譬如常量以及built-in函数都位于System`，而我们自己定义的变量和函数则都存储于Global`，同时我们也可为变量和函数定义它们自己的context。但是位于不同context的同名变量在调用时会覆盖掉已经位于内存中的那个，同时Mathematica会提示。如果应用Clear[]把当前context下的变量抹掉，这个变量仍然会存在，而它的context属性中对应的路径会被抹去。这个标准的上下文路径位于一个名叫$ContextPath的表中，这个表也是List。如果对context还有疑问，请参考这里。

4.将List, String以及Symbol类型的符号插入符号表中

5.建立特殊的上下文，如Integrate`

所谓特殊的上下文，是系统内建的标准路径。因为这篇文章写于1992年，那时的计算机硬件水平较低，因而如果把所有的Built-in函数全都装载到MathKernel里会减慢速度。因而那时设立了相当多像这样的上下文，这样使得用的时候再去装载，不会令系统崩溃。到了目前的第6版已经取消了像Integrate`这样的上下文，大量的Built-in函数被直接装载到了System`里面。不过还有很多其他非Mathematica主要功能，或者是第三方开发的package，需要我们自己去装再，具体请参考相关的文档。

6.建立Built-in符号与函数，并且与初始属性(Attributes)和其它变换规则进行关联。

Attributes:所谓attributes其实可以理解为副词，它决定了某些符号的行为方式。比如具有Listable属性的函数如Sin[]，输入Sin[{arg1, arg2, arg3}]，就等于输入Map[Sin, {arg1, arg2, arg3}]。Listable算是比较简单的属性，还有很多其他复杂的属性，有一些会在后面说明，具体请参考这里。

7.初始化快速处理表(Dispatch Table)，全局变量和其他内部算法的特殊结构。

Dispatch Table:在Mathematica中，存在一个Dispatch[]函数会对已经建立的规则进行优化，如果有很多数据需要通过规则代换处理，那么用它会节约很多时间。在下一章效率编程中我们仍然会提到它。事实上，Mathematica6在运行的时候还有一个叫做javaw.exe的进程。没错你猜对了，Mathematica6一定程度上就是基于Java虚拟机技术。在今年5月份Wolfram公司在清华的讲座上，我有幸和Wolfram的二头儿Theodore Gray交谈过一次。谈话确认了built-in函数比我们自己定义实现相同功能的函数快得多的原因，就是那些函数其实都是编译过的字节码。那些函数不仅在算法上都是最优的，而且代码的效率也是尽可能最高的。后来我又问Theo为什么Mathematica不能提供一个编译器或者是优化代码的装置让我们自己写的程序也运行的一样快，他说我们都给你做好了你还操心这个干嘛。果然Wolfram铁了心不开源。关于Dispatch请看这里。

8.将流(Stream)$Output, $Messages和$Urgent开放

此处的流和C++里面的基本一样。因为Mathematica兼容了部分C++的标准输入输出方式，换句话说，Mathematica也将文件和显示器均作为了输出位置。个人认为Mathematica既然不支持独立于MathKernel的程序运行，那么像这样的功能实在是多此一举。上述流的功能分别是为标准结果输出、信息以及警告的输出位置进行指派，它们可以流向显示器，也可以流向文件。关于这些流的帮助可以参考这里。

9.检验密码

看你用的是不是正版

10.执行-run参数的表达式

在Mathematica6的MathKernel和Math中均无法找到关于-run参数的说明，在网上也没有任何相关资料。估计它完全被废了。

11.装载init.m，并进入主循环(Main loop)等待输入

init.m是Mathematica层次上的基本配置文件。所谓主循环，说的是在一次Mathematica会话(也就是从输入完敲Ctrl+Enter开始至输出完毕到下一个in[n]:=出现)，中间调用代码解析器进行parsing, lexicalanalysis和evaluation。关于主循环请参考这里，Mathematica的文档会讲得比我详细很多。

再议Expression: 这丫到底包含了多少信息？

Expression分为两种，一种叫做正常的表达式，就是非常严谨地以Head[args]形式定义的，不正常的表达式就是字符串，数字和符号。虽然它们都可以写成Head[args]的形式 (String[], Integer[]和Symbol[]) ，但是它们就是不正常o_0。Expression在内部定义的形式类似C的struct或是Pascal的RECORD。在这个版本的文档中说Mathematica的精度和C是一样的，但是据我们所知Mathematica事实上可以表示任意精度的数字。事实上后来才知道，其实所有的数字都被表示成了表，或至少是正常表达式的结构。精度则是用一个叫做Indeterminate的常量控制的，它决定了某一位是不确定的，并且在它之后无论多少位也是不确定的。这个符号和Infinity类似，详情请参阅文档。

Expression保留了所谓的“参考计数”(Reference Count)， 参考计数用来记录已经执行过的Expression，如果有新的Expression被执行，那么原有的Expression的参考计数就会减少，如果减少至零，就相当于加上了一个标记声明它不需要继续呆在内存里。这个数字可以调节。

此外，如果你执行两次相同的Expression，那么你会发现两者所用的时间很不一样。这是因为第一次执行后，Expression和其结果被关联起来了。所以运行过的Expression包含的信息也包含其运行后的结果。

执行

如果Expression是一个数字或字符串，那么就原封不动地返回

如果Expression是一个符号且无OwnValue，那么就原封不动地返回。

OwnValue是符号本身的值，事实上赋值操作”=”其实就是为一个符号OwnValue赋值的过程

如果Expression子上一次执行后无任何变化，返回

接下来执行表达式Head h，并按以下方式执行表达式内部的元素e [下文中所说的表达式均是以h为Head的那一层]

如果h具有HoldFirst，HoldRest以及HoldAll属性，那么对应位置的e[第一个，除了第一个以外的以及全部的]都不执行

HoldFirst属性: h内的第一个项目不执行
HoldRest属性: h内除第一个之外的项目不执行
HoldAll属性: h内项目全不执行

这些属性尽管是阻止程序执行的，但并不意味着它们没有用。在调试程序时善于利用这些属性会很有帮助。

如果表达式内部存在以Evaluate为Head的元素，那么执行它

如果h具有上面说的几种Hold属性，或者表达式内有以Hold为Head的项目，但是有时又希望执行在这些标记为不执行的表达式之中的项目，那么用Evaluate[]就好了

如果表达式内部存在以Unevaluated为Head的元素，那么把外面的Unevaluate[]脱掉，然后将里面的内容留着不变

注意，Hold[]和Unevaluate[]均是标记不执行的表达式，但是区别在于在执行时Hold[]这个标记不会脱掉。比如Length@Unevaluated[{1,2,3,4}]结果是4，而Length@Hold[{1,2,3,4}]结果是1

如果h具有Flat属性，那么就把h的项目中同样以h为Head的表达式的h[]脱掉

具体来说，带有Flat属性的h意味着执行Flatten[expr, Infinity, h]       (expr指的是以h为Head的整个表达式)

如果表达式内包含带有Sequence[]的项，那么直接把Sequence[]脱掉

Sequence是比较好玩的东西，Sequence几乎和List一样，但是比List多两个特点：
1.Head[Sequence[…]]<==>Head[…]
2.Sequence[Sequence[…]]<==>Sequence[…]

就是说，Sequence自己就有Flat的属性，此外如果Sequence外面有有一层Head，那么它自己也被脱掉了。其实，Sequence[1, 2, 3, 4, 5]就是1, 2, 3, 4, 5。但是单纯的数列不能独立存在所以才有了Sequence。有点说不清，但是不难理解。

如果h具有Listable属性，那么对表达式内以List为Head的项，应用Thread

相当于对h里面所有Head为List的项目ArgList应用Thread[h[ArgList]]

如果h具有Orderless属性，那么对所有e进行排序

——————————————–等会儿再说分割线————————————————

应用用户定义的关联到e的UpValues属性

UpValue和DownValue:
之前曾经提到过，现在举个例子：

g/:g[x_]*g[y_]:=gtimes[x, y];
g[x_]:=Blah[x]

那么当我输入g[a]*g[b]时，出现的是gtimes[a, b]，而非Blah[a] Blah[b]。原因在于，符号g包含的定义属性包含UpValue和DownValue两种，DownValue就是后面要说的。而UpValue因为比DownValue先执行，因此就实现了在不与现有定义冲突的情况下对某些特殊的情况进行定义，并且这些特殊情况的定义优先执行。符号的UpValue属性可用UpValues[]查看，DownValue同理。此类定义方法，请参考帮助文档中的UpSet和Set，以及UpSetDelay和SetDelay。

应用系统内定义的关联到e的UpValues

如果e的Head为Symbol，那么应用用户定义的DownValues至e，如果不是Symbol则应用用户定义的SubValues

SubValues:
这东西一般不怎么常用。它指的是符号a有这么一种属性，就是a[x][y]=n。有的时候可能会有这种用法，就是用a[x]生成一组head，然后再把这些head应用到项目表[y]中对应的位置。所以，SubValue属性有可能是考虑到在这种用法上也会存在某些特殊情况才设计的。但是这种方法从我接触Mathematica以来从未见到有人用过。SubValues[]可以查看符号的SubValue属性，但是在第6版中并没有SubValues的文档。

如果e的Head为Symbol，接着应用系统内部定义的DownValues至e，如果不是，则应用系统内部定义的SubValues

如果没有更多的可以应用的规则，那么把原来去掉Unevaluated[]的地方再补回去

结束

小结：

我在那个位置划分割线的原因是，分割线之前，对于h后面项目的操作主要是集中在决定哪些要执行，哪些不执行，以及层次嵌套、顺序等问题上，而分割线之后，才是真正执行的部分。我们能够发现，真正执行的部分里面尽是些UpValue, DownValue等规则，这进一步说明了，MathKernel的核心实质上是一个规则代换的系统。事实上，所谓的函数式编程，和我们最开始介绍的谓词演算注记格式差不多，“函数式”仅是一个“式”而已，但是这种注记形式可以和规则代换紧密地联系在一起。不过真正的编译过程对我们来说是不可见的，事实上我们也并不在意程序内部真正的执行过程，既然在Mathematica中FP风格比用IP风格写的代码运行起来要快，那就姑且把它作为函数编程语言好了。无论怎样，我们Mathematica Hacker的宗旨始终是：简洁，高效，好玩。

Discussion on Programming Language by 陶悦 is licensed under a Creative Commons 署名-非商业性使用 2.5 中国大陆 License.

消歧义-Disambiguation

我们所有的语言都是一维的。我们既不可能在同一个时刻说出两个词汇，也无法在同一时刻理解两个词汇。同时，文字也是一行一行地书写，无论是从左往右还是从上至下。尽管我们可以用某些特定的词来表示某些意群之间的关系是递进、转折、并列或是让步，然而我们在阅读的过程中首先必须要做的事情就是分析每两个相邻的词之间的关系。由于这些关系都是线性的，如果某些意思出现缺失，就会影响到整个意群。在英文中有一个很著名的例子，“How time flies so fast”。按照一般习惯，它被理解成感叹句“光阴似箭”。但是我也可以这么理解，就是把fly看做名词(苍蝇，复数为flies)，而有一种苍蝇叫做“时间苍蝇”，现在请听题：“时间苍蝇怎么这么快？”

通过改写实现词性变化的英文都能产生歧义，就更不用说以增加成分实现词性变化的中文了，有这么个段子，说的是“西哈努克亲王八日到京”，因为“亲”字到了一页的最后一个字，于是被播音员念成了“西哈努克亲，王八日到京”。当然有人会说那句英文由于缺乏标点所以并不是一句完整的话，而如果加上问号或者感叹号问题就解决了。可是这仅是个很简单的例子。在英文中也很常见到需要上下文(Context)确定词义的情形。如果没有语境，那么很容易造成表义不清。为了确保一个表达能够精确地对应一个意思，语言学和逻辑学从数学借鉴了括号的用法。也就是说，我们用一种和语义无关的注记方式来分割意群，使我们可以在尝试理解表达内容之前先确定意群。目前最有效的一种方法被称为“谓词演算” (Predicate Calculus)。例如

“小明在看一个穿得很骚包的女同学，于是小明产生了邪念。”

按照谓词演算的注记规则，上句被表示为

IsLooking[IsXiaoming[x], IsFlam[IsGirl[y]]]->Think[IsXiaoming[x], evil]

其中， IsXiaoming 代表所指的是一个叫做小明的人类， IsGirl 代表所指的是一个人类女同学， IsFlam 代表所指的穿得很骚包， IsLooking代表所指的前者在看后者，Think 代表想，而evil是个常量，代表坏念头。x和y是两个不同的谓词变量，代表那个穿得很骚包的女同学和小明不是一个所指。中间的->表示可由前者推出后者。事实上，既然“推出”也是一种行为，那么上面的表达可进一步表示为
Deduce[IsLooking[IsXiaoming[x], IsFlam[IsGirl[y]]], Think[IsXiaoming[x], evil]]

我们可以发现，这样的句子不会产生歧义。因为每一个意群都被一个括号包含起来，而一个意群一定需要对应一个操作来表示。这个操作就是谓词，表示一个对某个对象的操作或者为某个对象添加属性。相信你能够注意到一下几点：

1. 它很像Mathematica的表达式
   不错，只要输入FullForm[Hold[expr]]，就会发现我们所有的输入都可以化成这种形式。
2. 它只由字符串(包括单个字符)、括号和逗号构成
   谓词演算就是因为这种简单的文法和清晰的表述才成功的
3. x, y以及evil都处于表达式的最深层，然而evil是常量而x和y不是，那么x和y到底是什么?
   在谓词逻辑中像x, y这样的被称为原子(atom)。在被施以操作或赋以属性前，它们什么都不是。
4. 这样的表达式可以写成树吗？
   显然可以。括号内容表示父子关系，而逗号表示同辈关系，每个字符串自然就是对应节点的内容。

小结：
消歧义到这里就结束了。我们了解了一般的自然语言是通过文字意思本身来界定意群的，这种方法由于规则宽松会造成歧义。如果我们需要让计算机准确地按照我们的意图工作，那么我们必须具有准确的表达规则来表述我们的想法。于是我们引入了谓词逻辑的这种注记形式进行消歧义。于是在判断一个句子的时候，我们可以在了解句子内容之前先划定意群，然后按照括号层次进行分析，正如我们在数学运算时对数学表达式的分析一样。
最后提到的问题并没有完全解决，它们都很重要，并且贯穿始终。

指令式编程-Imperative Programming [后文统称为IP]

指令式编程是一种编程风格。这种风格衍生出了很多子风格，如面向过程编程(Procedure Oriented Programming, POP)以及面向对象编程(Object Oriented Programming, OOP)。POP将代码翻译成一个todo-list，顺序执行每一步操作，同时要求每一步都要有具体的含义，否则程序无法运行下去。换句话说，POP是时序的。OOP则是引入很多概念，简单地说就是事件引发行为导致对象属性的改变。换句话说，POP是事件驱动的，但是在后文我们会说明POP仍然是时序的。但是总体来说，IP是这样一种风格:代码和数据严格区分，它们分别是操作行为和操作对象，角色分明。同时不允许有不明确的语言出现。当遇到一段代码时，计算机可以立刻了解到这个操作最终落实到那些指令；当遇到一段数据时，计算机也能追踪到对应的立即数或者存储器地址。

关于IP的根源，需要涉及到数字计算机的物理结构。数字计算机中所有的芯片都有一个晶体振荡器，简称晶振。由于在通电的情况下，晶体因压电效应会产生稳恒脉冲电信号，就数字电路的角度来说，就是逻辑电位的稳恒变换。数字芯片的基础是逻辑门电路和触发器，算术和逻辑指令也均是通过这些硬件电路实现的。它们必须依赖于时间公度来确定事件的先后顺序，否则就需要把所有的芯片之间都建立连接以获取当前的状态，而这显然是不现实的。晶振则很好地扮演了这个角色，所以它被成为时钟(CLK)。接下来，在冯@诺依曼确定了计算机的基本结构之后，代码和数据由于物理地址的区别而被分别对待。于是，此时的程序真的像“程序”一词的字面意思“进程的顺序”一样，就是一个列表，什么时候对什么对象进行什么操作。最早的机器语言，就是这样直接用二进制代码来控制芯片引脚的逻辑电平工作的。

后来出现了汇编语言。汇编语言的进步在于将机器指令转化成了稍微好懂一点的助记符。但是汇编语言仍然要求在实践上顺序执行的代码不能出现未定义的成分，包括无法识别的助记符和变量。再后来出现了更为人性化的语言，譬如COBOL, FORTRAN, ALGOL 60, PASCAL以及C，但是它们只是用不同的更简单的助记符对汇编代码进行替换，基本上在语法上相同的结构可以对应到同样的汇编代码上，这也导致了这些较高级的语言之间相互翻译并不困难。

之前提到了OOP的实质也是时序。这是因为OOP的思想是通过事件激发行为，而行为是对对象属性的改变。但是具体到内部的改变过程，仍然是POP。因此它可以看做POP和后文提到的规则编程的合成。

由于IP的所有代码都建立在对先验知识的基础上而不涉及后验知识以及对上下文的依赖，或者说在翻译的进程中能够严格确保不产生二义性，所以代码是很稳定的。于是Harold Abelson老师说了一句很经典的话：

Pascal is for building pyramids – imposing, breathtaking, static structures built by armies pushing heavy blocks into place. Lisp is for building organisms – imposing, breathtaking, dynamic structures built by squads fitting fluctuating myriads of simpler organisms into place. The organizing principles used are the same in both cases, except for one extraordinarily important difference: The discretionary exportable functionality entrusted to the individual Lisp programmer is more than an order of magnitude greater than that to be found within Pascal enterprises.  […] As a result the pyramid must stand unchanged for a millennium; the organism must evolve or perish.

Pascal是用来盖金字塔的——壮观，激动人心，由劳动大军们用厚重的砖瓦来构建静态结构。Lisp是构建有机体的——壮观，激动人心，由一小撮人将无数变化着的更简单的有机体来构建动态结构。对于两者而言组织的原则都相同，除了一个极为重要的差异：那些依赖于单独的Lisp程序员的自由变化的函数特性，要比能够在Pascal大厦中找到的多出一个数量级。所以，金字塔能够矗立千年不变，而有机体必须得不断进化，否则就会枯朽。

小结：
此处Pascal可以被替换成任何一种IP语言如C, FORTRAN之类的，并且指令式语言的特点也很形象地进行了说明。计算机的硬件几乎就是为IP设计的。IP的特点就是明确，明确地区分代码和数据，明确地指出每一步具体要做的事情，每一步的操作都一定要得到一个结果。这使得IP就像金字塔一样稳定，坚实。

请听题：什么是Lisp? 什么是函数特性？

函数式编程-Functional Programming [后文统称FP]

在上世纪三十年代，阿隆佐邱奇老师和斯蒂芬柯尔克里尼老师提出了一种新的形式系统，名字叫λ-Calculus，中文叫做λ演算。它被用来证明关于一些可计算性的问题（比如图灵停机问题）。所谓形式系统是指一套语言和一套语法规则。关于这个形式系统的严谨定义请参考λ-Calculus。为了便于理解，并且避免在和Mathematica关系不是很大的地方消耗太多时间，我在这里仅说明它的特性。

1. 它是递归结构，因为它的结构是递归定义的，通过括号的嵌套来实现。这一点和上文提到的谓词逻辑很类似。
2. 利用λ符号来定义变换规则。在别的地方是lambda，在Mathematica中是Function
3. 一切变量仅是用来表示关系，即约束变量。严格意义上说，没有可以代入数值的变量，即自由变量。

函数编程的思想基本继承了λ-Calculus。上文提到的Lisp就是λ-Calculus在编程方面的一次应用。而Lisp的开发者约翰麦卡锡老师正是阿隆佐邱奇的研究生。然而因为某些原因，which会在后面说明，Lisp并不是一个纯粹的函数编程语言。后来出现的Scheme, Haskell才是。那么函数编程的意义在什么地方呢？

1. 不需要赋值操作。
   因而编译器/解释器不是通过程序内出现的变量名和函数名进行寻址。
2. 没有复杂的值传递过程。
   由于代码是嵌套结构，所以内层的运算结果直接就成为外层的参数。因而不需要讨论如何传递的问题，按值传递和按引用传递是等价的。
3. 所有的函数都可以通过λ来定义，函数的规则随使用生成，随使用完毕而废弃。
4. “Lazy evaluation”
   如果在下文出现了对上文x新的应用，则上文所有x都会得到新的应用。这应用包括声明类型，采用定义等等。

FP更贴近于谓词逻辑，因而它能够自如地应付谓词逻辑中什么都不是的原子。如果是IP，遇到这样的x一定会提示“undefined variable”，但FP就会认为“如果x不是别的东西，那么x就是x，不管那么多”。同时，FP中倾向于打破代码和数据的区别，而把它们看做一个有机的整体。就像小明那个例子一样，所有的东西都包含代码和数据的双重身份，与其这样解释不如说它们既不是数据也不是代码，而是均为表达式。

此外，FP有一个很重要的原则，就是倾向于把所有的表达式看做一个整体，如果是对整体进行操作，那么就不把它拆开。如果要拆开，那么就意味着不再进行组合。这就好像拉面的师傅，通过反复地折叠把一个面团拉成一大把很细的面条，这个工作是一次完成的，而不是把面团拽成很小的粒，然后再把每一粒拽成一根面条。如果你经常使用Map和Apply，便会对此感触颇深。在Mathematica中，对List结构进行增删操作是很浪费时间的，因此尽可能不要破坏原有表达式。道理基本就和一根一根拽面条很费时间一样。但是，由于硬件层面上还是以IP为主，所以FP辛辛苦苦建立起的有机体在硬件层次上仍然被撕成碎片，然后一条一条执行。这造成了极为严重的效率瓶颈。尽管这个瓶颈正在慢慢化解。事实上MIT曾经专门为他们开发的FP语言Scheme设计过专门的芯片。不过FP中的匿名函数因为其灵活的特点，已经在Java的Scala和FunctionalJ，Python以及C++0x中得到了应用。

小结：
关于函数式编程，简单地说就是这么几个元素：括号递归，匿名函数和lazy evaluation。我往复杂里说说不好，因为已经有人无法超越了。在消歧义那节说了那段经典的话的Harold Abelson老师也写过一本很经典的书，叫做Structure and Interpretation of Computer Program，在这本书里面对于函数式编程从哲学到具体实施都谈得鞭辟入里。这本书自1965年成为MIT的教材以来一直沿用到今天。

注：
在之前的一个草稿中，我打算对这里进行详述，尤其是关于Mathematica的函数编程用法。但后来经过考虑还是删掉了这部分内容。它们在官方文档和各种教材中都写得很全面，并且对后文基本并无贡献。因此我只在这里说一句话，对于多个并列元素的操作，能用Map, Apply就不要用For这类控制流语句+单个元素操作+表的追加；对于嵌套控制，能用递归(Nest, Fold)就不要用循环(For loop, Do loop)；能用built-in函数就不要自己写，真的其实不丢人，一切以效率优先，效率自然同时考虑运行速度和你写代码的速度。至于里面提到的这些操作，还是自己查文档吧，毕竟这是进阶教程嘛。当然当然，至于高效编程的具体方法以后会做详细说明。
对了，我想起来很早以前我还写过一个笔记，虽然简单，但是也能说明一些问题，看这里

其实还有一个很关键的问题使我不能在FP上过多停留。还记不记得小明的例子？在Mathematica中，是不会把->替换成Deduce的！因为，规则定义才是Mathematica真正的核心。
那么，什么是规则？

规则代换编程, Rule-Based Programming  [下文简称为RP]

关于名字简短提一下，所有的Mathematica教材都这么称呼，“规则代换编程”是我根据这个英文以及个人使用经验直接翻译过来的。事实上它应该叫做Logic Programming。但是出于习惯且不会产生歧义，我仍然沿用RP的简称。没问题吧？

相对地，RP的定义更简单。其代码甚至很难叫做“程序”，因而个人认为RP叫做编程都不太恰当。事实上RP其实就是建立规则库的过程。经典的RP语言是Prolog，在Wikipedia上的描述可以看到它其实和我们最开始谈及的谓词演算很类似。它建立的代码看起来是这个样子的：

如果 条件1 Λ 条件2 Λ…Λ 条件n 那么 采取措施1 Λ 措施2 Λ…Λ 措施 n

关于它本身的我个人觉得没什么可说的，因为它事实上已经和人类的思维方式极其类似了。如果你学过数字电子电路，可能听说过一种叫做有限状态机的概念 (Finite State Machine) ，它也叫做自动机 (Automaton) 。它包含一套状态集合和一套规则集合，规则集合规定状态之间如何跳转。这和形式系统所定义的语言和语法极其类似，就像我们用语法规定出现一个词之后接下来的词的词性一样。如果说函数编程构筑的是一个树，那么规则编程则构筑的是一个更平凡的图。

事实上，规则编程本身并不是一个很具体的程序，它只能很模糊地告诉计算机在什么情况下该做什么，而真正该怎么做还是需要借助具体的指令来执行。而上文提到的面向对象编程则整合了这两者的优点，使得程序既具有动态性又能够顺利实施。我想这就是面向对象编程能够红起来的原因。

那么Mathematica到底是什么语言风格？

关于Mathematica语言系统的讨论: Pattern & Rules

从官方文档可以了解到，Mathematica三种风格都支持。Mathematica提供了类似于C的控制流语句 (如For, While, Do) 以及一些很类似的函数 (如Print)。FP在官方文档的Functional Programming里面也写得很全，而养成函数编程的习惯基本上只要遵守尽可能不破坏表达式结构这一条就够了。但是在文档和却很少提及，用的人也不太多，但是无论是文档还是在教材中，RP却很少被提及，用的人也不是很多(包括我本人)，然而它却触及了Mathematica的本质。所以接下来我们一起研究一下。

Mathematica作为RP语言，并不像之前提到的典型RP的格式。举个简单的例子。

A_Statement/.{Pattern→Another_Statement}

翻译过来，就是如果A_Statement中存在有符合Pattern的部分，那么这部分就会被替换为Another_Statement。而Pattern→Another_Statement便是一条规则(Rule)。

Pattern中文翻译过来叫做模式，可以理解把pattern理解为DOS下面的通配符，当然pattern涉及的范围可是比通配符广泛得多，它可以表示一切Mathematica表达式的类型。pattern可以定义不同类型的表达式，包括整数、实数、表以及字符串。当然，其实这些也都是表达式。所有关于Mathematica的pattern都可以在这儿找到。

Rules则需要具体说明。在Mathematica中一共有6种Rule，它们分别是

lhs=rhs
一旦执行，当前内存中所有的lhs都会被替换为rhs。而以后输入的包含lhs的部分也会被替换为rhs。作用于全局。

lhs:=rhs
运行且仅在lhs出现的时候才将lhs替换为rhs。作用于全局。

lhs->rhs
作为规则，定义之后并不起任何作用，只有受到/.的驱使才会起作用，针对/.之前的表达式进行替换。作用域仅为表达式。

lhs:>rhs
作为规则，定义之后也不起作用。它之于->的区别正如:=之于=一样。

接下来几个可能不大常见，解释起来也比较困难。它们是

f[args]=rhs
如果rhs中出现args，那么执行后无论args变成什么，f[args]都会变换为rhs。如果没有出现，那么这个变换只针对args成立


t/:f[args, t]=rhs 或 t/:f[t[args]]=rhs
它的用法是，不好意思我也不太清楚.我真觉得它没啥用啊

f[g[args]]^:=rhs
它的用法是，无论之前g定义为什么，只要上面的规则运行后，如果再出现f[t[args]]，则会被替换为rhs而不是之前t的定义。t既可以是变量，也可以是head。

在应用规则时对模式进行匹配有可能还不足以实现想法，有时需要对模式进行更多的约束，于是有了pattern test(?)和predicate(/;)。两者用法基本类似，具体用法请参考文档。事实上前者是真正地对模式进行检验，而后者是将模式带入符号后的一个纯函数内检测返回值是否为真。它们不仅能够应用在规则编程里，也可以应用在某些以真值为参数的函数编程语句，如Cases等。在后面的效率编程中关于List manipulation的介绍里会具体说明Cases以及类似的东西怎么用

Introduction by 陶悦 is licensed under a Creative Commons 署名-非商业性使用 2.5 中国大陆 License.

PREFACE

你将看到的东西很可能难以称为教材。我写这个东西的目的主要是为了消除国内很普遍的关于Mathematica的偏见。因为Mathematica的中文教材太少，因此大家只能依据自己很有限的知识来学习Mathematica。但我并没有打算写一份全面的中文文档，很多涉及到使用细节的地方我都尽可能的没有提到，或者给出了参考书目，或者直接提供了web链接。由于绝大多数的材料都是英文的，因此我假定读者同学们有一定的英文基础，能够读得懂Mathematica的官方文档以及一些对Mathematica使用细节详细介绍的英文教材如Mastering Mathematica，或者Computer Science with Mathematica。当积累了必要的使用经验后，再来看就很容易了。

这个tutorial最开始打算介绍很多内容，但是经过再三考虑我都删去了。因为认真研究过6版文档的用户都会发现关于使用细节其实文档都说得很详细了，因此我打算说一些文档中没怎么说的。所以最后经过整理，就只剩下了4节。第一节讨论了Mathematica从数学、逻辑学以及计算机硬件的基础；第二节开始深入探索Mathematica kernel的工作方式；第三节从效率的角度上对常用的操作进行了对比，并且会把很多Mathematica“奇技淫巧”穿插在里面，介绍如何能用最短的时间写出最快的Mathematica程序；第四节则介绍了Dynamic这个在6新出现的东西。关于它有很多值得说道的地方，但是文档里关于它的描述太过简短，我会拿它做做文章。

我的很多工作是基于Verbeia所总结的Mathematica Tricks完成的，事实上它才是真正的Advance Mathematica Programming Tutorial。如果读者有兴趣认真研究一下，绝对会有重大发现。

此外需要说明，为了探索Mathematica kernel的工作方式，会涉及到很多不常见的东西，事实上这些东西确实不好用，或者有更为便利的方法代替。所以我不会对它们作过多说明。