日历

September 2009
M T W T F S S
« Aug   Oct »
 123456
78910111213
14151617181920
21222324252627
282930  

冒号课堂§2.2:声明范式

冒号课堂

第二课 重要范式(2)

2.2 声明范式——目标决定行动

郑晖

摘要

声明式编程简谈


给我一个支点,我能挪动地球

Archimedes

!预览

  • 命令式编程是行动导向的,因而算法是显性而目标是隐性的;声明式编程是目标驱动的,因而目标是显性而算法是隐性的

  • 声明式编程重目标、轻过程,专注问题的分析和表达而不致陷入算法的迷宫,其代码也更加简洁清晰、易于修改和维护

  • 归根结底,编程是寻求一种机制,将指定的输入转化为指定的输出

?提问

  • 什么是声明式编程?它与命令式编程有何区别?

  • 什么是函数式和逻辑式?

  • 变量在命令式编程和声明式编程中有何不同的涵义?

  • 声明式语言有何优点?为什么没有命令式语言流行?

  • 命令式语言与声明式语言有无相通之处?

  • 编程的本质是什么?命令式、函数式和逻辑式分别采用了怎样的编程机制?

:讲解

冒号迅速转移了话题:“下面我们来谈谈与命令式编程相对的声明式编程(declarative programming)。顾名思义,声明式编程由若干规范(specification)的声明组成的,即一系列陈述句:‘已知这,求解那’,强调‘做什么’而非‘怎么做’。声明式编程是人脑思维方式的抽象,即利用数理逻辑或既定规范对已知条件进行推理或运算。”

问号询问:“声明式产生的背景是什么呢?”

