Haskell2010中文報告/語言/表達式

本章，我們討論Haskell表達式的語法以及非形式語義，我們也適時給出表達式到Haskell核的轉化。除了let表達式，所有的轉化都保持程序的動態及靜態語義。轉化中用到的自由變量或者構造符都是來自於Prelude的實體。比如，在列表組合轉換中用到的"concatMap"指的就是Prelude中定義的concatMap, 無論符號"concatMap"是否出現在列表組合作用域或是它所綁定的作用域(如果concatMap在列表組合的作用域)。

exp → infixexp :: [context =>] type (表達式類型簽名)

| infixexp

infixexp → lexp qop infixexp (中綴操作符應用)

| - infixexp (前綴求反)

| lexp

lexp → \ apat₁ … apat_n -> exp (lambda抽象, n ≥ 1)

| let decls in exp (let表達式)

| if exp [;] then exp [;] else exp (條件式)

| case exp of { alts } (case表達式)

| do { stmts } (do表達式)

| fexp

fexp → [fexp] aexp (函數應用) aexp → qvar (變量)

| gcon (通用構造符)

| literal

| ( exp ) (括號表達式)

| ( exp₁ , … , exp_k ) (元祖, k ≥ 2)

| [ exp₁ , … , exp_k ] (列表, k ≥ 1)

| [ exp₁[, exp₂] ... [exp₃] ] (算術序列)

| [ exp | qual₁ , … , qual_n ] (列表組合, n ≥ 1)

| ( infixexp qop ) (左分切)

| ( qop_<-> infixexp ) (右分切)

| qcon { fbind₁ , … , fbind_n } (標記構造, n ≥ 0)

| aexp_<qcon>{ fbind₁ , … , fbind_n } (標記更新, n ≥ 1)

表達式，包括中綴表達式，用操作符結合信息來分辨(嵌套聲明節)。連續的無括號操作符，如果優先級相等，必須指定是左結合還是右結合，否則會產生語法錯誤。假定無括號表達式"x gop^(a,i) y qop^(b,j) z"(qop^(a,i)表示操作符綴為a，優先級是i)，且i=j，這時必須在"x qop^(a,i) y"或者"y qop^(b,j) z"兩側添加括號，除非a=b=l或a=b=r。

結合解析節給出了包括中綴表達式在內的表達式結合判定算法。

求反是唯一的前綴表達式；它和Prelude中(嵌套聲明)的中綴操作符-有相同的優先級。

如果考慮lambda抽象、let表達式和條件式的延伸，則通常會出現歧義文法。歧義文法的判定，由下面的元規則確定：這些結構總是儘可能的右延。

下面是一些樣例解析：

表達式	解析
f x + g y	(f x) + (g y)
- f x + y	(- (f x)) + y
let { ... } in x + y	z + (let { ... } in (x + y))
f x y ::Int	(f x y)::Int
\ x -> a+b :: Int	\ x -> ((a+b) :: Int)

為了便於闡述，本節餘下部分假定包含中綴操作符在內的表達式，根據操作符的結合信息有唯一的解析。

錯誤

Haskell中，表達式求值過程中的錯誤，用⊥(底)表示。Haskell不區分⊥和程序非終止。Haskell是一個非即時語言，所有的Haskell類型都包含⊥。即，任何類型的值都可能綁定到某個計算，計算啟動後返回一個錯誤。求值過程中出現錯誤，會立即終止程序，不能被用戶捕獲。Prelude提供兩個函數，可以直接產生錯誤：

error     :: String -> a  
undefined :: a

調用error終止當前程序執行，並返回合適錯誤信息給作業系統。同時，會以系統相關的方式顯式錯誤串。調用undefined時，編譯器產生錯誤信息。

Haskell表達式的轉化使用error和undefined顯式表達可能發生執行期錯誤的位置。發生錯誤時的程序行為由具體實現決定。表達式轉化傳遞給error函數的消息僅僅只是建議；實際上，由具體實現來打印錯誤發生時的大概信息。

變量，構造符，操作符和終結符

aexp → qvar (變量)

| gcon (一般構造符)

| literal

gcon → ()

| []

| (,{,})

| qcon

Haskell通過特殊語法支持中綴表示。操作符可以看做是使用中綴表示的函數(操作符應用)，也可以通過分切(分切)實現偏應用。

