1.1 值與求值

Haskell 是個可被編譯(compile)、也可被直譯(interpret)的語言。Haskell 直譯器延續了 LISP 系列語言的傳統，是個「讀、算、印 (read, evaluate, pring)」的迴圈 --- 電腦從使用者端讀取一個算式，算出結果，把結果印出，然後再等使用者輸入下一個算式。一段與 Haskell 直譯器的對話可能是這樣：

Main> 3+4
7
Main> sum [1..100]
5050
Main>

在此例中，Main> 是 Haskell 直譯器的提示符號。 (註1) 此處的人機互動紀錄擷取自 GHCi (Glasgow Haskell Compiler Interactive). GHC 為目前最被廣泛使用的 Haskell 實作。 使用者輸入 3+4, Haskell 算出其值 7 並印出. 接著，使用者想得知 1 到 100 的和，Haskell 算出 5050.

上例中的算式只用到 Haskell 已知的函數（如(+), sum等）。 使用者若要自己定義新函數，通常得寫在另一個檔案中，命令 Haskell 直譯器去讀取。 例如，我們可把如下的定義寫在一個檔案中：

double :: Int -> Int
double x = x + x 

上述定義的第一行是個型別宣告。當我們寫 e :: t, 代表 e 具有型別 t. Int 是整數的型別，而箭號 (->) 為函數型別的建構元。第一行 double :: Int -> Int 便是告知電腦我們將定義一個新識別字 double, 其型別為「從整數(Int)到整數的函數」。 (註2) Haskell 標準中有多種整數，其中 Int 為有限大小（通常為該電腦中一個字組(word)）的整數，Integer 則是所謂的大整數或任意精度整數，無大小限制。本書中只使用 Int. 至於該函數的定義本體則在第二行 double x = x + x, 告知電腦「凡看到 double x, 均可代換成 x + x.」

求值  第0 章曾提及：一套程式語言是設計者看待世界的抽象觀點。程式通常用來表達計算，因此程式語言也得告訴我們：在其假想的世界中，「計算」是怎麼一回事。 指令式語言的世界由許多容器般的變數組成，計算是將值在變數之間搬來搬去。 邏輯編程中，描述一個問題便是寫下事物間的邏輯關係，計算是邏輯規則「歸結(resolution)」的附帶效果。 共時(concurrent)程式語言著眼於描述多個同時執行的程式如何透過通道傳遞訊息，計算也靠此達成。

   expr0
 =   { reason0 }
   expr1
 >=  { reason1 }
   expr2
   :
 = exprn 

函數語言中，一個程式便是一個數學式，而「計算」便是依照該式子中各個符號的定義，反覆地展開、歸約，直到算出一個「值」為止。 這個過程又稱作「求值(evaluation)」。 在 Haskell 直譯器中，若 double 的定義已被讀取，輸入 double (9 * 3), 電腦會算出 54:

Main> double (9 * 3)
54

但 54 這個值是怎麼被算出來的？以下是其中一種可能：

  double (9 * 3)
=   {- (*) 的定義 -}
  double 27
=   {- double 的定義 -}
  27 + 27
=   {- (+) 的定義 -}
  54 

上述演算的第一步將 9*3 歸約成 27 --- 我們尚未定義 (*) 與 (+), 但目前只需知道它們與大家所熟悉的整數乘法、加法相同。 第二步將 double 27 變成 27 + 27, 根據的是 double 的定義：double x = x + x. 最後，27 + 27 理所當然地歸約成 54. 「歸約」一詞由 $\beta$-reduction 而來，在此處指將函數本體中的形式參數代換為實際參數。 (註3) Reduction 的另一個常見譯名是「化簡」，然而，許多情況下，一個式子被 reduce 後變得更長而不「簡」，因此本書譯為「歸約」。 在上述例子中，我們遇到如 double (9*3) 的函數呼叫，先將參數 (9*3)化簡，再展開函數定義，可說是由內到外的歸約方式。 大部分程式語言都依這樣的順序求值，讀者可能也對這種順序較熟悉。

但這並不是唯一的求值順序。我們能否由外到內，先把 double 展開呢？

  double (9 * 3)
=   {- double 的定義 -}
  (9 * 3) + (9 * 3)
=   {- (*) 的定義 -}
  27 + (9 * 3)
=   {- (*) 的定義 -}
  27 + 27
=   {- (+) 的定義 -}
  54 

以這個順序求值，同樣得到 54.

一般說來，一個式子有許多種可能的求值順序：可能是由內往外、由外往內、或其他更複雜的順序。 我們自然想到一個問題：這些不同的順序都會把該式子化簡成同一個值嗎？ 有沒有可能做出一個式子，使用一個順序會被化簡成 54, 另一個順序化簡成 53?

我們看看如下的例子。 函數 three 顧名思義，不論得到什麼參數，都傳回 3；inf 則是一個整數：

three :: Int -> Int
three x = 3 

inf :: Int
inf = 1 + inf 

在指令式語言中，inf 的定義可能會被讀解為「將變數 inf 的值加一」。 但函數語言中「變數」的值是不能更改的。 此處的意義應是：inf 是一個和 1 + inf 相等的數值。 我們來看看 three inf 會被為甚麼？ 如果我們由內往外求值：

  three inf
=   {- inf 的定義 -}
  three (1 + inf)
