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 (Reference: Print).
gap> Print(sayhello, "\n"); function ( ) Print( "hello, world.\n" ); return; end
Note the additional newline character "\n" in the Print (Reference: 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 an integer.
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 4.2. 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 Reference: Functions. The if statement is described in more detail in Section Reference: If. More about Fibonacci numbers is found in Section Fibonacci (Reference: Fibonacci) and more about partitions in Section Partitions (Reference: Partitions).
generated by GAPDoc2HTML