%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% %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