1.17 About Writing Functions

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.

Previous Up Top Next
Index

GAP 3.4.4
April 1997