Go To 有害大論戰

函數語言簡介時提到了結構化程式設計與 GOTO, 於是順便又複習了這串筆戰。

Go To 有害論

1968 年,Edsger Dijkstra 投了一篇文章到 Communications of the ACM。「幾年前我便觀察到,一個程式員的品質是其程式中 go to 密度的遞減函數。」他說,「後來我發現了為什麼 go to 的使用有這麼嚴重的後果,並相信所有『高階』語言都應該把 go to 廢除掉。」

Dijkstra 原本下的標題是 ‘A Case Against the Goto Statement’ (一個反對 go to 的理由)。CACM 編輯 Niklaus Wirth 靈感來了,把標題改為 ‘Go To Statement Considered Harmful’ (Go To 有害!)。讀者看了標題已先是一驚,而 Dijkstra 寫的內文也不改他一貫的犀利語氣,用流行話講,戰意可濃厚呢。Wirth 的神來一筆也帶起了計算學界用 ‘X considered harmful‘ 當文章標題的風潮,直到終於有人受不了為止。

為什麼 go to 不好? Dijkstra 說,一個變數代表什麼意義要看其上下文。一個程式用 n 記錄房間裡的人數,在大部分時候 n 代表的是「目前房間裡的人」。但在觀察到又有一個人進房間後、把 n 遞增的指令前的這段程式區塊中,n 的值代表的是「目前房間裡的人數減一」。因此,要正確詮釋程式的狀態,必須知道程式執行的歷史,或著說,知道現在「算到哪」了。

怎麼談「算到哪了」?如果是一直線執行下來的程式,我們只要手指一伸,說「到這裡」,就可以了。如果是有迴圈的程式,我們可能得說「現在在迴圈的這個地方,迴圈已經執行了 i 次」。如果是在副程式中,我們可能得說「現在執行到副程式 p 的這一點;p 剛剛被 q 呼叫,呼叫點在一個迴圈中,已經執行了 i 次。」並需要一個堆疊來放這些數字。但無論如何,程式的執行雖是動態的,上述資訊仍可用少量的靜態(意即由程式結構可推論出的)資訊來描述。

如果可以多用一個技術名詞:在上述的情形中,由於程式中每點的執行歷史可用相對少量資訊表達,我們仍不難在程式裡面放一些斷言(assertion),說「凡是執行到這裡的時候,這些事情一定會成立。」

如果有 go to 呢?那就麻煩了。因為電腦在執行某個指令前,可能是從程式中許許多多 go to 其中之一跳過來的。要談某個變數的性質也幾乎變得不可能了。

「Go To 有害論」有害論!

Dijkstra 這篇文章後來成為結構化程式論戰最有名的文章之一。長達 19 年之後,Frank Rubin 投了一篇文章到 CACM, 標題為 GOTO Considered Harmful’ Considered Harmfulgo to 有害論才是有害的!Rubin 說,「雖然 Dijkstra 的說法既太學術又缺乏說服力」,卻似乎烙到每個程式員的心裡了。

Go to 有害」的說法固然一鳴驚人,卻也使得後人不自覺地陷入一方不斷提出「用 go to 會比較好」的難題、另一方不斷解題的無意義虛耗。Rubin 這次出的題目是這樣的:令 XN × N 的整數陣列。如果 X 的第 i 行全都是零,請印出 i。如果不只一行,印出最小的 i.

Rubin 找了一些慣用 go to 和不用 go to 的程式員來解題,認為前者的程式又快又清楚。後者通常花了更多的時間,寫出很複雜的解答。

你會怎麼寫這題呢?

「『Go To 有害論』有害論」有害論?

以後幾個月的 CACM 果然很熱鬧。編輯收到許多回應,兩個月後刊出了其中五篇。標題?當然囉,“‘GOTO Considered Harmful’ Considered Harmful” Considered Harmful? –「『Go To 有害論』有害論」有害?

有些回應贊同 Rubin,有些則否。但後者的表現並不是很好。有人建議結構化語言還需要新的控制結構,例如可提早終止的 for 迴圈。有人認為這是 Pascal 沒有 break 指令之故。有的提出了他們的程式,但老實說不容易看出好在哪裡。

Dijkstra 有點看不下去了。

「令人失望的對談」

同一個月,Dijkstra 寫了一篇短文 On a somewhat disappointing correspondence(關於一次令人失望的對談)。「我以為我想講的都有人會講,因此沒回 Frank Rubin 的信。但兩個月後發表的五篇回信中,竟沒人做到。」

接著,Dijkstra 不客氣地開罵了,從大小寫的使用 –「我以為到了現在,一個專業程式員該有高一點的自我要求了」、陣列應該從 0 算起 — 「我以為到了現在,一個專業程式員該知道自然數從 0 開始的好處了」開始,接著指出 Rubin 的三個程式中兩個有錯(都是結構化程式) –「我以為到了現在,一個專業程式員該知道這種 bug 怎麼來的。」

Dijkstra 接著指出 Rubin 第三個程式的正確性要靠這個性質 — 如果邏輯 and 的第一個參數是 false, 第二個參數不必有結果。但這種運算元的數學性質不好,用起來是很危險的。

最後,不知為什麼沒人看出來,Rubin 的問題只需把同一個演算法 — 「有界線性搜尋」(bounded linear search)套用兩次即可。Dijkstra 示範了這種搜尋該使用什麼迴圈不變量(loop invariant),如何推導、使用。他認為這都應已是基本常識才對。程式設計研究已發展多年,依他的標準,一個 1987 年的專業程式員應該

  • 要能看得出來 Rubin 的問題適合把同一個演算法套兩層來解;
  • 要知道有界線性搜尋定理;
  • 要能導出這個定理和其證明;
  • 而且也不遲疑去用它;
  • 不用浪費時間指出(Dijkstra 本文示範的演算法中)有個變數可以省掉;
  • 能用簡單、不雜亂的迴圈;

等等。

也許他的意思是,當時不是比賽省一兩個記憶體空間或一兩個指令的時代;他在意的是組織程式、以及程式的證明的清晰思路。如果有已經證明出的性質和程式推導模式可以使用,他覺得就該用,不應見樹不見林。

他的期望,現在實現了多少呢?

後續…

Dijkstra 銳利的風格一直沒變。他的 Turing Award 演講題為「謙卑的程式員」,意謂程式員面對問題的複雜度應有著謙卑的態度,以數學工具和方法為倚靠。但同年又有人在 ACM SIGCSE Bulletin 上投稿 ‘The arrogant programmer: Dijkstra and Wegner considered harmful‘ (傲慢的程式員:Dijkstra 與 Wegner 是有害的),與其針鋒相對。

另一方面,Communications of ACM 畢竟不是靠炒話題賣錢的雜誌,在這場論戰後便決定不再刊登立場過於強烈的文章了。

參考資料

This entry was posted in 計算算計 and tagged , , , . Bookmark the permalink. Post a comment or leave a trackback: Trackback URL.

14 Comments