More small changes to
[haskell-report.git] / report / lexemes.verb
1 %
2 % $Header: /home/cvs/root/haskell-report/report/lexemes.verb,v 1.14 2003/01/13 13:08:55 simonpj Exp $
3 %
4 %*section 2
5 %**<title>Haskell 98 Lexical Structure</title>
6 %**~header
7 \section{Lexical Structure}\index{lexical structure}
8 \label{lexical-structure}
9
10 % this quote is not in because: it is supposed to show Curry as an
11 % early advocate of abstract syntax.  However, as far as I know (which
12 % I can't be sure w/out going to the library), this quote is from 1972
13 % (when Vol II was published ?), which isn't particularly early.  This
14 % doesn't seem the sort of thing to get wrong!  If someone wants to do
15 % the checking and put it in (and re-BibTeX and re-check the page
16 % breaks :-), please feel free.
17
18 %% \begin{quote}
19 %% ``{\em The various systems of combinatory logic are presented in this
20 %% book as abstract obs systems.  It was mentioned in \S{}~1 that any
21 %% such system can be represented as a concrete syntactical system, and
22 %% that this can be done mechanically.  Nevertheless it seems expedient
23 %% to give such a representation explicitly for two reasons: in the first
24 %% place there is at present an almost universal insistence on such a
25 %% representation; in the second place the discussion of certain
26 %% philosophical questions is made somewhat easier by having a specific
27 %% representation before us.}''
28 %% \begin{flushright}
29 %% Haskell B.~Curry {\em et al.}\\
30 %% in {\em Combinatory Logic}, Vol.~II, page 8 \cite{curry-etal:volII}.
31 %% \end{flushright}
32 %% \end{quote}
33
34 \noindent
35 In this chapter, 
36 we describe the low-level lexical structure of \Haskell{}.
37 Most of the details may be skipped in a first reading of
38 the report.
39
40 \subsection{Notational Conventions}
41 \label{notational-conventions}
42
43 These notational conventions are used for presenting syntax:
44
45 \[\ba{cl}
46 "[pattern]"             & \tr{optional} \\
47 "\{pattern\}"           & \tr{zero or more repetitions} \\
48 "(pattern)"             & \tr{grouping} \\
49 "pat_1 | pat_2"         & \tr{choice} \\
50 "pat_{\langle{}pat'\rangle{}}"  & \tr{difference---elements generated by "pat"} \\
51                         & \tr{except those generated by "pat'"} \\
52 "@fibonacci@"           & \tr{terminal syntax in typewriter font}
53 \ea\]
54
55 Because the syntax in this section describes {\em lexical} syntax, all
56 whitespace is expressed explicitly; there is no
57 implicit space between juxtaposed symbols.  BNF-like syntax is used
58 throughout, with productions having the form:
59 @@@
60 nonterm         -> alt_1 | alt_2 | ... | alt_n
61 @@@
62
63 Care must be taken in distinguishing metalogical syntax such as "|"
64 and "[...]" from concrete terminal syntax (given in typewriter font)
65 such as @|@ and @[...]@, although usually the context makes the
66 distinction clear.
67
68 \Haskell{} uses the Unicode \cite{unicode} character set.
69 \index{Unicode character set}
70 However, source 
71 programs are currently biased toward the ASCII character set
72 \index{ASCII character set} used in earlier versions of \Haskell{}.
73
74 %       Removed Sept 02
75 % Haskell uses a pre-processor to convert non-Unicode character sets into
76 % Unicode.  This pre-processor converts all characters to Unicode and
77 % uses the escape sequence @\u@"hhhh", where the @"h"@ are hex digits,
78 % to denote escaped Unicode characters.  Since this translation occurs
79 % before the program is compiled, escaped Unicode characters may appear in
80 % identifiers and any other place in the program.
81
82 This syntax depends on properties of the Unicode characters as defined
83 by the Unicode consortium. 
84 \Haskell{} compilers are expected to make use of
85 new versions of Unicode as they are made available.
86
87 \subsection{Lexical Program Structure}
88 \label{lexemes}
89 \label{whitespace}
90
91 \input{syntax-lexical}
92
93 Lexical analysis should use the ``maximal munch'' rule:
94 at each point, the longest possible lexeme
95 satisfying the "lexeme" production is read.
96 \index{maximal munch rule}
97 % using a context-independent deterministic lexical analysis
98 % (i.e.~no lookahead beyond the current character is required).
99 % Not so -- consider the input "F. 9. 0o 0x 9.0e+f", which 
100 % should lex as "F . 9 . 0 o 0 x 9.0 e + f" but that needs up 
101 % to 2 additional characters of lookahead.  
102 So, although @case@ is a reserved word, @cases@ is not.
103 Similarly, although @=@ is reserved, @==@ and @~=@ are
104 not.  
105
106 Any kind of "whitespace" is also a proper delimiter for lexemes.
107
108 Characters not in the category "ANY" are not valid
109 in \Haskell{} programs and should result in a lexing error.
110
111 \subsection{Comments}
112
113 Comments\index{comment} are valid whitespace.
114
115 An ordinary comment\index{comment!end-of-line} begins with a sequence of
116 two or more consecutive dashes (e.g. @--@) and extends to the following newline.
117 {\em The sequence of dashes must not form part of a legal lexeme.}
118 For example, ``@-->@'' or ``@|--@'' do {\em not} begin
119 a comment, because both of these are legal lexemes; however ``@--foo@''
120 does start a comment.
121
122 A nested comment\index{comment!nested} begins with ``@{-@'' 
123 and ends with ``@-}@''.  No legal lexeme starts with ``@{-@''; 
124 hence, for example, ``@{---@'' starts a nested comment despite the trailing dashes.
125
126 The comment itself is not lexically analysed.  Instead, the first
127 unmatched occurrence of the string ``@-}@'' terminates the nested
128 comment.  Nested comments may be nested to any depth: any occurrence
129 of the string ``@{-@'' within the nested comment starts a new nested
130 comment, terminated by ``@-}@''.  Within a nested comment, each
131 ``@{-@'' is matched by a corresponding occurrence of ``@-}@''.
132
133 In an ordinary comment, the character
134 sequences ``@{-@'' and ``@-}@'' have no special significance, and, in a
135 nested comment, a sequence of dashes has no special significance.
136
137 Nested comments are also used for compiler pragmas, as explained in
138 Chapter~\ref{pragmas}.
139
140 If some code is commented out using a nested comment, then any
141 occurrence of @{-@ or @-}@ within a string or within an end-of-line
142 comment in that code will interfere with the nested comments.
143
144 \subsection{Identifiers and Operators}\index{identifier}\index{operator}
145 \label{ids}
146
147 @@@
148 varid   -> (small \{small | large | digit | @'@ \})_{\langle{}reservedid\rangle{}}
149 conid           -> large \{small | large | digit | @'@ \} 
150 reservedid -> @case@ | @class@ | @data@ | @default@ | @deriving@ | @do@ | @else@
151         | @if@ | @import@ | @in@ | @infix@ | @infixl@ | @infixr@ | @instance@
152         | @let@ | @module@ | @newtype@ | @of@ | @then@ | @type@ | @where@ | @_@
153 @@@
154 \indexsyn{varid}%
155 \indexsyn{conid}%
156 \indexsyn{reservedid}%
157
158 An identifier consists of a letter followed by zero or more letters,
159 digits, underscores, and single quotes.  Identifiers are lexically
160 distinguished into two namespaces (Section~\ref{namespaces}): those that begin with a lower-case letter
161 (variable identifiers) and those that begin with an upper-case letter
162 (constructor identifiers).  Identifiers are case sensitive: @name@,
163 @naMe@, and @Name@ are three distinct identifiers (the first two are
164 variable identifiers, the last is a constructor identifier).
165
166 Underscore, ``@_@'', is treated as a lower-case letter, and can occur
167 wherever a lower-case letter can.  However, ``@_@'' all by itself is a
168 reserved identifier, used as wild card in patterns.  Compilers that offer
169 warnings for unused identifiers are encouraged to suppress such warnings for
170 identifiers beginning with underscore.  This allows programmers to use
171 ``@_foo@'' for a parameter that they expect to be unused.
172
173 @@@
174 varsym          -> ( symbol \{symbol | @:@\} )_{\langle{}reservedop | dashes\rangle{}}
175 consym          -> (@:@ \{symbol | @:@\})_{\langle{}reservedop\rangle{}}
176 reservedop      -> @..@ | @:@ | @::@ | @=@ | @\@ | @|@ | @<-@ | @->@ | \verb+@@+ | @~@ | @=>@
177 @@@
178 \indexsyn{varsym}%
179 \indexsyn{consym}%
180 \indexsyn{reservedop}%
181
182 {\em Operator symbols} \index{operator} 
183 are formed from one or more symbol characters, as
184 defined above, and are lexically distinguished into two namespaces 
185 (Section~\ref{namespaces}):
186 \begin{itemize}
187 \item An operator symbol starting with a colon is a constructor.
188 \item An operator symbol starting with any other character is an ordinary identifier.
189 \end{itemize}
190 Notice that a colon by itself, ``@:@'', is reserved solely for use
191 as the Haskell list constructor; this makes its treatment uniform with
192 other parts of list syntax, such as ``@[]@'' and ``@[a,b]@''.
193
194 Other than the special syntax for prefix negation, all operators are
195 infix, although each infix operator can be used in a {\em
196 section}\index{section} to yield partially applied operators (see
197 Section~\ref{sections}).
198 All of the standard infix operators are just
199 predefined symbols and may be rebound.  
200
201 In the remainder of the report six different kinds of 
202 names\index{namespaces} will be used:
203
204 @@@
205 varid                  && (\tr{variables})
206 conid                  && (\tr{constructors})
207 tyvar   ->  varid       & (\tr{type variables})
208 tycon   ->  conid       & (\tr{type constructors})
209 tycls   ->  conid       & (\tr{type classes})
210 modid   ->  conid       & (\tr{modules})
211 @@@
212 \indexsyn{varid}%
213 \indexsyn{conid}%
214 \indexsyn{tyvar}%
215 \indexsyn{tycon}%
216 \indexsyn{tycls}%
217 \indexsyn{modid}%
218
219 Variables and type variables are represented by identifiers beginning
220 with small letters, and the other four by identifiers beginning with
221 capitals; also, variables and constructors have infix forms, the other
222 four do not.  Namespaces are also discussed in
223 Section~\ref{namespaces}.
224
225 \index{qualified name}
226 A name may optionally be {\em qualified} in certain
227 circumstances by prepending them with a module identifier.  This
228 applies to variable, constructor, type constructor and type class
229 names, but not type variables or module names.  Qualified
230 names are discussed in detail in Chapter~\ref{modules}.
231 @@@
232 qvarid   -> [modid @.@] varid
233 qconid   -> [modid @.@] conid
234 qtycon   -> [modid @.@] tycon
235 qtycls   -> [modid @.@] tycls
236 qvarsym  -> [modid @.@] varsym
237 qconsym  -> [modid @.@] consym
238 @@@
239 \indexsyn{qvarid}%
240 \indexsyn{qconid}%
241 \indexsyn{qtycon}%
242 \indexsyn{qtycls}%
243 \indexsyn{qvarsym}%
244 \indexsyn{qconsym}%
245 Since a qualified name is a lexeme, no spaces are
246 allowed between the qualifier and the name.
247 Sample lexical analyses are shown below.
248 \[\bto{|l|l|}
249 \hline
250 This                                & Lexes as this                       \\
251 \hline
252 @f.g@                               & @f . g@ (three tokens)             \\
253 @F.g@                               & @F.g@ (qualified `g')            \\
254 @f..@                               & @f ..@ (two tokens)    \\
255 @F..@                               & @F..@ (qualified `.')         \\
256 @F.@                                & @F .@ (two tokens)                     \\
257 \hline\eto\]
258 The qualifier does not change the syntactic treatment of a name;
259 for example, @Prelude.+@ is an infix operator with the same fixity as the 
260 definition of @+@ in the Prelude (Section~\ref{fixity}).
261
262
263 \subsection{Numeric Literals}\index{number!literal syntax}
264 \label{lexemes-numeric}
265
266 @@@
267 decimal         -> digit\{digit\}
268 octal           -> octit\{octit\}
269 hexadecimal     -> hexit\{hexit\}
270 @@@
271 \indexsyn{decimal}%
272 \indexsyn{octal}%
273 \indexsyn{hexadecimal}%
274 @@@
275 integer         -> decimal
276                 |  @0o@ octal | @0O@ octal
277                 |  @0x@ hexadecimal | @0X@ hexadecimal
278
279
280 float           -> decimal @.@ decimal [exponent]
281                 |  decimal exponent
282
283 exponent        -> (@e@ | @E@) [@+@ | @-@] decimal
284 @@@
285 \indexsyn{integer}%
286 \indexsyn{float}%
287 There are two distinct kinds of numeric literals: integer and
288 floating.  Integer literals may be given in decimal (the default),
289 octal (prefixed by @0o@ or @0O@) or hexadecimal notation (prefixed by
290 @0x@ or @0X@).
291 Floating literals are always decimal.
292 A floating literal must contain digits both before and after the
293 decimal point; this ensures that a decimal point cannot be mistaken
294 for another use of the dot character.  Negative numeric literals are
295 discussed in Section~\ref{operators}.  The typing of numeric literals
296 is discussed in Section~\ref{numeric-literals}.
297
298 \subsection{Character and String Literals}
299 \index{character!literal syntax}
300 \index{string!literal syntax}
301 \label{lexemes-char}
302
303 @@@
304 char    ->  @'@ (graphic_{\langle{}@'@ | @\@\rangle{}} | space | escape_{\langle{}@\&@\rangle{}}) @'@
305 string  ->  @"@ \{graphic_{\langle{}@"@  | @\@\rangle{}} | space | escape | gap\} @"@
306 escape  ->  @\@ ( charesc | ascii | decimal | @o@ octal | @x@ hexadecimal )
307 charesc -> @a@ | @b@ | @f@ | @n@ | @r@ | @t@ | @v@ | @\@ | @"@ | @'@ | @&@
308 ascii   -> @^@cntrl | @NUL@ | @SOH@ | @STX@ | @ETX@ | @EOT@ | @ENQ@ | @ACK@ 
309        | @BEL@ | @BS@ | @HT@ | @LF@ | @VT@ | @FF@ | @CR@ | @SO@ | @SI@ | @DLE@ 
310        | @DC1@ | @DC2@ | @DC3@ | @DC4@ | @NAK@ | @SYN@ | @ETB@ | @CAN@ 
311        | @EM@ | @SUB@ | @ESC@ | @FS@ | @GS@ | @RS@ | @US@ | @SP@ | @DEL@
312 cntrl   -> ascLarge | @@ | @[@ | @\@ | @]@ | @^@ | @_@
313 gap     ->  @\@ whitechar \{whitechar\} @\@
314 @@@
315 \indexsyn{char}%
316 \indexsyn{string}%
317 \indexsyn{escape}%
318 \indexsyn{charesc}%
319 \indexsyn{ascii}%
320 \indexsyn{cntrl}%
321 \indexsyn{gap}%
322 \index{\\a@@{\tt {\char'134}a}}%
323 \index{\\b@@{\tt {\char'134}b}}%
324 \index{\\f@@{\tt {\char'134}f}}%
325 \index{\\n@@{\tt {\char'134}n}}%
326 \index{\\r@@{\tt {\char'134}r}}%
327 \index{\\t@@{\tt {\char'134}t}}%
328 \index{\\v@@{\tt {\char'134}v}}%
329 \index{\\\&@@{\tt {\char'134}\&}}%
330
331 Character literals are written between single quotes, as in
332 @'a'@, and strings between double quotes, as in @"Hello"@.
333
334 Escape codes may be used in characters and strings to represent
335 special characters.  Note that a single quote~@'@ may be used in a string, but
336 must be escaped in a character; similarly, a double quote~@"@ may be used in a
337 character, but must be escaped in a string.  @\@ must always be
338 escaped.  The category "charesc" also includes portable
339 representations for the characters ``alert'' (@\a@), ``backspace''
340 (@\b@), ``form feed'' (@\f@), ``new line'' (@\n@), ``carriage return''
341 (@\r@), ``horizontal tab'' (@\t@), and ``vertical tab'' (@\v@).
342
343 Escape characters for the Unicode\index{Unicode character set} character
344 set, including
345 control characters such as @\^X@, are also provided.
346 Numeric escapes such as @\137@ are used to designate the character
347 with decimal representation 137; octal
348 (e.g.~@\o137@) and hexadecimal (e.g.~@\x37@) representations are also
349 allowed.  
350 % Numeric escapes that are out-of-range of the Unicode standard
351 % (16 bits) are an error.
352
353 Consistent with the ``maximal munch'' rule,
354 \index{maximal munch rule}
355 numeric escape
356 characters in strings consist of all consecutive digits and may
357 be of arbitrary length.  Similarly, the one ambiguous ASCII escape
358 code, @"\SOH"@, is parsed as a string of length 1.  The escape
359 character @\&@ is provided as a ``null character'' to allow strings
360 such as @"\137\&9"@ and @"\SO\&H"@ to be constructed (both of length
361 two).  Thus @"\&"@ is equivalent to @""@ and the character
362 @'\&'@\ is disallowed.  Further equivalences of characters
363 are defined in Section~\ref{characters}.
364
365 A string may include a ``gap''---two backslants enclosing
366 white characters---which is ignored.
367 This allows one to write long strings on more than one line by writing
368 a backslant at the end of one line and at the start of the next.  For
369 example,
370 \bprog
371 @
372 "Here is a backslant \\ as well as \137, \
373     \a numeric escape character, and \^X, a control character."
374 @
375 \eprogNoSkip
376
377 String literals are actually abbreviations for lists of characters
378 (see Section~\ref{lists}).
379
380 \subsection{Layout}\index{layout}
381 \label{lexemes-layout}
382
383 \Haskell{} permits the omission of the braces and semicolons used in several
384 grammar productions, by
385 using {\em layout} to convey the same information.  This allows both
386 layout-sensitive and layout-insensitive styles of coding, which
387 can be freely mixed within one program.  Because layout is
388 not required, \Haskell{} programs can be straightforwardly
389 produced by other programs.
390 % without worrying about deeply nested layout difficulties.
391
392 The effect of layout on the meaning of a Haskell program
393 can be completely specified by adding
394 braces and semicolons in places determined by the layout.  The meaning of
395 this augmented program is now layout insensitive.
396
397 Informally stated, the braces and semicolons are inserted as follows.
398 The layout (or ``off-side'') rule\index{off-side rule} takes effect
399 whenever the open brace is omitted after the keyword @where@, @let@,
400 @do@, or
401 @of@.  When this happens, the indentation of the next lexeme (whether
402 or not on a new line) is remembered and the omitted open brace is
403 inserted (the whitespace preceding the lexeme may include comments).
404 For each subsequent line, if it contains only whitespace or is
405 indented more, then the previous item is continued (nothing is
406 inserted); if it is indented the same amount, then a new item begins
407 (a semicolon is inserted); and if it is indented less, then the
408 layout list ends (a close brace is inserted).  If the indentation of the 
409 non-brace lexeme immediately following a @where@, @let@, @do@ or @of@ is less 
410 than or equal to the current indentation level, then instead of starting 
411 a layout, an empty list ``@{}@'' is inserted, and layout processing 
412 occurs for the current level (i.e. insert a semicolon or close brace). 
413 A close brace is
414 also inserted whenever the syntactic category containing the
415 layout list ends; that is, if an illegal lexeme is encountered at
416 a point where a close brace would be legal, a close brace is inserted.
417 The layout rule matches only those open braces that it has
418 inserted; an explicit open brace must be matched by
419 an explicit close brace.  Within these explicit open braces,
420 {\em no} layout processing is performed for constructs outside the
421 braces, even if a line is 
422 indented to the left of an earlier implicit open brace.
423
424 Section~\ref{layout} gives a more precise definition of the layout rules.
425
426 Given these rules, a single newline may actually terminate several
427 layout lists.  Also, these rules permit:
428 \bprog
429 @
430 f x = let a = 1; b = 2 
431           g y = exp2
432        in exp1
433 @
434 \eprog
435 making @a@, @b@ and @g@ all part of the same layout
436 list.
437
438 As an example, Figure~\ref{layout-before} shows a (somewhat contrived)
439 module and Figure~\ref{layout-after} shows the result of applying the
440 layout rule to it.  Note in particular: (a)~the line beginning @}};pop@,
441 where the termination of the previous line invokes three applications
442 of the layout rule, corresponding to the depth (3) of the nested
443 @where@ clauses, (b)~the close braces in the @where@ clause nested
444 within the tuple and @case@ expression, inserted because the end of the
445 tuple was detected, and (c)~the close brace at the very end, inserted
446 because of the column 0 indentation of the end-of-file token.
447
448 \begin{figure}
449 \outlinec{\small
450 @
451 module AStack( Stack, push, pop, top, size ) where
452 data Stack a = Empty 
453              | MkStack a (Stack a)
454
455 push :: a -> Stack a -> Stack a
456 push x s = MkStack x s
457
458 size :: Stack a -> Int
459 size s = length (stkToLst s)  where
460            stkToLst  Empty         = []
461            stkToLst (MkStack x s)  = x:xs where xs = stkToLst s
462
463 pop :: Stack a -> (a, Stack a)
464 pop (MkStack x s)
465   = (x, case s of r -> i r where i x = x) -- (pop Empty) is an error
466
467 top :: Stack a -> a
468 top (MkStack x s) = x                     -- (top Empty) is an error
469 @
470 }
471 %**<div align=center> <h4>Figure 1</h4> </div>
472 \ecaption{A sample program}
473 \label{layout-before}
474 \outlinec{\small
475 @
476 module AStack( Stack, push, pop, top, size ) where
477 {data Stack a = Empty 
478              | MkStack a (Stack a)
479
480 ;push :: a -> Stack a -> Stack a
481 ;push x s = MkStack x s
482
483 ;size :: Stack a -> Int
484 ;size s = length (stkToLst s)  where
485            {stkToLst  Empty         = []
486            ;stkToLst (MkStack x s)  = x:xs where {xs = stkToLst s
487
488 }};pop :: Stack a -> (a, Stack a)
489 ;pop (MkStack x s)
490   = (x, case s of {r -> i r where {i x = x}}) -- (pop Empty) is an error
491
492 ;top :: Stack a -> a
493 ;top (MkStack x s) = x                        -- (top Empty) is an error
494 }
495 @
496 }
497 %**<div align=center> <h4>Figure 2</h4> </div>
498 \ecaption{Sample program with layout expanded}
499 \label{layout-after}
500
501 \end{figure}
502
503
504 %**~footer
505
506 % Local Variables: 
507 % mode: latex
508 % End:
509