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