URL http://www.cs.hmc.edu/~keller/rex
Convenience link to CS 60 and to the rex liteReference Card.
Last updated 5 September 1999 by keller@cs.hmc.edu.Please report any errors or inaccuracies to keller@cs.hmc.edu.
This card also forms the basis of the interactive help file callable from rex, which might explain its slightly unusual organization. The rex help system looks for the keyword "bullets"which mark each item.
One way to get help interactively is to type
*h(return)
to the rex read loop. This puts you into the help loop, wherein you can type terms, or parts of terms and get descriptions from this document.
To return to the rex read loop from the help loop, type the character control-d.
Another way to invoke help on a topic is to call, within rex,
help(Topic);
It is not necessary to put quotes around the topic. Help is available on the following topics, as well on all individual functions.
rex runs an interactive "read loop", also called read-eval-printloop. This means that the following cycle repeats until the user types end-of-file (e.g. control-d):
In some cases, it is a little more complicated than this: the evaluation can be interleaved with printing the answer. This ishelpful when the answer is very long, and essential when the answeris infinite. An evaluation can be interrupted (seeinterrupting rex).
Quick commands provide an alternative for entering system and helpcommands with a minimum of key strokes. A quick command is identifiedby a single line starting with * and terminated by return (no ;) Thefollowing quick commands are available:
*i Filename *h *q *r *t *N *-N ** Comments are as in C++. They either start with
// and continue to end-of-line, or start with
/* and continue to */.
Currently the latter comments cannot be recursive (i.e. you can'thave /* .... */ within /* ....*/).
rex is a dynamically-typed language, meaning that types are associated with values, rather than with variables. A given variablecan be bound to any type of value and there are no type declarations. Many of the functions are polymorphic (accepting more than one type of argument).
The down-side of this is that types have to be checked for sensibility at run-time. For example, it doesn't make sense to multiply one string by another. Thus there may be errors about whichyou don't find out until run-time, but which would have been caughtat compile-time by a statically-typed language. rex handles such errors for you by returning an error value when types don't makesense. A list of types is given with the description of the functiontype which will indicate the type of adata item.
Another sense in which rex is dynamic is that there are no storage allocation commands. Data items, typically lists, get created as theresult of function evaluations. But the programmer does not preallocate space for these results. Reclamation of unused storage issimilarly handled by the system.
There are three types of rex expressions:
All expressions to be evaluated are terminated with asemi-colon. (end-of-line doesn't terminate an expression,because expressions can take an arbitrary number of lines, and it isnot generally evident when there isn't more to an expression.)
Definitions bind variables and function names. A definitionappears as
LHS = RHS;
where LHS is the variable or variables being defined, and RHS iswhat defines them. Examples are:
cube(x) = x*x; // defines the cube function alist = [1, 2, 3, 4]; // defines a list variable called alist [x, y, z] = foo(alist); // defines variables x, y, and z,
Caution: While definitions have a certain similarity toassignments (e.g. in C), they should not be used that way. Theability to reassign is simply for convenience in interacting with thesystem. At the core, rex is a functional language and is designed tohelp learn to program without assignment statements. Global definitions have a value 1 if the definition succeeds and 0 if not.The reason a definition might not succeed is that the RHS valuesdon't match the LHS pattern. For example, in
[x, y, z] = [1, 2];
the list on the right has two values whereas the one on the lefthas three. On the other hand
[x, y | z] = [1, 2];
will succeed and bind x to 1, y to 2, andz to [ ]. See also localdefinitions.
Rules define parts of functions by using pattern matching andguards, and are collected together by rex to make a definition. A rule has the form: LHS => RHS; (The symbol=> an = followed by a > and is read "yields"). The following are examples of rules (for the greatest-common-divisorfunction):
gcd(0, y) => y;
gcd(x, y) => x <= y ? gcd(y % x, x);
gcd(x, y) => gcd(y, x);
The second rule above uses a guard, anexpression which must be true in order for the rule to apply. Asanother example, the following rules use pattern matching to find thelast element in a non-empty list.
last([X]) => X; last([_ | X]) => last(X);
Although all expressions have a value, the remaining kinds ofexpressions are entered for purposes of evaluation. They yield avalue which is printed. They can also have side-effects, but the routine use of side-effects is discouraged. The computations of theseexpressions are done in the context of definitions and rules.
For example, to use the gcd and lastfunctions defined above in a computation, we'd need to enter anexpression:
gcd(56, 72);
rex would respond with the answer 8. If we entered:
last([1, 2, 3, 4, 5]);
rex would respond with the answer 5.
A variable is a sequence of contiguous characters starting with aletter (upper or lower case) or underscore, and containing letters,underscores, and digits. Names of functions are considered to bevariables bound to anonymous function values.
The following kinds of operators are available:
Arithmetic, logical, and relational operators are pretty much thesame as in C and C++.
The following lists operator precedence tightest to weakest. Alloperators group left unless otherwise indicated.
These functions are defined as follows:
N1 + N2 + .... + Nn N1 - N2 N1 * N2 * .... * Nn N1 / N2 N1 % N2 For example, divides(3)(N1) will return 1 whenver N1 divides 3.
These apply to more than just numeric values. For example, listsand arrays can be compared in lexicographic order.
The Boolean model used by rex is: 0, [ ] (the empty list), andfailure values are false, and anything elseis true. When a built-in returns a Boolean, it is either 0 or 1.
The logical operators are:
List formation is represented by [X0, X1, ...., Xn-1]. A listresult will show in this fashion as well, unless it is converted tosome other format. The null list is [ ].
Lists may be written to and read from files as S expressions bysingle commands.
A list may be formed from an item and an existing list by [X | L],meaning to construct the list consisting of X followed by the elements of L. Another way to get the same effect is cons(X, L). Withrespect to the list thus created, X is the "first" of the list and Lis the "rest".
This notation may be generalized: [X0, X1, ...., Xn-1 | L] formsthe list starting with the n elements indicated, followed by the elements of L.
An "improper list" is formed by [X | Y] where Y is not a list. Aresult of this form will show as [X | Y]. Programming will generallybe simplified if improper lists are avoided.
Incrementaland "infinite" lists may be created by deferring the rest of thelist: In [X |$ L] the $ acts to defer the evaluation of L. Taking therest of the list will give the seed $L which is not further evaluateduntil needed (e.g. in the case of checking to see whether the rest isthe empty list.
Some list functions are:
Other list functions may be found undersequence functions.
Other selections from lists may be made by treating the list as a function from {0, 1, 2, ..., length-1} to values: i.e. L(i) is the ith element of L.
If N1 <= N2, range(N1, N2) yields the list [N1, N1+1, N1+2, ...., N2].
If N1 > N2, range(N1, N2) yields the list [N1, N1-1, N1-2, ...., N2].
range(N1, N2, K) yields the list [N1, N1+K, N1+2*K, ...., N2] in case that N1 <= N2 and K is positive, or N1 >= N2 and K is negative. Otherwise the result is [ ].
Examples:
range(1, 9) ==> [1, 2, 3, 4, 5, 6, 7, 8, 9] range(9, 1) ==> [9, 8, 7, 6, 5, 4, 3, 2, 1] range(1, 9, 2) ==> [1, 3, 5, 7, 9] range(9, 1, -2) ==> [9, 7, 5, 3, 1]
from(N, K) creates the infinite list [N, N+K, N+2*K, ...]. If N is floating, the items will be floating. If K is floating, but N is not, all but the first item will be floating. Otherwise all items will be fixed.
A literal string must be in double quotes, e.g.
"this is a string"
Strings are distinguished from single characters, which are insingle quotes, e.g. 'x'. In either case, backslash(\) can be used as an escape character. The standard Cescape codes apply:
\n is newline \t is tab \\ is backslash \f is form-feed \b is backspace \a is bell \v is vertical tab \r is carriage return
Note: As with sequences, a particular character of a stringmay be extracted by treating the string as a function: S(i),where i is between 0 and (length of the string) -1 yields theith character of S.
Selections from arrays may be made by treating the array as afunction from {0, 1, 2, ..., length-1} to values: i.e. A(i) is theith element of A.
) yields an array with the elements of the argument, a list, as elements.
For example make_array(10, id) returns an array of values from 0 to 9.
These apply to both lists and arrays, as well as tostrings in a few cases. The ones which apply to incremental orinfinite, as well as finite, lists are annotated as "incremental".
assoc(X, L) yields the first list element of an association list
having X as its first item. If there is no such
item, yields [ ].
For example, assoc('c', [['a', 1], ['b', 2], ['c', 3], ['d', 4]]) will
return [c, 3].
every(N, L, K) yields a list consisting of every Nth element of L starting at the Kth (where K = 0 means the first, etc. [incremental]
extract(P, L) creates a new list by finding the first item X in L for which P(X) and bringing it to the front of the list. If there is no such item, this function diverges [incremental]
find(P, L) yields the suffix of L beginning with the first item X for which P(X). If there is no such item, yields [ ], unless L is infinite, in which case this function diverges. [See also keep.]
find(P, L) yields index (starting with 0 as the first index) of the first item X for which P(X). If there is no such item, yields -1, unless L is infinite, in which case this function diverges.
find(P, L) yields the list of indices of all items X for which P(X). If L is infinite but there are only finitely-many such X, this function diverges after producing the indices of those X. [See also keep.] [incremental]
keep(P, S) If S is an array or list, and P is a 1-ary function, then keep(P, S) is the array or list resulting from keeping those elements for which P is true. [incremental]
leaves(A) treats the list as the root of a tree, and returns a list of the leaves of the tree. The tree can have arrays or lists as nodes.
leafcount(A) is the length of leaves(A)
length(S) returns the length of the list, array, or string
map(F, S) If S is an array or list, constructs a new array or list the same length as S, by applying F to each element of S. map(B, S1, S2) S1 and S2 should be both arrays or both lists. The result is a new array or list constructed by applying binary function B to the elements of S1 and S2, element-by-element. [incremental]
mappend(F, L) Assuming L is a list, and F is a function which will return a list when applied to a member of L, returns the result of appending the elements of map(F, L) together in order.
merge(L, M) assuming that L and M are in order according to the built-in order <, merges them together into a single with respect to <. [incremental]
merge(P, L, M) assuming that L and M are in order according to the partial order P, represented as a binary function, merges them together into a single list in order with respect to P. [incremental]
no(P, L) yields 1 if no X occurring in L is such that P(X). Otherwise yields 0.
pmap(F, S) is like map(F, S) except that (if multithreading is in force) each element of the result is evaluated in parallel
prefix(N, L) yields the first N items in L. If L doesn't have N items, yields all of L. [incremental]
reduce(B, U, S) Here B is a binary operator with unit U and S is an array or list. The result is the accumulation of applying B to elements in S. For example, reduce(+, 0, S) is the sum of elements in S, while reduce(*, 1, S) is the product. Grouping is to the left, i.e. if S were [S0, S1, S2, ... Sn], then the result is B( .... B(B(B(U, S0), S1), S2) ...., Sn). [incremental]
remove_duplicates(L) returns a list with any duplicates removed [incremental]
reverse(L) returns the list consisting of elements of L in reverse order
scale(F, S) If S is an array or list, constructs a new array or list the same length as S, in which each element of the original is multiplied by F. [incremental]
scan(B, S) B is a binary operator and S is an array or list. The result is the array or list (of the same length as S) of partial accumulations of B applied to the elements of S. For example, scan(+, S), where S = [S0, S1, S2, ... Sn], yields [S0, S0+S1, S0+S1+S2, ...., S0+....+Sn-1]. [incremental]
some(P, L) yields 1 if an X occurs in L such that P(X). Otherwise yields 0.
sort(S) returns an array or list (whichever S is) containing the elements of S in sorted order. The ordering is the natural one built into rex.
suffix(N, L) yields the last N items in L. If L doesn't have N items, yields all of L. [incremental]
zip(L, M) yields the list formed by alternating an element of L with an element of M [incremental]
log(N) returns the natural logarithm of N. log(N1, N2) returns the logarithm of N2 base N1.
sin(N) returns the sine of N.
cos(N) returns the cosine of N.
tan(N) returns the tangent of N.
asin(N) returns the inverse sine of N.
atan(N) returns the inverse tangent of N.
sinh(N) returns the hyperbolic sine of N.
cosh(N) returns the hyperbolic cosine of N.
tanh(N) returns the hyperbolic tangent of N.
asinh(N) returns the inverse hyperbolic sine of N.
acosh(N) returns the inverse hyperbolic cosine of N.
atanh(N) returns the inverse hyperbolic tangent of N.
erf(N) returns the "error function" of N, 2/sqrt(pi)*integral from 0 to N of exp(-t*t) dt.
erfc(N) returns the "complementary error function", 1.0 - erf(N), computed by methods that avoid cancellation for large N.
close(Ostream) closes the argument Ostream. If the stream is input to a Unix process, closing is necessary for that process to terminate.
endl(Ostream) sends an end-of-line to the argument Ostream.
eof() indicates whether the standard input is in an end-of-file condition and clears that condition
exec(Command) executes a command in the operating system (e.g. Unix). It returns a pair [Istream, Ostream]. The program sends input to the command via the Ostream and gets output from the Istream, using appropriate primitives described in this section.
inchars() yields a list of characters from the characters in the standard input. The input can be unlimited, e.g. piped in from Unix. The result is an incremental list. inchars(Filename) yields an incremental list of characters from the characters in the named file. The list is built incrementally on demand.
insexps() yields a list of values as determined by S expressions in the standard input. The list is incremental and the input can be unlimited, e.g. piped.
insexps(Filename) yields an incremental list of values as determined by S expressions in the named file.
insexp(Filename) yields single value as determined by the first S expression in the named file. The file is opened, then closed.
flush(Ostream) flushes the identified Ostream without sending an end-of-line.
make_istream(Filename)
make_istream() make_commented_istream(Filename)
make_commented_istream() make_ostream(Filename) yields an ostream value, e.g. for use with writesexp.
outsexps(L) outputs an incremental list L (possibly infinite) to the standard output. outsexps(Filename, L) outputs an incremental list L (possibly infinite) to the named file.
outsexp(Filename, V) outputs a single value to the named file. The file is opened, then closed.
readchar() reads a single character from the standard input. readchar(Istream) reads a single character from the istream identified.
readchars(Istream) makes stream of chars from the istream identified into an incremental list.
readline() reads a single line from the standard input as a string. readline(Istream) reads a single line, as a string, from the istream identified.
readsexp() reads a single S expression from the standard input. readsexp(Istream) reads a single S expression from the istream identified.
readsexps(Istream) makes stream of S expressions from istream into an incremental list.
writesexp(Sexp) writes a single S expression to the standard output. Note that Sexp can be a single char or a single string. writesexp(Ostream, Sexp) writes a single S expression to the ostream identified. atomic(A) returns 1 if its argument is not a list or array.
builtin(Name, Arity) returns a specific builtin function given literal name and arity.
[[!, 1],[!=, 1], [!=, 2], [%, 2], [&&, 5], [*, 1], [*, 2],[*, 5],[+, 1], [+, 2], [+, 5], [-, 1], [-, 2], [/, 1 ], [/, 2], [<, 1], [<, 2], [<=, 1], [<=, 2], [=, 3], [==, 1], [==, 2],[=>, 2], [>, 1],[>=, 1],[asin, 1], [asinh, 1], [atan, 1], [atanh, 1], [atomic, 1], [builtin, 0], [builtin, 2], [ceil, 1], [char, 1], [close, 1], [concat, 5], [cons, 2],
etc. Each function is paired with an arity.
Note that a special meaning is attached to arity 5; rather than being a specific arity, it means that the arity is arbitrary. For example, concat(), concat(A), concat(A, B), concat(A, B,C), ... are all valid since [concat, 5] appears in the list. In some cases, such as with cons above, both arity 5 and arity 2 appear. This could indicate special over-riding treatment for the specific arity 2, although in this case it turns out to be just an efficiency hack, since cons is usually used with just 2 arguments.
defined() Creates a list of names (as strings) of identifiers (other than builtins) which are currently defined.
eval(Expression) Expression is evaluated, then that value is treated as if it were an expression and evaluated. This allows expressions to be constructed from lists on the fly, then evaluated. To see how expressions are constructed in general, analyze them withs the quote operator. Example: eval(["+", 2, ["*", 3, 4]]) ==> 14
id(Datum) returns Datum (useful in certain contexts, e.g. make_array).
k(Datum) makes a constant function with value Datum. That is, it returns a function which, when applied to any argument, returns Datum. i.e. k(Datum)(Anything) is Datum. (useful in certain contexts, e.g. make_array).
quote(Expression) The argument is not evaluated, but is converted into a literal structure of the same form used by the rex interpreter for programs. The resulting value may then be processed as a string or list, as appropriate. Example: quote(a+b*c) has the value ["+", "a", ["*", "b", "c"]]
test(Expression1, Expression2) evaluates the expressions and compares them for equality. Usually Expression2 is the expected answer. Prints a message indicating whether the test is "ok" or "bad".
type(A) returns a string naming the type of its argument A. The following types are available:The following functions return 1 or 0, depending on whether theargument is of the corresponding type:
See also atomic which returns 1 ifits argument is not a list or array.
sow(Expression) If multithreading is available, the value of Expression is evaluated in a separate thread. Meanwhile, the expression is treated as being deferred. Any attempt to use the value will synchronize with the evaluating thread until the value becomes available.
grow(Expression) Explicitly waits for the result of Expression to be evaluated, e.g. in the case that the result is that of a sow. This function is implicit in the built-in functions which require it, thus it is not often used.
spec(Name, Arity) or Name#Arity Returns a specific function given literal name and arity.
Caution: Use of side effects is not in the spirit of a functional language. These primitives may be disabled for purposes of teaching functional programming.
set(Variable, Value) Changes the value of an already-defined variable, local or global, to the specified value. At the global level, if the variable is not yet defined, set will define it.
undef(Variable) The most recent global definition of Variable, if any, is removed. The previous definition is restored. The value returned is 1 if there was a definition, 0 otherwise. Caution: This effects globals, even if called inside a function with the same variable bound locally.
repeat(Value, Command) does Command the number of times specified by Value.
while(Condition, Command) repeatedly tests Condition and if true executes Command. Returns the value [].
for(Initialization, Condition, Incrementation, Command) does Initialization, then repeatedly tests Condition and if true executes Command, after which Incrementation is executed.
Guard ? Body Guard is the guard, a logical expression, and Body is an expression. The rule applies only if the guard is true, in which case the result is the value of Body. Condition ? True_Alternative : False_Alternative Condition is evaluated first and if true, the result is the value of True_Alternative, otherwise it is the value of False_Alternative.
Head => Body To define a rule:
Head => Body; where Head is a function name with arguments, defines one rule for the named function.
Example: foo([A | L], N) => foo(L, A+N);
On the other hand,
Head => Body
where Head is just a list of arguments in parentheses, is an "anonymous function" (also known as a "lambda expression").
Example: (F, X) => F(F(X)) is the function of two arguments, say F and X, which applies F to X, then applies F to the resulting value.
Evaluation of the expression following the $ operator is deferreduntil the value is actually needed. The definition of "needed" isdependent on the operators which apply to the value.
For example, in the conditional form
C ? F : T,
if F or T is deferred, then they are leftdeferred in the result. On the other hand, applying the function"first" to the result would evaluate a deferred argument, since itneeds to know the first element of the argument as a list. Theimmediate value of a defer before evaluation is an internalstructure called a seed. While seeds are not seen as output,they may be seen in tracing.
Some built-in functions are overloaded. For example,map has two or three arguments. When abuilt-in function is passed as an argument, the ambiguity of whichfunction is to be used can be resolved by appending to the function name a # followed by the arity, e.g. map#2 vs.map#3. The same applies to operators, e.g.+#1 vs. +#2. Some functions can take anarbitrary number of arguments, e.g. max takes any number greater thanzero of arguments. Similarly, + is two differentfunctions: +#1 is the "curried" +, while+#_ is the addition function with any other number ofarguments. If # is not attached, rex will make a choice of arity. Forexample, the binary arithmetic functions are the choice for+, -, *, /, %.
A local definition takes the form
LHS = RHS, Expression;
The value of the overall expression is the value ofExpression in the context of the bindings made in the equation. These bindings are local, and hold only for the evaluationof Expression. They have no impact on existing bindings tothe variables. Example:
root = sqrt(x), f(root, g(root));
Here root is bound to the value of sqrt(x), for the evaluation of f(root, g(root)). One use of a localdefinition is to prevent repeated expensive evaluation of anexpression.
When the right-hand side of a rule has this form, we call it anequational guard. The idea is that the rule only applies if thedefinition succeeds. As with global definitions, a definition willfail if there is a mis-match between the LHS and RHS. Example:
f(x) => root = sqrt(x), g(root,h(root));
Here the value of f(x) is computed by binding root tosqrt(x), then returning the value g(root,h(root)). Since root is only a single variable, the pattern istrivial and this guard will never fail. If the evaluation of gfails, this translates to a failure of the whole function f,not to the failure of a guard.
When an ordinary local definition is made, the values of variablesand functions on the RHS is that determined by the surroundingcontext. Sometimes it is desirable to make those values be exactlythe ones being defined locally. This is particularly true in the caseof defining a recursive function locally. For example, suppose forsome reason we wished to apply a local definition of the factorialfunction. The following would not work:
f(N) = N < 2 ? 1 : N*f(N-1), f(10);
{ f(N) = N < 2 ? 1 : N*f(N-1); f(10) }; In general, the expressions inside braces consist of some number of equations terminated by semi-colon, followed by an expression, the value of which becomes the value of the overall brace expression. Another use of local recursive definitions is in infinite-list functions with loops. For example, to define a function which is the infinite repetition of an item X, without recomputing X, we can define
repeat(X) = { Y = [X |$ Y]; Y }; Here it is Y which is the same on both the left- and right-hand sides of the equation Y = [X |$ Y].
System commands look just like expressions to be evaluated, butthey generally have side-effects, such as reading a rex source file.The "function" sys is thus not really a mathematical function. Thesecond argument to sys is interpreted literally as one of a number ofsub-commands, and there will usually be additional arguments, whichare either literal or evaluated, depending on the sub-command.
The in sub-command:
sys(in, Filename)
Here in is literal and Filename is an expressionwhich must evaluate to a string. That string is looked up accordingto the usual interpretation and loaded as a series of rexexpressions.
The on and off sub-commands:
sys(on, Flag)
sys(off, Flag)
Here on and off are literal and Flag isinterpreted literally (without evaluation). The corresponding flag isturned on or off. The following are possible flags:
The get and set sub-commands:
sys(set, Variable, Value) sys(get, Variable)
Here set and get are literal. The expressionsets or gets the value of system variable as indicated. Thefollowing system variables aresupported:
To trace or not trace function entry and exit, use one of
*t- toggles the function trace
sys(on, ftrace);- turns the trace on
sys(off, ftrace);- turns the trace off
To interrupt rex while in evaluation, type control-c once ortwice. You will be offered a menu of possible options, such as:
Interrupt: Please select one of the following: a - abort to top level b - enter break loop c - continue where program left off f - continue with ftrace on h - enter the help loop n - continue with ftrace off s - continue in line-by-line stop mode q or control D - quit the program
In UNIX implementations, a file name to be read initially as rexsource can be specified on the command line. Example, with thebold-face representing what the user types:
UNIX > rex fac.rex fac.rex loaded 1 rex > fac(10); 3628800
In addition to the full examples below, see other examples in thetext such as gcd. Below we show the definitionwith a sample interactive execution.
compose composes two unary functions compose(F, G)(x) = F(G(x)); compose(sq, sq)(4) ==> 256 fibs is a way of defining the Fibonacci sequence with a "loop" fibs = [1, 1 |$ map(+, fibs, rest(fibs))]; fibs ==> [1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, ... prod is a parallel product prod(M, N) => M >= N ? M; prod(M, N) => Median = (M+N)/2, bottom = sow(prod(M, Median)), // creates parallel thread top = prod(Median+1, N), bottom*top; prod(1, 10) ==> 3628800 9 threads created, 9 threads completed inner computes the inner product of two lists, using an accumulator inner(X, Y) = inner_aux(X, Y, 0); inner_aux([], _, Acc) => Acc; inner_aux(_, [], Acc) => Acc; inner_aux([A | X], [B | Y], Acc) => inner_aux(X, Y, Acc+A*B); inner([1, 2, 3], [4, 5, 6]) ==> 32
This is a simplified grammar. Some constraints and nuances are notshown. The following without quotes are meta-symbols: ( ) | -> { }{....} means "any number of repetitions of", including zero. Commentsfollow // to end-of-line.
input_item -> definition ';' | rule ';' | term ';' definition -> head '=' body head -> var_head | function_head function_head -> identifier var_list { '(' var_list ')' } var_head -> identifier | '[' var_head_list ']' var_list -> empty | identifier { ',' identifier } var_head_list -> var_head { ',' var_head } | var_head { ',' var_head } '|' var_head rule -> match_head '=>' body match_head -> identifier '(' match_list ')' match_list -> empty | match_term { ',' match_term } match_term -> identifier | constant | identifier '+' numeric_constant | '[' match_list ']' | '[' match_list '|' match_term ']' body -> term '?' term // guard | { definition ',' } term // equational guard term -> or_exp '?' term ':' term | or_exp or_exp -> and_exp { '||' and_exp } and_exp -> not_exp { '&&' not_exp } not_exp -> { '!' } rel_exp rel_exp -> add_exp comp_op add_exp comp_op -> '!=' | '>=' | '>' | '==' | '<=' | '<' add_exp -> mul_exp { add_op mul_exp } add_op -> '+' | '-' mul_exp -> un_exp { mul_op un_exp } mul_op -> '*' | '/' | '%' un_exp -> { '-' | '$' } primary primary -> constant | '(' term ')' | '[' list ']' | '[' list | term ']' | identifier { '(' list ')' } // variable or function application list -> empty | term { ',' term } constant -> numeric_constant | string_constant | char_constant string_constant -> '"' { char } '"' // e.g. "a123" char_constant -> ''' char ''' // e.g. 'a' or '\n' numeric_constant -> sign digits exponent | sign digits '.' exponent | sign '.' digits exponent | sign digits '.' digits exponent sign -> '+' | '-' | empty // optional sign exponent -> ( 'e' | 'E' ) sign digits | empty // optional exponent digits -> digit { digit } identifier -> letter { letter | digit } letter -> 'a'|'b'|'c'|'d'|'e'|'f'|'g'|'h'|'i'|'j'|'k'|'l'|'m' |'n'|'o'|'p'|'q'|'r'|'s'|'t'|'u'|'v'|'w'|'x'|'y'|'z' |'A'|'B'|'C'|'D'|'E'|'F'|'G'|'H'|'I'|'J'|'K'|'L'|'M' |'N'|'O'|'P'|'Q'|'R'|'S'|'T'|'U'|'V'|'W'|'X'|'Y'|'Z' |'_' digit -> '0'|'1'|'2'|'3'|'4'|'5'|'6'|'7'|'8'|'9' char -> any ascii character | '\' any ascii character // escape sequence empty -> // the empty string