> <\body> The most basic form of a function declaration in is <\code> <\mmx-code> fun_name (arg_1: Type_1, ..., arg_n: Type_n): Ret_Type == fun_body The function name can be an arbitrary identifier, such as , or +>. Using the keywords >>> or >, it is also possible to construct function expressions. For instance, the following three declarations are equivalent: <\mmx-code> cube (x: Int): Int == x*x*x; cube: Int -\ Int == (x: Int) :-\ (x*x*x: Int); cube: Int -\ Int == lambda (x: Int): Int do x*x*x; >>We recall that provides two syntaxes for function application: the classical syntax and the operator syntax . In the case of nested applications, these two syntaxes use adifferent grouping: whereas parses as , the expression should be parsed as . Functions with an arbitrary number of arguments of a given type can be formed by using so called tuple types. More precisely, assume a function declaration of the form <\mmx-code> fun_name (arg_1: Type_1, ..., arg_n: Type_n, x: Tuple X): Ret_Type == fun_body Then the function applies to first arguments of types until and optional arguments which are all of type . For instance, the routine <\mmx-code> extract (v: Vector Double, t: Tuple Int): Vector Double == \ \ [ v[i] \| i: Int in [t] ]; can be used to extract the vector of all entries with given indices from a given vector. Hence, <\mmx-code> v: Vector Double == [ 1.0, 2.0, 6.0, 3.14, 2012.0 ]; mmout \\ extract (v, 1, 2, 3, 3, 0) \\ lf; prints the vector >. In a similar way, one may pass a generator instead of a tuple as a last argument of a function.

Functions definitions are allowed to be recursive, such as the following routine for computing the factorial of an integer: <\mmx-code> postfix ! (n: Integer): Integer == \ \ if n \= 1 then 1 else n * (n-1)!; Functions which are defined in the same scope are also allowed to be mutually recursive. An example of mutually recursive sequences are Hofstadter's female and male sequences > and > defined by =1>, =0> and <\eqnarray*> >||>>>|>||>,>>>> for 0>. They can be implemented in as follows: <\mmx-code> F (n: Integer): Integer == if n = 0 then 1 else n - M F (n-1); M (n: Integer): Integer == if n = 0 then 0 else n - F M (n-1); In large multiple file programs, it sometimes happens that the various mutually recursive functions are defined in different files, and thus in different scopes. In that case, prototypes of the mutually recursive functions should be defined in a file which is included by all files where the actual functions are defined. Protypes of functions are declared using the syntax <\mmx-code> fun (arg_1: Src_1, ..., arg_n: Src_n): Dest; In case of the above example, we might define prototypes for and in a file : <\mmx-code> F (n: Integer): Integer; M (n: Integer): Integer; Next, a first file would include and define : <\mmx-code> include "common.mmx"; F (n: Integer): Integer == if n = 0 then 1 else n - M F (n-1); In a second file , we again include and define : <\mmx-code> include "common.mmx"; M (n: Integer): Integer == if n = 0 then 0 else n - F M (n-1); Besides mutually recursive function definitions, also allows for dependencies among the arguments of a function and dependencies of the return type on the arguments. Although the dependencies among the arguments may occur in any order, mutual dependencies are not allowed. For instance, the following routine takes a ring together with an element of this ring on input and displays the first powers of this element: <\mmx-code> first_powers (x: R, R: Ring, n: Int): Void == { \ \ p: R := x; \ \ for i: Int in 1 to n do { \ \ \ \ mmout \\ i \\ " -\ " \\ p; \ \ \ \ p := x * p; \ \ } } In this example, the type > of is a category. We refer to section

