Haskell史傳：帶類的惰性語言（三）

2.1 惰性的呼喚 接著在70年代晚期和80年代早期，新事物出現了。一系列獨創性的出版物引起人們爆炸般的興趣—把惰性（非嚴格的，或call-by-need）函數式語言作為一種書寫嚴肅程序工具的興趣。惰性求值（lazy evaluation）看來被獨立發明了三次。 * Dan Friedman和David Wise（都在Indiana），發表了《Cons不應求其參數的值》（Friedman和Wise,1976），這篇論文從Lisp的角度來看待惰性求值。 * Peter Henderson（在Newcastle)和James H. Morris Jr.（Xerox PARC）發表了《一個惰性求值器》（Henderson和Morris, 1976）。作為思想上的來源，他們參引了Vuillemin（Vuillemin, 1974）和Wadsworth（Wadsworth, 1971），但是是他們在POPL會議上使這個思想廣為人知，并且他們另外還有一個重要貢獻—這個思想的名字。他們也使用了Lisp的一種變體（variant），并展示了他們的求值器在指稱語義下的完備（soundness）。 * David Turner（在 St. Andrews和Kent）引入了一系列有影響的語言：SASL（St Andrews Static Language）（Turner, 1976），該語言最初在1972年被設計成一種嚴格的語言，但在1976年則變成一種惰性語言；還有KRC（Kent Recursive Calculator）（Turner, 1982）。Turner展示了惰性求值編程的優美，特別是通過惰性列表（lazy lists）來模擬許多不同類型的行為（Turner, 1981; Turner, 1982）。在Burroughs，SASL甚至被用來開發一整個操作系統—這幾乎肯定是最早的、大規模的純惰性函數式編程的練習。 與此同時，人們也息息相關的致力於以令人激動的新方式實現惰性語言。 # 在軟件方面，一些基于圖規約（graph reduction）的不同技術得到了探索，特別是Turner，他頗有靈感的、優美的使用了SK組合子（SK combinators）（Turner, 1979b; Turner, 1979a）。（Turne的工作基于Haskell Curry的組合子演算（combinatory calculus）（Curry和Feys, 1958），該演算是Alonzo Church的lambda演算（Church, 1941）的一種無變量版本。） # 另外一個強有力的因素是這樣一種可能性，所有這些將導致一種激進的非von Neumann的硬件體系結構。幾個建造不同類型數據流機或者圖規約機（graph reduction machines）的認真計劃正在進行（或將進行），它們包括MIT的Id計劃（Arvind和Nikhil, 1987），Utah的Rediflow計劃（Keller et al., 1979），劍橋的SK組合子機SKIM（Stoye et al.,1984），Manchester數據流機（Watson and Gurd,1982），帝國理工（Imperial）的ALICE并行規約機（Darlington和Reeve, 1981），Burroughs的NORMA組合子機（Scheevel, 1986），以及Utah的DDM數據流機（Davis, 1977）。當后來發現好的面向棧結構（stock architecture？疑為stack architecture）的編譯器可勝出於特殊的體系結構之時，大部分（但不是所有）面向體系結構的工作都轉向一個死亡的結局。但在那時，一切都是那么激進和振奮。 幾個重大的會議也出現在80年代，這些會議給這個領域更多的推動力。 在1980年8月，首届Lisp会议（Lisp conference）在加利福尼亚的Stanford召开。讲演包括了Rod Burstall、Dave MacQueen和Don Sannella的Hope，一种包括代数数据类型（algebraic data types）的语言（Burstall et al., 1980a）。 在1981年7月，Peter Henderson、John Darlington和David Turner在Newcastle開辦了一個關于函數式程序設計及應用的高級課程（Darlington et al., 1982）。所有知名人物都在其中：參與者包括Gerry Sussman、Gary Lindstrom、David Park、Manfred Broy,、Joe Stoy和Edsger Dijkstra。（Hughes和Peyton Jones作為學生參加）。Dijkstra特別表示未留下很深印象—他寫道：“整體而言，我不能掩飾深深的失望之情。我仍然相信這個論題值得更多更適當的對待；但確信無疑的，相當多我們展現出來的沒有達到一定水準。”（Dijkstra, 1981）—但對許多與會者來說，這次會議是一個分水嶺。 在1981年9月，首屆函數式程序設計語言與計算機體系結構會議（conference on Functional Programming Languages and Computer Architecture，FPCA）—請留意標題—在新漢普郡的Portsmouth召開。這次Turner發表了他頗有影響的論文《可應用語言語義的優美性》（The semanticelegance of applicative languages）（Turner, 1981）。（Wadler也在這次會議上發表了他第一篇論文。）FPCA成為了這個領域關鍵性的雙年會議。 在1982年9月，第二屆Lisp會議在賓夕法尼亞的Pittsburgh召開，會議更名為Lisp和函數式程序設計（Lisp and Functional Programming，LFP）。講演包括了Peter Henderson的關于函數幾何（functional geometry）（Henderson, 1982），Turner的特邀演講—關于無窮數據結構（infinite data structures）上的編程。（這次也看到Hudak、Hughes和Peyton Jones第一次發表論文）。這次會議的特約嘉賓包括Church和Curry。Barkley Rosser作了晚飯后的演講，演講當中他受到兩次歡呼：一次是當他給出Curry悖論（Curry’s paradox）的證明并將之與Y組合子（Y combinator）聯系起來，另一次是他展示了Church-Rosser定理（Church-Rosser theorem）的一個新證明。LFP成為另一個關鍵性的雙年會議。 （在1996年，FPCA與LFP合并至一個每年一度的函數式程序設計國際會議，ICFP，直至今日這個會議仍然是這個領域的關鍵性會議。） 在1987年8月，作為Texas大學“編程之年”的一部分，Texas大學的Ham Richards和David Turner在得克萨斯州的Austin組織了一次關于聲明式程序設計（Declarative Programming）的國際學校。講者包括了Samson Abramsky、John Backus、Richard Bird、Peter Buneman、Robert Cartwright、Simon Thompson、David Turner和Hughes。這個學校的主要設置是一門惰性函數式程序設計的課程，而且还有采用了Miranda的實習课。 所有這些帶來了巨大的興奮感。函數式程序設計的簡潔與優美俘虜了現在的作者們以及和他们一起的許多其他研究者。與惰性求值直接聯系的是，純的、按名調用（call-by-name）的lambda演算，可表示并操作無窮數據結構的不同凡響的可能性，以及引人的簡單而優美的實現技術，所有这些就像一劑毒品一样使人上癮。 （一個匿名的評審者作出了如下表述：“一個有趣的杂闻是Friedman和Wise的論文曾经鼓舞Sussman和Steele檢查Scheme中的惰性求值，并且有段時間他們在權衡，在Schema的一個版本中，究竟采用按名調用還是按值調用。比之在按名調用的語言中模擬按值調用（需要一種分離的強制求值機制），在一個按值調用的語言中更易於實現按名調用（把lambda表達式作為thunks），考慮到此，他們最終選擇保留原有的按值調用的設計方案。不論我們如何看待這個论证，假如他們做了相反的決定，我們唯一能作的推想就是，現今的學術性程序設計語言將會多么的不同呀！”）