=   {- inf 的定義 -}
  three (1 + (1 + inf))
=   {- inf 的定義 -}
  ...

看來永遠停不下來！但如果我們由外往內，three inf 第一步就可變成 3：

  three inf
=   {- three 的定義 -}
  3 

我們該如何理解、討論這樣的現象呢？

範式與求值順序   為描述、討論相關的現象，我們得非正式地介紹一些術語。 用較直觀、不形式化的方式理解，一個式子中「接下來可歸約之處」稱作其歸約點(redex)。例如(9*3) + (4*6)中，9*3 與 4*6 都是歸約點。 如果一個式子已沒有歸約點、無法再歸約了，我們說該式已是個範式 (normal form)。

回頭看，經由之前的例子我們已得知：

• 有些式子有範式(如 double (9*3) 有個範式 54)，有些沒有（如 inf）。

• 同一個式子可用許多順序求值。有些求值順序會碰到範式，有些不會。

給一個式子，我們很自然地希望知道它有沒有值，並算出其值。如果一個式子有很多個範式，我們便難說哪一個才是該式子的「值」。如此一來，立刻衍生出幾個問題。給定一個式子，我們是否能得知它有沒有範式呢？如果有，用哪個求值順序才能得到那個範式？以及，有沒有可能用一個求值順序會得到某範式，換另一個求值順序卻得到另一個範式？

很不幸地，第一個問題的答案是否定的：沒有一套固定的演算法可判定任意一個式子是否有範式。 這相當於計算理論中常說到的停機問題(halting problem) --- 沒有一個演算法能準確判斷任意一個演算法（對某個輸入）是否能正常終止。

但對於另兩個問題，計算科學中有個重要的Church-Rosser 定理。 非常粗略地說，該定理告訴我們：在我們目前討論的這類語言中 (註4) 此處討論的可粗略說是以 $\lambda$-calculus 為基礎的函數語言。基於其他概念設計的程式語言當然可能不遵守 Church-Rosser 定理。

• 一個式子最多只有一個範式。

• 如果一個式子有範式，使用由外到內的求值順序可得到該範式。

如此一來，給定任一個式子，我們都可用由外到內的方式算算看。 假設一算之下得到（例如）54。 用其他的求值順序可能得不到範式，但若有了範式，必定也是 54. 如果由外到內的順序得不到範式，用其他任何順序也得不到。

由於「由外到內」的求值順序有「最能保證得到範式」的性質，又被稱作「範式順序 (normal order evaluation)」\index {evaluation 求值!normal order 範式順序}。 「由內到外」的則被稱作「應用順序(applicative order evaluation)」\index {evaluation 求值!applicative order 應用順序}。 以本書的目的而言，我們可大致把 Haskell 使用的求值方式視為範式順序。 但請讀者記得這是個粗略、不盡然正確的說法 --- Haskell 實作上使用的求值方式經過了更多最佳化。 正式的 $\lambda$-calculus 教科書中對於歸約點、求值順序、Church-Rosser 定理等概念會有更精確的定義。

被迫求值   型別 Bool 表示真假，有兩個值 False 和 True。 常用的函數 not 可定義如下：

not :: Bool -> Bool
not False  = True
not True   = False 

此處 not 的定義依輸入值不同而寫成兩個條款。 這種定義方式在 Haskell 中稱作樣式配對(pattern matching)： False 與 True 在此處都是樣式 (patterns)。 遇到這樣的定義時，Haskell 將輸入依照順序與樣式們一個個比對。 如果對得上，便傳回相對應的右手邊。 本例中，若輸入為 False，傳回值為 True，否則傳回值為 False。

我們來看看 not (5 <= 3) 該怎麼求值？若依照範式順序，照理來說應先將 not 的定義展開。 但若不知 5 <= 3 的值究竟是 False 還是 True, 我們不知該展開哪行定義！ 因此，要計算 not (5 <= 3)，也只好先算出 5 <=3 了：

  not (5 <= 3)
=   {- (<=) 之定義 -}
  not False
=   {- not 之定義 -}
  True 

求值過程中若必須得知某子算式的值才能決定如何進行，只好先算那個子算式。 在 Haskell 中有不少（有清楚定義的）場合得如此， 包括遇上(<=)、(>=) 等運算子、樣式配對、case 算式（將於第1.6.1 節中介紹）...等等。

mod   :: Int -> Int -> Int 
(==)  :: Int -> Int -> Bool 

myeven   :: Int -> Bool
myeven x = x `mod` 2 == 0  

area    :: Float -> Float
area r  = (22/7) * r * r 

惰性求值   實作上，Haskell 求值的方式還經過了更多的最佳化： 例如將歸約過的算式改寫為它的值，避免重複計算。 這套求值方式稱為惰性求值(lazy evaluation).

技術上說來，惰性求值和範式順序求值並不一樣。 但前者可視為後者的最佳化實作 --- 惰性求值的結果必須和範式順序求值相同。 因此，在本書之中大部分地方可忽略他們的差異。 和惰性求值對偶的是及早求值(eager evaluation) ， 可視為應用順序求值的實作 --- 在呼叫一個函數之前，總是把其參數先算成範式。 這也是一般程式語言較常見的計算方法。

本書中談到偏向實作面的議題時會用「惰性求值/及早求值」， 在談不牽涉到特定實作的理論時則使用「範式順序求值/應用順序求值」。