一個操作符可以是一個符號，比如+或$$，也可以是一個方言標記(反引號)的常規符號，比如`op`. 舉個例子，前綴應用op x y，也可以寫成中綴應用x `op` y。如果沒有`op`沒有結合定義，那麼它缺省有最高的優先級並左結合(見聲明與綁定節)。、

同樣，符號表示的操作符也可以轉換為常規符號，方法是添加括號。比如，(+) x y和x + y等價。foldr (*) 1 xs 和foldr (\x y -> x * y) 1 xs等價。

命名一些內置類型的構造符時使用了一些特殊語法，比如產生式gcon和literal。這些將在標準Haskell類型節闡述。

一個整數符表示函數fromInteger應用於類型為Integer的對應值。類似地，一個浮點數符表示fromRational應用一個類型為Rational的值(即，比率數(有理數))。

轉化：整數符i被轉化為fromInteger i，這裏fromInteger是Num類的一個方法(見數節)。浮點數符f等價於fromRational (n Ratio.% d)，這裏fromRational是Fractional類的方法，Ratio.% 由兩個整數構造一個有理數，在Ratio庫中定義。整數n和d選擇方法是n/d = f.

Curry應用及Lambda抽象

fexp → [fexp] aexp (函數應用)
lexp → \ apat₁ … apat_n -> exp (lambda抽象, n ≥ 1)

函數應用記為e₁ e₂。函數應用是左結合，因此(f x) y中的括號可以省略。除函數外，e₁也可以是數據構造符，因此，數據構造符的偏應用也是允許的。

Lambda抽象記為，\ p₁ ... p_n -> e, 其中，p_i是模式。形如\x:xs -> x的表達式語法上非法; 合法寫法是\ (x:xs) -> x。

模式集合必須是線性的-集合中的變量至多出現一次。

轉化：下面的轉化等價: \ p₁ … p_n -> e = \ x₁ … x_n -> case (x₁, …, x_n) of (p₁, …, p_n) -> e 其中，x_i是新標識符。

如果由這裏的轉換以及模式匹配節給出的case表達式以及模式匹配的語義不能匹配某個模式，則其結果是⊥。

操作符應用

infixexp → lexp qop infixexp

| - infixexp (前綴求反)

| lexp

qop → qvarop | qconop (限定操作符)
e₁ qop e₂是二元操作符qop應用於表達式e₁及e₂的中綴形式。表達式-e形式特殊，是Haskell中唯一的前綴操作符，是negate (e)的語法表示。二元操作符"-"不一定指 Prelude中定義的"-"操作符，它有可能被模塊系統重新定義。而，單元操作符"-"總是指Prelude中定義的求反函數。本地定義"-"操作符和單元求反之間沒有聯繫。

前綴求反和中綴操作符-有相同的優先級(見嵌套聲明節表)。表達式e₁ - e₂被解析為二元操作符-的中綴應用，因此，如果要得到另外一種解析，我們必須寫成e₁ (-e₂)。類似地，(-)是(\ x y -> x - y)的語法，和其它中綴操作符一樣，它不表示(\ x -> -x)，我們必須使用求反來獲得(\ x-> -x)。

轉化：下面式子等價: e₁ = (op) e₁ e₂ -e = negate (e)

分切

aexp → ( infixexp qop ) (左分切)

| ( qop_<-> infixexp ) (右分切)

分切被記為( op e)或(e op)，這裏，op是二元操作符，e是表達式。分切是二元操作符實現偏應用的便利語法。

語法優先級規則應用於分切如下所述：當且僅當(x op (e))和(x op e)語法解析相同時，(op e)合法。同理，(e op)也有此規則。舉個例子，(*a+b)語法非法，但(+a*b)及(*(a+b))卻合法。由於(+)左結合，(a+b+)語法正確，但(+a+b)錯誤。後者可以合法記為(+(a+b))。另外一個例子，由表達式節let/lambda元規則，表達式：

  (let n = 10 in n +)

非法。因為，表達式

  (let n = 10 in n + x)

語法解析為:

  (let n = 10 in (n + x))

而不是

  ((let n = 10 in n) + x)

由於語法中對-處理特殊，(- exp)不是分切，而是前綴求反應用。這在前面章節中有所論述。然而，Prelude定義了一個subtract函數，(subtract exp)等價於前面被禁掉的分切。同樣地，表達式(+ (- exp))也能達到相同的目的。

