fbe1b6be096f62a0978e8c85332394b8912812d3
[haskell-report.git] / report / syntax-iso.verb
1 %
2 % $Header: /home/cvs/root/haskell-report/report/syntax-iso.verb,v 1.11 2002/12/10 11:51:11 simonpj Exp $
3 %
4 %**<title>Haskell 98 Syntax</title>
5 %**~header
6 \section{Syntax Reference}
7 \label{syntax}
8 \index{syntax}
9
10 \subsection{Notational Conventions}
11
12 These notational conventions are used for presenting syntax:
13
14 \[\ba{cl}
15 "[pattern]"             & \tr{optional} \\
16 "\{pattern\}"           & \tr{zero or more repetitions} \\
17 "(pattern)"             & \tr{grouping} \\
18 "pat_1 | pat_2"         & \tr{choice} \\
19 "pat_{\langle{}pat'\rangle{}}"  & \tr{difference---elements generated by "pat"} \\
20                         & \tr{except those generated by "pat'"} \\
21 "@fibonacci@"           & \tr{terminal syntax in typewriter font}
22 \ea\]
23
24 BNF-like syntax is used throughout, with productions having the form:
25 @@@
26 nonterm         -> alt_1 | alt_2 | ... | alt_n
27 @@@
28
29 There are some families of nonterminals indexed by
30 precedence levels (written as a superscript).  Similarly, the
31 nonterminals "op", "varop", and "conop" may have a double index:
32 a letter "l", "r", or "n" for left-, right- or nonassociativity and
33 a precedence level.  A precedence-level variable "i" ranges from 0 to 9;
34 an associativity variable "a" varies over "\{l, r, n\}".
35 Thus, for example
36 @@@
37 aexp    ->  @(@ exp^{i+1} qop^{(a,i)} @)@
38 @@@
39 actually stands for 30 productions, with 10 substitutions for "i"
40 and 3 for "a".
41
42 In both the lexical and the context-free syntax, there are some
43 ambiguities that are to be resolved by making grammatical phrases as
44 long as possible, proceeding from left to right (in shift-reduce
45 parsing, resolving shift/reduce conflicts by shifting).  In the lexical
46 syntax, this is the ``maximal munch'' rule\index{maximal munch rule}.  In the
47 context-free syntax, this means that conditionals, let-expressions, and
48 lambda abstractions extend to the right as far as possible.
49
50 % here we input a list of the main changes in version 1.1
51 % \input{syntax-changes-11}
52
53 %*anchor on
54 \subsection{Lexical Syntax}
55
56 % This covers only part of the lexical syntax.  The rest is directly
57 % included since it is much more scattered.
58
59 \input{syntax-lexical}
60
61 @@@
62 varid   -> (small \{small | large | digit | @'@ \})_{\langle{}reservedid\rangle{}}
63 conid           -> large \{small | large | digit | @'@ \} 
64 reservedid -> @case@ | @class@ | @data@ | @default@ | @deriving@ | @do@ | @else@
65         | @if@ | @import@ | @in@ | @infix@ | @infixl@ | @infixr@ | @instance@
66         | @let@ | @module@ | @newtype@ | @of@ | @then@ | @type@ | @where@ | @_@
67
68 varsym          -> ( symbol \{symbol | @:@\} )_{\langle{}reservedop | dashes\rangle{}}
69 consym          -> (@:@ \{symbol | @:@\})_{\langle{}reservedop\rangle{}}
70 reservedop      -> @..@ | @:@ | @::@ | @=@ | @\@ | @|@ | @<-@ | @->@ | {\tt @@} | @~@ | @=>@
71
72 varid                   && (\tr{variables})
73 conid                   && (\tr{constructors})
74 tyvar   ->  varid       & (\tr{type variables})
75 tycon   ->  conid       & (\tr{type constructors})
76 tycls   ->  conid       & (\tr{type classes})
77 modid   ->  conid       & (\tr{modules})
78
79 qvarid   -> [ modid @.@ ] varid
80 qconid   -> [ modid @.@ ] conid
81 qtycon   -> [ modid @.@ ] tycon
82 qtycls   -> [ modid @.@ ] tycls
83 qvarsym  -> [ modid @.@ ] varsym
84 qconsym  -> [ modid @.@ ] consym
85
86 decimal         -> digit\{digit\}
87 octal           -> octit\{octit\}
88 hexadecimal     -> hexit\{hexit\}
89
90 integer         -> decimal
91                 |  @0o@ octal | @0O@ octal
92                 |  @0x@ hexadecimal | @0X@ hexadecimal
93 float           -> decimal @.@ decimal [exponent]
94                 |  decimal exponent
95 exponent        -> (@e@ | @E@) [@+@ | @-@] decimal
96
97 char    ->  @'@ (graphic_{\langle{}@'@ | @\@\rangle{}} | space | escape_{\langle{}@\&@\rangle{}}) @'@
98 string  ->  @"@ \{graphic_{\langle{}@"@  | @\@\rangle{}} | space | escape | gap\} @"@
99 escape  ->  @\@ ( charesc | ascii | decimal | @o@ octal | @x@ hexadecimal )
100 charesc -> @a@ | @b@ | @f@ | @n@ | @r@ | @t@ | @v@ | @\@ | @"@ | @'@ | @&@
101 ascii   -> @^@cntrl | @NUL@ | @SOH@ | @STX@ | @ETX@ | @EOT@ | @ENQ@ | @ACK@ 
102        | @BEL@ | @BS@ | @HT@ | @LF@ | @VT@ | @FF@ | @CR@ | @SO@ | @SI@ | @DLE@ 
103        | @DC1@ | @DC2@ | @DC3@ | @DC4@ | @NAK@ | @SYN@ | @ETB@ | @CAN@ 
104        | @EM@ | @SUB@ | @ESC@ | @FS@ | @GS@ | @RS@ | @US@ | @SP@ | @DEL@
105 cntrl   -> ascLarge | @@ | @[@ | @\@ | @]@ | @^@ | @_@
106 gap     ->  @\@ whitechar \{whitechar\} @\@
107 @@@
108 \indexsyn{varid}%
109 \indexsyn{conid}%
110 \indexsyn{reservedid}%
111 \indexsyn{varsym}%
112 \indexsyn{consym}%
113 \indexsyn{symbol}%
114 \indexsyn{reservedop}%
115 \indexsyn{tyvar}%
116 \indexsyn{tycon}%
117 \indexsyn{tycls}%
118 \indexsyn{modid}%
119 \indexsyn{qvarid}%
120 \indexsyn{qconid}%
121 \indexsyn{qtycon}%
122 \indexsyn{qtycls}%
123 \indexsyn{qvarsym}%
124 \indexsyn{qconsym}%
125 \indexsyn{decimal}%
126 \indexsyn{octal}%
127 \indexsyn{hexadecimal}%
128 \indexsyn{char}%
129 \indexsyn{string}%
130 \indexsyn{escape}%
131 \indexsyn{charesc}%
132 \indexsyn{ascii}%
133 \indexsyn{cntrl}%
134 \indexsyn{gap}%
135
136
137 \subsection{Layout}
138 \label{layout}
139 \index{layout}
140
141 Section~\ref{lexemes-layout} gives an informal discussion of the layout
142 rule. This section defines it more precisely.
143
144 The meaning of a Haskell program may depend on its {\em layout}.
145 The effect of layout on its meaning can be completely described by adding
146 braces and semicolons in places determined by the layout.  The meaning of
147 this augmented program is now layout insensitive.
148
149 The effect of layout is specified in this section by describing
150 how to add braces and semicolons to a laid-out program.  The specification
151 takes the form of a function "L" that performs the translation.
152 The input to "L" is:
153 \begin{itemize}
154 \item 
155 A stream of lexemes as specified by the lexical syntax in the Haskell report,
156 with the following additional tokens: 
157 \begin{itemize}
158 \item If a @let@, @where@, @do@, or @of@ keyword is not followed by the lexeme @{@, 
159 the token "\{n\}" is inserted after the keyword, where "n" is the indentation of the 
160 next lexeme if there is one, or "0" if the end of file has been reached.
161 \item If the first lexeme of a module is not @{@ or @module@, 
162 then it is preceded by "\{n\}" where "n" is the indentation of the lexeme. 
163 \item Where the start of a lexeme is preceded only by white space on the
164    same line, this lexeme is preceded by "<n>" where "n"
165    is the indentation of the lexeme, provided that it is not,
166    as a consequence of the first two rules, preceded by "\{n\}".
167    (NB: a string literal may span multiple lines -- Section~\ref{lexemes-char}.  So in the fragment
168 \bprog
169 @
170   f = ("Hello \
171           \Bill", "Jake")
172 @
173 \eprog
174 There is no "<n>" inserted before the "@\Bill@", because it is not the beginning of
175 a complete lexeme; nor before the "@,@", because it is not preceded only by white space.)
176 \end{itemize}
177
178 \item A stack of ``layout contexts'', in which each element is either:
179 \begin{itemize}
180 \item Zero, indicating that the enclosing context is explicit (i.e. the programmer 
181 supplied the opening brace. 
182 If the innermost context is 0, then no layout tokens will be inserted 
183 until either the enclosing context ends or a new context is pushed. 
184 \item A positive integer, which is the indentation column of the enclosing layout context. 
185 \end{itemize}
186 \end{itemize}
187
188 The ``indentation'' of a lexeme is the column number
189 of the first character of that lexeme; the indentation of a line is the
190 indentation of its leftmost lexeme.  To determine the column number,
191 assume a fixed-width font with the following conventions:
192 \begin{itemize}
193 \item The characters "newline", "return", "linefeed", and "formfeed", all start a new line.
194 \item The first column is designated column 1, not 0.
195 \item Tab stops are 8 characters apart.
196 \item A tab character causes the insertion of
197 enough spaces to align the current position with the next tab stop.
198 \end{itemize}
199 For the purposes of the layout rule, Unicode characters in a source program
200 are considered to be of the same, fixed, width as an ASCII character.
201 However, to avoid visual confusion, programmers should avoid writing programs in which 
202 the meaning of implicit layout depends on the width of non-space characters.
203
204 The application
205 \[
206 L~tokens~[]
207 \]
208 delivers a layout-insensitive translation of "tokens", where "tokens"
209 is the result of lexically analysing a module and adding column-number
210 indicators to it as described above.
211 The definition of "L" is as follows, where we use ``":"'' as a stream
212 construction operator, and ``"\emptystr"'' for the empty stream.
213 % \begin{center}
214 % \[\ba{lcll}
215 %      L~ (<n>:ts)~ (m:ms)   & = & @;@ ~:~ (L~ ts~(m:ms))           &\mbox{if}~ m = n \\
216 %                            & = & @}@ ~:~ (L~ (<n>:ts)~ ms)       & \mbox{if}~ n < m \\
217 %                            & = & L~ ts~(m:ms)                   & \mbox{otherwise} \\
218 % \\
219 %      L~ (\{n\}:ts)~ (m:ms)   & = & @{@ ~:~ (L~ ts~(n:m:ms))         & \mbox{if}~n > m~   (Note~ 1)\\
220 %                            & = & @{@ ~:~ @}@ ~:~  (L~ ts~(<n>:m:ms))  & \mbox{otherwise}~   (Note~ 2)\\
221 % \\
222 %      L~ (t:ts)~ (m:ms)       & = & @}@ ~:~ (L~ (t:ts)~ ms)           & \mbox{if}~ m /= 0 ~\mbox{and}~ \mbox{parse-error}(t) \\
223 %                           &&& (Note~ 3) \\
224 % \\
225 %      L~ (@}@:ts)~ (0:ms)     & = & @}@ ~:~ (L~ ts~ms)     &                       (Note~ 4) \\
226 % \\
227 %      L~ (@{@:ts)~ ms         & = & @{@ ~:~ (L~ ts~(0:ms))                   &     (Note~ 5)\\
228 % \\
229 %      L~ (t:ts)~ ms           & = & t ~:~ (L~ ts~ms)\\
230 % \\
231 %      L~ \emptystr~ [0]                   & = & \emptystr\\
232 %      L~ \emptystr~ (m:ms)        & = & @}@ ~:~ L~ \emptystr~ ms          & \mbox{if}~m \neq 0~  (Note~ 6)
233 % \ea\]
234 % \end{center}
235 \begin{center}
236 \[\ba{lcll}
237      L~ (<n>:ts)~ (m:ms)   & = & @;@ ~:~ (L~ ts~(m:ms))           &\mbox{if}~ m = n \\
238                            & = & @}@ ~:~ (L~ (<n>:ts)~ ms)       & \mbox{if}~ n < m \\
239      L~ (<n>:ts)~ms        & = & L~ ts~ms \\
240 \\
241      L~ (\{n\}:ts)~ (m:ms)   & = & @{@ ~:~ (L~ ts~(n:m:ms))      & \mbox{if}~n > m~   (Note~ 1)\\
242      L~ (\{n\}:ts)~ []       & = & @{@ ~:~ (L~ ts~[n])           & \mbox{if}~n > 0~   (Note~ 1)\\
243      L~ (\{n\}:ts)~ ms       & = & @{@ ~:~ @}@ ~:~  (L~ (<n>:ts)~ms) & (Note~ 2)\\
244 \\
245      L~ (@}@:ts)~ (0:ms)     & = & @}@ ~:~ (L~ ts~ms)           & (Note~ 3) \\
246      L~ (@}@:ts)~ ms         & = & \mbox{parse-error}           & (Note~ 3) \\
247      
248 \\
249      L~ (@{@:ts)~ ms         & = & @{@ ~:~ (L~ ts~(0:ms))       &     (Note~ 4)\\
250 \\
251      L~ (t:ts)~ (m:ms)       & = & @}@ ~:~ (L~ (t:ts)~ ms)      & \mbox{if}~ m /= 0 ~\mbox{and}~ \mbox{parse-error}(t) \\
252                                                                     &&& (Note~ 5) \\
253      L~ (t:ts)~ ms           & = & t ~:~ (L~ ts~ms)\\
254 \\
255      L~ \emptystr~ []              & = & \emptystr\\
256      L~ \emptystr~ (m:ms)          & = & @}@ ~:~ L~ \emptystr~ ms          & \mbox{if}~m \neq 0~  (Note~ 6)
257 \ea\]
258 \end{center}
259 \begin{description}
260 \item[Note 1.] A nested context must be further indented 
261 than the enclosing context ("n>m"). If not, "L" fails, and the compiler should indicate a
262 layout error.  An example is:
263 \bprog
264 @
265   f x = let
266            h y = let
267     p z = z
268                  in p
269         in h
270 @
271 \eprog
272 Here, the definition of @p@ is indented less than the indentation of
273 the enclosing context, which is set in this case by the definition of @h@.
274
275 \item[Note 2.] If the first token after a @where@ (say) is not indented more
276 than the enclosing layout context, then the block must be empty, so empty
277 braces are inserted.  The $\{n\}$ token is replaced by $<n>$, to mimic the
278 situation if the empty braces had been explicit.
279
280 \item[Note 3.] By matching against 0 for the current layout context, 
281 we ensure that an explicit close brace can only match an explicit open brace. 
282 A parse error results if an explicit close brace matches an implicit open brace.
283
284 \item[Note 4.] This clause means that all brace pairs are treated as explicit layout 
285 contexts, including labelled construction and update (Section~\ref{field-ops}). 
286 This is a difference between this formulation and Haskell 1.4.
287
288 \item[Note 5.] The side condition "\mbox{parse-error}(t)" is to be interpreted as follows: 
289 if the tokens generated so far by "L" together with the next token "t" 
290 represent an invalid prefix of the Haskell grammar, and the 
291 tokens generated so far by "L" followed by the token ``@}@''
292 represent a valid prefix of the Haskell grammar, then "\mbox{parse-error}(t)" is true. 
293
294 The test $m /= 0$ checks that an implicitly-added closing brace would match
295 an implicit open brace.
296
297 \item[Note 6.] At the end of the input, any pending close-braces are inserted. 
298 It is an error at this point to be within a non-layout context (i.e.~ "m = 0"). 
299 \end{description}
300
301 If none of the rules given above matches, then the algorithm fails. It
302 can fail for instance when the end of the input is reached, and a
303 non-layout context is active, since the close brace is missing. Some
304 error conditions are not detected by the algorithm, although they
305 could be: for example @let }@.
306
307 Note 1 implements the feature that layout processing can be stopped
308 prematurely by a parse error.  For example
309 \bprog
310 @
311         let x = e; y = x in e'
312 @
313 \eprog
314 is valid, because it translates to 
315 \bprog
316 @
317         let { x = e; y = x } in e'
318 @
319 \eprog
320 The close brace is inserted due to the parse error rule above.
321 The parse-error rule is hard to implement in its full generality, because 
322 doing so involves fixities.  For example, the expression
323 \bprog
324 @
325   do a == b == c
326 @
327 \eprog
328 has a single unambiguous (albeit probably type-incorrect) parse, namely
329 \bprog
330 @
331   (do { a == b }) == c
332 @
333 \eprog
334 because @(==)@ is non-associative.   Programmers are therefore advised to avoid
335 writing code that requires the parser to insert a closing brace in such
336 situations.
337
338
339 \startnewsection
340 \subsection{Literate comments}
341 \label{literate}
342 \index{literate comments}
343
344 The ``literate comment''
345 convention, first developed by Richard Bird and Philip Wadler for
346 Orwell, and inspired in turn by Donald Knuth's ``literate
347 programming'', is an alternative style for encoding \Haskell{} source
348 code. 
349 The literate style encourages comments by making them the default.  A
350 line in which ``@>@'' is the first character is treated as part of the
351 program; all other lines are comment.
352
353 The program text is recovered
354 by taking only those lines beginning with ``@>@'', 
355 and replacing the leading ``@>@'' with a space.
356 Layout and comments apply
357 exactly as described in Chapter~\ref{syntax} in the resulting text.
358
359 To capture some cases where one omits an ``@>@'' by mistake, it is an
360 error for a program line to appear adjacent to a non-blank comment line,
361 where a line is taken as blank if it consists only of whitespace.
362
363 By convention, the style of comment is indicated by the file
364 extension, with ``@.hs@'' indicating a usual Haskell file and
365 ``@.lhs@'' indicating a literate Haskell file.  Using this style, a
366 simple factorial program would be:
367 \bprog
368 @
369    This literate program prompts the user for a number
370    and prints the factorial of that number:
371
372 > main :: IO ()
373
374 > main = do putStr "Enter a number: "
375 >           l <- readLine
376 >           putStr "n!= "
377 >           print (fact (read l))
378           
379   This is the factorial function.
380
381 > fact :: Integer -> Integer
382 > fact 0 = 1
383 > fact n = n * fact (n-1)
384 @
385 \eprog
386
387
388 An alternative style of literate programming is particularly
389 suitable for use with the LaTeX text processing system.
390 In this convention, only those parts of the literate program that are
391 entirely enclosed between @\begin{code}@$\ldots$@\end{code}@ delimiters are
392 treated as program text; all other lines are comment.  More precisely:
393 \begin{itemize}
394 \item Program code begins on the first line following a line that begins @\begin{code}@.
395 \item Program code ends just before a subsequent line that begins @\end{code}@ (ignoring
396 string literals, of course).
397 \end{itemize}
398 It is not necessary
399 to insert additional blank lines before or after these delimiters, though
400 it may be stylistically desirable.  For example,
401 \bprog
402 @
403 \documentstyle{article}
404
405 \begin{document}
406
407 \section{Introduction}
408
409 This is a trivial program that prints the first 20 factorials.
410
411 \begin{code}
412 main :: IO ()
413 main =  print [ (n, product [1..n]) | n <- [1..20]]
414 \end{code}
415
416 \end{document}
417 @
418 \eprog
419 This style uses the same file extension.  It is not advisable to mix
420 these two styles in the same file.
421
422 \startnewsection
423 \subsection{Context-Free Syntax}
424 \label{bnf}
425 @@@
426 module -> @module@ modid [exports] @where@ body 
427        |  body
428 body   -> @{@ impdecls @;@ topdecls @}@
429         | @{@ impdecls  @}@
430         | @{@ topdecls  @}@
431
432 impdecls     -> impdecl_1 @;@ ... @;@ impdecl_n         &  (n>=1)
433 @@@
434 \indexsyn{module}%
435 \indexsyn{body}%
436 \indexsyn{modid}%
437 \indexsyn{impdecls}%
438
439 @@@
440 exports  -> @(@ export_1 @,@ ... @,@ export_n [ @,@ ] @)@ & (n>=0)
441
442 export   -> qvar
443          |  qtycon [@(..)@ | @(@ cname_1 @,@ ... @,@ cname_n @)@] & (n>=0)
444          |  qtycls [@(..)@ | @(@ qvar_1 @,@ ... @,@ qvar_n @)@] & (n>=0)
445          |  @module@ modid
446 @@@
447 \indexsyn{exports}%
448 \indexsyn{export}%
449
450 @@@
451 impdecl   -> @import@ [@qualified@] modid [@as@ modid] [impspec]
452           |     & (\tr{empty declaration})
453
454 impspec   -> @(@ import_1 @,@ ... @,@ import_n [ @,@ ] @)@ & (n>=0)
455              |  @hiding@ @(@ import_1 @,@ ... @,@ import_n [ @,@ ] @)@ &  (n>=0)
456
457 import    -> var
458           |  tycon [ @(..)@ | @(@ cname_1 @,@ ... @,@ cname_n @)@] & (n>=0)
459           |  tycls [@(..)@ | @(@ var_1 @,@ ... @,@ var_n @)@] & (n>=0)
460 cname     -> var | con
461 @@@
462 \indexsyn{impdecl}%
463 \indexsyn{impspec}%
464 \indexsyn{import}%
465 \indexsyn{cname}%
466
467 @@@
468 topdecls -> topdecl_1 @;@ ... @;@ topdecl_n     &  (n>=0)
469 topdecl -> @type@ simpletype @=@ type
470         |  @data@ [context @=>@] simpletype @=@ constrs [deriving]
471         |  @newtype@ [context @=>@] simpletype @=@ newconstr [deriving]
472         |  @class@ [scontext @=>@] tycls tyvar [@where@ cdecls]
473         |  @instance@ [scontext @=>@] qtycls inst [@where@ idecls]
474         |  @default@ @(@type_1 @,@ ... @,@ type_n@)@ & (n>=0)
475         |  decl
476 @@@
477 \indexsyn{topdecls}%
478 \indexsyn{topdecl}%
479
480 @@@
481 decls   -> @{@ decl_1 @;@ ... @;@ decl_n  @}@           &  (n>=0)
482 decl    -> gendecl
483         |  (funlhs | pat^0) rhs
484
485 cdecls  -> @{@ cdecl_1 @;@ ... @;@ cdecl_n  @}@         &  (n>=0)
486 cdecl   -> gendecl
487         |  (funlhs | var) rhs
488
489 idecls  -> @{@ idecl_1 @;@ ... @;@ idecl_n  @}@         &  (n>=0)
490 idecl   -> (funlhs | var) rhs
491         |                                               & (\tr{empty})
492
493 gendecl -> vars @::@ [context @=>@] type        & (\tr{type signature})
494         |  fixity [integer] ops                 & (\tr{fixity declaration})
495         |                                       & (\tr{empty declaration})
496
497 ops     -> op_1 @,@ ... @,@ op_n                & (n>=1)
498 vars    -> var_1 @,@ ...@,@ var_n               & (n>=1)
499 fixity  -> @infixl@ | @infixr@ | @infix@
500 @@@
501 \indexsyn{vars}%
502 \indexsyn{fixity}%
503 \indexsyn{ops}%
504 \indexsyn{gendecl}%
505 \indexsyn{decls}%
506 \indexsyn{decl}%
507 \indexsyn{cdecls}%
508 \indexsyn{cdecl}%
509 \indexsyn{idecls}%
510 \indexsyn{idecl}%
511
512
513 @@@
514 type      -> btype [@->@ type]                    & (\tr{function type})
515
516 btype    ->  [btype] atype                        & (\tr{type application})
517
518 atype    ->  gtycon
519           |  tyvar
520           |  @(@ type_1 @,@ ... @,@ type_k @)@ & (\tr{tuple type}, k>=2)
521           |  @[@ type @]@                      & (\tr{list type})
522           |  @(@ type @)@                      & (\tr{parenthesized constructor})
523
524 gtycon    -> qtycon
525           |  @()@                              & (\tr{unit type})
526           |  @[]@                              & (\tr{list constructor})
527           |  @(->)@                            & (\tr{function constructor})
528           |  @(,@\{@,@\}@)@                    & (\tr{tupling constructors})
529
530 context -> class
531         |  @(@ class_1 @,@ ... @,@ class_n @)@          &  (n>=0)
532 class   -> qtycls tyvar                 
533         |  qtycls @(@ tyvar atype_1 ...  atype_n @)@ &  (n>=1)
534 scontext -> simpleclass
535         |  @(@ simpleclass_1 @,@ ... @,@ simpleclass_n @)@              &  (n>=0)
536 simpleclass -> qtycls tyvar                     
537 @@@
538 \indexsyn{type}%
539 \indexsyn{btype}%
540 \indexsyn{atype}%
541 \indexsyn{gtycon}%
542 \indexsyn{context}%
543 \indexsyn{class}%
544 \indexsyn{simpleclass}%
545 \indexsyn{scontext}%
546
547
548 @@@
549 simpletype -> tycon tyvar_1 ... tyvar_k &  (k>=0)
550 constrs    -> constr_1 @|@ ... @|@ constr_n     &  (n>=1)
551 constr     -> con [@!@] atype_1 ... [@!@] atype_k       & (\tr{arity} con = k, k>=0)
552            |  (btype | @!@ atype) conop (btype | @!@ atype) & (\tr{infix} conop)
553            |  con @{@ fielddecl_1 @,@ ... @,@ fielddecl_n @}@ &  (n>=0)
554 newconstr  -> con atype
555            |  con @{@ var @::@ type @}@ 
556 fielddecl  -> vars @::@ (type | @!@ atype)
557 deriving   -> @deriving@ (dclass | @(@dclass_1@,@ ... @,@ dclass_n@)@)&  (n>=0)
558 dclass     -> qtycls
559 @@@
560 \indexsyn{simpletype}%
561 \indexsyn{constrs}%
562 \indexsyn{constr}%
563 \indexsyn{fielddecl}%
564 \indexsyn{deriving}%
565 \indexsyn{dclass}%
566 \indexsyn{newconstr}%
567
568 @@@
569 inst    -> gtycon
570         |  @(@ gtycon tyvar_1 ... tyvar_k @)@   & (k>=0, tyvars \tr{distinct})
571         |  @(@ tyvar_1 @,@ ... @,@ tyvar_k @)@  & (k>=2, tyvars \tr{distinct})
572         |  @[@ tyvar @]@
573         |  @(@ tyvar_1 @->@ tyvar_2 @)@         & tyvar_1 \tr{and} tyvar_2 \tr{distinct}
574 @@@
575 \indexsyn{inst}%
576
577 @@@
578 funlhs  ->  var apat \{ apat \}
579         |   pat^{i+1} varop^{(a,i)} pat^{i+1}
580         |   lpat^i varop^{({\rm{}l},i)} pat^{i+1}
581         |   pat^{i+1} varop^{({\rm{}r},i)} rpat^i
582         |   @(@ funlhs @)@  apat \{ apat \}
583
584 rhs     ->  @=@ exp [@where@ decls]
585         |   gdrhs [@where@ decls]
586
587 gdrhs   ->  gd @=@ exp [gdrhs]
588
589 gd      ->  @|@ exp^0 
590 @@@
591 \indexsyn{funlhs}%
592 \indexsyn{rhs}%
593 \indexsyn{gdrhs}%
594 \indexsyn{gd}%
595
596 @@@
597 exp     ->  exp^0 @::@ [context @=>@] type      & (\tr{expression type signature})
598         |   exp^0
599 exp^i   ->  exp^{i+1} [qop^{({\rm{}n},i)} exp^{i+1}]
600         |   lexp^i
601         |   rexp^i
602 lexp^i  ->  (lexp^i | exp^{i+1}) qop^{({\rm{}l},i)} exp^{i+1}
603 lexp^6  ->  @-@ exp^7
604 rexp^i  ->  exp^{i+1} qop^{({\rm{}r},i)} (rexp^i | exp^{i+1})
605 exp^{10} ->  @\@ apat_1 ... apat_n @->@ exp     & (\tr{lambda abstraction}, n>=1)
606         |   @let@ decls @in@ exp                & ({\tr{let expression}})
607         |   @if@ exp @then@ exp @else@ exp      & (\tr{conditional})
608         |   @case@ exp @of@ @{@ alts @}@        & (\tr{case expression})
609         |   @do@ @{@ stmts  @}@            & (\tr{do expression})
610         |   fexp
611 fexp    ->  [fexp] aexp                         & (\tr{function application})
612 @@@
613 \indexsyn{exp}%
614 \index{exp@@"exp^i"}%
615 \index{lexp@@"lexp^i"}%
616 \index{rexp@@"rexp^i"}%
617 \indexsyn{fexp}%
618
619 @@@
620 aexp    ->  qvar                                & (\tr{variable})
621         |   gcon                                & (\tr{general constructor})
622         |   literal                             
623         |   @(@ exp @)@                       & (\tr{parenthesized expression})
624         |   @(@ exp_1 @,@ ... @,@ exp_k @)@     & (\tr{tuple}, k>=2)
625         |   @[@ exp_1 @,@ ... @,@ exp_k @]@     & (\tr{list}, k>=1)
626         |   @[@ exp_1 [@,@ exp_2] @..@ [exp_3] @]@ & (\tr{arithmetic sequence})
627         |   @[@ exp @|@ qual_1 @,@ ... @,@ qual_n @]@   & (\tr{list comprehension}, n>=1)
628         |   @(@ exp^{i+1} qop^{(a,i)} @)@        & (\tr{left section})
629         |   @(@ lexp^{i} qop^{(l,i)} @)@        & (\tr{left section})
630         |   @(@ qop^{(a,i)}_{\langle@-@\rangle}  exp^{i+1} @)@        & (\tr{right section})
631         |   @(@ qop^{(r,i)}_{\langle@-@\rangle}  rexp^{i} @)@        & (\tr{right section})
632         |   qcon @{@ fbind_1 @,@ ... @,@ fbind_n @}@ & (\tr{labeled construction}, n>=0)
633         |   aexp_{\langle{}qcon\rangle{}} @{@ fbind_1 @,@ ... @,@ fbind_n @}@ & (\tr{labeled update}, n >= 1)
634 @@@
635 \indexsyn{aexp}%
636
637 @@@
638 qual    -> pat @<-@ exp         & (\tr{generator})
639          | @let@ decls          & (\tr{local declaration})
640          | exp                  & (\tr{guard})
641
642 alts    ->  alt_1 @;@ ... @;@ alt_n             &  (n>=0)
643 alt     ->  pat @->@ exp [@where@ decls]
644         |   pat gdpat [@where@ decls]
645         |                                       & (empty alternative)
646
647 gdpat   ->  gd @->@ exp [ gdpat ]
648
649 stmts -> stmt_1 ... stmt_n exp [@;@]  &  (n>=0)
650 stmt -> exp @;@
651       | pat @<-@ exp @;@
652       | @let@ decls @;@
653       | @;@                     & (empty statement)
654
655 fbind   ->  qvar @=@ exp
656         
657 @@@
658 \indexsyn{qual}%
659 \indexsyn{alts}%
660 \indexsyn{alt}%
661 \indexsyn{gdpat}%
662 \indexsyn{stmt}%
663 \indexsyn{stmts}%
664 \indexsyn{fbind}%
665
666 @@@
667 pat     ->  var @+@ integer & (\tr{successor pattern})
668         |  pat^0
669 pat^i   ->  pat^{i+1} [qconop^{({\rm{}n},i)} pat^{i+1}]
670         |   lpat^i
671         |   rpat^i
672 lpat^i  ->  (lpat^i | pat^{i+1}) qconop^{({\rm{}l},i)} pat^{i+1}
673 lpat^6  ->  @-@ (integer | float)               & (\tr{negative literal})
674 rpat^i  ->  pat^{i+1} qconop^{({\rm{}r},i)} (rpat^i | pat^{i+1})
675 pat^{10} ->  apat
676         |   gcon apat_1 ... apat_k              & (\tr{arity} gcon = k, k>=1)
677 @@@
678 \indexsyn{pat}%
679 \index{pat@@"pat^i"}%
680 \index{lpat@@"lpat^i"}%
681 \index{rpat@@"rpat^i"}%
682 \indexsyn{fpat}%
683 \indexsyn{fpats}%
684
685 @@@
686 apat    ->  var [{\tt @@} apat]                 & (\tr{as pattern})
687         |   gcon                                & (\tr{arity} gcon = 0) 
688         |   qcon @{@ fpat_1 @,@ ... @,@ fpat_k @}@ & (\tr{labeled pattern}, k>=0)
689         |   literal
690         |   @_@                                 & (\tr{wildcard})
691         |   @(@ pat @)@                         & (\tr{parenthesized pattern})
692         |   @(@ pat_1 @,@ ... @,@ pat_k @)@     & (\tr{tuple pattern}, k>=2)
693         |   @[@ pat_1 @,@ ... @,@ pat_k @]@     & (\tr{list pattern}, k>=1) 
694         |   @~@ apat                            & (\tr{irrefutable pattern})
695
696 fpat    ->  qvar @=@ pat
697 @@@
698 \indexsyn{apat}%
699 @@@
700 gcon    ->  @()@
701         |   @[]@
702         |   @(,@\{@,@\}@)@
703         |   qcon
704
705 var     ->  varid | @(@ varsym @)@              & (\tr{variable})
706 qvar    ->  qvarid | @(@ qvarsym @)@            & (\tr{qualified variable})
707 con     ->  conid | @(@ consym @)@              & (\tr{constructor})
708 qcon    ->  qconid | @(@ gconsym @)@            & (\tr{qualified constructor})
709 varop   ->  varsym | \bkqB varid \bkqA          & (\tr{variable operator})
710 qvarop  ->  qvarsym | \bkqB qvarid \bkqA        & (\tr{qualified variable operator})
711 conop   ->  consym | \bkqB conid \bkqA          & (\tr{constructor operator})
712 qconop  ->  gconsym | \bkqB qconid \bkqA        & (\tr{qualified constructor operator})
713 op      ->  varop | conop                       & (\tr{operator})
714 qop     ->  qvarop | qconop                     & (\tr{qualified operator})
715 gconsym ->  @:@ | qconsym
716 @@@
717 \indexsyn{gcon}%
718 \indexsyn{var}%
719 \indexsyn{qvar}%
720 \indexsyn{con}%
721 \indexsyn{qcon}%
722 \indexsyn{varop}%
723 \indexsyn{qvarop}%
724 \indexsyn{conop}%
725 \indexsyn{qconop}%
726 \indexsyn{op}%
727 \indexsyn{qop}%
728
729 %*anchor off
730 % Local Variables: 
731 % mode: latex
732 % End:
733 %**~footer
734