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

var → varid | ( varsym ) (变量)
qvar → qvarid | ( qvarsym ) (限定变量)
con → conid | ( consym ) (构造符)
qcon → qconid | ( gconsym ) (限定构造符)
varop → varsym | ` varid ` (变量操作符)
qvarop → qvarsym | ` qvarid ` (限定变量操作符)
conop → consym | ` conid ` (构造符操作符)
qconop → gconsym | ` qconid ` (限定构造符操作符)
op → varop | conop (操作符)
qop → qvarop | qconop (限定操作符)
gconsym → : | qconsym

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。

模式集合必须是线性的-集合中的变量至多出现一次。

转化：下面的转化等价: \ p1 … pn -> e = \ x1 … xn -> case (x1, …, xn) of (p1, …, pn) -> e 其中，xi是新标识符。

如果由这里的转换以及模式匹配节给出的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)。

转化：下面式子等价: e1 = (op) e1 e2 -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 e1 then e2 else e3 = case e1 of { True -> e2 ; False -> e3 } 其中，True和False是Prelude中定义的、类型为Bool的非空构造符。e1的类型必须为Bool; e2和e3类型必须相同，且都是整个条件式的类型。

列表

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节)。

转化：下面式子等价: [e1,...,ek] = e1:(e2:(...(ek:[])))，其中，:及[]是列表的构造符(见列表节)。e1到ek的类型都必须一样(称类型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章)。

转化： (e1,...,ek)(其中k≥2)是定义在Prelude中的k维元祖实例，无需转换。如果t1至tk分别是e1至ek的类型，那么结果元组的类型是(t1,...,tk)(见元组节)。

元表达式和括号表达式

aexp -> gcon

| ( exp )

gcon -> ()

(e)形式是简单括号表达式，等价于e。 单元表达式()类型为()(见类型文法)。 除去⊥, 单元表达式是()的唯一成员，可以被看作是"空类型"(见单元数据类型节)。

转化：下面式子等价: (e)等价于e。

算术序列

aexp -> [ exp₁ [, exp₂] .. [exp₃] ]
算术序列[e₁, e₂ .. e₃]表示元素类型为t的列表，其中每个表达式e_i有类型t, 类型t是类Enum的一个实例。

转化：下面的算术序列等价: [e1..] = enumFrom e1 [e1,e2..] = enumFromThen e1 e2 [e1..e3] = enumFromTo e1 e3 [e1,e2..e3] = enumFromThenTo e1 e2 e3

其中，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 {d1; … ;dn } in e0 的动态语义可由下面的转化表达：在去除所有的类型标签后，每个声明di 被转化为一个等式，形如pi = ei, 这里pi和ei分别表示模式和表达式，使用函数与模式绑定节中的转化。一旦转化完成，这些标示符可用作到核的一个转化。 let {~p1, ..., ~pn } in e0 = let (~p1, ..., ~pn) = (e1, ..., en) in e0 let p = e1 in e0 = case e1 of ~p -> e0 这里，p中变量不会自由出现在e1 let p = e1 in e0 = let p = fix (\ ~p -> e1) in e0 其中，fix是最小不动点算子。需要注意这里使用的巩固模式~p. 这个转化不能保持静态语义, 使用case禁止了绑定变量的全多态类型。let表达式中绑定的静态语义在函数与模式绑定节讲述。

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类型。是两种不同的类型了。