冒号和他的学生们(连载6)——基本范式

冒号和他的学生们

——程序员提高班纪事

  1. 基本范式

人生最伟大的目标是行动                                           ——《洛克菲勒的忠告》


第二课伊始,冒号开门见山:“首先介绍的是最基本的两种编程范式:命令式和声明式,其中命令式又称过程式。通俗点说,命令式编程由命令序列组成,即一系列祈使句:‘先做这,再做那’,强调‘怎么做’;声明式编程由相关表达式组成,即一系列陈述句:‘已知这,求解那’,强调‘做什么’。学术点说,命令式编程是电脑(von Neumann机)运行机制的抽象,即有序地从内存中获取指令和数据然后去执行;声明式编程是人脑思维方式的抽象,即利用数理逻辑或既定规范(specification)对已知条件进行推理运算。”

引号嘟囔着:“大多数语言好像都是命令式的。”

冒号接口道:“语言的演化是渐进的,大多数语言追根溯源是汇编语言的升级,而作为与机器语言一一对应的汇编语言自然是命令式的,因而这种范式最为传统和普及。声明式语言则发轫于人工智能的研究,主要包括函数式语言和逻辑式语言。其实它们的出现并不比命令式的晚多少——最早的函数式语言LispLISt Processor)已有半个世纪的历史,最早之一的逻辑式语言PrologPROgramming in LOGic)也与C同龄。只是由于大多数更多地用于学术研究而非商业应用,颇有些‘养在深闺人未识’。起源的不同决定了这两大类范式代表着迥然不同的编程理念和风格:命令式编程是行动导向(Action-Oriented)的,因而算法是显性而目标是隐性的声明式编程是目标驱动(Goal-Driven)的,因而目标是显性而算法是隐性的。为便于说明,下面分别用三种代表性的语言来实现阶乘(factorial)运算。”

冒号在黑板上打出投影——

C(命令式):

int factorial(int n)

{

     int f = 1;

      for (; n > 0; --n) f  *= n;

      return f;

} 

Lisp(函数式):

(defun factorial(n)

(if (= n 0) 1                          //  n等于0,则n!等于 1

       (* n (factorial(- n 1)))))      //  否则n!等于n* (n-1)

Prolog(逻辑式):

// 0! 等于1

factorial(0,1).

// M等于N-1 M!等于FmF等于N*Fm,则N! 等于F

factorial(N,F) :-   M is N-1, factorial(M,Fm), F is N * Fm.    

冒号提问:“撇开语法细节,大家说说以上三段代码区别在哪里?”

句号沉思片刻,答道:“C明确给出了阶乘的迭代算法,而Lisp仅描述了阶乘的递归定义,Prolog则陈述了两个关于阶乘的断言。”

冒号很满意:“一语中的!第二个问题:你们更习惯哪一种思维方式?”

逗号不加思索:“当然是第一种!”

冒号微笑着说:“这证明你至少是受过一定训练的程序员。大家回想一下,当你们初学编程时,是否习惯这种思维方式?”

叹号沉吟道:“好像不太习惯i = i + 1之类的语句。”

“对!”冒号的一嗓子吓了众人一跳,“我们最早接触的变量是代数方程中的xyz等,本质上是抽象化的符号,变量值是该符号在给定约束条件下的允许值。而命令式编程中的变量本质上是抽象化的内存,变量值是该内存的储存内容。通俗地说,前者好比姓名,所指之人是固定的;后者好比住址,所住之人是变化的。此外,等号在代数中是一种约束,而在许多命令式语言中则表示赋值。因此i = i + 1可以在命令式编程中出现,但绝不可能在数学推理中出现——除非在反证法中。”

叹号又道:“现在回头再看代数,反倒有些不习惯了。”

“这就是思维的定势效应。”冒号感慨道,“声明式编程让我们重回数学思维,其中函数式编程类似代数中的表达式变换和计算,逻辑式编程则类似数理逻辑推理。其中的变量也如数学中的一样,是抽象符号而非内存地址,因此没有赋值运算,不会产生变量被改写的副作用,也不存在内存分配和释放的问题。这既简化了代码,也减少了调试——不妨想一想,有多少bug是由于某个变量被意外改写或内存管理不慎而造成的?”

问号问道:“声明式语言与命令式语言看来是两个世界的产物,它们有何相通之处?”

冒号答道:“首先,所有高级语言都建立于低级语言之上,最终转化为机器语言,声明式语言也不例外。其次,声明式语言与命令式语言并非泾渭分明,而是互相交叉渗透的。一些‘非纯粹’ 的声明式语言也提供变量赋值和流程控制,而一些命令式语言也在逐渐发展,通过调用其他软件或增加新的语言特征来实现声明式编程。总的说来,在命令式语言中融入声明式的元素应当是一种趋势,尤其是函数式,它的一些特征已经在许多命令式语言中得到了支持。比较而言,声明式编程重目标、轻过程,专注问题的分析和表达而不致陷入算法的迷宫,其代码也更加简洁清晰、易于修改和维护。”

逗号仍然有些疑惑:“既然声明式编程有这么多好处,为什么命令式语言不仅占大多数,而且流行程度也不减呢?”

冒号回答:“编程语言的流行程度与其擅长的领域关系密切。声明式语言擅长基于数理逻辑的应用,如人工智能、符号处理、数据库、编译器等,对基于业务逻辑的、尤其是交互式或事件驱动型的应用就不那么得心应手了。而大多数软件是面向用户的,交互性强、多为事件驱动、业务逻辑千差万别,显然命令式语言在此更有用武之地。”

