%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%
%W  function.tex              GAP documentation             Thomas Breuer
%W                                                         & Frank Celler
%W                                                     & Martin Schoenert
%W                                                       & Heiko Theissen
%%
%H  @(#)$Id: function.tex,v 4.13 2001/10/06 18:32:31 gap Exp $
%%
%Y  Copyright 1997,  Lehrstuhl D fuer Mathematik,  RWTH Aachen,   Germany
%%
%%  This file contains a tutorial introduction to functions.
%%


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Chapter{Functions}

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.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Writing Functions}

Writing a function that prints `hello, world.'  on the screen is a simple
exercise in {\GAP}.

\beginexample
gap> sayhello:= function()
> Print("hello, world.\n");
> end;
function(  ) ... end
\endexample

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.

\)\fmark 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'.

\beginexample
gap> Print(sayhello, "\n");
function (  )
    Print( "hello, world.\n" );
    return;
end
\endexample

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.

\beginexample
gap> sayhello();
hello, world.
\endexample

However, this is not a typical example as no  value is returned but only a
string is printed.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{If Statements}

In the following example we define a function `sign' which determines
the sign of a number.

\beginexample
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
\endexample

This example also introduces the `if' statement which is  used to execute
statements  depending  on  a  condition.   The  `if'  statement  has  the
following syntax.

\fmark`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 \geq 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)$.)

\beginexample
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
\endexample

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.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Local Variables}

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.

\beginexample
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
\endexample

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.

\beginexample
gap> c:= 7;;
gap> gcd(30, 63);
3
gap> c;
7
\endexample

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.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Recursion}

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.

\beginexample
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
\endexample

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.)

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Further Information about Functions}

The function  syntax is described  in Section "ref:Functions".   The `if'
statement is described  in more detail in  Section "ref:If".  More  about
Fibonacci  numbers is found  in  Section "ref:Fibonacci"  and more  about
partitions in Section "ref:Partitions".

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%
%E  function.tex. . . . . . . . . . . . . . . . . . . . . . . . ends here