and the chapter for a declaration of this category and more details on how to use them. The following code defines a container > for vectors with entries of type and a fixed size . <\mmx-code> class Fixed_Size_Vector (T: Type, n: Int) == { \ \ mutable rep: Vector T; \ \ constructor fixed_size_vector (c: T, n: Int) == { \ \ \ \ rep == [ c \| i: Int in 0..n ]; \ \ } } The return type of the constructor depends on the argument to the same constructor. Functions are first class objects in , so they can consistently be used as arguments or return values of other functions. They can also be declared locally inside other functions or used as constant or mutable fields of user defined classes. as argument> \ Asimple example of a function which takes a function predicate as an argument is <\mmx-code> filter (v: Vector Int, pred?: Int -\ Boolean): Vector Int == \ \ [ x: Int in v \| pred? x ]; The construct systematically exploits this possibility to use functions as arguments. For instance, the following instruction prints the vector >: <\mmx-code> mmout \\ map (infix *, [1, 2, 3], [4, 5, 6]) \\ lf; as return value> Atypical example of a function which returns another function is <\mmx-code> shift (x: Int): Int -\ Int == (y: Int) :-\ (x+y: Int); This kind of functions are so common that provides a special syntax for it, which generalizes the syntax of basic function declarations: <\code> <\mmx-code> fun_name (arg_11: Type_11, ..., arg_1n1: Type_1n1) \ \ \ \ \ \ \ \ \ ... \ \ \ \ \ \ \ \ \ (arg_k1: Type_k1, ..., arg_knk: Type_knk): Ret_Type == fun_body This syntax allows to simplify the definition of > into <\mmx-code> shift (x: Int) (y: Int): Int == x+y; as local variable> In a similar way that functions can be used as arguments or return values of other functions, it is possible to locally define functions inside other functions. One typical example is <\mmx-code> shift_all (v: Vector Int, delta: Int): Vector Int == { \ \ shift (x: Int): Int == x + delta; \ \ return map (shift, v); } Recursion and mutual recursion are still allowed for such local function declarations. For instance, we may generalize Hofstadter's example of female and male sequences by allowing the user to choose arbitrary initial conditions: <\mmx-code> FM (n: Int, init_F: Int, init_M: Int): Int == { \ \ F (n: Integer): Integer == if n = 0 then init_F else n - M F (n-1); \ \ M (n: Integer): Integer == if n = 0 then init_M else n - F M (n-1); \ \ return F n; } As in the case of ordinary variables, functions can be declared to be mutable, using the syntax <\code> <\mmx-code> fun_name (arg_1: Type_1, ..., arg_n: Type_n): Ret_Type := fun_body In that case, the function can be replaced by another function during the execution of the program: <\mmx-code> foo (n: Int): Int := n*n; foo := (n: Int) :-\ (n*n*n: Int); In section

below, we will how the mechanism of conditional overloading can exploit this possibility to dynamically replace functions by others. In classical mathematics, operators such as are heavily overloaded, in the sense that the same notation can be used in order to add numbers, polynomials, matrices, and so on. One important feature of is that it has powerful support for overloaded notations, which allows the programmer to mimick classical mathematical notations in a faithful way. The simplest mechanism of allows the user to redefine the same symbol several times with different types. For instance, <\mmx-code> dual: Int \ \ \ == 123; dual: String == "abc"; In this case, the variable can both be interpreted as a machine integer and as a string. For instance, assuming the above declaration, the following code is correct: <\mmx-code> hop : Int \ \ \ == dual + 1; hola: String == dual \\ "def"; Indeed, in the definition of (and similarly for ), the code only makes sense when is of type , so the correct disambiguation can be deduced from the context. On the other hand, the instruction <\mmx-code> mmout \\ dual \\ lf; is ambiguous and will provoke an error message of the compiler. In such cases, we may explicitly disambiguate using the operator >. Both the following two lines are correct: <\mmx-code> mmout \\ dual :\ Int \\ lf; mmout \\ dual :\ String \\ lf; In case of doubt, successions of disambiguations, such as Integer :\ Rational> can be useful in order to make the meaning of an expression clear. Of course, overloading is most useful in the case of functions, and the mechanism described above applies in particular to this case. For instance, we may define <\mmx-code> twice (x: Int): Int == 2*x; twice (s: String): String == s \\ s; Then we may write <\mmx-code> mmout \\ twice 111 \\ lf; mmout \\ twice "hello" \\ lf; Overloaded functions can very well be applied to overloaded expressions. For instance, the expression admits both the types and . We may thus write <\mmx-code> plok: Int == twice dual; mmout \\ twice dual :\ String \\ lf; It should also be noticed that both the arguments and the return values of functions can be overloaded. For instance, we may overload a third time <\mmx-code> twice (x: Int): String == twice as_string x; After this, the expression can both be interpreted as the number and as the string.

