You have already seen how to use the functions of the GAP library, i.e., how to apply them to arguments. This section will show you how to write your own functions.
Writing a function that prints hello, world. on the screen is a simple
exercise in GAP.
gap> sayhello:= function()
> Print("hello, world.\n");
> end;
function ( ) ... end
This function when called will only execute the Print statement in the
second line. This will print the string hello, world. on the screen
followed by a newline character \n that causes the GAP prompt to
appear on the next line rather than immediately following the printed
characters.
The function definition has the following syntax.
function(arguments) statements end
A function definition starts with the keyword function followed by the
formal parameter list arguments enclosed in parenthesis. The formal
parameter list may be empty as in the example. Several parameters are
separated by commas. Note that there must be no semicolon behind the
closing parenthesis. The function definition is terminated by the
keyword end.
A GAP function is an expression like integers, sums and lists. It
therefore may be assigned to a variable. The terminating semicolon in
the example does not belong to the function definition but terminates the
assignment of the function to the name sayhello. Unlike in the case of
integers, sums, and lists the value of the function sayhello is echoed
in the abbreviated fashion function ( ) ... end. This shows the most
interesting part of a function: its formal parameter list (which is
empty in this example). The complete value of sayhello is returned if
you use the function Print.
gap> Print(sayhello, "\n");
function ( )
Print( "hello, world.\n" );
end
Note the additional newline character "\n" in the Print statement.
It is printed after the object sayhello to start a new line.
The newly defined function sayhello is executed by calling sayhello()
with an empty argument list.
gap> sayhello();
hello, world.
This is however not a typical example as no value is returned but only a string is printed.
A more useful function is given in the following example. We define a
function sign which shall determine the sign of a number.
gap> sign:= function(n)
> if n < 0 then
> return -1;
> elif n = 0 then
> return 0;
> else
> return 1;
> fi;
> end;
function ( n ) ... end
gap> sign(0); sign(-99); sign(11);
0
-1
1
gap> sign("abc");
1 # strings are defined to be greater than 0
This example also introduces the if statement which is used to execute
statements depending on a condition. The if statement has the
following syntax.
if condition then statements elif condition then statements else
statements fi;
There may be several elif parts. The elif part as well as the else
part of the if statement may be omitted. An if statement is no
expression and can therefore not be assigned to a variable. Furthermore
an if statement does not return a value.
Fibonacci numbers are defined recursively by f(1) = f(2) = 1 and f(n)
= f(n-1) + f(n-2). Since functions in GAP may call themselves, a
function fib that computes Fibonacci numbers can be implemented
basically by typing the above equations.
gap> fib:= function(n)
> if n in [1, 2] then
> return 1;
> else
> return fib(n-1) + fib(n-2);
> fi;
> end;
function ( n ) ... end
gap> fib(15);
610
There should be additional tests for the argument n being a positive
integer. This function fib might lead to strange results if called
with other arguments. Try to insert the tests in this example.
A function gcd that computes the greatest common divisor of two
integers by Euclid's algorithm will need a variable in addition to the
formal arguments.
gap> gcd:= function(a, b)
> local c;
> while b <> 0 do
> c:= b;
> b:= a mod b;
> a:= c;
> od;
> return c;
> end;
function ( a, b ) ... end
gap> gcd(30, 63);
3
The additional variable c is declared as a local variable in the
local statement of the function definition. The local statement, if
present, must be the first statement of a function definition. When
several local variables are declared in only one local statement they
are separated by commas.
The variable c is indeed a local variable, that is local to the
function gcd. If you try to use the value of c in the main loop you
will see that c has no assigned value unless you have already assigned
a value to the variable c in the main loop. In this case the local
nature of c in the function gcd prevents the value of the c in the
main loop from being overwritten.
We say that in a given scope an identifier identifies a unique variable.
A scope is a lexical part of a program text. There is the global scope
that encloses the entire program text, and there are local scopes that
range from the function keyword, denoting the beginning of a function
definition, to the corresponding end keyword. A local scope introduces
new variables, whose identifiers are given in the formal argument list
and the local declaration of the function. The usage of an identifier in
a program text refers to the variable in the innermost scope that has
this identifier as its name.
We will now write a function to determine the number of partitions of a positive integer. A partition of a positive integer is a descending list of numbers whose sum is the given integer. For example [4,2,1,1] is a partition of 8. The complete set of all partitions of an integer n may be divided into subsets with respect to the largest element. The number of partitions of n therefore equals the sum of the numbers of partitions of n-i with elements less than i for all possible i. More generally the number of partitions of n with elements less than m is the sum of the numbers of partitions of n-i with elements less than i for i less than m and n. This description yields the following function.
gap> nrparts:= function(n)
> local np;
> np:= function(n, m)
> local i, res;
> if n = 0 then
> return 1;
> fi;
> res:= 0;
> for i in [1..Minimum(n,m)] do
> res:= res + np(n-i, i);
> od;
> return res;
> end;
> return np(n,n);
> end;
function ( n ) ... end
We wanted to write a function that takes one argument. We solved the
problem of determining the number of partitions in terms of a recursive
procedure with two arguments. So we had to write in fact two functions.
The function nrparts that can be used to compute the number of
partitions takes indeed only one argument. The function np takes two
arguments and solves the problem in the indicated way. The only task of
the function nrparts is to call np with two equal arguments.
We made np local to nrparts. This illustrates the possibility of
having local functions in GAP. It is however not necessary to put it
there. np could as well be defined on the main level. But then the
identifier np would be bound and could not be used for other purposes.
And if it were used the essential function np would no longer be
available for nrparts.
Now have a look at the function np. It has two local variables res
and i. The variable res is used to collect the sum and i is a loop
variable. In the loop the function np calls itself again with other
arguments. It would be very disturbing if this call of np would use
the same i and res as the calling np. Since the new call of np
creates a new scope with new variables this is fortunately not the case.
The formal parameters n and m are treated like local variables.
It is however cheaper (in terms of computing time) to avoid such a recursive solution if this is possible (and it is possible in this case), because a function call is not very cheap.
In this section you have seen how to write functions in the GAP
language. You have also seen how to use the if statement. Functions
may have local variables which are declared in an initial local
statement in the function definition. Functions may call themselves.
The function syntax is described in Functions. The if statement is
described in more detail in If. More about Fibonacci numbers is found
in Fibonacci and more about partitions in Partitions.
GAP 3.4.4