轉化：下面式子等價: (op e) = \ x -> x op e (e op) = \ x -> e op x 其中，op是二元操作符，e是表達式，x是不在e中自由出現的變量。

條件式

lexp → if exp [;] then exp [;] else exp

條件式形如if e₁ then e₂ else e₃。當e₁值為True時，返回e₂的值，當e₁值為False時返回e₃，其它情況下，返回⊥

轉化：下面式子等價: if e₁ then e₂ else e₃ = case e₁ of { True -> e₂ ; False -> e₃ } 其中，True和False是Prelude中定義的、類型為Bool的非空構造符。e₁的類型必須為Bool; e₂和e₃類型必須相同，且都是整個條件式的類型。

列表

infixexp -> exp₁ qop exp₂
aexp -> [exp₁, ..., exp_k] (k ≥ 1)

| gcon

gcon -> []

| qcon

qcon -> ( gconsym )
qop -> qconop
qconop -> gconsym
gconsym -> :

列表記為[e₁,...,e_k],其中k≥1。列表構造符是:, 空列表表示為[]。列表的標準操作在Prelude節給出(見列表，及標準Prelude章，特別是Prelude preludelist節)。

轉化：下面式子等價: [e₁,...,e_k] = e₁:(e₂:(...(e_k:[])))，其中，:及[]是列表的構造符(見列表節)。e₁到e_k的類型都必須一樣(稱類型t)，整個表達式的類型是[t](見類型文法節)。

構造符":"僅為列表構造保留；類似[]，是語言文法的一部分，不能被隱藏或者重定義。它是右結合操作符，優先級為5(見綴聲明節)。

元組

aexp -> ( exp₁ , … , exp_k ) (k ≥ 2)

| qcon

qcon -> (,{,})

元組記為(e₁,...,e_k)，可以是任意長度(k≥2)。n元組的構造符表示為(,...,)，其中有n-1個逗號。這樣，(a,b,c)和(,,) a b c 表示同樣的值。標準元組操作定義在Prelude章(見元組節，及標準Prelude章)。

轉化： (e₁,...,e_k)(其中k≥2)是定義在Prelude中的k維元祖實例，無需轉換。如果t₁至t_k分別是e₁至e_k的類型，那麼結果元組的類型是(t₁,...,t_k)(見元組節)。

元表達式和括號表達式

aexp -> gcon

| ( exp )

gcon -> ()

(e)形式是簡單括號表達式，等價於e。單元表達式()類型為()(見類型文法)。除去⊥, 單元表達式是()的唯一成員，可以被看作是"空類型"(見單元數據類型節)。

轉化：下面式子等價: (e)等價於e。

算術序列

aexp -> [ exp₁ [, exp₂] .. [exp₃] ]
算術序列[e₁, e₂ .. e₃]表示元素類型為t的列表，其中每個表達式e_i有類型t, 類型t是類Enum的一個實例。

轉化：下面的算術序列等價: [e₁..] = enumFrom e₁ [e₁,e₂..] = enumFromThen e₁ e₂ [e₁..e₃] = enumFromTo e₁ e₃ [e₁,e₂..e₃] = enumFromThenTo e₁ e₂ e₃

其中，enumFrom, enumFromThen, enumFromTo及enumFromThenTo是Enum類的類方法，見Prelude(見標準Haskell類型)中的定義。

因此，算術序列的語言全部依賴於類型t的實例聲明。Enum類節給出了更多的細節，包括定義在Prelude中的Enum類型，以及它們的語義。

列表組合

aexp → [ exp | qual₁ , … , qual_n ] (列表組合, n ≥ 1)
qual → pat <- exp (生成器)

| let decls (本地聲明)

| exp (布爾守護)

列表組合形為[e|q₁,...,q_n],n≥1, 這裏量詞q_i可能是

形為p<-e的生成器，p是一個類型為t的模式(見模式匹配節)，e是類型是[t]的表達式
本地綁定，生成新的定義，供生成的表達式e或隨後的布爾守衛和生成器使用
布爾守衛，為Bool類型的任意表達式