大家频频颔首。

问号突然想到了什么,指着投影问:“这里用Lisp实现阶乘的方法不也可以用在C上吗?”

冒号点点头,写下一段代码——

int factorial(int n)

{

      return n == 0 ? 1 : n * factorial(n - 1);

}

“这是C的递归实现。”冒号娓娓道来,“除了细微的语法差别外,二者的确很相似,这说明用命令式语言也可以讲出声明式的味道。实际上,命令式语言提倡迭代而不鼓励递归,早期的Fortran 甚至都不支持递归。一则迭代比递归更符合命令式的思维模式,因为前者贴近机器语言而后者贴近数学语言;二则除尾递归(tail recursion)外,一般递归比迭代的开销(overhead)大。相反,声明式语言提倡递归而不支持迭代。就语法而言,它不允许迭代中的循环变量;就视角而言,迭代着眼微观过程而递归着眼宏观规律。”

叹号轻叹:“原来貌似普通的迭代和递归有那么多道道!”

“任何语言都难脱命令式或声明式的窠臼,因此上述三种范式最为基本。”冒号归纳道,“归根结底,编程是寻求一种机制,将指定的输入转化为指定的输出。三种范式对此提供了迥然不同的解决方案:命令式把程序看作一个自动机,输入是初始状态,输出是最终状态,编程就是设计一系列指令,通过自动机执行以完成状态转变;函数式把程序看作一个数学函数,输入是自变量,输出是因变量,编程就是设计一系列函数,通过表达式变换以完成计算;逻辑式把程序看作一个逻辑证明,输入是题设,输出是结论,编程就是设计一系列命题,通过逻辑推理以完成证明。绘成表格如下——”

范式

程序

输入

输出

程序设计

程序运行

命令式

自动机

初始状态

最终状态

设计指令

命令执行

函数式

数学函数

自变量

因变量

设计函数

表达式变换

逻辑式

逻辑证明

题设

结论

设计命题

逻辑推理

冒号见众人微显难色,宽慰道:“这部分理论性稍微强了些,对函数式和逻辑式也仅作了描述性说明,并未深入。不解之处,大可不必介怀,撒下的种子总有一天会萌动。先休息片刻,不要走开,广告之后更精彩。”

posted on 2008-05-05 23:55 郑晖 阅读(2821) 评论(10)  编辑  收藏 所属分类: 冒号和他的学生们

评论

# re: 冒号和他的学生们(连载6)——基本范式 2008-05-06 07:33 sanmu

写得好,受益非浅  回复  更多评论   

# re: 冒号和他的学生们(连载6)——基本范式 2008-05-06 08:16 herowzz

继续支持  回复  更多评论   

# re: 冒号和他的学生们(连载6)——基本范式 2008-05-06 12:13 viMory

老师的空间终于正常了,哈哈
哦也,<!--[if !supportEmptyParas]--> <!--[endif]--> 又走光了...

最近在看自动机,怎么用c++新建一个自动机啊?  回复  更多评论   

# re: 冒号和他的学生们(连载6)——基本范式 2008-05-06 13:24 郑晖

@viMory
1。因为修改了CSS却未照顾到分辨率宽度小于1200象素的显示器,故菜单栏过于偏右,特此致歉。
2。走光问题已解决,请验收。
3。建一个自动机的难度不在于用C++或其他的语言,关键是熟悉FSM的基本原理,并将它的数学模型用编程语言正确地表达出来。
  回复  更多评论   

# re: 冒号和他的学生们(连载6)——基本范式 2008-05-06 19:50 viMory

"老冒"厉害,我现在可以不看了,高兴中,不过改成正则表达式了。  回复  更多评论   

# re: 冒号和他的学生们(连载6)——基本范式 2008-05-07 12:41 dennis

不知道有没有gmail?期待交流下,谢谢  回复  更多评论   

# re: 冒号和他的学生们(连载6)——基本范式 2008-05-07 13:16 郑晖

@dennis
承蒙抬举,我的blog专用邮箱是xyzdll#gmail.com。  回复  更多评论   

# re: 冒号和他的学生们(连载6)——基本范式 2008-05-14 13:51 lanser

“声明式语言提倡递归而不支持迭代”,我接触声明式语言不多,但我记得scheme是提倡把递归转成迭代的,从底层实现将递归总是要比迭代非资源吧。  回复  更多评论   

# re: 冒号和他的学生们(连载6)——基本范式 2008-05-14 14:46 郑晖

@lanser
声明式语言一般用尾递归来实现迭代,scheme也不例外。scheme中的迭代本质上是尾递归,是一种语法上的甜头(syntactic sugar)。它与普通迭代的区别在于:前者的循环变量是重新绑定(rebind)的,而后者的循环变量是重复赋值(reassign)的。另外,尾递归不同于一般递归,它与迭代在效率上没有太大的差别。  回复  更多评论   

# re: 冒号和他的学生们(连载6)——基本范式 2008-06-18 23:31 leweslove

很晕呼。。  回复  更多评论   


只有注册用户登录后才能发表评论。


网站导航:
 

导航

统计

公告

博客搬家:http://blog.zhenghui.org
《冒号课堂》一书于2009年10月上市,详情请见
冒号课堂

留言簿(17)

随笔分类(61)

随笔档案(61)

文章分类(1)

文章档案(1)

最新随笔

积分与排名

最新评论

阅读排行榜

评论排行榜