Besides discrete overloading, also features parametric overloading, based on the > construct. In this case, the overloaded value no longer takes a finite number of possible types, but rather an infinite number of possible types which depend on one or more parameters. The general syntax for making one or more parametrically overloaded declarations is <\mmx-code> forall (param_1: Type_1, ..., param_n: Type_n) declarations The parameters , ..., are usually types themselves, in which case their types are so called . For instance, consider the following declaration: <\mmx-code> forall (R: Ring) cube (x: R): R == x*x*x; It states that for any type which has the structure of a ring, we have a function R>>. Parametrically overloaded functions such as are also called templates. The conditions for to be a ring are stated by declaring the category . One possible such declaration is the following: <\mmx-code> category Ring == { \ \ convert: Int -\ This; \ \ prefix -: This -\ This; \ \ infix +: (This, This) -\ This; \ \ infix -: (This, This) -\ This; \ \ infix *: (This, This) -\ This; } In this case, any type with the usual operations > and a converter R> will be considered to be a ring. The mere presence of these operations in the current context is sufficient: the compiler does not check any of mathematical ring axioms. Assuming a context in which both the types and are present, we may apply the template as follows: <\mmx-code> mmout \\ cube 123 \\ lf; \ \ \ \ \ \ // applies cube: Int -\ Int mmout \\ cube 1.0e100 \\ lf; \ \ // applies cube: Double -\ Double Although this is usually not necessary, it is sometimes useful to make the values of the parameters explicit, for instance in order to make expressions less ambiguous. This can be done using the infix operator. For instance, <\mmx-code> mmout \\ cube#Int (123) \\ lf; mmout \\ cube#Double (1.0e100) \\ lf; |grouping> It often happends that several generic routines share the same parameters. In that case, they can be grouped together in a common block. For instance, given a ring , assume that we are developing acontainer > for arithmetic in |]>/|)>> (see also the section on ): <\mmx-code> class Tangent (R: Ring) == { \ \ b: R; \ // base point (coefficient of 1) \ \ s: R; \ // slope \ \ \ \ \ (coefficient of epsilon) \ \ constructor tangent (b2: R) == { b == b2; s == 0; } \ \ constructor tangent (b2: R, s2: R) == { b == b2; s == s2; } } Then we may define a ring structure on using <\mmx-code> forall (R: Ring) { \ \ convert (i: Int): Tangent R == \ \ \ \ tangent (i :\ R); \ \ prefix - (x: Tangent R): Tangent R == \ \ \ \ tangent (-x.b, -x.s); \ \ infix + (x: Tangent R, y: Tangent R): Tangent R == \ \ \ \ tangent (x.b + y.b, x.s + y.s); \ \ infix - (x: Tangent R, y: Tangent R): Tangent R == \ \ \ \ tangent (x.b - y.b, x.s - y.s); \ \ infix * (x: Tangent R, y: Tangent R): Tangent R == \ \ \ \ tangent (x.b * y.b, x.b * y.s + x.s * y.b); } It often happens that template parameters need to fulfill several requirements, such as being a ring and an ordering at the same time. provides the keyword > for this purpose. For example: <\mmx-code> forall (R: Ring) assume (R: Ordering) operator \= (x: Tangent R, y: Tangent R): Boolean == \ \ x = y or x.b \ y.b; Such additional assumptions can naturally be included in blocks: <\mmx-code> forall (R: Ring) { \ \ ... \ \ infix * (x: Tangent R, y: Tangent R): Tangent R == \ \ \ \ tangent (x.b * y.b, x.b * y.s + x.s * y.b); \; \ \ assume (R: Ordering) \ \ operator \= (x: Tangent R, y: Tangent R): Boolean == \ \ \ \ x = y or x.b \ y.b; }

