> <\body> classes provide a simple way to introduce new data types with specified data fields, methods, constructors and an optional destructor. unions provide a convenient tool for the definition of unions and more general free data types. One typical example of a union is the type of finite integer sequences, defined as follows: <\mmx-code> union Sequence == { \ \ null (); \ \ cons (head: Integer, tail: Sequence); } Any such sequence is a formal expression of the form <\equation*> cons,cons,\\cons,null|)>|)>|)>, where ,\,a> are integers. The symbols and are called the for the union and any union of the type is always either of the form > or >, with and . The declaration of the union automatically gives rise to predicates <\mmx-code> null?: Sequence -\ Boolean; cons?: Sequence -\ Boolean; which allow the user to determine the kind of union. The symbols and induce partially defined <\mmx-code> postfix .head: Sequence -\ Integer; postfix .tail: Sequence -\ Sequence; If a union is of the form , then holds and we may obtain and via the expressions and respectively. For instance, the following function can be used in order to compute the length of a sequence: <\mmx-code> prefix # (s: Sequence): Int == \ \ if null? s then 0 else #s.tail + 1; Pattern matching provides us with an alternative way to do this: <\mmx-code> prefix # (s: Sequence): Int == \ \ match s with { \ \ \ \ case null () do return 0; \ \ \ \ case cons (_, t: Sequence) do return #t + 1; \ \ } also provides the following syntax for doing the same thing: <\mmx-code> prefix # (s: Sequence): Int == 0; prefix # (cons (_, t: Sequence)): Int == #t + 1; Notice that this syntax relies on the mechanism of conditional overloading (see the section on ). Likewise classes, unions can be parameterized. The container is a typical example of aparameterized union which generalizes the union : <\mmx-code> union List (T: Type) == { \ \ null (); \ \ cons (head: T, tail: List T); } > The general syntax for the declaration of a union is the following: <\mmx-code> union S == { \ \ cons_1 (field_11: T_11, ..., field_1n1: T_1n1); \ \ ... \ \ cons_k (field_k1: T_k1, ..., field_knk: T_knk); } This declaration in particular induces the declaration of functions <\mmx-code> cons_1: (T_11, ..., T_1n1) -\ S; ... cons_k: (T_k1, ..., T_knk) -\ S; These functions , >, are called the for , and all instances of are expressions which are built up freely using these constructors. Hence, any instance has the form (y_1, ..., y_ni)> for exactly one index and , >, . The declaration of also declares predicates <\mmx-code> cons_1?: S -\ Boolean; ... cons_k?: S -\ Boolean; such that holds if and only if is of the form (y_1, ..., y_ni)>. The declaration of finally induces the declaration of partially defined <\mmx-code> postfix .field_11 : S -\ T_11; ... ... postfix .field_knk: S -\ T_knk; Whenever is of the form then can be retrieved the expression . Whenever is not of this form, the expression is undefined and may provoke an error or worse. Parameterized unions are defined in a similar way as ordinary unions using the syntax <\mmx-code> union S (Param_1: C_1, ..., Param_p: C_p) == { \ \ cons_1 (field_11: T_11, ..., field_1n1: T_1n1); \ \ ... \ \ cons_k (field_k1: T_k1, ..., field_knk: T_knk); } Such declarations induce declarations of constructors, inspection predicates and accessors in the same way as their unparameterized homologues. In additional to the constructors, inspection predicates and accessors, declarations of (parameterized) unions also give rise to the following additional functions and constants for more low level introspection: <\mmx-code> postfix .kind: S -\ Int; cons_1_kind?: Int -\ Boolean; ... cons_k_kind?: Int -\ Boolean; cons_1_kind: Int; ... cons_k_kind: Int; If is of the form , then is just the integer . The predicate just checks whether the input integer is equal to , so that holds if and only if holds. Finally, is equal to the integer . Under some circumstances, it is useful to add additional constructors to unions . For instance, assume that we are writing a compiler for some language and that the expressions of the language are represented by a union. It might be that someone else would like to define alanguage extension but still use as much as possible the existing functions in the compiler for all kinds of manipulations of expressions. The simplest solution would then be to extend the expression type with some new constructors provided by the extended language, modulo customization of existing functions on expressions whenever necessary. Another important example is the design of a flexible type for symbolic expressions. Symbolic expression types are usually unions of various basic expression types, such as literals, integers, function applications, sums, products, etc. Whenever someone develops a library for a new kind of mathematical objects, say differential operators, then it is useful if these new objects can be seen as a new kind of symbolic expressions. In , extensible unions can be declared using the syntax <\mmx-code> union S := { \ \ cons_1 (field_11: T_11, ..., field_1n1: T_1n1); \ \ ... \ \ cons_k (field_k1: T_k1, ..., field_knk: T_knk); } The only distinction with respect to the mechanism from the previous section is that we are now allowed to further extend the union using the following syntax: <\mmx-code> union S += { \ \ extra_1 (added_11: X_11, ..., added_1n1: X_1n1); \ \ ... \ \ extra_l (added_l1: X_l1, ..., added_lnl: X_lnl); } An arbitrary number of such extensions can be made after the initial declaration of and these extensions may occur in different files (provided that the file with the initial declaration is (directly or indirectly) included in each of these files). Whenever we extend a union in the above way the corresponding new constructors, inspection predicates and accessors are automatically defined. The lower level inspection routines are also automatically extended, although the actual values of , >, now depend on the initialization order, and are therefore harder to predict. Nevertheless, the set of all these kinds is always of the form ,r-1|}>>, where is the total number of constructors. The constructors of a union can also be used as building bricks for so called . For instance, given the union <\mmx-code> union Sequence == { \ \ null (); \ \ cons (head: Integer, tail: Sequence); } from the beginning of this section, the expression <\mmx-code> cons (_, cons (_, tail_tail: Sequence)) is a pattern which corresponds to all sequences of length at least two, and with an explicit name for the typed name of the tail of the tail of the sequence. More generally, there are six kinds of patterns: <\enumerate> Structural patterns, of the form where is a constructor with arity of some union, and , >, are other patterns. User defined patterns, to be described in the next section. Wildcards of the form , where is the name of a variable and a type. Unnamed wildcards of the form , where is a type. The unnamed and untyped wildcard >. Ordinary expressions. One may define a natural relation ``matches'' on expressions and patterns, and if an expression matches a pattern, then there exists a binding for the wildcards which realizes the match. For instance, the expression is said to match the pattern for the binding > ())>. Patterns can be used as arguments of the > keyword inside bodies of the > keyword. Whenever the pattern after matches the expression after , the wildcards are bound using the bindings of the match, and can be used inside the body of the statement. For instance, we may use the following function in order to increase all terms of a sequence with an even index: <\mmx-code> even_increase (s: Sequence): Sequence == \ \ match s with { \ \ \ \ case cons (x: Integer, cons (y: Integer, t: Sequence)) do \ \ \ \ \ \ return cons (x, cons (y+1, even_increase t)); \ \ \ \ case _ do \ \ \ \ \ \ return s; \ \ } Patterns can also be used as generalized arguments inside function declarations. In that case, the declaration is considered as a special kind of conditionally overloaded function declaration. For instance, the declaration <\mmx-code> prefix # (cons (_, t: Sequence)): Int == #t - 1; is equivalent to <\mmx-code> prefix # (s: Sequence \| cons? s): Int == { \ \ t: Sequence == s.tail; \ \ #t - 1; } Again, the bindings of potential matches are used as values for the wildcards, which become local variables inside the function body. Besides the patterns which are induced by constructors of unions, new patterns may be defined explicitly by the user. The syntax for pattern declaration is as follows:> <\mmx-code> pattern pat_name (sub_1: T_1, ..., sub_n: T_n): PT == pat_body where the body consist of a finite number of cases of the form> <\mmx-code> case pat_case do { \ \ sub_1 == expr_1; \ \ ... \ \ sub_n == expr_n; } where is a pattern. Assuming this declaration of , any patterns ,>, of types ,>, give rise to a pattern of type . This pattern is matched if and only if one of the patterns in the various cases for is matched (with all occurrences of ,>, in replaced by ,>,). In that case, we privilege the first case which matches, and bind to whenever is of the form T_i>. In a similar way as for unions, replacing by or in the declaration of the above pattern allows for the declaration of an extensible pattern an actual extension of it. The above declaration of the pattern also gives rise to a generalized inspection predicate <\mmx-code> pat_name?: PT -\ Boolean; and functions <\mmx-code> postfix .sub_1: PT -\ T_1; ... postfix .sub_n: PT -\ T_n; which behave in a similar way as accessors of unions. For instance, for sequences ,\,x|]>> which really represent association lists \x,\,x\x|]>>, we may use the following pattern for retrieving the first association \x>: <\mmx-code> pattern assoc (key: Integer, val: Integer, next: Sequence): Sequence == \ \ case cons (k: Integer, cons (v: Integer, n: Sequence)) do { \ \ \ \ key \ == k; \ \ \ \ val \ == v; \ \ \ \ next == n; \ \ } The implementation of the predicate is equivalent to <\mmx-code> assoc? (s: Sequence): Boolean == cons? s and cons? s.next; and the implementations of the accessors , and are equivalent to <\mmx-code> postfix .key (s: Sequence): Integer == s.head; postfix .val (s: Sequence): Integer == s.tail.head; postfix .next (s: Sequence): Sequence == s.tail.tail; As mentioned in the introduction of section, one important special case where extensible unions are useful is for the definition of a flexible type for symbolic expressions. This type is essentially a union type. For instance, we might start with <\mmx-code> union Symbolic := { \ \ sym_undefined (); \ \ sym_boolean (boolean: Boolean); \ \ sym_literal (literal "literal": Literal); \ \ sym_compound (compound: Compound); } and further extend whenever necessary: <\mmx-code> union Symbolic += { \ \ sym_integer (integer: Integer); } <\mmx-code> union Symbolic += { \ \ sym_rational (rational: Rational); } The prefix provides us with a clean syntatic distinction between a ``symbolic expression which contains an object of type '' and a mere object of type . However, it would be simpler to write instead of as an inspection predicate, and it is somewhat cumbersome to implement addition of symbolic integers using <\mmx-code> infix + (sym_integer (i: Integer), sym_integer (j: Integer)): Symbolic == \ \ sym_integer (i + j); For this reason, provides us with a special operator > to be used for union constructors with one argument. For instance, the constructor would rather be declared using <\mmx-code> union Symbolic += { \ \ sym_integer (integer :: Integer); } This declaration automatically declares the synonym for and also introduces the simplified notation for the pattern . Assuming the further implementation of a constructor <\mmx-code> convert (i: Integer): Symbolic == sym_integer i; we may then simplify the declaration of our addition on symbolic integers into <\mmx-code> infix + (i :: Integer, j :: Integer): Symbolic == i + j; In a similar way, provides support for an operator >>> which allows us to mimick the notation > used for conversions for their symbolic wrappers. This notation is best illustrated with the example of an ``symbolic converter from symbolic integers to symbolic rational numbers'': <\mmx-code> pattern sym_as_rational (as_rational ::\ Rational): Symbolic := { \ \ case sym_rational (x: Rational) do as_rational == x; \ \ case sym_integer (x: Integer) do as_rational == x :\ Rational; } This allows us for instance to write <\mmx-code> infix + (i :: Integer, x ::\ Rational): Symbolic == i + x; We already noticed that the mechanism of conditional overloading induces a performance overhead (see the section on ). In the case of basic operations on symbolic expressions, such as additions, which are overloaded dozens if not hundreds of times, this performance penalty is too significant. Fortunately, the union as described in the previous section is essentially an extensible union type. Given a unary conditionally overloaded operation on symbolic expressions, the appropriate routine to be called for a given input can often be determined as a function of the integer only. This makes it possible to use a fast lookup table instead of the usual conditional overloading mechanism in this particular case. In order to do so, we have to declare the operation using> <\mmx-code> foo (x: dispatch Symbolic): Symbolic := default_implementation Operations with higher arities and operations which involve other types are treated in a similar way: the type of each argument involved in the fast table lookup should be preceded by the keyword . For instance, <\mmx-code> infix + (x: dispatch Symbolic, y: dispatch Symbolic): Symbolic := ...; postfix [] (x: dispatch Symbolic, i: Int): Symbolic := ...; Notice that the size of the dispatch table is equal to the product of the number of union constructors of all arguments on which we perform our dispatching. For this reason, we do not allow dispatching on more than two arguments. also provides the keyword > as a special case of user defined patterns which is compatible with the above dispatching mechanism. A typical example of a disjunction is <\mmx-code> disjunction sym_scalar (scalar :: Scalar): Symbolic := { \ \ sym_boolean _; \ \ sym_integer _; \ \ sym_rational _; } . If you don't have this file, write to the Free Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.> >