编程的修炼（中英双语）
編程的修煉（中英雙語）（圖靈獎(jiǎng)獲得者EdsgerW. Dijkstra 是每個(gè)在計(jì)算機(jī)領(lǐng)域?qū)W習(xí)和工作的人都應(yīng)該了解和尊重的先驅(qū)者，本書為他最重要的述著，堪稱編程領(lǐng)域里，經(jīng)典著作的經(jīng)典！）
【荷】Edsger W. Dijkstra 著
裘宗燕譯
ISBN 978-7-121-20250-6
2013年7月出版
定價(jià)：79.00元
456頁
16開
編輯推薦
本書寫于20世紀(jì)70年代中后期，但其對(duì)編程技術(shù)領(lǐng)域的開發(fā)、編程語言發(fā)展和程序理論研究的深刻影響持續(xù)至今。
內(nèi)容提要
本書是圖靈獎(jiǎng)獲得者Edsger W. Dijkstra在編程領(lǐng)域里的經(jīng)典著作中的經(jīng)典。作者基于其敏銳的洞察力和長(zhǎng)期的實(shí)際編程經(jīng)驗(yàn)，對(duì)基本順序程序的描述和開發(fā)中的許多關(guān)鍵問題做了獨(dú)到的總結(jié)和開發(fā)。書中討論了順序程序的本質(zhì)特征、程序描述和對(duì)程序行為（正確性）的推理，并通過一系列從簡(jiǎn)單到復(fù)雜的程序的思考和開發(fā)范例，闡釋了基于嚴(yán)格的邏輯推理開發(fā)正確可靠程序的過程。
本書寫于20世紀(jì)70年代中后期，但其對(duì)編程技術(shù)領(lǐng)域的開發(fā)、編程語言發(fā)展和程序理論研究的深刻影響持續(xù)至今。本書值得每個(gè)關(guān)注計(jì)算機(jī)科學(xué)技術(shù)的本質(zhì)，冀求在程序和軟件領(lǐng)域有長(zhǎng)遠(yuǎn)發(fā)展的計(jì)算機(jī)工作者、教師和學(xué)生閱讀。
目錄
序???? IX
前言???????? XI
第0章? 執(zhí)行抽象????????? 1
第1章? 編程語言的作用???? 13
第2章? 狀態(tài)及其特征????????? 19
第3章? 語義的性質(zhì)???? 29
第4章? 一種編程語言的語義特征???? 47
第5章? 兩個(gè)定理????????? 73
第6章? 論完滿終止結(jié)構(gòu)的設(shè)計(jì)????????? 81
第7章? 再論歐幾里得算法????????? 89
第8章? 幾個(gè)小例子的形式化處理???? 101
第9章? 論受限的非確定性????????? 143
第10章? 有關(guān)記法的短論：“變量的作用域”????????? 157
第11章? 數(shù)組變量?????? 187
第12章? 線性檢索定理?????? 209
第13章? 下一個(gè)排列?? 213
第14章? 荷蘭國(guó)旗問題?????? 221
第15章? 更新順序文件?????? 233
第16章? 再論歸并?????? 245
第17章? 來自R.W.HAMMING的一個(gè)練習(xí)??????? 257
第18章? 模式匹配問題?????? 269
第19章? 將一個(gè)數(shù)寫成兩個(gè)平方之和?????? 279
第20章? 大數(shù)的最小素因子問題?????? 285
第21章? 最孤立村莊問題?? 297
第22章? 最短子支撐樹問題?????? 307
第23章? 記錄等價(jià)類的REM算法????? 321
第24章? 三維空間的凸包問題?? 335
第25章? 有向圖的最大強(qiáng)連通分支?? 383
第26章? 論手冊(cè)和實(shí)現(xiàn)?????? 401
第27章? 跋?? 417
精彩節(jié)摘
第1?章
編程語言的作用
?
?
?
?
?
在“執(zhí)行抽象”一章中，我非形式化地描述了計(jì)算兩個(gè)（不太大的）正整數(shù)的最大公因子的幾種不同“機(jī)器”的設(shè)計(jì)。其中一部機(jī)器采用在紙板上移動(dòng)石子的方式；另一部機(jī)器基于兩個(gè)半拉石子，而且它們都在坐標(biāo)軸上移動(dòng)；最后一個(gè)基于兩個(gè)寄存器，每個(gè)里面可以保存一個(gè)（直至某個(gè)上限的）整數(shù)值。從物理上說，這三臺(tái)“機(jī)器”大相徑庭；而從數(shù)學(xué)上看，它們卻很類似，做出這一論斷的主要原因是，三者都能計(jì)算最大公因子，這是三者的共性。由于這三臺(tái)機(jī)器只不過是同樣一組“游戲規(guī)則”中不同的具體實(shí)現(xiàn)，而實(shí)際上，這組規(guī)則才是一個(gè)發(fā)明的核心，該發(fā)明就是大名鼎鼎的“歐幾里得算法”。
在前一章里，歐幾里得算法是用一種相當(dāng)非形式化的方式描述的。有人會(huì)提出，由于與之對(duì)應(yīng)的可能計(jì)算的數(shù)目如此之大，因此，我們必須要有一個(gè)關(guān)于其正確性的證明。如果一個(gè)算法只是以非形式化的方式給出，它就不容易作為一種形式化處理的對(duì)象。為了形式化地處理，我們就需要用某種適當(dāng)?shù)男问交挠浄▉碜鏊惴ǖ拿枋觥?/span>
這樣一種形式化記述技術(shù)的可能優(yōu)勢(shì)有許多方面。任何記述技術(shù)都蘊(yùn)涵著一個(gè)事實(shí)：它所實(shí)際表述的任何東西都是它有可能描述的那個(gè)對(duì)象集合（通常是一個(gè)無窮集合）的一個(gè)特定成員。我們的記述技術(shù)當(dāng)然應(yīng)該能給出歐幾里得算法的一個(gè)優(yōu)雅而簡(jiǎn)潔的描述，而一旦做好了這件事，也就是把它表示成了一個(gè)包含各種算法的巨大的類中的一個(gè)成員。而在描述該類中的其他算法時(shí)，我們可能期望發(fā)現(xiàn)自己所用的記述技術(shù)的一些更有趣的應(yīng)用。對(duì)于歐幾里得算法，可能會(huì)有人說因?yàn)樗绱撕?jiǎn)單，用一個(gè)非形式化的描述就能對(duì)付了。形式化記法的威力應(yīng)該表現(xiàn)在一些沒有它就絕不可能做到的成就方面。
形式化記述技術(shù)的第二個(gè)優(yōu)勢(shì)是，它使我們有可能將算法作為一種數(shù)學(xué)對(duì)象來研究，算法的形式化描述將成為我們的智力收獲的抓手，使我們能證明一些有關(guān)算法類的定理，例如，由于算法所采用的描述而使之共有的一些結(jié)構(gòu)性的性質(zhì)。
最后，這樣一種記述技術(shù)將使我們能毫無歧義地定義算法，這樣，給定了用它描述的一個(gè)算法，并給定一組實(shí)際參數(shù)（輸入），有關(guān)與之對(duì)應(yīng)的答案（輸出）應(yīng)該是什么，將沒有任何疑義或者非確定性。可以斷言，相應(yīng)的計(jì)算完全可以用一部自動(dòng)機(jī)器完成：給它該算法（的形式化描述）和相應(yīng)的實(shí)際參數(shù)，它就能產(chǎn)生出相應(yīng)的答案，完全無須進(jìn)一步的人工干預(yù)。這樣一種能對(duì)付這種相互對(duì)應(yīng)的算法和實(shí)際參數(shù)的自動(dòng)機(jī)器已經(jīng)造出來了，它就是人們說的“自動(dòng)計(jì)算機(jī)”。為能在計(jì)算機(jī)上自動(dòng)執(zhí)行而寫出的算法稱為“程序”，而自20世紀(jì)50年代后期以來，用于寫程序的形式化記述技術(shù)就被稱為“編程語言”。（與程序的記述技術(shù)有關(guān)的術(shù)語“語言”的引入已受到多方面關(guān)注。一方面，現(xiàn)有的語言理論為相關(guān)討論提供了一種很自然的框架和一套有用的術(shù)語，如“文法”、“語法”、“語義”等。另一方面，我們也必須注意到，與現(xiàn)存的“自然語言”的類似性也造成了許多誤導(dǎo)，因?yàn)楦鞣N自然語言，無論怎樣做形式化，其弱點(diǎn)和威力都來自它們的非明確性和非精確性。）
從歷史情況看，這最后一個(gè)方面，即各種編程語言可以用作指揮現(xiàn)有的自動(dòng)計(jì)算機(jī)的媒介，這個(gè)事實(shí)已經(jīng)在很長(zhǎng)時(shí)期里成為它們最重要的屬性。現(xiàn)有的自動(dòng)計(jì)算機(jī)執(zhí)行某種特定語言寫出的程序的效率，也成為評(píng)判該語言的質(zhì)量的最重要標(biāo)準(zhǔn)。這種情況導(dǎo)致了一個(gè)令人遺憾的后果：不難看到，現(xiàn)有計(jì)算機(jī)的許多很反常的特性都被忠實(shí)地反映在現(xiàn)有的編程語言里，為此付出的代價(jià)是，用這樣一個(gè)語言描述的程序是很難用智力去把握的（實(shí)際上，即使沒有這種情況，編程的工作也已經(jīng)非常困難了！）。在下面將要提出的方法中，我們將試著重新考慮這方面的平衡。按我們的認(rèn)識(shí)，寫出的程序需要實(shí)際地由一臺(tái)計(jì)算機(jī)執(zhí)行，這只是由于偶然性而導(dǎo)致的一種實(shí)際情況，它不應(yīng)該居于我們考慮問題的中心。（在最近的一本培養(yǎng)PL/I程序員的教材里，可以看到作者強(qiáng)烈建議盡可能避免過程調(diào)用，理由是“因?yàn)樗鼈儠?huì)大大影響程序的效率”。由于過程是PL/I中描述結(jié)構(gòu)的最重要的工具，上述建議實(shí)在太可怕了，以至于我完全無法把這本書看作真的能“用于教育”。如果你確信過程是一種有用的概念，而在你的工作環(huán)境中，過程機(jī)制的實(shí)現(xiàn)帶來的開銷卻令人難以忍受，那么應(yīng)該詛咒的是這些不適當(dāng)?shù)膶?shí)現(xiàn)，而不應(yīng)該是把它們的表現(xiàn)作為一種標(biāo)準(zhǔn)！這方面的權(quán)衡確實(shí)應(yīng)該重新做！）
我把一種編程語言看作是一種工作媒介，用于描述（可能非常復(fù)雜的）抽象機(jī)制。正如在有關(guān)“抽象執(zhí)行”一章里可以看到的，算法最突出的優(yōu)點(diǎn)就在于對(duì)它們能夠做出的論證的簡(jiǎn)潔性。我們對(duì)于有關(guān)機(jī)制的信心也是基于這個(gè)事實(shí)。如果失去了這種簡(jiǎn)潔性，算法就失去了其（存在的權(quán)利）中很大一部分，因此，我們將把保持這種簡(jiǎn)潔性作為始終如一的目標(biāo)。另外，我們對(duì)所有編程語言的選擇也將直面這一目標(biāo)。
?
?
?
序
在詩歌、音樂、藝術(shù)和科學(xué)等歷史更為悠久的智力修煉領(lǐng)域，歷史學(xué)家們都把頌詞獻(xiàn)給那里最卓越的實(shí)踐者，因?yàn)樗麄兊某删屯卣沽似滟澝勒叩捏w驗(yàn)和理解，也大大啟迪和提升了其追隨者們的才華。他們的創(chuàng)新基于其在實(shí)踐中積累的卓越技藝，并結(jié)合了他們對(duì)相應(yīng)領(lǐng)域的基礎(chǔ)理論的敏銳洞見。在很多情況下，他們的影響還由于其廣博的文化積淀，以及他們?cè)诒磉_(dá)方式上的力量和透徹性而得到進(jìn)一步的提升。
在本書中，作者以其習(xí)慣的文字風(fēng)格，詳盡地描述了他對(duì)計(jì)算機(jī)編程的基本性質(zhì)的激進(jìn)的新見解。基于這些見解，作者開發(fā)了一套編程方法以及與之相適應(yīng)的記法工具，并用一大批優(yōu)雅而且高效的實(shí)例展示和檢驗(yàn)了它們。本書將注定成為在計(jì)算機(jī)編程的智力修煉領(lǐng)域發(fā)展中最杰出的成就之一。
C.A.R.Hoare
作者簡(jiǎn)介
作者簡(jiǎn)介：
艾茲赫爾?戴克斯特拉（Edsger W. Dijkstra，1930年5月11日－2002年8月6日），生于荷蘭鹿特丹，自喻為荷蘭第一個(gè)以程序設(shè)計(jì)作為職業(yè)的人。他早年積極推動(dòng)結(jié)構(gòu)化程序設(shè)計(jì)，一生致力于將計(jì)算（computing）發(fā)展為一門科學(xué)，在計(jì)算機(jī)科學(xué)技術(shù)的諸多領(lǐng)域有開拓性建樹，并由于在程序設(shè)計(jì)基礎(chǔ)研究中的卓越貢獻(xiàn)獲得1972年圖靈獎(jiǎng)。
?
?
譯者簡(jiǎn)介：
裘宗燕，北京大學(xué)數(shù)學(xué)學(xué)院教授。主要研究興趣是軟件形式化方法和程序設(shè)計(jì)的理論基礎(chǔ)，也關(guān)注程序設(shè)計(jì)實(shí)踐。翻譯過若干相關(guān)著作，包括《從規(guī)范出發(fā)的程序設(shè)計(jì)》、《B方法》、《編程原本》、《計(jì)算機(jī)程序的構(gòu)造和解釋》、《C++語言的設(shè)計(jì)和演化》等。
媒體評(píng)論
在本書中，作者以其習(xí)慣的文字風(fēng)格，詳盡地描述了他對(duì)計(jì)算機(jī)編程的基本性質(zhì)的激進(jìn)的新見解。基于這些見解，作者開發(fā)了一套編程方法以及與之相適應(yīng)的記法工具，并用一大批優(yōu)雅而且高效的實(shí)例展示和檢驗(yàn)了它們。本書將注定成為在計(jì)算機(jī)編程的智力修煉領(lǐng)域發(fā)展中最杰出的成就之一。
C.A.R.Hoare
前言
很長(zhǎng)時(shí)間以來，我一直想寫一本基本上是按照本書線索的著作，原因是：一方面，我知道程序可以有迷人的形態(tài)和深刻的邏輯之美；另一方面，我又不得不接受這樣的事實(shí)，即絕大部分程序只是以一種適合機(jī)器執(zhí)行的方式表達(dá)，完全沒有什么美感，也不適合人們欣賞。這種不滿意還有第二個(gè)原因，那就是各種算法通常總是以一種完成了的產(chǎn)品形式發(fā)表，而在設(shè)計(jì)過程中起著最重要作用的，以及成為證明所完成程序的最終形式的正當(dāng)性的各種思考的主要部分，通常都完全沒有提及。我最初的想法是以讀者能欣賞到它們的美的方式發(fā)表一系列優(yōu)美的算法。對(duì)于如何做這件事，我當(dāng)時(shí)的想法是描述一些實(shí)際的和想象中的設(shè)計(jì)過程，使其中的每個(gè)過程最終都得到了一個(gè)所需的程序。我在一定程度上實(shí)現(xiàn)了最初的想法，作為這本專著的核心部分是一系列的章節(jié)，每一章處理并解決一個(gè)新問題。而在另一方面，最終寫出的這本書與我早前的期望又有很大不同，由于我特別希望用一種自然而且方便的方式來展現(xiàn)這些內(nèi)容，因這種追求而強(qiáng)加給自己的任務(wù)變成了一種重要的責(zé)任。我將永遠(yuǎn)為自己完成了這一工作而感到欣慰。
在開始寫一本像本書這樣的著作時(shí)，人們立刻會(huì)面臨一個(gè)問題：“我準(zhǔn)備使用哪一種編程語言？”而實(shí)際上這并不僅僅是一個(gè)有關(guān)展示形式的問題！任何工具的一個(gè)最重要的（而且也是最難琢磨的）方面，就是它對(duì)于被訓(xùn)練而將使用它的人們的工作習(xí)慣的影響，這種影響——無論我們是否喜歡——是對(duì)我們的思考習(xí)慣的影響。在盡可能地分析了這種影響的各方面情況之后，我得出了一個(gè)結(jié)論：沒有一個(gè)現(xiàn)存的語言，也沒有一個(gè)它們的子集適合我的目標(biāo)。其次，我也知道自
己完全沒有為設(shè)計(jì)一種新的編程語言做好準(zhǔn)備，因此，我曾發(fā)誓在隨后的五年里不去做這件事。而且我有一種非常清晰的感覺：這個(gè)時(shí)期還沒有過去！（但還有一個(gè)前提，就是除了其他事情外，這本書必須要寫。）我試著消解這一矛盾的方式是設(shè)計(jì)了一個(gè)適合我的具體目標(biāo)的小型語言，只做出一些看起來不可能避免，而且其正當(dāng)性也得到了充分證實(shí)的承諾。
這種猶豫和自我強(qiáng)加的約束如果被錯(cuò)誤地理解，有可能使本書的許多潛在讀者對(duì)它感到很失望。那些把編程的困難等同于老練地利用那些精細(xì)而花哨的稱為“高級(jí)編程語言”的工具，或者（更糟糕的！）“編程系統(tǒng)”的困難的人們注定會(huì)對(duì)這本書不滿意。如果因?yàn)槲液雎粤怂心切┱T人的花哨玩意兒而使他們感到受了騙，我只能回答說：“你真能確定所有那些誘人的花哨玩意兒，以及那些你所謂‘強(qiáng)大的’編程語言的美妙功能確實(shí)屬于解集合，而不屬于問題的集合嗎？”我只是希望，即便我用的是一種小型語言，他們也能看看這本書。在做完這件事之后，他們有可能同意，雖然沒有那些誘人的花哨玩意兒，仍然有非常豐富的問題需要討論。因此，是否在一開始就介紹大部分花哨玩意兒，確實(shí)是應(yīng)該質(zhì)疑的。還有，對(duì)于那些明顯是對(duì)編程語言的設(shè)計(jì)有興趣的讀者，我只能表示我的歉意。正如我已經(jīng)做的那樣，我沒辦法在這個(gè)問題上做更明確的事情。但在另一方面，我也希望隨著時(shí)間的推移，這一專著會(huì)對(duì)他們有所啟示，而且能幫助他們避免一些如果沒有讀過它有可能犯的錯(cuò)誤。
在寫作的過程中——它持續(xù)不斷地讓我感到驚喜和激動(dòng)——逐漸呈現(xiàn)的文本與我初始時(shí)頭腦中的想象大不相同。我一開始設(shè)想以一種（易理解的）方式去展示程序的開發(fā)過程，帶上比我在（引論）課程中更多一點(diǎn)的形式化設(shè)施，其中以直觀的方式介紹所使用的語義，有關(guān)正確性的論證采用通常的嚴(yán)格論述，手工編排，再加上有說服力的文字。在為更形式化的方法建立了必要的基礎(chǔ)后，我得到了兩個(gè)驚喜。第一個(gè)驚喜就是所謂的“謂詞轉(zhuǎn)換器”，作為我選用的工具，它提供了一種方法，使我們可以直接定義初始狀態(tài)與最終狀態(tài)之間的關(guān)系，不需要參考在程序?qū)嶋H執(zhí)行中可能經(jīng)歷的中間狀態(tài)。我對(duì)這種情況感到非常欣慰，因?yàn)檫@清晰地區(qū)分了程序員的兩個(gè)主要關(guān)注點(diǎn)：數(shù)學(xué)的正確性（即程序是否定義了初始狀態(tài)與最終狀態(tài)之間所需的正確關(guān)系——謂詞轉(zhuǎn)換器是我們研究這一問題的一種形式化工具，研究中不需要考慮實(shí)際的計(jì)算進(jìn)程），以及工程上對(duì)于效率的關(guān)注（現(xiàn)在也很清楚，這件事只與實(shí)現(xiàn)有關(guān)）。這已經(jīng)成為一種最有幫助的發(fā)現(xiàn)，因?yàn)橥粋€(gè)程序正文總是有兩種相當(dāng)互補(bǔ)的解釋：它可以解釋為一個(gè)謂詞轉(zhuǎn)換器的編碼，這樣做看起來更適合我們的需要；或者解釋為可執(zhí)行代碼，我寧愿把這種解釋留給機(jī)器去做。第二個(gè)驚喜是，我能夠想象到的最自然而且最系統(tǒng)化的“謂詞轉(zhuǎn)換器的編碼”，在被看作“可執(zhí)行代碼”時(shí)，將要求一種非確定性的實(shí)現(xiàn)。有一段時(shí)間，我對(duì)把非確定性引進(jìn)單道編程感到不寒而栗（我對(duì)它給多道編程帶來的復(fù)雜性知道得太多了！），直到我認(rèn)識(shí)到，將程序正文解釋為一個(gè)謂詞轉(zhuǎn)換器的編碼有其自身的存在理由。（回顧往事，我們可以看到，過去提出的有關(guān)多道編程的許多問題并不是別的什么，只不過是不適當(dāng)?shù)剡^分強(qiáng)調(diào)了確定性的重要性而帶來的后果。）我最終認(rèn)識(shí)到，應(yīng)該把非確定性看作正常情況，這樣，確定性將變成一種——并不很有趣的——特例了。
在打好了有關(guān)的基礎(chǔ)之后，我將所有的時(shí)間都投入了想做的事情上，也就是說，去解決一系列的問題。做這件事使我得到了未曾預(yù)料的快樂。與我以前的工作方式相比，形式化的設(shè)施使我能更牢固地把握所做的工作。我很高興地發(fā)現(xiàn)，明確地關(guān)注終止性問題能帶來許多富于啟發(fā)性的看法，以至于使我覺得偏向于考慮部分正確性的觀點(diǎn)如此常見是非常令人遺憾的。然而，最大的快樂是，對(duì)于大部分我原來做過的問題，這次都得到了更漂亮的解答！這是非常令人鼓舞的事情，我將它看作是一種指示劑，說明我所開發(fā)的方法確實(shí)提升了我的編程能力。
應(yīng)該怎樣學(xué)習(xí)這本專著呢？我能給出的最佳建議就是，一旦看完了問題的描述，就停止閱讀，轉(zhuǎn)去試著自己解決它。嘗試自己解決問題，是你能自己認(rèn)識(shí)和評(píng)價(jià)問題的困難程度的唯一方法，它也使你有機(jī)會(huì)去比較你的解和我給出的解，還給你得到滿足的機(jī)會(huì)，即看到你給出的解比我給出的更好。還是要先說一下，當(dāng)你發(fā)現(xiàn)這里的內(nèi)容遠(yuǎn)不是非常容易讀的時(shí)候，請(qǐng)不要沮喪。研讀過這本專著的人都覺得它的內(nèi)容通常是很難的（但收獲也同樣很多！）。然而，每次我們分析遇到的困難時(shí)，得到的結(jié)論都是應(yīng)該將這種困難“歸咎于”實(shí)際討論的問題，而不是有關(guān)的文字本身（即它的表達(dá)方式）。它的寓意是，一個(gè)非平凡的算法本身就是非平凡的，而與論證其設(shè)計(jì)的正確性的思考相比，在一個(gè)編程語言里做出的算法描述是高度緊湊的：不要受到最后的程序正文長(zhǎng)度的誤導(dǎo)！我的一個(gè)助理給出的建議——這也是我忠實(shí)地采納的，因?yàn)樗梢院苡袃r(jià)值——是讓學(xué)生分為一些小
組一起學(xué)習(xí)這本書。（在這里，我必須對(duì)書中正文的“困難程度”加一點(diǎn)附帶的說明。我本人科學(xué)生涯中的許多年一直在致力于弄清楚程序員的任務(wù)，目標(biāo)是設(shè)法使它成為智力上可以管理的工作。從事了多年的這種澄清性的工作之后，我感到好玩，也很吃驚地發(fā)現(xiàn)，反復(fù)出現(xiàn)的回饋是“我把編程弄得更困難了”。但困難始終在那里，只有將其變?yōu)槊黠@可見的，我們才有希望設(shè)計(jì)出具有高度信任水平的程序，而不僅僅是做出了一些“胡亂涂抹出的代碼”，即那種基于根本無法得到支持的假設(shè)，準(zhǔn)備著被第一個(gè)反例推翻的程序正文。不用說，本書的任何一個(gè)程序都沒有在機(jī)器上測(cè)試過。）
我還要給讀者解釋為什么我把這里的小型語言弄得這么小，小到?jīng)]有包含過程和遞歸。由于任何一點(diǎn)語言擴(kuò)充都會(huì)給這本書增加幾章內(nèi)容，并因此使它也相應(yīng)地變得更昂貴，所以對(duì)于大部分可能的擴(kuò)充（例如多道編程），我都不需要更多的解釋。而過程總是在編程中居于核心的地位，遞歸對(duì)于計(jì)算科學(xué)而言也是最受學(xué)術(shù)界重視的標(biāo)志，因此，我必須給出一些解釋。
首先，這本專著不是為新手寫的，因此，我期望本書的讀者熟悉這些概念。其次，本書不是某個(gè)特殊編程語言的引論教材，缺乏這些結(jié)構(gòu)和使用它們的例子，不會(huì)被解釋為我不能或者不希望使用它們，也不會(huì)被作為是建議那些有能力使用這些結(jié)構(gòu)的人不要用它們。這里的關(guān)鍵是我覺得在傳遞想給出的信息時(shí)我并不需要這些結(jié)構(gòu)。我想討論的是應(yīng)該仔細(xì)地分離各種關(guān)注，以及為什么從各個(gè)方面看這種做法都是設(shè)計(jì)出高質(zhì)量程序的最重要的基礎(chǔ)。以這里的小型語言作為一種有節(jié)制的工具，對(duì)于給出各種非平凡而且非常令人滿意的設(shè)計(jì)而言，已經(jīng)能給我們足夠的行動(dòng)自由了。
前面的解釋雖然已經(jīng)很充分，但還不是故事的全部。在任何情況下，我都覺得必須把重復(fù)結(jié)構(gòu)本身作為語言中的一種結(jié)構(gòu)，因?yàn)樵谖铱磥?#xff0c;這樣的闡釋是早就應(yīng)該有的東西。當(dāng)編程語言誕生時(shí)，其賦值語句的“動(dòng)態(tài)”性質(zhì)看起來與傳統(tǒng)數(shù)學(xué)的“靜態(tài)”性質(zhì)很不吻合。由于沒有合適的理論，數(shù)學(xué)家就覺得很不喜歡它。而且，由于重復(fù)結(jié)構(gòu)是需要變量賦值的最根本原因，數(shù)學(xué)家也很不喜歡重復(fù)結(jié)構(gòu)。當(dāng)人們開發(fā)出沒有賦值，也沒有重復(fù)結(jié)構(gòu)的編程語言——例如，純LISP——時(shí)，許多人都大大地松了一口氣。這使他們又可以回到自己熟悉的場(chǎng)地里，看到了一點(diǎn)希望的微光：有可能將編程變成一種具有堅(jiān)實(shí)的而且得到廣泛尊重的數(shù)學(xué)基礎(chǔ)
的活動(dòng)。（直到目前，在更偏向于理論的計(jì)算科學(xué)家中仍然有一種廣泛存在的感覺，認(rèn)為遞歸程序比基于重復(fù)的程序“來得更自然”。）
另一種角度就是為“重復(fù)結(jié)構(gòu)”和“給變量賦值”提供一種可靠的而且可用的數(shù)學(xué)基礎(chǔ)，為此，我們又必須等待另一個(gè)十年。這方面研究的成果是，正如在這本專著里闡釋的，一個(gè)重復(fù)結(jié)構(gòu)的語義可以基于謂詞之間的一個(gè)遞歸關(guān)系定義，而一個(gè)廣義遞歸的語義定義則需要基于謂詞轉(zhuǎn)換器之間的一個(gè)遞歸關(guān)系。這一點(diǎn)很清楚地說明，為什么我認(rèn)為廣義遞歸的復(fù)雜性比重復(fù)結(jié)構(gòu)高一個(gè)數(shù)量級(jí)。因此，我很害怕看到將下面這樣重復(fù)結(jié)構(gòu)的語義
?
定義為調(diào)用
?
其中的whiledo是如下定義的遞歸過程（用ALGOL60的語法描述）
?
雖然這樣做不錯(cuò)，但它卻傷到我了，因?yàn)槲也幌矚g用一把大錘去敲一個(gè)雞蛋，無論用大錘做這件事是多么的有效。對(duì)于在20世紀(jì)60年代涉足這一問題的那一代理論計(jì)算科學(xué)家來說，上面的定義常常不僅是“自然的那一個(gè)”，而且是“真正的那一個(gè)”。應(yīng)該看到下面的事實(shí)：如果不訴諸重復(fù)的概念，我們甚至無法定義圖靈機(jī)能夠做什么。這說明需要重新做一些權(quán)衡。
對(duì)于沒有參考文獻(xiàn)的問題，我不準(zhǔn)備解釋，也不表示歉意。
致謝：下列人士對(duì)本書有直接影響，他們或者是提出過本書擬議中的內(nèi)容的期望，或是請(qǐng)他們?yōu)楸緯?#xff08;或其中一些部分）寫評(píng)論：C. Bron，R.M. Burstall，W.H.J. Feijen，C.A.R. Hoare，D.E. Knuth，M. Rem，J.C. Reynolds，D.T. Ross，C.S. Scholten，G. Seegmüller，N. Wirth和M. Woodger。能寫下對(duì)他們的合作的謝意是我的榮幸。我還要特別感謝Burroughs公司為我提供了機(jī)會(huì)和各方面的便利，感謝我妻子不斷的支持和鼓勵(lì)。
EdsgarW. Dijkstra
荷蘭Nuenen
?
總結(jié)
以上是生活随笔為你收集整理的编程的修炼（中英双语）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 正月初二
- 下一篇： ByteBuffer详解（大概2333）