<html><head><title>[tut] 4 Functions</title></head> <body text="#000000" bgcolor="#ffffff"> [<a href="../index.htm">Top</a>] [<a href = "chapters.htm">Up</a>] [<a href ="CHAP003.htm">Previous</a>] [<a href ="CHAP005.htm">Next</a>] [<a href = "theindex.htm">Index</a>] <h1>4 Functions</h1><p> <P> <H3>Sections</H3> <oL> <li> <A HREF="CHAP004.htm#SECT001">Writing Functions</a> <li> <A HREF="CHAP004.htm#SECT002">If Statements</a> <li> <A HREF="CHAP004.htm#SECT003">Local Variables</a> <li> <A HREF="CHAP004.htm#SECT004">Recursion</a> <li> <A HREF="CHAP004.htm#SECT005">Further Information about Functions</a> </ol><p> <p> You have already seen how to use functions in the <font face="Gill Sans,Helvetica,Arial">GAP</font> library, i.e., how to apply them to arguments. <p> In this section you will see how to write functions in the <font face="Gill Sans,Helvetica,Arial">GAP</font> language. You will also see how to use the <code>if</code> statement and declare local variables with the <code>local</code> statement in the function definition. Loop constructions via <code>while</code> and <code>for</code> are discussed further, as are recursive functions. <p> <p> <h2><a name="SECT001">4.1 Writing Functions</a></h2> <p><p> Writing a function that prints <code>hello, world.</code> on the screen is a simple exercise in <font face="Gill Sans,Helvetica,Arial">GAP</font>. <p> <pre> gap> sayhello:= function() > Print("hello, world.\n"); > end; function( ) ... end </pre> <p> This function when called will only execute the <code>Print</code> statement in the second line. This will print the string <code>hello, world.</code> on the screen followed by a newline character <code>\n</code> that causes the <font face="Gill Sans,Helvetica,Arial">GAP</font> prompt to appear on the next line rather than immediately following the printed characters. <p> The function definition has the following syntax. <p> <code> function( </code><var>arguments</var><code> ) </code><var>statements</var><code> end</code> <p> A function definition starts with the keyword <code>function</code> followed by the formal parameter list <var>arguments</var> 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 <strong>no</strong> semicolon behind the closing parenthesis. The function definition is terminated by the keyword <code>end</code>. <p> A <font face="Gill Sans,Helvetica,Arial">GAP</font> 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 <code>sayhello</code>. Unlike in the case of integers, sums, and lists the value of the function <code>sayhello</code> is echoed in the abbreviated fashion <code>function ( ) ... end</code>. This shows the most interesting part of a function: its formal parameter list (which is empty in this example). The complete value of <code>sayhello</code> is returned if you use the function <code>Print</code>. <p> <pre> gap> Print(sayhello, "\n"); function ( ) Print( "hello, world.\n" ); return; end </pre> <p> Note the additional newline character <code>"\n"</code> in the <code>Print</code> statement. It is printed after the object <code>sayhello</code> to start a new line. The extra <code>return</code> statement is inserted by <font face="Gill Sans,Helvetica,Arial">GAP</font> to simplify the process of executing the function. <p> The newly defined function <code>sayhello</code> is executed by calling <code>sayhello()</code> with an empty argument list. <p> <pre> gap> sayhello(); hello, world. </pre> <p> However, this is not a typical example as no value is returned but only a string is printed. <p> <p> <h2><a name="SECT002">4.2 If Statements</a></h2> <p><p> In the following example we define a function <code>sign</code> which determines the sign of a number. <p> <pre> 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 </pre> <p> This example also introduces the <code>if</code> statement which is used to execute statements depending on a condition. The <code>if</code> statement has the following syntax. <p> <code>if </code><var>condition</var><code> then </code><var>statements</var><code> elif </code><var>condition</var><code> then </code><var>statements</var><code> else </code><var>statements</var><code> fi</code> <p> There may be several <code>elif</code> parts. The <code>elif</code> part as well as the <code>else</code> part of the <code>if</code> statement may be omitted. An <code>if</code> statement is no expression and can therefore not be assigned to a variable. Furthermore an <code>if</code> statement does not return a value. <p> Fibonacci numbers are defined recursively by <i>f</i>(1) = <i>f</i>(2) = 1 and <i>f</i>(<i>n</i>) = <i>f</i>(<i>n</i>−1) + <i>f</i>(<i>n</i>−2) for <i>n</i> ≥ 3. Since functions in <font face="Gill Sans,Helvetica,Arial">GAP</font> may call themselves, a function <code>fib</code> that computes Fibonacci numbers can be implemented basically by typing the above equations. (Note however that this is a very inefficient way to compute <i>f</i>(<i>n</i>).) <p> <pre> 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 </pre> <p> There should be additional tests for the argument <code>n</code> being a positive integer. This function <code>fib</code> might lead to strange results if called with other arguments. Try inserting the necessary tests into this example. <p> <p> <h2><a name="SECT003">4.3 Local Variables</a></h2> <p><p> A function <code>gcd</code> that computes the greatest common divisor of two integers by Euclid's algorithm will need a variable in addition to the formal arguments. <p> <pre> 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 </pre> <p> The additional variable <code>c</code> is declared as a <strong>local</strong> variable in the <code>local</code> statement of the function definition. The <code>local</code> statement, if present, must be the first statement of a function definition. When several local variables are declared in only one <code>local</code> statement they are separated by commas. <p> The variable <code>c</code> is indeed a local variable, that is local to the function <code>gcd</code>. If you try to use the value of <code>c</code> in the main loop you will see that <code>c</code> has no assigned value unless you have already assigned a value to the variable <code>c</code> in the main loop. In this case the local nature of <code>c</code> in the function <code>gcd</code> prevents the value of the <code>c</code> in the main loop from being overwritten. <p> <pre> gap> c:= 7;; gap> gcd(30, 63); 3 gap> c; 7 </pre> <p> We say that in a given scope an identifier identifies a unique variable. A <strong>scope</strong> 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 <code>function</code> keyword, denoting the beginning of a function definition, to the corresponding <code>end</code> 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. <p> <p> <h2><a name="SECT004">4.4 Recursion</a></h2> <p><p> We have already seen recursion in the function <code>fib</code> in Section <a href="CHAP004.htm#SECT002">If Statements</a>. Here is another, slightly more complicated example. <p> 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 <i>n</i> may be divided into subsets with respect to the largest element. The number of partitions of <i>n</i> therefore equals the sum of the numbers of partitions of <i>n</i>−<i>i</i> with elements less than or equal to <i>i</i> for all possible <i>i</i>. More generally the number of partitions of <i>n</i> with elements less than <i>m</i> is the sum of the numbers of partitions of <i>n</i>−<i>i</i> with elements less than <i>i</i> for <i>i</i> less than <i>m</i> and <i>n</i>. This description yields the following function. <p> <pre> 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 </pre> <p> 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 <code>nrparts</code> that can be used to compute the number of partitions indeed takes only one argument. The function <code>np</code> takes two arguments and solves the problem in the indicated way. The only task of the function <code>nrparts</code> is to call <code>np</code> with two equal arguments. <p> We made <code>np</code> local to <code>nrparts</code>. This illustrates the possibility of having local functions in <font face="Gill Sans,Helvetica,Arial">GAP</font>. It is however not necessary to put it there. <code>np</code> could as well be defined on the main level, but then the identifier <code>np</code> would be bound and could not be used for other purposes, and if it were used the essential function <code>np</code> would no longer be available for <code>nrparts</code>. <p> Now have a look at the function <code>np</code>. It has two local variables <code>res</code> and <code>i</code>. The variable <code>res</code> is used to collect the sum and <code>i</code> is a loop variable. In the loop the function <code>np</code> calls itself again with other arguments. It would be very disturbing if this call of <code>np</code> was to use the same <code>i</code> and <code>res</code> as the calling <code>np</code>. Since the new call of <code>np</code> creates a new scope with new variables this is fortunately not the case. <p> Note that the formal parameters 'n' and 'm' of 'np' are treated like local variables. <p> (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.) <p> <p> <h2><a name="SECT005">4.5 Further Information about Functions</a></h2> <p><p> The function syntax is described in Section <a href="../ref/CHAP005.htm">Functions</a>. The <code>if</code> statement is described in more detail in Section <a href="../ref/CHAP004.htm#SECT016">If</a>. More about Fibonacci numbers is found in Section <a href="../ref/CHAP017.htm#SSEC003.1">Fibonacci</a> and more about partitions in Section <a href="../ref/CHAP017.htm#SSEC002.15">Partitions</a>. <p> <p> [<a href="../index.htm">Top</a>] [<a href = "chapters.htm">Up</a>] [<a href ="CHAP003.htm">Previous</a>] [<a href ="CHAP005.htm">Next</a>] [<a href = "theindex.htm">Index</a>] <P> <font face="Gill Sans,Helvetica,Arial">GAP 4 manual<br>December 2008 </font></body></html>