You have already seen how to use functions in the GAP library, i.e., how to apply them to arguments.
In this section you will see how to write functions in the GAP
language. You will also see how to use the if statement and declare
local variables with the local statement in the function definition.
Loop constructions via while and for are discussed further, as are
recursive 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 an integer, a sum or a list.
Therefore it 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" );
return;
end
Note the additional newline character "\n" in the Print
statement. It is printed after the object sayhello to start a new
line. The extra return statement is inserted by GAP to simplify
the process of executing the function.
The newly defined function sayhello is executed by calling sayhello()
with an empty argument list.
gap> sayhello(); hello, world.
However, this is not a typical example as no value is returned but only a string is printed.
In the following example we define a function sign which determines
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
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) for n ≥ 3.
Since functions in GAP may call themselves,
a function fib that computes Fibonacci numbers can be implemented
basically by typing the above equations. (Note however that this is a very
inefficient way to compute f(n).)
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 inserting the necessary tests into 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.
gap> c:= 7;; gap> gcd(30, 63); 3 gap> c; 7
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 have already seen recursion in the function fib
in Section If Statements.
Here is another, slightly more complicated example.
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. Note that there is just one partition of 0, namely [ ]. 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 or equal to 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 indeed takes 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 was
to 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.
Note that the formal parameters 'n' and 'm' of 'np' are treated like local variables.
(Regardless of the recursive structure of an algorithm it is often cheaper (in terms of computing time) to avoid a recursive implementation if possible (and it is possible in this case), because a function call is not very cheap.)
The function syntax is described in Section Functions. The if
statement is described in more detail in Section If. More about
Fibonacci numbers is found in Section Fibonacci and more about
partitions in Section Partitions.
[Top] [Up] [Previous] [Next] [Index]
GAP 4 manual
March 2006