2.18 Functions

function ( [ arg-ident {, arg-ident} ]

)
    

end

A function is in fact a literal and not a statement. Such a function literal can be assigned to a variable or to a list element or a record Function Calls.

The following is an example of a function definition. It is a function to compute values of the Fibonacci sequence (see Fibonacci)

    gap> fib := function ( n )
    >         local  f1,  f2,  f3,  i;
    >         f1 := 1;  f2 := 1;
    >         for i  in [3..n]  do
    >             f3 := f1 + f2;
    >             f1 := f2;
    >             f2 := f3;
    >         od;
    >         return f2;
    >     end;;
    gap> List( [1..10], fib );
    [ 1, 1, 2, 3, 5, 8, 13, 21, 34, 55 ] 

Because for each of the formal arguments arg-ident and for each of the formal locals loc-ident a new variable is allocated when the function is called (see Function Calls), it is possible that a function calls itself. This is usually called recursion. The following is a recursive function that computes values of the Fibonacci sequence

    gap> fib := function ( n )
    >         if n < 3  then
    >             return 1;
    >         else
    >             return fib(n-1) + fib(n-2);
    >         fi;
    >     end;;
    gap> List( [1..10], fib );
    [ 1, 1, 2, 3, 5, 8, 13, 21, 34, 55 ] 

Note that the recursive version needs 2 * fib(n)-1 steps to compute fib(n), while the iterative version of fib needs only n-2 steps. Both are not optimal however, the library function Fibonacci only needs on the order of Log(n) steps.

arg-ident - expr

This is a shorthand for
function ( arg-ident ) return expr; end.
arg-ident must be a single identifier, i.e., it is not possible to write functions of several arguments this way. Also arg is not treated specially, so it is also impossible to write functions that take a variable number of arguments this way.

The following is an example of a typical use of such a function

    gap> Sum( List( [1..100], x -> x^2 ) );
    338350 

When a function fun1 definition is evaluated inside another function fun2, GAP binds all the identifiers inside the function fun1 that are identifiers of an argument or a local of fun2 to the corresponding variable. This set of bindings is called the environment of the function fun1. When fun1 is called, its body is executed in this environment. The following implementation of a simple stack uses this. Values can be pushed onto the stack and then later be popped off again. The interesting thing here is that the functions push and pop in the record returned by Stack access the local variable stack of Stack. When Stack is called a new variable for the identifier stack is created. When the function definitions of push and pop are then evaluated (as part of the return statement) each reference to stack is bound to this new variable. Note also that the two stacks A and B do not interfere, because each call of Stack creates a new variable for stack.

    gap> Stack := function ()
    >         local   stack;
    >         stack := [];
    >         return rec(
    >             push := function ( value )
    >                 Add( stack, value );
    >             end,
    >             pop := function ()
    >                 local   value;
    >                 value := stack[Length(stack)];
    >                 Unbind( stack[Length(stack)] );
    >                 return value;
    >             end
    >         );
    >    end;;
    gap> A := Stack();;
    gap> B := Stack();;
    gap> A.push( 1 );  A.push( 2 );  A.push( 3 );
    gap> B.push( 4 );  B.push( 5 );  B.push( 6 );
    gap> A.pop();  A.pop();  A.pop();
    3
    2
    1
    gap> B.pop();  B.pop();  B.pop();
    6
    5
    4 

This feature should be used rarely, since its implementation in GAP is not very efficient.

Previous Up Top Next
Index