“声明式编程发轫于人工智能的研究,主要包括函数式编程(functional programming,简称FP)和逻辑式编程(logic programming,简称LP)。其中,函数式编程将计算描述为数学函数的求值,而逻辑式编程通过提供一系列事实和规则来推导或论证结论。其实支持它们的语言出现得并不比命令式的晚多少——最早的函数式语言Lisp(LISt Processor)已有半个世纪的历史,最早之一的逻辑式语言Prolog(PROgramming 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!等于Fm且F等于N*Fm,则N! 等于F
    factorial(N,F) :-   M is N-1, factorial(M,Fm), F is N * Fm. 

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

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

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

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

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

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

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

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

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

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

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

句号一拍脑袋:“命令式是模拟电脑的,声明式是模拟人脑的,人脑当然比电脑高级啦。”

冒号另有佐证:“早在命令式语言引入函数从而进化为过程式语言时,就已经开始向声明式过渡了。何以见得?比方说调用一个函数的语句:doWhat(),这不正是在声明‘what to do’吗?至于‘how to do’,即函数的具体实现细节,则不劳调用者费心。这种声明式的风格,提高了语言的抽象能力和开发效率,促成了语言的升级。”

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

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

大家频频颔首。

“值得指出的是,声明式编程并不仅仅局限于函数式和逻辑式。”冒号旋即补充道,“比方说,C#中的attribute、Java中的annotation和XDoclet库等采用的也是具有声明式特征的属性导向式编程(Attribute-Oriented Programming,简称@OP)。再比如,Prograph[2] 、SISAL[3]数据流语言(dataflow language)采用的数据流式编程(Dataflow Programming)与函数式编程有不少共同点,同样属于声明式的范畴。还有一些语言如Oz、CHIP等支持与逻辑式编程相交的约束式编程(Constraint Programming)[4]。此外,大家熟悉的数据库语言SQL,样式语言XSLT、CSS,标记语言HTML、XML、SVG,规范语言IDL(Interface Description Language)等等都是声明式的。算上它们,声明式语言所占的比例也是非常可观的。此前之所以没有提及,一方面,不少声明式语言采用的范式并没有专门的名称;另一方面,这些语言大多是领域特定语言,并且不少并非图灵完备的,有的连运算都没有。毕竟,目前我们的重点还是放在通用编程语言上。”

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

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

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

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

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

“任何语言都难脱命令式或声明式的窠臼。事实上,凡是非命令式的编程都可归为声明式编程。因此,命令式、函数式和逻辑式是最核心的三种范式。为清楚起见,我们用一幅图来表示它们之间的关系。”说罢,冒号换了一个幻灯片——

图2-4. 编程范式的简单分类

编程范式的简单分类

末了,冒号归纳道:“归根结底,编程是寻求一种机制,将指定的输入转化为指定的输出。三种范式对此提供了截然不同的解决方案:命令式把程序看作一个自动机,输入是初始状态,输出是最终状态,编程就是设计一系列指令,通过自动机执行以完成状态转变;函数式把程序看作一个数学函数,输入是自变量,输出是因变量,编程就是设计一系列函数,通过表达式变换以完成计算;逻辑式把程序看作一个逻辑证明,输入是题设,输出是结论,编程就是设计一系列命题,通过逻辑推理以完成证明。绘成表格如下(如表2-1所示)——”

表2-1. 三种核心编程范式的比较

范式程序输入输出程序设计程序运行
命令式自动机初始状态最终状态设计指令命令执行
函数式数学函数自变量因变量设计函数表达式变换
逻辑式逻辑证明题设结论设计命题逻辑推理

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

,插语

  1. 数学中应该用类似in+1 = in + 1的表示法。

  2. Prograph即Programming in Graphics,是一种可视化的、对象导向(OO)的数据流语言,它用图表(diagram)来取代文本编码。

  3. SISAL即Streams and Iteration in a Single Assignment Language,是一种函数式数据流语言,擅长并行科学计算。

  4. 约束式编程通过数据之间的约束关系来进行运算。它可以借助逻辑推理机制或其他数学和算法技巧来实现。有一种观点认为:用函数式、逻辑式或约束式三者之一的语言来编写程序,即是声明式编程。这种以编程语言反过来定义编程范式的说法值得商榷,但从中可看出约束式编程的代表性。

  5. 尾递归是一种特殊的递归,其递归调用出现在函数的最后一步运算(尾部)。这类递归很容易通过手工或编译器转化为迭代形式,以优化性能。

  6. 有些声明式语言(例如Lisp的一个变种Scheme)虽然支持迭代,但一般是用尾递归来实现的。从本质上说,这只是一种语法上的甜头(syntactic sugar)。它与普通迭代的区别在于:前者的循环变量是重新绑定(rebind)的,而后者的循环变量是重复赋值(reassign)的。

。总结

  • 命令式编程通过一系列改变程序状态的指令来完成计算,声明式编程只描述程序应该完成的任务。命令式编程模拟电脑运算,是行动导向的,关键在于定义解法,即“怎么做”,因而算法是显性而目标是隐性的;声明式编程模拟人脑思维,是目标驱动的,关键在于描述问题,即“做什么”,因而目标是显性而算法是隐性的。

  • 函数式编程通过数学函数的表达式变换和计算来求值。

  • 逻辑式编程通过一系列事实和规则,利用数理逻辑来推导或论证结论。

  • 命令式编程中的变量代表抽象化的内存,所存内容可能改变。声明式编程中的变量代表抽象化的符号,所指对象一般不会改变。

  • 声明式编程专注问题的分析和表达而不是算法实现,不用指明执行顺序,一般没有或极少副作用,也不存在内存管理问题。这些都大大降低了编程的复杂度,同时也非常适合于并发式计算。

  • 编程语言的流行程度与其擅长的领域密切相关。函数式语言和逻辑式语言擅长基于数理逻辑的应用,命令式语言擅长基于业务逻辑的、尤其是交互式或事件驱动型的应用。

  • 声明式语言与命令式语言之间并无绝对的界限,它们均建立于低级语言之上,并且互相渗透融合。

  • 在命令式语言中引入函数或过程,是一种向声明式风格的趋近。

  • 编程是寻求一种机制,将指定的输入转化为指定的输出。

  • 三种核心编程范式采用如下不同的机制——

    命令式:自动机机制,通过设计指令完成从初始态到最终态的转变。

    函数式:数学变换机制,通过设计函数完成从自变量到因变量的计算。

    逻辑式:逻辑证明机制,通过逻辑推理完成从题设到结论的证明。

“”参考

  1. Elena Bolshakova.PROGRAMMING PARADIGMS IN COMPUTER SCIENCE EDUCATION.International Journal “Information Theories & Applications”,2005,Vol.12:285-290

  2. Ravi Sethi.Programming Languages: Concepts & Constructs(英文版第2版).北京:机械工业出版社,2002.301-340,423-470

  3. Wikipedia.Declarative programming.http://en.wikipedia.org/wiki/Declarative_programming

Share
 请您评分1星(很差)2星(不行)3星(一般)4星(不错)5星(很棒)

1 comment to 冒号课堂§2.2:声明范式

Leave a Reply

You can use these HTML tags

<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

  

  

  

This blog is kept spam free by WP-SpamFree.