Objective Caml comprises a library type for streams (possibly infinite
sequences of elements, that are evaluated on demand), and associated
stream expressions, to build streams, and stream patterns, to
destructure streams. Streams and stream patterns provide a natural
approach to the writing of recursive-descent parsers.
Streams are presented by the following extensions to the syntactic
classes of expressions:
expr ::= ...
| [< >]
| [< stream-component { ; stream-component } >]
| parser [pattern] stream-matching
| match expr with parser [pattern] stream-matching
stream-component ::=
' expr
| expr
stream-matching ::= stream-pattern [pattern] -> expr
{ | stream-pattern [pattern] -> expr }
stream-pattern ::=
[< >]
| [< stream-pat-comp
{ ; stream-pat-comp [ ?? expr ] }>]
stream-pat-comp ::=
' pattern [ when expr ]
| pattern = expr
| ident
Stream expressions are bracketed by [< and >]. They
represent the concatenation of their components. The component ' expr
represents the one-element stream whose element is the value of
expr. The component expr represents a sub-stream. For instance, if
both s and t are streams of integers, then [<'1; s; t; '2>] is a
stream of integers containing the element 1, then the elements of s,
then those of t, and finally 2. The empty stream is denoted by [< >].
Unlike any other kind of expressions in the language, stream
expressions are submitted to lazy evaluation: the components are not
evaluated when the stream is built, but only when they are accessed
during stream matching. The components are evaluated once, the first
time they are accessed; the following accesses reuse the value
computed the first time.
Stream patterns, also bracketed by [< and >], describe
initial segments of streams. In particular, the stream pattern
[< >] matches all streams. Stream pattern components are
matched against the corresponding elements of a stream. The component
' pattern matches the corresponding stream element against the
pattern; if followed by when, the match is accepted only if the result
of the guard expression is true. The component pattern = expr
applies the function denoted by expr to the current stream, then
matches the result of the function against pattern. Finally, the
component ident simply binds the identifier to the stream being
matched.
Stream matching proceeds destructively: once a component has been
matched, it is discarded from the stream (by in-place modification).
Stream matching proceeds in two steps: first, a pattern is selected by
matching the stream against the first components of the stream
patterns; then, the following components of the selected pattern are
checked against the stream. If the following components do not match,
the exception Stream.Error is raised. There is no backtracking here:
stream matching commits to the pattern selected according to the first
element. If none of the first components of the stream patterns match,
the exception Stream.Failure is raised. The Stream.Failure exception
causes the next alternative to be tried, if it occurs during the
matching of the first element of a stream, before matching has
committed to one pattern.
The streams hold the count of their elements discarded. The optional
pattern before the first stream pattern is bound to the stream count
before the matching. The one after each stream pattern (optional, too)
is bound to the stream count after the matching.
The exception Stream.Error has a string parameter coming from the
optional ?? expr after the stream pattern components (its
default is the empty string). This expression is evaluated only in
case of error.