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.

Subsections

The forward Declaration

Example `Lang_Recursion (H1E15)`

> 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_Procedures (H1E16)`

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 (H1E17)`

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]