表達式e，在隨後的量詞列表中按照嵌套、深度優先的方式求值，返回的元素序列即是列表組合的返回值。綁定變量按照一般模式匹配的形式(見模式匹配出現，如果某個匹配失敗，則列表中那個元素被忽略。比如：

[ x | xs <- [ [(1,2),(3,4)], [(5,4),(3,2)] ], (3,x) <- xs]

生成列表[4,2]. 如果某個量詞是布爾守衛，它必須求值為真才能讓之前的模式繼續。作為一般規則，列表組合中的綁定可以映射外部域綁定，舉個例子：

[ x | x <- x, x <- x]

=

[ z | y <- x, z <- y]

轉化：下面的轉化等價: [ e \| True ] = [e] [ e \| q ] = [ e \| q, True ] [ e \| b, Q ] = if b then [ e \| Q ] else [] [ e \| p <- l, Q ] = let ok p = [ e \| Q ] ok _ = [] in concatMap ok l [ e \| let decls, Q ] = let decls in [ e \| Q ] 其中，e是表達式，p是模式，l是列表表達式，b是布爾表達式，decls是聲明列表，q是量詞，Q表示量詞序列，ok是全新的自由變量，函數concatMap以及布爾值True,在Prelude中定義。

正如列表組合轉化中所表達的，let綁定的變量是全多型變量，由<-定義的lambda變量是單態變量(見單態節)。

let表達式

lexp -> let decls in exp
Let表達式通用形式為let { d₁ ; ... ; d_n } in e, let引入嵌入地、詞法域、互遞歸聲明列表(let在其它語言也稱為letrec). 聲明的域為表達式e以及聲明的右半邊。聲明在聲明和綁定章講述。模式綁定採用惰性匹配；隱式的~使得這些模式異常鞏固。比如，

let (x,y) = undefined in e

不會發生運行時錯誤，除非需要對x或y求值。

轉化：表達式 let {d₁; … ;d_n } in e₀ 的動態語義可由下面的轉化表達：在去除所有的類型標籤後，每個聲明d_i 被轉化為一個等式，形如p_i = e_i, 這裏p_i和e_i分別表示模式和表達式，使用函數與模式綁定節中的轉化。一旦轉化完成，這些標示符可用作到核的一個轉化。 let {~p₁, ..., ~p_n } in e₀ = let (~p₁, ..., ~p_n) = (e₁, ..., e_n) in e₀ let p = e₁ in e₀ = case e₁ of ~p -> e₀ 這裏，p中變量不會自由出現在e₁ let p = e₁ in e₀ = let p = fix (\ ~p -> e₁) in e₀ 其中，fix是最小不動點算子。需要注意這裏使用的鞏固模式~p. 這個轉化不能保持靜態語義, 使用case禁止了綁定變量的全多態類型。let表達式中綁定的靜態語義在函數與模式綁定節講述。

case表達式

do表達式

lexp -> do {stmts}
stmts -> stmt1 ... stmtn exp [;]
stmt - >exp;<br\>

|pat<-exp;

|let decls;

|;

do 表達式為monadic編程提供了很多方便的語法。他可以允許下面的表達式

putStr "x: "  >>
getLine	      >>= \l->
return (words l)

用更傳統的方式可以這樣

do putStr "x: " 
   l<-getLine
   return (words l)

轉換：Do 表達式滿足以下特性： do {e} = e do {e;stmts} = e>>do{stmts} do {p<-e;stmts} = let ok p = do {stmts} ok _ = fail "..." do {let decls;stmts} = let decls in do {stmts} 這個省略號"..." 代表編譯器的錯誤信息,傳遞給fail,最好可以指示模式匹配錯誤的位置；函數>>,>>=,以及fail都是Monad類中操作符。 ok函數，如果p<-e返回的是p則執行do {stmts},否則失敗報錯

正如do轉換所示，被let綁定的變量有完全的多類型類(函數可以用於多種類型)，而被<-定義的變量卻是lambda綁定的，並且是單一同態的(函數只能用一種類型)。

舉例來說，你可以在do中可以

let a = "str" let b = 2

但是不可以

a<-Just "st"  b<-getLine

因為a後面跟着的是Maybe類型，b後面跟着的是IO類型。是兩種不同的類型了。

錯誤

變量，構造符，操作符和終結符

Curry應用及Lambda抽象

操作符應用

分切

條件式

列表

元組

元表達式和括號表達式

算術序列

列表組合

let表達式

case表達式

do表達式

域標記數據類型

表達式類型簽名

模式匹配