chap4.txt

  
  4 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.
  
  
  4.1 Writing Functions
  
  Writing  a  function  that  prints  hello,  world. on the screen is a simple
  exercise in GAP.
  
    Example  
    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).
  
    Example  
    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.
  
    Example  
    gap> sayhello();
    hello, world.
  
  
  However,  this  is  not a typical example as no value is returned but only a
  string is printed.
  
  
  4.2 If Statements
  
  In the following example we define a function sign which determines the sign
  of an integer.
  
    Example  
    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).)
  
    Example  
    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.
  
  
  4.3 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.
  
    Example  
    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.
  
    Example  
    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.
  
  
  4.4 Recursion
  
  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.
  
    Example  
    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.)
  
  
  4.5 Further Information about Functions
  
  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).