1 值、函數、與定義

1.11 參考資料

本章中的許多想法取自 Bird [1998] ,該書是我相當推薦的 Haskell 教材。

Haskell 為何叫 Haskell?

1980 年代中期,程式語言學者們已各自開發出了許多個語法、語意類似但卻稍有不同、大都只在出生機構被使用的惰性純函數語言。沒有一個語言取得壓倒性的優勢。 為溝通方便、以及為了讓整個領域能走向下一步,大家有了該設計個統合、共通的惰性純函數語言的共識。 1988年一月,新語言設計小組在耶魯大學開會,眾多討論項目中包括幫語言取個名字。 以下軼事節錄自 Hudak et al. [2007] .

當天被提出的選項包括 Haskell, Vivaldi, Mozart, CFL (Common Functional Language), Curry, Frege, Peano, Nice, Fun, Light...等等。最後經程序選出的名字是 ``Curry'', 紀念邏輯學家 Haskell B. Curry --- 他在組件邏輯(combinatorial logic)、Curry-Howard 同構等領域的研究一直深遠影響函數語言學界。

但當天晚上就有人覺得這名字會招惹太多雙關語笑話。除了咖哩之外,小組成員覺得實在不行的是:TIM (three instruction machine) 是函數語言用的一種抽象機器,但 Tim Curry 則成了電影洛基恐怖秀(Rocky Horror Picture Show, 1975)的男主角。

於是新語言的名字就改成 Haskell 了。

小組成員 Paul Hudak 和 David Wise 寫信給 Curry 的遺孀 Virginia Curry,徵求她的同意。Hudak 後來親自登門拜訪,Virginia Curry 和他聊了之前的訪客(包含 Church 與 Kleene)的故事;後來她也去聽了 Hudak 關於 Haskell (語言)的演講,表現得十分友善。臨別前,她說:「其實呀,Haskell 一直都不喜歡他的名字。」

Currying   Moses [Sch{\"{o}}nfinkel 1924] 提出多參數函數可用單參數函數表達。 Haskell Curry 在許多著作中(例:Curry [1980] )使用 currying, 但當時並沒有 currying 一詞。 為何此概念最後會以 Curry 命名呢? David A. Turner (Haskell 語言的前身之一 Miranda 的設計人) 在一次網路討論 [Sankar et al. 1997] 中表示 currying 一詞由 Christopher Strachey 取名,於 1967 年前後使用在其上課資料中。 這種說法目前廣被大家接受,但我目前尚未找可佐證的上課資料。 相反地,Strachey [1967] 之中明確表示他認為 currying 的概念是由 Sch\"{o}nfinkel 發明的,並稱之為「Sch\"{o}nfinkel 的裝置」。 原文:``There is a device originated by Sch\"{o}nfinkel, for reducing operators with several operands to the successive application of single operand operators.'' 但 currying 的想法可追溯得比 Sch\"{o}nfinkel 或 Curry 都早。 F. L. Gottlob Frege 1891 年的 \"{U}ber Funktion und Begriff (英譯 Function and Concept) [Frege 1960] 結尾幾頁的概念即是 currying.

全麥編程   「全麥編程」一詞由牛津大學 Geraint Jones 取名,由來可能是模仿健康食物的說詞。 如 Bird [2010, 第19章] 便寫道,「全麥編程好處多多,可預防『索引症』(indexitis),鼓勵合法的程式建構。」 在該章之中,Richard Bird 以大量使用串列組件函數的全麥編程為起點, 推導出能相當迅速地解數獨的程式。 Hinze [2009] 以全麥編程為工具,示範了河內塔問題(Tower of Hanoi) 的許多性質,以及其與謝爾賓斯基(Sierpi\'{n}ski)三角形的關係。 其中寫道「函數語言擅長全麥編程。這個詞彙由 Geraint Jones 命名。 全麥編程意謂由大處去想:處理整個串列,而不是一連串的元素;發展出整個解答的空間,而不是個別的解答;想像整個圖,而不是單一的路徑。對於已知的問題,全麥編程常給我們新洞察與新觀點。」 Hutton [2016, 第五章] 則以編、解密碼為例。 凱撒加密(Caesar cipher)為一種簡單的加密方式: 將明文中的每個字母都往前或後偏移固定的量,例如當偏移量為 2 時, 'a' 變成 'c', 'b' 變成 'd' ... 一種解凱撒密碼的有效方式是計算密文中每個字母的分佈,和一般英文文章中的平均字母分佈做比較,藉以猜出偏移量。Graham Hutton 在書中示範如何用組件函數、完全不用遞迴地寫出編碼與解碼程式。以上都是相當值得一看的例子。

LISP 的串列   誕生於 1958 年的 LISP 是目前仍被使用的高階程式語言中歷史第二悠久的 --- 最早的是 FORTRAN. 但 LISP 與 FORTRAN 是風格截然不同的語言。 雖然具有含副作用的指令,LISP 仍被認為是函數語言的先驅。

LISP 為「串列處理(list processing)」的縮寫。 但事實上,LISP 中的聚合資料結構「S 算式 (S-expression)」不只可用來表達串列。 CONS 函數做出的是一個序對, 其中第一個元素被稱作 CAR (contents of the address part of register), 第二個稱作 CDR (contents of the decrement part of register). 如果 CDR 的部分仍是一個 CONS 做出的序對,或是特殊值 NIL, 整個結構表達的就是一個串列。 S 算式也可用來做出二元樹、語法樹... 等等。 Haskell 串列的建構元 [] 可唸成 nil'', |(:)| 唸成cons'', 這兩個詞彙都從 LISP 而來。

在前幾波人工智慧熱潮時,大家認為符號與邏輯的處理是人工智慧的基礎。 但早期的程式語言大多針對數值運算而設計,會處理串列的 LISP 便被視為最適合做符號處理的語言 ---「人工智慧用的語言」。 另一個被視為「人工智慧專用語言」的是奠基於述語邏輯與歸結(resolution) 的 PROLOG. 今日的人工智慧技術以神經網路為基礎,「人工智慧專用語言」的頭銜則給了 Python。