冒号课堂
第四课 重温范式（1）
课前导读
本课对函数式编程与逻辑式编程作了更详细的展开，并对前面介绍的范式进行了汇总分析，最后用情景式编程贯穿所学范式。
本课共分四节——
- 函数范式
- 逻辑范式
- 汇总范式
- 情景范式
4.1函数范式——精巧的数学思维
知不知，上；不知不知，病 ——《老子·德经》
关键词：编程范式,函数式编程,Haskell,Groovy
摘要： 再谈函数式编程
？提问
- 掌握编程范式对编程语感的提高有什么作用？
- 为什么声明式程序一般比命令式程序更简洁？
- 函数式编程有哪些特征？为何简洁而不失强大？
- 函数的无副作用性的意义何在？
- 相比过程式和OOP，函数式编程的弱点是什么？
：讲解
众人落座之后，冒号鸣锣开场：“上两节课为大家介绍了多种编程范式，虽未将所有类型尽囊其中，但最具代表性的均在其列。我们也不必贪多求全，俗话说得好：贪多嚼不烂啊。现在给大家一个知识反刍的机会。”
问号正感求之不得：“总算可以喘口气了。我们就像观光客，被导游带着从一个景点赶往另一景点。一天下来，虽然大开眼界，但都是走马观花，无法充分领略各地的风光。”
“你说得没错，我就是那个不近情理的导游。”冒号哈哈一笑，“类似时下流行的欧洲N国M日游，大部分人的收获就是一堆照片和日渐模糊的记忆。不出多日，如果不看标注，八成连照片上的背景是在法国还是在意大利都分不清了。”
逗号颇有同感：“差不多，目前我的收获就是一堆幻灯片和似懂非懂的概念。”
冒号料有此果：“这一点也不奇怪。别说几天游一个国家，单一个罗马，没有一个月是不可能深入了解的。至于编程范式，单一个OOP，没有两年以上的实践和思考，是难以真正领会其精髓的。”
叹号深表怀疑：“OOP需要两年以上才能领会？！”
“那还得看你是否有足够的勤奋和悟性。”冒号加强了语气，“前面说过，单靠记忆只能触及知识之表，单靠练习只能深入知识之里，唯有培养方能渗透知识之根。编程范式正处知识的根部，你们又怎能奢望只听几堂课即豁然贯通呢？”
引号表达自己的感受：“虽然学了不少东西，但也存了不少疑惑，搁在心里有点不舒服。”
“我明白你的意思。凡事追根究底是一种良好的学习习惯，也是一种可贵的学习精神。” 冒号表示理解和肯定，“但学习如打仗，除了要有直线式的纵深攻击，还要有曲线式的迂回包抄。回顾我们中学的课堂，往往是每引入一个概念或理论，便围绕其作深入的学习和反复的练习。在此过程中的种种疑惑，随着学习的深入都会烟消云散。这样稳扎稳打、层层推进，学得扎实，心里也踏实。但这种方法并不总是最好的，尤其在面临动态的、开放的知识体系时，难免左支右绌。为此，我们必须学会适度地容忍无知。请注意，容忍无知不是放任无知，而是一种学习的技巧，让无知成为求知的动力而不是障碍。容忍无知能使我们既不沮丧气馁，也不急于求成。在学习时不妨略过一些细节或难点，先概览全貌以获取感性认识，然后在逐步积累中升华为理性认识。要而言之，我们不仅需要强调钻劲和深度的‘钉子精神’，还需要强调磨功和广度的‘刨子精神’。我一口气兜售这么多编程范式，就是为了刺激大家求知欲，同时为大家进行第一道刨磨。”
引号得到一些安慰：“看来今后我们还会故地重游的。”
“不仅会重游，而且会‘深度游’。” 冒号肯定地说，“此番我们一路行色匆匆，若能感受到途中景色带来的感官冲击，便算是不枉此行了。其实，把编程范式类比旅游景点并不十分准确，或许比作当地的风俗文化更确切些。”
句号立刻会意：“景点是具体的，背后的风俗文化是抽象的；编程语言是具体的，背后的编程范式是抽象的。”
“此乃其一。”冒号右手伸出食指，“其二，如果不了解景点的历史文化和风俗人情，仅仅满足于表面的奇观异景，一切很快便会淡忘。比如说，你若不了解圣经文化、不了解文艺复兴史，则欧洲之行至多只是视觉的盛宴，而非文化的洗礼，收获将是有限的，印象将是肤浅的。同样，如果你不了解编程范式，那么眼中的编程语言只是语法、语义、核心库、规范等组成的集合，写出的代码虽能编译、能工作，却会显得生硬、别扭。就像中式英语，语法正确、表达也正确，可就是不正宗、不地道。其症结我们在第一节课中已经提过了，即所谓的语感缺失。”
问号实话实说：“可我还是不明白编程范式如何提高我们的编程语感。”
“那就让我们再说说范式吧。”冒号并不着急，“范式可以粗略理解为模范、模型、模式、风格、流派等等。软件中的范式除了编程范式外，还有架构范式[1]、数据库范式[2]等。比如，对象导向式（Object-Oriented）可以应用于编程、架构和数据库中，分别成为OOP（Object-Oriented Programming）、OOA（Object-Oriented Architecture）和OODB（object-oriented database）；类似地，事件驱动式（Event-Driven）可以是一种编程范式，可以是一种架构模型，也可以是一种设计模式。总之，每种范式都代表着一套独特而有效的解决问题的思想和方法。掌握范式对编程语感的提高至少有两层作用：首先，编程语言的语法、语义等都是从编程范式的树根衍生而出的枝叶，把握了这种脉络和节奏，代码才会如音乐舞蹈般韵律有致；其次，每种范式擅长的问题领域不尽相同，只有博闻广识，方可扬长避短，程序才会如行云流水般流畅自然。”
逗号添油加醋：“武功练至化境，一定是博采众长，就像杨过融合了东邪、西毒、南帝、北丐、中神通等各派武功，才能随心所欲地打出黯然销魂掌来。”
提起武侠人物，众人俱是逸兴遄飞，哪能体会到半点黯然消魂之伤？
冒号道：“天下之理，殊途同归。我们停止玄玄之论，用实例来说明吧。谁来介绍一下快速排序法(quicksort)？”
众人飞舞的思绪渐渐收敛，终于由引号作答：“快速排序法的思想是：在列表中找一个基准元素，将所有小于它的元素划归一个子列，置于其前；将所有大于等于它的元素划归另一子列，置于其后。然后递归地对前后两个子列作同样处理，直至最终。”
“很好，让我们用Java来实现一下该算法。”冒号显示出一段代码——
/** 快速排序法的Java实现 */
public class Sorter
{
public static <T extends Comparable<? super T>> void qsort(T[] list)
{
qsort(list, 0, list.length - 1);
}
private static <T extends Comparable<? super T>> void qsort(T[] list, int low, int high)
{
if (low >= high) return;
int i = low - 1, j = high + 1;
T pivot = list[low]; // 基准元素
for ( ; ; )
{
do { ++i; } while (list[i].compareTo(pivot) < 0);
do { --j; } while (list[j].compareTo(pivot) > 0);
if (i >= j) break;
// 交换
T tmp = list[i]; list[i] = list[j]; list[j] = tmp;
}
// 找到分割点j，递归
qsort(list, low, j);
qsort(list, j + 1, high);
}
}
“请问这里用到了哪些编程范式？”冒号提问。
叹号心想，有何难哉？遂答：“既然是用Java实现的，自然少不了OOP。同时为了使算法更具普适性，还用到了泛型编程。”
“你好像忘记了最重要的过程式，反倒是OOP的色彩极淡。”冒号显然不满意他的答案。
叹号不解：“不是说Java是100%的OOP语言吗？”
冒号颇为不屑：“不要轻信这种浮浅之论。且不说Java的基本类型（primitive type）不属于类（class），本就不是100%的OOP，即使是100%的OOP，那与过程式也不矛盾啊。此例中的Sorter类连一个实例成员（instance member）也没有，唯一与OOP沾边的是作为interface的Comparable，在C中也可用函数指针代替。如果不考虑泛型式的特征，本例无论用Java还是用C，并没有本质差别。事实上，对于这类纯算法的问题，OOP范式本无太多用武之地。换句话说，quicksort虽然是通过以OOP著称的Java来实现的，但用的主要还是过程式的思想和方法。”
问号赶紧问道：“还能用其他范式来实现吗？”
此问正合冒号之意：“我们改用纯函数式语言Haskell来试试——”
-- 快速排序法的Haskell实现
qsort :: (Ord a) => [a] -> [a] --函数声明
qsort[] = [] --递归终点
qsort(pivot : rest) = qsort[x| x <- rest, x < pivot] --对前面的子列递归
++ [pivot]
++ qsort[x| x <- rest, x >= pivot] --对后面的子列递归
叹号几不能信：“竟然可以如此精炼？”
“上面的Java代码很难再精简了，但与Haskell代码相比还是太冗长了。后者省去了所有的赋值、迭代和流程控制，只有单纯的递归，反映了典型的函数式特征。”冒号解说着，“鉴于你们对Haskell不太熟悉，我稍微解释一下。第一步，声明函数类型[3]：同类型列表之间的变换，其中Ord可类比Java中的Comparable，以保证列表元素之间能进行比较；第二步，声明递归终点：空列排序后仍是空列；第三步，描述递归原则：基准元素pivot与剩余子列rest进行排序后的列表，正是将小于基准的子列和超过基准的子列分别排序，中间插入基准元素后的结果。”
句号思有所得，不禁喜形于色：“我明白了，这两段代码生动地反映了命令式编程与声明式编程之间的差别：前者需要指定计算的过程，后者只需指定计算的原则。一个着重微观的细节，一个着重宏观的方向，自有繁简之别。”
冒号亦有所慰：“非常好！类似的话我以前也说过，但你们自己说的才是真正的收获啊。我们还提过，过程式与函数式的差别同时也是机器思维与数学思维的差别。不妨对比Haskell表达式与数学中的集合表达式，它们是多么地相近！”
黑板上出现两行式子——
数学表达式： {x| x ∈ rest, x < pivot}
Haskell表达式：[x| x <- rest, x < pivot]
逗号仔细打量着：“嗯，的确像，跟哥俩似的，连符号<-都是仿照集合属于符∈的。”
“还有另一种表达方法。”冒号又添加了一行——
Haskell表达式2：(filter (< pivot) rest)
“虽然与前一表达式的简洁度相差无几，但可读性更强。filter即是过滤，将列表rest中的元素进行筛选，条件是小于基准元素。”冒号讲解道。
问号略感迷惑：“（< pivot）的用法看起来有点怪异。”
“它是一个函数，也是filter的第一个参数，用来判断第二个参数rest的元素是否合格，即 < pivot。这体现了函数式的一个重要特征：函数是头等公民（first-class citizen）[4]——可作为传递参数、可作为表达式的值、可嵌入数据结构、也可与某变量绑定，与普通的基本数据类型毫无二致。这是函数式编程简洁而强大的重要根源。”冒号细加解释，“大家还记得上节课谈到的回调函数吧？callback无非是将函数作为参数来传递，本质上是将代码当数据来使用，回调机制的巨大威力均拜此高级用法所赐。”
众人又一段筋脉被打通了。
引号提出一个很实际的问题：“函数式编程的确很酷，可Java并不支持。如果采用Haskell之类的函数式语言，会不会带来系统集成上的困难？”
冒号打消了他的疑虑：“Java平台下已经集成了不少的支持函数式编程的语言，如JRuby、Jython、Groovy、Scala等，甚至Haskell在JVM下也有相应的Jaskell。其中Groovy与Java的结合最为自然，我们看一下它是如何实现quicksort的——”
/** 快速排序法的Groovy实现 */
def qsort(list) {
if (list.size() <= 1) return list
def pivot = list[0]
return (qsort(list.findAll{x -> x < pivot})
+ list.findAll{x -> x == pivot}
+ qsort(list.findAll{x -> x > pivot}))
}
“虽然比Haskell的代码略长了些，并且还带着过程式的烙印，但总体思想还是函数式的。”冒号紧扣本质，“函数式还有一个重要特征：无副作用或尽量减少副作用[5]。所谓无副作用，是指一个函数在被调用前后保持程序的状态不变。无副作用的函数不会改变非局部变量的值，不会改变传入的参数，也没有I/O操作。”
逗号脱口而出：“什么状态都不变，那这样的函数有什么用？”
冒号不以为奇：“你的这种想法源自根深蒂固的命令式思维。我们曾把命令式程序比作状态自动机，其运行过程就是在不断地修改机器的状态。而函数式程序则是进行表达式变换，一般不会改变变量的值。其实函数式并非完全不改变内存，只不过改变的是栈内存（stack）罢了。换言之，无副作用函数的作用关键在于其估值结果，按过程式的说法是返回值。”
逗号如梦初醒。
问号仍有疑问：“药物最好没有副作用，函数没有副作用的好处是什么？”
冒号嘴一咧：“好处太多了。首先，没有副作用的函数易于重构、调试和单元测试。其次，代码有效性与函数顺序无关，方便并发处理和优化处理。举个简单的例子，计算两个函数的乘积：f(x) * g(y)。由于无副作用，f(x) 和g(y)的估值过程是独立的，估值顺序也不重要，因此理论上可以对二者并行计算。另外，还可利用惰性计算（lazy evaluation）：如果算出f(x)为零，那么不用计算g(y)便可知乘积为零了。”
叹号忍不住赞叹：“听起来真不错！”
冒号言犹未尽：“最后，没有副作用的函数是引用透明的（referential transparency），即一个表达式随时可以用它的值来替换[6]，正如数学中的函数一样，保证了数学思维的贯彻和运用。”
引号自感获益颇丰：“前面介绍范式时，觉得函数式最为神秘。现在总算有了些感性认识了。”
冒号道出缘由：“函数式编程不仅有许多独特的概念和方法，还有很深的数学背景——λ-演算（λ-Calculus）。如果一开始便倾囊相授，你们必会望而却步，我岂不是打草惊蛇了？”
众人始觉：老冒原来是在诱敌深入啊。
“尽管函数式有这么多优点，运算能力从理论上比诸过程式也毫不逊色[7]，但一直没有成为主流范式，”冒号话锋一转，“细究之，至少有两方面的原因：主观上，程序员更习惯机器风格的过程式思维和现实风格的OOP思维，不容易接纳数学风格的函数式思维；客观上，函数式语言在表现力和运行效率等方面与过程式和OOP语言也有一定的差距。饶是如此，支持它的语言还是越来越多，其简洁精巧的特性也为越来越多的人所青睐。它的整体应用虽然主要集中于数学计算、人工智能等领域，但局部应用早已遍地开花了。”
，插语
[1] 如OOA（Object-Oriented Architecture），COA(Component-Oriented Architecture)，SOA(Service- Oriented Architecture) 、EDA（Event-Driven Architecture）等。
[2] 如关系数据库（relational database）、对象导向式数据库（object-oriented database）等。
[3] 这一步可省略，但出于对代码的清晰度以及性能、调试等方面的考虑，最好保留。
[4] 这类函数更数学化的说法是高阶函数（higher-order function）。
[5] 没有副作用的函数式语言被称为纯函数式（purely functional），如Haskell和SISAL；有副作用的被称为非纯函数式（impurely functional），如Lisp和ML。
[6] 这是因为函数的无副作用性保证了相同的输入一定有相同的输出。
[7] λ-演算被证明是图灵完备的。
。总结
- 学习知识之表须通过记忆，掌握知识之里须通过练习，渗透知识之根须通过培养。编程范式正是知识之根。
- 适度地容忍无知也是一种学习技巧。
- “钉子精神”固然可贵，“刨子精神”也不可少。
- 不同的编程范式代表不同的解决问题的思想和方法。不同的编程语言提倡不同的编程范式，并在语法上给予支持。只有掌握范式，才能更合理、更有效地运用编程语言的语法和语义特征，并能针对不同的问题领域使用不同的编程风格，编写的代码才会和谐自然、富于美感。
- 命令式编程需要指定计算的过程，着重微观的细节；声明式编程只需指定计算的原则，着重宏观的方向。因此二者繁简有别。
- 在函数式编程中，函数是程序的核心，是头等公民，一般没有或很少副作用，同时没有显式的内存管理。
- 由于函数式编程中的函数与基本数据类型平起平坐，故可将代码作数据用，这是程序既简洁又强大的原因之一。回调机制采用的正是函数式风格。
- 无副作用的函数容易重构、调试和测试，便于并发和优化处理，并能贯彻和运用数学思维。
- 相比过程式和OOP，函数式编程思想过于数学化和抽象化，语言的表现力和运行效率也有所不足。
“”参考
[1] Michael Lee Scott．Programming Language Pragmatics．San Francisco：Morgan Kaufmann，2000．589-620
[2] Stephen H. Kaisler．SOFTWARE PARADIGMS．New Jersey：Wiley，2005．23-24