5.4 Definition of Operators

An operator is defined by giving its signature and its name. Operators with the same signature can be defined at once. The signature of an operator contains its domain (types of its sons) and its codomain.

Operators may be classified into four classes: atomic operators, fixed arity operators, list operators and second-order operators.

5.4.1 Atomic Operators

Atomic operators     are operators whose domain are string, integer or tree. They correspond to the terminal of the syntax and carry a value whose type depends on their domain. This class of operators inherited from Metal may be merge with fixed arity operators in a future version of AS.

The following examples give the typical declaration for identifiers or integers:

Examples:

id : string -> Id;
int : integer -> Int;

5.4.2 Fixed Arity Operators

Fixed arity operators  are operators whose domain are a product of some phyla. There is no limit on the size of the product. Operators of arity zero are fixed arity operators (their correspond to the singletons of Metal that was considered as atomic operators).

Examples:

pair : Elem # Elem -> Pair;
plus : Exp # Exp -> Exp;
void : -> Option;

5.4.3 List Operators

List operators   are operators whose domain is of the form ``list of P'' where P is a phylum. As Metal, AS distinguish lists that may be empty (``*-list'') from those that cannot be empty (``+-list'').

Examples:

exp_s : Exp* -> Exp_s;
id_s : Id+ -> Id_s;

5.4.4 Second-order Operators

Second-order operators    are operators that introduce a binder in the abstract syntax. From a unique declaration, the system generates a first order operator for a first order version of the formalism and a second order operator for a higher-order version of the syntax.

In a -calculus like language, the first-order abstract syntax of the expression is usually defined by lamb : Id # Exp -> Exp, as x must be a variable name (an identifier), and E an expression. As is also a function of type Exp -> Exp, its higher-order abstract syntax is usually defined by lamb : (Exp -> Exp) -> Exp. In order to allow the use of both the first-order and the second-order view, AS merge these two definitions into a unique one as in the following example. The type-checker verifies that the phylum given for the first-order type of the variable (here Id) contains a unique operator whose domain is string.

Example:

lamb : (Id:Exp -> Exp) -> Exp;

5.4.5 Modularity

Notice that the phyla used in the signatures may come from another formalism previously defined and accessible to the system, allowing modular definition of abstract syntaxes.

Formalism Inclusion, Typed Names

5.4.6 Syntax

We give here the complete syntax of operator declarations:

operator  --> id ("," id)* ":" signature ";"
signature --> domain "->" id
domain   -->   "string"
              | "integer"
              | "tree"
              | [tid ("#" tid)*]
              | tid "+"
              | tid "*"
              | "(" tid ":" tid "->" tid ")"