冒號課堂
第二課 重要范式(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