冒號課堂§2.2：聲明范式

冒號課堂

第二課 重要范式(2）

2.2聲明范式——目標決定行動

給我一個支點，我能挪動地球                                           ——Archimedes

關鍵詞：編程范式,命令式,聲明式,函數式,邏輯式

摘要：聲明式編程簡談

 
？提問  

• 什么是聲明式編程？它與命令式編程有何區別？
• 什么是函數式和邏輯式？
• 變量在命令式編程和聲明式編程中有何不同的涵義？
• 聲明式語言有何優點？為什么沒有命令式語言流行？
• 命令式語言與聲明式語言有無相通之處？
• 編程的本質是什么？命令式、函數式和邏輯式分別采用了怎樣的編程機制？

：講解

冒號迅速轉移了話題：“下面我們來談談與命令式編程相對的聲明式編程（declarative programming）。顧名思義，聲明式編程由若干規范（specification）的聲明組成的，即一系列陳述句：‘已知這，求解那’，強調‘做什么’而非‘怎么做’。聲明式編程是人腦思維方式的抽象，即利用數理邏輯或既定規范對已知條件進行推理或運算。”

問號詢問：“聲明式產生的背景是什么呢？”

“聲明式編程發軔于人工智能的研究，主要包括函數式編程（functional programming）和邏輯式編程（logic programming）。其中，函數式編程將計算描述為數學函數的求值，而邏輯式編程通過提供一系列事實和規則來推導或論證結論。其實支持它們的語言出現得并不比命令式的晚多少——最早的函數式語言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可以在命令式編程中出現，但絕不可能在數學推理中出現——除非在反證法中。”

嘆號又道：“現在回頭再看代數，反倒有些不習慣了。”

“這就是思維的定勢效應。”冒號感慨道，“聲明式編程讓我們重回數學思維：函數式編程類似代數中的表達式變換和計算，邏輯式編程則類似數理邏輯推理。其中的變量也如數學中的一樣，是抽象符號而非內存地址，因此沒有賦值運算，不會產生變量被改寫的副作用（side-effect），也不存在內存分配和釋放的問題。這既簡化了代碼，也減少了調試——不妨想一想，有多少bug是由于某個變量被意外改寫或內存管理不慎而造成的？”

問號問道：“聲明式語言與命令式語言看來是兩個世界的產物，它們是否有相通之處？”

冒號答道：“首先，所有高級語言都建立于低級語言之上，最終轉化為機器語言，聲明式語言也不例外。其次，聲明式語言與命令式語言并非涇渭分明，而是互相交叉滲透的。一些‘非純粹’ 的聲明式語言也提供變量賦值和流程控制，而一些命令式語言也在逐漸發展，通過利用其他程序或增加新的語言特征來實現聲明式編程。總的說來，在命令式語言中融入聲明式的元素應當是一種趨勢。尤其是函數式，它的一些特征已經在許多命令式語言中得到了支持。比較而言，聲明式編程重目標、輕過程，專注問題的分析和表達而不致陷入算法的迷宮，其代碼也更加簡潔清晰、易于修改和維護。從這種意義上說，聲明式語言天然地就比命令式語言更高級。上節課提到的前三代計算機語言基本上都是命令式的，而后兩代基本上都是聲明式的，由此可見一斑。”

句號一拍腦袋：“命令式是模擬電腦的，聲明式是模擬人腦的，人腦當然比電腦高級啦。”

冒號另有佐證：“早在命令式語言引入函數從而進化為過程式語言時，就已經開始向聲明式過渡了。何以見得？比方說調用一個函數的語句：doWhat()，這不正是在聲明‘what to do’嗎？至于‘how to do’，即函數的具體實現細節，則不勞調用者費心。這種聲明式的風格，提高了語言的抽象能力和開發效率，促成了語言的升級。”

逗號仍然有些疑惑：“既然聲明式編程有這么多好處，為什么命令式語言不僅占大多數，而且流行程度也不減呢？”

冒號回答：“編程語言的流行程度與其擅長的領域關系密切。聲明式語言——尤其是函數式語言和邏輯式語言——擅長基于數理邏輯的應用，如人工智能、符號處理、數據庫、編譯器等，對基于業務邏輯的、尤其是交互式或事件驅動型的應用就不那么得心應手了。而大多數軟件是面向用戶的，交互性強、多為事件驅動、業務邏輯千差萬別，顯然命令式語言在此更有用武之地。”

大家頻頻頷首。

“值得指出的是，聲明式編程并不僅僅局限于函數式和邏輯式。”冒號旋即補充道，“比方說，C#中的attribute、Java中的annotation和XDoclet庫等采用的也是具有聲明式特征的屬性導向式編程（Attribute-Oriented Programming）。再比如，Prograph^[1] 、SISAL^[2]等數據流語言（dataflow language）采用的數據流式編程（Dataflow Programming）與函數式編程有不少共同點，同樣屬于聲明式的范疇。還有一些語言如Oz、CHIP等支持與邏輯式編程相交的約束式編程（Constraint Programming）^[3]。此外，大家熟悉的數據庫語言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）^[4]外，一般遞歸比迭代的開銷（overhead）大。相反，聲明式語言提倡遞歸而不支持迭代^[5]。就語法而言，它不允許迭代中的循環變量；就視角而言，迭代著眼微觀過程而遞歸著眼宏觀規律。”

嘆號輕嘆：“原來貌似普通的迭代和遞歸有那么多道道！”

“任何語言都難脫命令式或聲明式的窠臼。事實上，凡是非命令式的編程都可歸為聲明式編程。因此，命令式、函數式和邏輯式是最核心的三種范式。為清楚起見，我們用一幅圖來表示它們之間的關系。”說罷，冒號換了一個幻燈片——

末了，冒號歸納道：“歸根結底，編程是尋求一種機制，將指定的輸入轉化為指定的輸出。三種范式對此提供了截然不同的解決方案：命令式把程序看作一個自動機，輸入是初始狀態，輸出是最終狀態，編程就是設計一系列指令，通過自動機執行以完成狀態轉變；函數式把程序看作一個數學函數，輸入是自變量，輸出是因變量，編程就是設計一系列函數，通過表達式變換以完成計算；邏輯式把程序看作一個邏輯證明，輸入是題設，輸出是結論，編程就是設計一系列命題，通過邏輯推理以完成證明。繪成表格如下——”

冒號見眾人微顯難色，寬慰道：“這部分理論性稍微強了些，對函數式和邏輯式也僅作了描述性說明，并未深入。不解之處，大可不必介懷，撒下的種子總有一天會萌動。先休息片刻，不要走開，廣告之后更精彩。”

  
，插語

[1]Prograph即Programming in Graphics，是一種可視化的、對象導向（OO）的數據流語言，它用圖表（diagram）來取代文本編碼。

[2] SISAL即Streams and Iteration in a Single Assignment Language，是一種函數式數據流語言，擅長并行科學計算。

[3] 約束式編程通過數據之間的約束關系來進行運算。它可以借助邏輯推理機制或其他數學和算法技巧來實現。有一種觀點認為：用函數式、邏輯式或約束式三者之一的語言來編寫程序，即是聲明式編程。這種以編程語言反過來定義編程范式的說法值得商榷，但從中可看出約束式編程的代表性。

[4] 尾遞歸是一種特殊的遞歸，其遞歸調用出現在函數的最后一步運算（尾部）。這類遞歸很容易通過手工或編譯器轉化為迭代形式，以優化性能。

[5] 有些聲明式語言（例如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

posted on 2008-11-03 23:27 鄭暉 閱讀(2603) 評論(0)  編輯  收藏 所屬分類: 冒號課堂