|
There are two slightly different syntactic forms provided for the definition
of a user function (as opposed to an intrinsic function). For the case of a
function whose definition can be expressed as a single expression, an abbreviated
form is provided. The syntax for the definition of user procedures is similar.
Names for functions and procedures are ordinary identifiers and so obey the
rules as given in Chapter 1 for other variables.
function f(x1, ..., xn : parameters)
statements
end function;
This creates a function taking n≥0 arguments, and assigns
it to f. The statements may comprise any number of valid Magma
statements, but at least one of them must be of the form
return expression;. The value of that expression (possibly
dependent on the values of the arguments x1, ..., xn) will be the
return value for the function; failure to return a value will lead
to a run-time error when the function is invoked. (In fact, a return
statement is also required for every additional `branch' of the function that
has been created using an if ... then ... else ... construction.)
The function may return multiple values. Usually one uses the
form return expression, ..., expression;. If one wishes
to make some return value(s) undefined (so that the number of return
values for the function is the same in all `branches' of the function)
the underscore symbol (_) may be used. (The undefined symbol
may only be used for final values of the list.)
This construct allows behaviour similar to the intrinsic function
IsSquare, say, which
returns true and the square root of its argument if that exists,
and false and the undefined value otherwise.
See also the example below.
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.
The only difference between the two forms of function declaration
lies in recursion. Functions may invoke themselves recursively since
their name is part of the syntax;
if the first of the above declarations is used, the identifier
f cannot be used inside the definition of f (and $$ will
have to be used to refer to f itself instead), while the second form
makes it possible to refer to f within its definition.
An invocation of the user function f takes the form
f(m1, ..., mn), where m1, ..., mn are
the actual arguments.
This is a short form of the function constructor designed for the
situation in which the value of the function can be defined by a
single expression. A function f is created which returns the value
of the expression (possibly involving the function arguments
x1, ..., xn). Optional parameters are permitted as
above.
function f(x_1, ..., x_n, ... : parameters)
statements
end function;
This creates a variadic function, which can take n or more arguments.
The semantics are identical to the standard function definition described above,
with the exception of function invocation. An invocation of a variadic
function f takes the form f(y1, ..., ym), where y1, ..., ym
are the arguments to the function, and m ≥n. These arguments get bound to
the parameters as follows: for i < n, the argument yi is bound to the
parameter xi. For i ≥n, the arguments yi are bound to the last
parameter xn as a list [ * yn, ..., ym * ].
This is a short form of the function constructor for variadic functions,
otherwise identical to the short form described above.
This example illustrates recursive functions.
> fibonacci := function(n)
> if n le 2 then
> return 1;
> else
> return $$(n-1) + $$(n-2);
> end if;
> end function;
>
> 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;
>
> Lucas(11);
199
> fibo := func< n | n le 2 select 1 else $$(n-1) + $$(n-2) >;
> fibo(10)+fibo(12);
199
This example illustrates the use of parameters.
> f := function(x, y: Proof := true, Al := "Simple")
> return <x, y, Proof, Al>;
> end function;
>
> f(1, 2);
<1, 2, true, Simple>
> f(1, 2: Proof := false);
<1, 2, false, Simple>
> f(1, 2: Al := "abc", Proof := false);
<1, 2, false, abc>
This example illustrates the returning of undefined values.
> f := function(x)
> if IsOdd(x) then
> return true, x;
> else
> return false, _;
> end if;
> end function;
>
> f(1);
true 1
> f(2);
false
> a, b := f(1);
> b;
1
> a, b := f(2);
> b; // Undefined value
>> b;
^
User error: Identifier 'b' has not been assigned
This example illustrates the use of variadic functions.
> f := function(x, y, ...)
> print "x: ", x;
> print "y: ", y;
> return [x + z : z in y];
> end function;
>
> f(1, 2);
x: 1
y: [* 2*]
[ 3 ]
> f(1, 2, 3);
x: 1
y: [* 2, 3*]
[ 3, 4 ]
> f(1, 2, 3, 4);
x: 1
y: [* 2, 3, 4*]
[ 3, 4, 5 ]
procedure p(x1, ..., xn : parameters)
statements
end procedure;
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 (yi) or
a referenced variable (~yi). Inside the procedure
only referenced variables (and local variables) may be (re-)assigned to.
The procedure p is
invoked by typing p(x1, ..., xn), 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).
This is a short form of the procedure constructor designed for the
situation in which the action of the procedure may be accomplished by a
single statement. A procedure p is defined which calls the procedure
given by the expression. This expression must be a simple procedure
call (possibly involving the procedure arguments x1, ..., xn).
Optional parameters are permitted as in the main procedure constructor.
procedure p(x1, ..., xn, ... : parameters)
statements
end procedure;
Creates and assigns a new variadic procedure to p. The use of a
variadic procedure is identical to that of a variadic function, described
previously.
This is a short form of the procedure constructor for variadic procedures.
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
> "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 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. (See also Chapter MAGMA SEMANTICS.)
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;
> isPrime(1087);
true;
[Next][Prev] [Right] [Left] [Up] [Index] [Root]
|