Functions and Procedures

[Next] [Prev] [Right] [Left] [Up] [Index] [Root]

User functions (as opposed to intrinsic functions) can be written in two, almost identical forms, and one short constructor form. User procedures can be created in only one way. Names for functions and procedures are ordinary identifiers and should obey the same rules as given above for other variables.

medbreak mulboxit{halign#hfil cr p := procedure(x_1, ..., x_n: parameters)cr statements cr end procedure;cr} mulboxit{halign#hfil cr procedure p(x_1, ..., x_n: parameters)cr statements cr end procedure;cr}

sigotherno p = procedure(x_1, ..., x_n: parameters) statements : ->

sigotherno procedure p(x_1, ..., x_n: parameters) statements : ->

The procedure, taking n >= 0 arguments and defined by the statements is created and assigned to p. Each of the arguments may be either a variable (y_i) or a referenced variable (~y_i). Inside the procedure only referenced variables (and local variables) may be (re-)assigned to. The procedure p is invoked by typing p(x_1, ..., x_n), where the same succession of variables and referenced variables is used (see the example below). Procedures cannot return values.

If there are parameters given, they must consist of a comma-separated list of clauses each of the form identifier := value. The identifier gives the name of the parameter, which can then be treated as a normal value argument within the statements. The value gives a default value for the parameter, and may depend on any of the arguments or preceding parameters; if, when the function is called, the parameter is not assigned a value, this default value will be assigned to the parameter. Thus parameters are always initialized. If no parameters are desired, the colon following the last argument, together with parameters, may be omitted.

As in the case of function, the only difference between the two declarations lies in the fact that the second version allows recursive calls to the procedure within itself using the identifier (p in this case).

Subsections

The forward Declaration

Example `Lang_Recursion (H1E17)`

> fibonacci := function(n)
>    if n le 2 then
>       return 1;
>    else
>       return $$(n-1) + $$(n-2);
>    end if;
> end function;
>
> print fibonacci(10)+fibonacci(12);
199


> function Lucas(n)
>    if n eq 1 then
>       return 1;
>    elif n eq 2 then
>       return 3;
>    else
>       return Lucas(n-1)+Lucas(n-2);
>    end if;
> end function;
>
> print Lucas(11);
199


> fibo := func< n | n le 2 select 1 else $$(n-1) + $$(n-2) >;
> print fibo(10)+fibo(12);
199

Example `Lang_Parameters (H1E18)`

> f := function(x, y: Proof := true, Al := "Simple")
>    return <x, y, Proof, Al>;
> end function;
>
> print f(1, 2);
<1, 2, true, Simple>
> print f(1, 2: Proof := false);
<1, 2, false, Simple>
> print f(1, 2: Al := "abc", Proof := false);
<1, 2, false, abc>

Example `Lang_Procedures (H1E19)`

By way of simple example, the following (rather silly) procedure assigns a Boolean to the variable holds, according to whether or not the first three arguments x, y, z satisfy x^2 + y^2=z^2. Note that the fourth argument is referenced, and hence can be assigned to; the first three arguments cannot be changed inside the procedure.

> procedure CheckPythagoras(x, y, z, ~h)
>     if x^2+y^2 eq z^2 then
>         h := true;
>     else
>         h := false;
>     end if;
> end procedure;

We use this to find some Pythagorean triples (in a particularly inefficient way):

> for x, y, z in { 1..15 } do
>    CheckPythagoras(x, y, z, ~h);
>    if h then
>       print "Yes, Pythagorean triple!", x, y, z;
>    end if;
> end for;
Yes, Pythagorean triple! 3 4 5
Yes, Pythagorean triple! 4 3 5
Yes, Pythagorean triple! 5 12 13
Yes, Pythagorean triple! 6 8 10
Yes, Pythagorean triple! 8 6 10
Yes, Pythagorean triple! 9 12 15
Yes, Pythagorean triple! 12 5 13
Yes, Pythagorean triple! 12 9 15

The forward Declaration

forward f : identifier ->

The forward declaration of a function or procedure f; although the assignment of a value to f is deferred, f may be called from within another function or procedure already.
The forward statement must occur on the `main' level, that is, outside other functions or procedures.

Example `Lang_forward (H1E20)`

We give an example of mutual recursion using the forward declaration. In this example we define a primality testing function which uses the factorization of n - 1, where n is the number to be tested. To obtain the complete factorization we need to test whether or not factors found are prime. Thus the prime divisor function and the primality tester call each other.

First we define a simple function that proves primality of n by finding an integer of multiplicative order n - 1 modulo n.

> function strongTest(primdiv, n)
>     return exists{ x : x in [2..n-1] | \
>       Modexp(x, n-1, n) eq 1 and
>       forall{ p : p in primdiv | Modexp(x, (n-1) div p, n) ne 1 }
>     };
> end function;

Next we define a rather crude isPrime function: for odd n>3 it first checks for a few (3) random values of a that a^(n - 1) = 1 mod n, and if so, it applies the above primality prover. For that we need the not yet defined function for finding the prime divisors of an integer.

> forward primeDivisors;
> function isPrime(n)
>    if n in { 2, 3 } or
>       IsOdd(n) and
>       forall{ a : a in { Random(2, n-2): i in [1..3] } |
>          Modexp(a, n-1, n) eq 1 } and
>          strongTest( primeDivisors(n-1), n )
>    then
>       return true;
>    else
>       return false;
>    end if;
> end function;

Finally, we define a function that finds the prime divisors. Note that it calls the isPrime function. Note also that this function is recursive, and that it calls a function upon its definition, in the form func< ..
> ( .. ).

> primeDivisors := function(n)
>    if isPrime(n) then 
>       return { n };
>    else
>       return func< d | primeDivisors(d) join primeDivisors(n div d) >
>          ( rep{ d : d in [2..Isqrt(n)] | n mod d eq 0 });
>    end if;
> end function;
> print isPrime(1087);
true;

[Next] [Prev] [Right] [Left] [Up] [Index] [Root]