It frequently occurs that for specific values of the template parameters, the generic implementation of the template can be further improved. For instance, consider the following generic implementation of apower operations on field elements: <\mmx-code> forall (F: Field) infix ^ (x: F, i: Int): F == { \ \ if i = 0 then return 1; \ \ else if i \ 0 then { \ \ \ \ s: F == square (x^(i quo 2)); \ \ \ \ if i rem 2 = 0 then return s; \ \ \ \ else return x * s; \ \ } \ \ else return (1 :\ F) / x^(-i); } This implementation uses binary powering and is more or less as efficient as it can get for elements in a generic field. However, in the \Pfield\Q of arbitrary precision floating point numbers, we have fast implementations of the operations and , so the following implementation is even more efficient in this specific case: <\mmx-code> infix ^ (x: Floating, i: Int): Floating == { \ \ if x \ 0 then \ \ \ \ return exp (i * log x); \ \ else if x \ 0 then { \ \ \ \ if i rem 2 = 0 then return (abs x)^i; \ \ \ \ else return -(abs x)^i; \ \ } \ \ else { \ \ \ \ if i \= 0 then return 0; \ \ \ \ else return 1.0 / 0.0; \ \ } } allows the above two implementations to happily coexist, thanks to the mechanism of partial specialization. Without this mechanism, any expression of the form with > and would be ambiguous, since both implementations of ^> allow for the interpretation of as an expresson of type . The idea behind partial specialization is that we always prefer the most particular ( \Pbest\Q) implementation, in this case the second one. In general, a first template (or function) is more particular than a second one, if any possible type ( by substituting concrete values for the parameters) of the first template is also a possible type of the second one. For instance, the first above implementation of ^> is not more particular than the second one, since the the type Rational> of > is not a possible type of the second implement of ^>. It should be noticed that the relation \Pis more particular than\Q is only a partial ordering. For instance, none of the two following routines is more particular than the other one: <\mmx-code> forall (R: Ring) mul (i: Int, x: R): R == (i :\ R) * x; forall (R: Ring) mul (x: R, i: Int): R == x * (i :\ R); Applying the function to two elements of type would therefore be ambiguous. This ambiguity can be removed by implementing the routine <\mmx-code> mul (i: Int, j: Int): Int == i * j; Indeed, this routine is more particular than each of the two generic implementations of , so it will be the preferred implementation whenever is applied to two elements of type . It should be noticed that the relation \Pis more particular than\Q does not necessarily mean that some of the parameters have to be substituted by actual values in order to become \Pmore particular\Q. For instance, consider the prototypes of two templates for the computation of determinants: <\mmx-code> forall (R: Ring) \ det: Matrix R -\ R; forall (F: Field) det: Matrix F -\ F; Then the second template is more particular than the first one, so it will be the preferred implementation when computing the determinant of a matrix with entries in a field. In , the special operator > is used for type conversions. For instance, given an integer and aconverter <\mmx-code> convert: Integer -\ Rational; we may use the expression Rational> in order to explicitly convert into a rational number. The operator is used for implicit type conversions only under the following particular circumstances: <\itemize> During the declaration of variables. With , we may thus write <\mmx-code> a: Rational == x; b: Rational := square x + 3; During assignments: <\mmx-code> b: Rational := x; b := x * x; When returning from a function: <\mmx-code> f (x: Integer): Rational == x + 1; g (x: Integer): Rational == { \ \ if x \= 0 then return x; \ \ else return 1/x; } Inside the - construct: <\mmx-code> for x: Rational in 1 to 10 do \ \ mmout \\ x \\ " -\ " \\ 1/x \\ lf; Except for the above special cases, does not perform any implicit conversions. For instance, even if we have an implicit converter, then application the following function cannot be applied to an expression of type : <\mmx-code> foo (x: Rational): Rational == x + 1/x; Nevertheless, using the mechanism of parametric overloading, we may define in the following way so as to make this possible: <\mmx-code> forall (F: To Rational) foo (x_orig: F): Rational == { \ \ x: Rational == x_orig :\ Rational; \ \ x + 1/x; } Here > stands for the following parameterized category: <\mmx-code> category To (T: Type) == { \ \ convert: This -\ T; } The new version of cannot only be applied to expressions of type , but to any expression of a type with a converter Rational>. The above way of adapting function declarations so as to accept convertable arguments is so common that provides a special syntax for it. This syntax allows us to simplify the second declaration of into <\mmx-code> foo (x :\ Rational): Rational == x + 1/x; We call this mechanism type conversion of function arguments. A similar syntax may be used for type conversion of the return value: <\mmx-code> bar (i: Integer) :\ Integer == 1 - i; This definition is equivalent to <\mmx-code> forall (T: From Integer) bar (i: Integer): T == (1 - i) :\ T; where <\mmx-code> category From (F: Type) == { \ \ convert: F -\ This; } The mechanisms of and type conversions are powerful, but one should be careful not to abuse them. For instance, at a first sight, it may be tempting to allow for priori> type conversions for all routines on rational numbers: <\mmx-code> infix + (x :\ Rational, y :\ Rational): Rational == ...; infix - (x :\ Rational, y :\ Rational): Rational == ...; infix * (x :\ Rational, y :\ Rational): Rational == ...; infix / (x :\ Rational, y :\ Rational): Rational == ...; ... Indeed, this would immediately give us support for the notation whenever is a rational number. However, this kind of abuse would quickly lead to ambiguities, since it also allows the addition on rational numbers to be applied to two integers. Although many of these ambiguities are automatically resolved by the partial specialization mechanism, they tend to become a serious source of problems in more voluminous mathematical libraries with many types and heavily overloaded notaions. Besides the semantic correctness issue, there is also a performance issue: the compiler has to examine all possible meanings of ambiguous expressions and then determine the preferred ones among them. It is therefore better to reduce potential ambiguities as much as possible beforehand. In the above case, this can for instance be achieved by using the following declarations instead: <\mmx-code> infix + (x: Rational, y :\ Rational): Rational == ...; infix - (x: Rational, y :\ Rational): Rational == ...; infix * (x: Rational, y :\ Rational): Rational == ...; infix / (x: Rational, y :\ Rational): Rational == ...; ... infix + (x :\ Rational, y: Rational): Rational == ...; infix - (x :\ Rational, y: Rational): Rational == ...; infix * (x :\ Rational, y: Rational): Rational == ...; infix / (x :\ Rational, y: Rational): Rational == ...; ... In order to avoid the same kind of ambiguity as in the example from section

