# 2.18 Functions

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

```)
```
[ `local `loc-ident {`, `loc-ident} `;` ]
`    `
statements
`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 )
>             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.

GAP 3.4.4
April 1997