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

  1. Posted 七月 4, 2009 at 8:58 下午 | Permalink

    看下來還是覺得 Dijkstra 有道理呀… 滿可能是我有立場的關係 XD。

    • Posted 七月 4, 2009 at 10:59 下午 | Permalink

      大概我們都是受過這種訓練的,比較能理解他的想法吧。

      我倒是有點好奇,不知現在在學校裡是怎麼教法?

      Java 和 Python 好像沒有 go to 了,學校如果用他們當第一語言就不會碰到這問題。C/C++ 當然是還有,C# 也把 go to 留著。那老師怎麼教呢?會跳過當作不存在嗎?
      go to 還是個議題嗎?我大學時,網路上還會有人在爭辯用 go to 是不是不好。現在不知怎樣了。
      Dijkstra 大概會希望大家學會那套 weakest precondition calculus. 這個.. 顯然是沒有發生。大概也很少有地方在教 loop invariant. 另外,一些常見的 programming idiom, 例如線性搜尋(其實也就是在 [0.. n) 之間找到滿足某條件 p 的最小整數啦),希望至少教些推理的過程。這個有嗎?我大學時的程式設計課似乎是把每個指令和控制結構走完,就當作你是學會了。

  2. Posted 七月 4, 2009 at 11:06 下午 | Permalink

    另外,上次找 ALGOL 的資料,也發現這篇軼事:原來 Dijkstra 的鬍子是這樣來的

    Maarten van Emden 的這個 blog 好像可看性蠻高的呢。

  3. jaiyalas
    Posted 七月 5, 2009 at 12:20 上午 | Permalink

    現在學校裡的教法。就我自己碰過的
    幾乎都是會講一下那是什麼。然後花
    非常非常多的力氣去警告學生說寫出
    那樣的程式非常糟糕的等等。順便恐
    嚇一下學生說在業界這樣做會被公幹
    等等。

    另外現在幾乎都一定會講OO,有的
    還會講一些design pattern。然後接下
    來就看老師怎麼想的,不過我現在看
    過的都很愛教寫GUI,有的還要學生
    會"背"GUI的API勒。

    還有一個印象很深的例子是現在系上的
    老師在講increment的時候,至少講了
    半個小時以上的「使用++/–有多麼糟
    糕」。不過期中考試的時候卻考了一
    題「i+++j–+++k」諸如此類的東西。

    ( ̄▽ ̄)a

    • Posted 七月 5, 2009 at 7:29 上午 | Permalink

      不過期中考試的時候卻考了一 題「i+++j–+++k」諸如此類的東西。

      這個在業界和學界都被公幹的可能性比較高。 XD

      欸,歡迎來逛。你現在應該在水深火熱之中吧?今年怎樣?

  4. Posted 七月 5, 2009 at 8:11 上午 | Permalink

    "Dijkstra" 的語意在絕大部份學生看來似乎只剩下 shortest path algorithm 吧… 頂多再加個 goto 有害論。

    我們的演算法已經是教得非常好的了,從問題開始,演算法會有直覺引導、版本演進,正確性、時間複雜度證明也都不馬虎。但 loop invariants 此類比較型式的概念不會特別突顯,當然知道的人很容易發現它經常出現。其他不證明的課就更不用說啦,沒在證明當然就不談什麼 loop invariants。

    只能說現在的大學課程非常需要 PLT 的滋潤…

  5. jaiyalas
    Posted 七月 5, 2009 at 11:13 下午 | Permalink

    > 欸,歡迎來逛。
    從Josh的blog連過來的 :p
    看到「小眾計算學」這個字樣就很開心的點下去了~

    > 你現在應該在水深火熱之中吧?今年怎樣?
    不知道是去年記憶已經開始淡了,還是今年的東西
    我比較陌生。今年還真的是水深火熱。聽蔡老師說
    今年因為配合部份老師的行程所以改成每一門課連
    接著上。這真是一場惡夢呀。之前我記得都是半天
    比較深入的課程搭配半天比較好吸收的課。今年變
    成有好幾天都是一整天講同一個東西。早上三個小
    時的課就快昏頭了,下午再三個小時繼續下去。囧
    都還沒搞清楚在做什麼整門課就結束一大半了,然
    後就是兩篇作業隔天交。所以,看來今年又會出現
    那張「地獄寫真」了。XD

    另,我覺得中研院的座位比較好坐 XD 每天下午下
    課的時候我都覺得我的屁股變成不像是我的一樣,
    有夠麻的。

  6. Posted 七月 19, 2009 at 11:23 下午 | Permalink

    哎呀呀,現在才看到你們有開個學分班,早點知道就去報了。真可惜…

    • Posted 七月 28, 2009 at 8:23 上午 | Permalink

      明年再來也可以唷。今年的主題是模型檢查,明年就又是程式語言了。兩個主題輪流換。

  7. Canaan
    Posted 十月 3, 2009 at 2:11 上午 | Permalink

    如果以比較低階或者是說比較接近硬體的軟體開發者來看 goto 這個議題,可能不會覺得它是個問題。
    大家若有興趣可以去查一下 Linux Kernel 中 goto 出現的次數,或是一個執行檔中 jmp/brance 指令出現的比率。
    為什麼寫 kernel 可以用?寫 application 不行用?就像是只許州官放火,不許百姓點燈,一樣令人莞爾。

    最後用一個不倫不類的比喻來做結束,假設 goto 是個屁,當你覺得它臭,並且想到要逃離的時候,你已經吸了一部份進去。
    • Posted 十月 3, 2009 at 8:42 上午 | Permalink

      何以說 kernel 是州官,application 是百姓呢?何不說是目的不同,著重之處與適用的方法自然不同?Knuth 另有一篇 Structured Programming with go to Statements, 由他著重的點談 goto 的使用,Knuth 對 goto 是有偏好的,該論文也闡述得相當精彩。

      Dijkstra 的意見是 1968 年的事情,對其著作熟悉的人可看出他的看法根植於他對程式論證、推理的要求。Knuth 則著眼在實用效率與配合電腦結構。須知他們都是實際寫過許多低階程式的人。 Knuth 的 TAOCP 是經典,這裡記錄著 Dijkstra 為 X1 寫的世界上第一個 ALGOL compiler.

      後來不論電腦結構或計算理論都另有新發展,我們現在談 goto 前應該確定自己踏在前人肩膀上,而不是重複已經發生過的爭辯。遺憾地,我並不認為現在的我們對於無論 Dijkstra 或 Knuth 的論述已有普遍、充分的了解。

      本篇只是回顧一下歷史。我對 goto 的個人看法,需要比較多的篇幅解釋。我得等到有時間再做了。

      關於最後一段「比喻」,我並不喜歡在我的部落格上出現那樣的話。恕以 CSS 隱藏,請見諒。

      • Canaan
        Posted 十月 5, 2009 at 12:38 上午 | Permalink

        我想,我並不是要再次重複前人的爭辯,而是說明 goto 其實是有其生存空間或者說市場。(在被宣告有害之後 41 年)

        另外,對於一些OO程式語言中的 exception handling,依照底層的實作,依照我個人的偏見,我還是把它們當 goto。假設 OO語言 是結構化語言的下一代,這個論點成立,那其實 goto 對 OO語言/結構化語言 來說,還是有點用處,不是那麼地 harmful。

        而當大家明白 goto 有市場之後,有害與無害的偏激之爭,似乎也就不是那麼的必要了,我想這應該也是我們比四十一年前的人進步的的地方。

        再說逝者以矣,現在的我們所要討論的應該要提升為,人腦的有害與無害,無害的人腦用再多的 goto 也不會寫出有害的程式,有害的人腦就算不用 goto 也會寫出有害的程式。(這也算是偏見 :-) )

        中秋過後,未必有時間繼續拜讀大作,若有批評指教,歡迎直接 email 。

        • Canaan
          Posted 十月 5, 2009 at 12:59 上午 | Permalink

          逝者以矣->逝者已矣

          (我其實不能因為我打錯這個詞,而說某個輸入法有害,right? :-) )

  8. Jason wu
    Posted 五月 25, 2010 at 3:57 下午 | Permalink

    對我來說 goto 是低階語言,高階語言不是不能用,是我不想幫你debug OK~

Post a Comment

Your email is never published nor shared. Required fields are marked *

*
*

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>