, we will also have to provide the routines <\mmx-code> infix + (x: Rational, y: Rational): Rational == ...; infix - (x: Rational, y: Rational): Rational == ...; infix * (x: Rational, y: Rational): Rational == ...; infix / (x: Rational, y: Rational): Rational == ...; ... In fact, most converters of a type into are actually compositions of a converter of into and the standard converter of into . Therefore, an even better idea is to replace the block of declarations with conversions by <\mmx-code> infix + (x: Rational, y :\ Integer): Rational == ...; infix - (x: Rational, y :\ Integer): Rational == ...; infix * (x: Rational, y :\ Integer): Rational == ...; infix / (x: Rational, y :\ Integer): Rational == ...; ... infix + (x :\ Integer, y: Rational): Rational == ...; infix - (x :\ Integer, y: Rational): Rational == ...; infix * (x :\ Integer, y: Rational): Rational == ...; infix / (x :\ Integer, y: Rational): Rational == ...; ... Indeed, besides the fact that we eliminate all possible ambiguities in this way, the above routines also admit more efficient implementations. In a similar way, for container types such as >, we usually have special implementations for scalar operations: <\mmx-code> forall (R: Ring) { \ \ infix + (p: Polynomial R, c :\ R): Polynomial R == ...; \ \ infix - (p: Polynomial R, c :\ R): Polynomial R == ...; \ \ infix * (p: Polynomial R, c :\ R): Polynomial R == ...; \ \ ... \ \ infix + (c :\ R, p: Polynomial R): Polynomial R == ...; \ \ infix - (c :\