The Haskell 98 Report
top | back
| next | contents
| function index
以下の表記規約は、構文を表現するのに用いる。
[pattern] | オプション(あってもなくてもよい) |
{pattern} | 0回以上のくりかえし |
(pattern) | グループ化 |
pat1 | pat2 | 選択 |
pat<pat'> | 差異 --- pat によって生成される要素のうち |
pat' によって生成される要素を除いたもの | |
fibonacci | タイプライタフォントで表現された終端構文 |
全体を通して BNF風の構文を使う。生成ルールは以下の形式である。
nonterm | -> | alt1 | alt2 | ... | altn |
(上付文字で書かれた)優先順位のインデックスがついた非終端記号のグルー プがいくつかある。同様に非終端記号 op、varop および conop には二つのインデックスがつくことがある。文字 l, r または n はそれぞれ、左結合性優先度、 右結合性優先度、非結合性優先度をあらわしています。優先度変数 i の範囲は、0 から 9 で、結合性変数 a のとりうる範囲は {l, r, n} である。したがって、たとえば、
aexp | -> | ( expi+1 qop(a,i) ) |
は 30 種類の生成結果、つまり、i について 10 通り、a に ついて 3 通りである。
字句構文および文脈自由構文の両方において、いくつかの曖昧性が存在し、 これらは、文法句を左から右へできるだけ伸ばすことで解決する(シフト還元 構文解析では、シフト/還元の衝突はシフトすることで解決する)。字句構文 において、これは「大喰らい」法である。文脈自由構文では、これは、条件 文、let-式、λ抽象は、可能な限り右へ拡張されるということを意味する。
program | -> | {lexeme | whitespace } |
lexeme | -> | qvarid | qconid | qvarsym | qconsym |
| | literal | special | reservedop | reservedid | |
literal | -> | integer | float | char | string |
special | -> | ( | ) | , | ; | [ | ] | `| { | } |
whitespace | -> | whitestuff {whitestuff} |
whitestuff | -> | whitechar | comment | ncomment |
whitechar | -> | newline | vertab | space | tab | uniWhite |
newline | -> | return linefeed | return | linefeed | formfeed |
return | -> | a carriage return |
linefeed | -> | a line feed |
vertab | -> | a vertical tab |
formfeed | -> | a form feed |
space | -> | a space |
tab | -> | a horizontal tab |
uniWhite | -> | any Unicode character defined as whitespace |
comment | -> | dashes [ any<symbol> {any}] newline |
dashes | -> | -- {-} |
opencom | -> | {- |
closecom | -> | -} |
ncomment | -> | opencom ANYseq {ncomment ANYseq}closecom |
ANYseq | -> | {ANY}<{ANY}( opencom | closecom ) {ANY}> |
ANY | -> | graphic | whitechar |
any | -> | graphic | space | tab |
graphic | -> | small | large | symbol | digit | special | : | " | ' |
small | -> | ascSmall | uniSmall | _ |
ascSmall | -> | a | b | ... | z |
uniSmall | -> | any Unicode lowercase letter |
large | -> | ascLarge | uniLarge |
ascLarge | -> | A | B | ... | Z |
uniLarge | -> | any uppercase or titlecase Unicode letter |
symbol | -> | ascSymbol | uniSymbol<special | _ | : | " | '> |
ascSymbol | -> | ! | # | $ | % | & | * | + | . | / | < | = | > | ? | @ |
| | \ | ^ | | | - | ~ | |
uniSymbol | -> | any Unicode symbol or punctuation |
digit | -> | ascDigit | uniDigit |
ascDigit | -> | 0 | 1 | ... | 9 |
uniDigit | -> | any Unicode decimal digit |
octit | -> | 0 | 1 | ... | 7 |
hexit | -> | digit | A | ... | F | a | ... | f |
varid | -> | (small {small | large | digit | ' })<reservedid> | |
conid | -> | large {small | large | digit | ' } | |
reservedid | -> | case | class | data | default | deriving | do | else | |
| | if | import | in | infix | infixl | infixr | instance | ||
| | let | module | newtype | of | then | type | where | _ | ||
varsym | -> | ( symbol {symbol | :})<reservedop | dashes> | |
consym | -> | (: {symbol | :})<reservedop> | |
reservedop | -> | .. | : | :: | = | \ | | | <- | -> | @ | ~ | => | |
varid | (variables) | ||
conid | (constructors) | ||
tyvar | -> | varid | (type variables) |
tycon | -> | conid | (type constructors) |
tycls | -> | conid | (type classes) |
modid | -> | conid | (modules) |
qvarid | -> | [ modid . ] varid | |
qconid | -> | [ modid . ] conid | |
qtycon | -> | [ modid . ] tycon | |
qtycls | -> | [ modid . ] tycls | |
qvarsym | -> | [ modid . ] varsym | |
qconsym | -> | [ modid . ] consym | |
decimal | -> | digit{digit} | |
octal | -> | octit{octit} | |
hexadecimal | -> | hexit{hexit} | |
integer | -> | decimal | |
| | 0o octal | 0O octal | ||
| | 0x hexadecimal | 0X hexadecimal | ||
float | -> | decimal . decimal [exponent] | |
| | decimal exponent | ||
exponent | -> | (e | E) [+ | -] decimal | |
char | -> | ' (graphic<' | \> | space | escape<\&>) ' | |
string | -> | " {graphic<" | \> | space | escape | gap}" | |
escape | -> | \ ( charesc | ascii | decimal | o octal | x hexadecimal ) | |
charesc | -> | a | b | f | n | r | t | v | \ | " | ' | & | |
ascii | -> | ^cntrl | NUL | SOH | STX | ETX | EOT | ENQ | ACK | |
| | BEL | BS | HT | LF | VT | FF | CR | SO | SI | DLE | ||
| | DC1 | DC2 | DC3 | DC4 | NAK | SYN | ETB | CAN | ||
| | EM | SUB | ESC | FS | GS | RS | US | SP | DEL | ||
cntrl | -> | ascLarge | @ | [ | \ | ] | ^ | _ | |
gap | -> | \ whitechar {whitechar}\ |
2.7 節ではレイアウト規則に ついて非形式的に議論した。この節では、それをもう少し正確に定義する。
Haskell のプログラムの意味はそのレイアウトに依存することがあ る。意味に影響を与えるレイアウトは、そのレイアウトによって決定される 場所にブレースとセミコロンを付け加えることによって、完全に記述するこ とができる。こうして補足されたプログラムは今度は、レイアウトには影響 されない。
レイアウトの影響は、この節では、レイアウトを用いているプログラムに、 どのようにして、ブレースとセミコロンを追加するかを記述することによっ て指定する。この仕様は、変換を行う関数 L の形をとる。L への入力は
この Haskell レポートの字句構文で指定されたような字句の並びで、以下 のような追加トークンがついているもの。
「レイアウト文脈」のスタックのそれぞれの要素は以下のどれかである。
字句の「インデント」は字句の最初の文字のカラム数である。ひとつの行の インデントとは最も左にある字句のインデントを表す。このカラム数を決定 するために以下のような規約をもつ固定幅のフォントを仮定する。
レイアウトルールにあわせるために、ソースプログラム中の Unicode 文字は ASCII 文字と同じ幅の固定幅であると看倣す。しかしながら、見た目との混 乱を避けるためプログラマは暗黙のレイアウトの意味が非空白文字の幅に依 存するようなプログラムを書かないようにすべきである。
適用
L tokens []
は、tokens のレイアウトに関知しない変換をもたらす。ここで、 tokens はモジュールの字句解析および上述のようにカラム数表示子 を追加した結果である。L の定義は以下のとおり、ここでは 「:」をストリーム構築操作子として使い、「[]」は空のスト リームである。
L (<n>:ts) (m:ms) | = | ; : (L ts (m:ms)) | if m = n |
= | } : (L (<n>:ts) ms) | if n < m | |
L (<n>:ts) ms | = | L ts ms | |
L ({n}:ts) (m:ms) | = | { : (L ts (n:m:ms)) | if n > m (Note 1) |
L ({n}:ts) [] | = | { : (L ts [n]) | if n > 0 (Note 1) |
L ({n}:ts) ms | = | { : } : (L (<n>:ts) ms) | (Note 2) |
L (}:ts) (0:ms) | = | } : (L ts ms) | (Note 3) |
L (}:ts) ms | = | parse-error | (Note 3) |
L ({:ts) ms | = | { : (L ts (0:ms)) | (Note 4) |
L (t:ts) (m:ms) | = | } : (L (t:ts) ms) | if m /= 0 and parse-error(t) |
(Note 5) | |||
L (t:ts) ms | = | t : (L ts ms) | |
L [] [] | = | [] | |
L [] (m:ms) | = | } : L [] ms | if m /=0 (Note 6) |
入れ子になった文脈は、囲まれた文脈 (n>m) よりも深くインデ ントされて
いなければならない。さもなければ、L は失敗し、また、 コンパイラはレイ
アウトエラーを表示しなければならない。たとえば、
f x = let
h y = let
p z = z
in p
in h
ここで、p の定義は囲まれた文脈のインデントよりも浅いインデン
トである。この場合、h の定義によって設定される。
where の後の最初のトークンが、たとえば、囲まれた文脈よりもイ ンデントされているのでなければ、そのブロックは空でなければならない。 だから、空のブレースが挿入される。トークン {n} は <n> に置き換 えられ、空のブレースが明示的になっていた場合の状況を模倣する。
現在のレイアウト文脈について 0 に対して照合することで、明示的な閉ブ レースが明示的な開ブレースにのみ対応することを確かめる。もし、明示的 な閉ブレースが暗黙の開ブレースに対応している場合には構文解析エラーと なる。
これは、すべてのブレースの対は明示的なレイアウト文脈として扱われる こ とを意味し、ラベル付のデータ構築および更新 (3.15 節)を含む。ここにこの形式化と Haskell 1.4 での 違いがある。
副次的な条件 parse-error(t) は次のように解釈される。もし、次の トークンが t であるような L によっ て生成されたトークン が Haskell の文法の不正な接頭辞を表わしている場合、および、 「}」トークンが続く L によって生成さたトー クンの Haskell 文法の正しい接頭辞である場合、parse-error(t) は真とな る。
m /= 0 のチェックは、暗黙に追加された閉ブレースが、暗黙の開ブレースに 対応することをたしかめる。
入力の終端において、保留された閉ブレースがすべて挿入される。この時点 でレイアウト文脈のなかにある(すなわち、m = 0 である)とエラーとなる。
上のような照合になんの規則もなければ、アルゴリズムは失敗する。入力の 終端に達すると直ちに失敗し、非レイアウト文脈がアクティブになる。それ は閉ブレースが欠けているからである。おこり得るにもかかわらず、このア ルゴリズムでは検出できないエラー状態がある。たとえば、 let } である。
Note 1 は、レイアウト処理はパーズエラーにより相互に停止するという性質
を実現したものである。たとえば、
let x = e; y = x in e'
は正しい構文である。なぜなら、
let { x = e; y = x } in e'
に変換されるからである。閉ブレースは上のパーズエラールールにより挿入
される。このパーズエラールールは、これがもつ一般性を実装するのは困難
である。それは、演算子位置の問題を含んでいるからである。たとえば、次
の式
do a == b == c
は、(型としては正しくないかもしれないが)一つの明白な構文解析結果
をもつ。すなわち、
(do { a == b }) == c
である。なぜなら、(==) には結合性がないからである。ゆえに、
プログラマは、パーザがこのような場合に閉ブレースを挿入しなければなら
ないようなコードを書かないようにするべきなのである。
「文芸的コメント」の規約は、最初 Richard Bird と Philip Wadler が、 Donald Knuth の「文芸的プログラミング」に触発されて、Orwell 用に開発 したのであるが、Haskell のソースコードを書くときのもうひとつのスタイ ルでもある。文芸的スタイルは、デフォルトでコメントである。行頭が、「>」 である行がプログラムの一部としてあつかわれる。それ以外のすべての行は コメントである。
プログラム本文は「>」で始まる行のみから再構成され、各行の先頭の 「>」は空白に置き換えられる。レイアウトとコメントはその結果のテキ ストに対して 9 章で解説されたよ うに厳密に適用される。
あやまって、「>」を忘れたことを捕捉するために、プログラムラインが空 ではないコメント行に隣接した場合、エラーになる。このとき、空白だけか ら構成される行は空白行と解釈される。
規約として、コメントのスタイルはそのファイルの拡張子によって表示され
る。拡張子が「.hs」であるときこれは通常の Haskell のファイルであるこ
とを示している。「.lhs」は文芸的 Haskell のファイルであることを示して
いる。このスタイルを使うと、単純な階乗のプログラムは次のようになる。
This literate program prompts the user for a number
and prints the factorial of that number:
> main :: IO ()
> main = do putStr "Enter a number: "
> l <- readLine
> putStr "n!= "
> print (fact (read l))
This is the factorial function.
> fact :: Integer -> Integer
> fact 0 = 1
> fact n = n * fact (n-1)
文芸的プログラミングには特に LaTeX のテキスト処理に適したもうひとつの スタイルがある。この規約では、 \begin{code}...\end{code} 区切り子で囲まれている文 芸的プログラムの部分だけが、プログラムテキストとして扱われる。それ以 外の行はすべてコメントである。より正確には、
スタイルとしてそうすることが望ましいが、この区切り子の前後には余分な
空白行を挿入する必要はない。例をあげると、
\documentstyle{article}
\begin{document}
\section{Introduction}
This is a trivial program that prints the first 20 factorials.
\begin{code}
main :: IO ()
main = print [ (n, product [1..n]) | n <- [1..20]]
\end{code}
\end{document}
module | -> | module modid [exports] where body | |
| | body | ||
body | -> | { impdecls ; topdecls } | |
| | { impdecls } | ||
| | { topdecls } | ||
impdecls | -> | impdecl1 ; ... ; impdecln | (n>=1) |
exports | -> | ( export1 , ... , exportn [ , ] ) | (n>=0) |
export | -> | qvar | |
| | qtycon [(..) | ( cname1 , ... , cnamen )] | (n>=0) | |
| | qtycls [(..) | ( qvar1 , ... , qvarn )] | (n>=0) | |
| | module modid |
impdecl | -> | import [qualified] modid [as modid] [impspec] | |
| | (empty declaration) | ||
impspec | -> | ( import1 , ... , importn [ , ] ) | (n>=0) |
| | hiding ( import1 , ... , importn [ , ] ) | (n>=0) | |
import | -> | var | |
| | tycon [ (..) | ( cname1 , ... , cnamen )] | (n>=0) | |
| | tycls [(..) | ( var1 , ... , varn )] | (n>=0) | |
cname | -> | var | con |
topdecls | -> | topdecl1 ; ... ; topdecln | (n>=0) |
topdecl | -> | type simpletype = type | |
| | data [context =>] simpletype = constrs [deriving] | ||
| | newtype [context =>] simpletype = newconstr [deriving] | ||
| | class [scontext =>] tycls tyvar [where cdecls] | ||
| | instance [scontext =>] qtycls inst [where idecls] | ||
| | default (type1 , ... , typen) | (n>=0) | |
| | decl |
decls | -> | { decl1 ; ... ; decln } | (n>=0) |
decl | -> | gendecl | |
| | (funlhs | pat0) rhs | ||
cdecls | -> | { cdecl1 ; ... ; cdecln } | (n>=0) |
cdecl | -> | gendecl | |
| | (funlhs | var) rhs | ||
idecls | -> | { idecl1 ; ... ; idecln } | (n>=0) |
idecl | -> | (funlhs | var) rhs | |
| | (empty) | ||
gendecl | -> | vars :: [context =>] type | (type signature) |
| | fixity [integer] ops | (fixity declaration) | |
| | (empty declaration) | ||
ops | -> | op1 , ... , opn | (n>=1) |
vars | -> | var1 , ..., varn | (n>=1) |
fixity | -> | infixl | infixr | infix |
type | -> | btype [-> type] | (function type) |
btype | -> | [btype] atype | (type application) |
atype | -> | gtycon | |
| | tyvar | ||
| | ( type1 , ... , typek ) | (tuple type, k>=2) | |
| | [ type ] | (list type) | |
| | ( type ) | (parenthesized constructor) | |
gtycon | -> | qtycon | |
| | () | (unit type) | |
| | [] | (list constructor) | |
| | (->) | (function constructor) | |
| | (,{,}) | (tupling constructors) | |
context | -> | class | |
| | ( class1 , ... , classn ) | (n>=0) | |
class | -> | qtycls tyvar | |
| | qtycls ( tyvar atype1 ... atypen ) | (n>=1) | |
scontext | -> | simpleclass | |
| | ( simpleclass1 , ... , simpleclassn ) | (n>=0) | |
simpleclass | -> | qtycls tyvar |
simpletype | -> | tycon tyvar1 ... tyvark | (k>=0) |
constrs | -> | constr1 | ... | constrn | (n>=1) |
constr | -> | con [!] atype1 ... [!] atypek | (arity con = k, k>=0) |
| | (btype | ! atype) conop (btype | ! atype) | (infix conop) | |
| | con { fielddecl1 , ... , fielddecln } | (n>=0) | |
newconstr | -> | con atype | |
| | con { var :: type } | ||
fielddecl | -> | vars :: (type | ! atype) | |
deriving | -> | deriving (dclass | (dclass1, ... , dclassn)) | (n>=0) |
dclass | -> | qtycls |
inst | -> | gtycon | |
| | ( gtycon tyvar1 ... tyvark ) | (k>=0, tyvars distinct) | |
| | ( tyvar1 , ... , tyvark ) | (k>=2, tyvars distinct) | |
| | [ tyvar ] | ||
| | ( tyvar1 -> tyvar2 ) | tyvar1 and tyvar2 distinct |
funlhs | -> | var apat {apat } |
| | pati+1 varop(a,i) pati+1 | |
| | lpati varop(l,i) pati+1 | |
| | pati+1 varop(r,i) rpati | |
| | ( funlhs ) apat {apat } | |
rhs | -> | = exp [where decls] |
| | gdrhs [where decls] | |
gdrhs | -> | gd = exp [gdrhs] |
gd | -> | | exp0 |
exp | -> | exp0 :: [context =>] type | (expression type signature) |
| | exp0 | ||
expi | -> | expi+1 [qop(n,i) expi+1] | |
| | lexpi | ||
| | rexpi | ||
lexpi | -> | (lexpi | expi+1) qop(l,i) expi+1 | |
lexp6 | -> | - exp7 | |
rexpi | -> | expi+1 qop(r,i) (rexpi | expi+1) | |
exp10 | -> | \ apat1 ... apatn -> exp | (lambda abstraction, n>=1) |
| | let decls in exp | (let expression) | |
| | if exp then exp else exp | (conditional) | |
| | case exp of { alts } | (case expression) | |
| | do { stmts } | (do expression) | |
| | fexp | ||
fexp | -> | [fexp] aexp | (function application) |
aexp | -> | qvar | (variable) |
| | gcon | (general constructor) | |
| | literal | ||
| | ( exp ) | (parenthesized expression) | |
| | ( exp1 , ... , expk ) | (tuple, k>=2) | |
| | [ exp1 , ... , expk ] | (list, k>=1) | |
| | [ exp1 [, exp2] .. [exp3] ] | (arithmetic sequence) | |
| | [ exp | qual1 , ... , qualn ] | (list comprehension, n>=1) | |
| | ( expi+1 qop(a,i) ) | (left section) | |
| | ( lexpi qop(l,i) ) | (left section) | |
| | ( qop(a,i)<-> expi+1 ) | (right section) | |
| | ( qop(r,i)<-> rexpi ) | (right section) | |
| | qcon { fbind1 , ... , fbindn } | (labeled construction, n>=0) | |
| | aexp<qcon> { fbind1 , ... , fbindn } | (labeled update, n >= 1) |
qual | -> | pat <- exp | (generator) |
| | let decls | (local declaration) | |
| | exp | (guard) | |
alts | -> | alt1 ; ... ; altn | (n>=1) |
alt | -> | pat -> exp [where decls] | |
| | pat gdpat [where decls] | ||
| | (empty alternative) | ||
gdpat | -> | gd -> exp [ gdpat ] | |
stmts | -> | stmt1 ... stmtn exp [;] | (n>=0) |
stmt | -> | exp ; | |
| | pat <- exp ; | ||
| | let decls ; | ||
| | ; | (empty statement) | |
fbind | -> | qvar = exp | |
pat | -> | var + integer | (successor pattern) |
| | pat0 | ||
pati | -> | pati+1 [qconop(n,i) pati+1] | |
| | lpati | ||
| | rpati | ||
lpati | -> | (lpati | pati+1) qconop(l,i) pati+1 | |
lpat6 | -> | - (integer | float) | (negative literal) |
rpati | -> | pati+1 qconop(r,i) (rpati | pati+1) | |
pat10 | -> | apat | |
| | gcon apat1 ... apatk | (arity gcon = k, k>=1) |
apat | -> | var [@ apat] | (as pattern) |
| | gcon | (arity gcon = 0) | |
| | qcon { fpat1 , ... , fpatk } | (labeled pattern, k>=0) | |
| | literal | ||
| | _ | (wildcard) | |
| | ( pat ) | (parenthesized pattern) | |
| | ( pat1 , ... , patk ) | (tuple pattern, k>=2) | |
| | [ pat1 , ... , patk ] | (list pattern, k>=1) | |
| | ~ apat | (irrefutable pattern) | |
fpat | -> | qvar = pat |
gcon | -> | () | |
| | [] | ||
| | (,{,}) | ||
| | qcon | ||
var | -> | varid | ( varsym ) | (variable) |
qvar | -> | qvarid | ( qvarsym ) | (qualified variable) |
con | -> | conid | ( consym ) | (constructor) |
qcon | -> | qconid | ( gconsym ) | (qualified constructor) |
varop | -> | varsym | `varid ` | (variable operator) |
qvarop | -> | qvarsym | `qvarid ` | (qualified variable operator) |
conop | -> | consym | `conid ` | (constructor operator) |
qconop | -> | gconsym | `qconid ` | (qualified constructor operator) |
op | -> | varop | conop | (operator) |
qop | -> | qvarop | qconop | (qualified operator) |
gconsym | -> | : | qconsym |
The Haskell 98 Report
top | back
| next | contents
| function index
December 2002