## Functions and Program Structure

Functions are a very important structuring device in programming.

They directly support the idea of abstraction, and are used to control complexity.

Without functions, large programs would be very difficult to understand and almost impossible to maintain.

A very simple view of a function: "a named block of C code".

As we shall see this week, they provide more than just a way to name code.

You must understand functions before you can read/write significant C programs.

## Functions

The definitions of mathematical functions give:

• the name of the function
• the types of the arguments and the result
• how the result is computed from the arguments

Example:

`    factorial :: Int -> Int`
`    factorial(n) = 1 2 ... n`

A function's type definition  (e.g. `Int->Int`)  is called its signature.

#### ... Functions

More examples of mathematical functions:

`    square :: Int -> Int`
`    square(n) = n n`
` `
`    max :: (Int, Int) -> Int`
`    max(x,y) = x, if x > y`
`             = y, otherwise`
` `
`    sum :: [Int] -> Int`
`    sum(v) = v1 + v2 + ... + vn`
`             where n = length(v)`
` `
`    mean :: [Int] -> Float`
`    mean(v) = sum(v) / length(v)`
` `
`    stats :: [Int] -> (Float, Float)`
`    stats(v) = (mean(v), stddev(v))`

#### ... Functions

You use mathematical functions by applying them to arguments.

E.g.

`    square(3) 9`
`    square(8) 64`
` `
`    max(2,3) 3`
`    max(3,2) 3`
`    max(2,1+1) 2`
` `
`    sum([1,2,3]) 6`
`    sum([1..10]) 55`

Arguments to functions are constant values (possibly expressions).

The result of function application is a single (possibly structured) value.

## C Functions

C functions are a generalisation of mathematical functions:

• they are not required to have any result type
• their arguments can be references to variables, as well as values

A C function definition requires:

• the name of the function
• the types/names of arguments and the (optional) result type
• how the result is computed from the arguments (as a C block)

The function definition may contain additional temporary/local variables.

#### ... C Functions

Examples of mathematical functions and their C counterparts:

`   square :: Int -> Int         int square(int x) {`
`   square(x) = x * x                return (x*x);`
`                                }`
` `
` `
`   max :: (Int,Int) -> Int      int max(int x, int y) {`
`   max(x,y) = x, if x > y           if (x > y)`
`              y, otherwise              return x;`
`                                    else `
`                                        return y;`
`                                }`

#### ... C Functions

More examples of mathematical functions and their C counterparts:

`   sum :: [Int] -> Int          int sum(int v[], int n) {`
`   sum(v) = v1+v2+...+vn            int i, total=0;`
`                                    for (i = 0; i < n; i++)`
`                                        total = total + v[i];`
`                                    return total;`
`                                }`
` `
` `
`   mean :: [Int] -> Int         int mean(int v[], int n) {`
`   mean(v) = sum(v)/length(v)       return sum(v,n) / n;`
`                                }`

## C vs Math Functions #### ... C vs Math Functions

As noted above, C functions are not required to return a value.

Such functions are marked with a special "return type" `void`.

Example:

`    void doSomething(int a, int b, float c) { ... }`

`void` can also be used to indicate that a function has no arguments
but this is usually done by simply writing empty parentheses after the function name, e.g.

`    int random() {...}    int random(void) {...}`

## Function Prototypes

You can supply function signatures using function prototypes.

Examples:

`    square :: Int -> Int        int square(int);`
`    max :: (Int,Int) -> Int     int max(int, int);`
`    sum :: [Int] -> Int         int sum(int[], int);`
`    mean :: [Int] -> Float      float mean(int[], int);`

Prototypes are typically found in C header files (e.g. `myfunctions.h`).

#### ... Function Prototypes

Prototypes are also useful to provide type information for functions:

• that are used near the top of the `prog.c` file
• but not defined until later on in the `prog.c` file

If a C function is used without being first defined, the C compiler assumes:

`    int function(int, int, int, ...);`

This may not always be what you intended always ensure that functions are defined (at least via a signature) before they are used.

## Using C Functions

C functions are used by applying them in C expressions

`    int a=20, b=4, x;`
`    ...`
`    x = square(b) + square(2);`
`    ...`
`    printf("%d %d\n", square(x), max(a,x));`

Since C statements are also valid expressions, it is possible to write:

`    int a,b;`
`    ...`
`    square(a);`
`    max(a,b);`

In this case, the functions are called and do all of their work, and then the result is simply thrown away.

## Function Calls

To call a function:

`   funcname ( arg1, arg2, ... )`

The arguments in the definition are formal parameters, e.g.

`    int f(int a, int b, int c) {...}`

The arguments supplied to the call are actual parameters, e.g.

`    z = f(x, 5, 3+y*2)`

#### ... Function Calls

The call to a function must ``match'' its definition:

• the same number of parameters
• in the same order
• of the same type (or a convertible type)

The C compiler complains about mis-matches, e.g.

`    int f(int, char, float);`
`    ...`
`    int a,b;  float d,e;  char f;`
`    ...`
`    e = fun(a, b, f, d);  `
`    e = fun(f, d, b);     `

Note: the actual paramaters do not need to have the same name as the formal parameters.

#### ... Function Calls

The effect of a function call is:

• the actual parameters are evaluated
• the value of each is assigned to the corresponding formal parameter
• the function code starts executing with parameters set to the values ## Function Return Values

Functions terminate and return a result whenever `return` is executed.

Not having a `return` in a non-`void` function is an error.

Function return values are typically used in expressions.

But C doesn't care if you ignore the value returned by a function.

E.g.

`    sqrt(2.0);`
`    scanf("%d%d%d", &a, &b, &c);`

which strictly ought to be

`    x = sqrt(2.0) + 3.0;`
`    n = scanf("%d%d%d", &a, &b, &c);`

## Example max() function (v.1)

A function to determine the larger of two integers.

Mathematical version:

`    max :: (Int,Int) -> Int`
`    max(x,y) = x, if x > y`
`             = y, otherwise`

C version:

`    int max(int x, int y)`
`    {`
`        if (x > y)`
`            return x;`
`        else`
`            return y;`
`    }`

#### ... Example max() function (v.1)

A program to use it:

`    #include <stdio.h>`
` `
`    main()`
`    {`
`        int a, b;`
`        int max(int,int); `
` `
`        printf("Enter two numbers: ");`
`        scanf("%d%d", &a, &b);`
`        printf("The larger is %d\n", max(a,b));`
`        return 0;`
`    }`

## Example max() function (v.2)

A function to determine the larger of two integers.

`    int max(int x, int y)`
`    {`
`        int bigger;  `
` `
`        if (x > y)`
`               bigger = x;`
`        else`
`               bigger = y;`
`        return bigger;`
`    }`

The variable `bigger` only exists while `max` is computing.

Most functions use local variables to store intermediate results.

## Example max() function (v.3)

A function to determine the larger of two integers.

`    int max(int x, int y)`
`    {`
`        return (x > y) ? x : y;`
`    }`

This uses a C conditional expression and is probably closest to the mathematical version.

All versions of the function are used in exactly the same way e.g. `max(2,3)`.

## Example factorial() function (v.1)

Consider the mathematical function to compute factorials:

`    factorial :: Int -> Int`
`    factorial(n) = 1 2 ... n`

And its equivalent in C:

`    int factorial(int n)`
`    {`
`        int i, product;`
`        product = 1;`
`        for (i = 1; i <= n; i++)`
`            product = product * i;`
`        return product;`
`    }`

#### ... Example factorial() function (v.1)

A program to use it:

`    #include <stdio.h>`
` `
`    main()`
`    {`
`        int a;`
`        int factorial(int); `
` `
`        printf("Enter a positive number: ");`
`        scanf("%d", &a);`
`        printf("%d! = %d\n", a, factorial(a));`
`        return 0;`
`    }`

## Example factorial() function (v.2)

In mathematics, factorial is often defined recursively:

`    factorial :: Int -> Int`
`    factorial(n) = 1,                  if n < 2`
`                 = n * factorial(n-1), otherwise`

(This kind of definition is related to mathematical induction (basis,step))

C also allows functions to be defined recurisvely:

`    int factorial(int n)`
`    {`
`        if (n < 2)`
`            return 1;`
`        else`
`            return n * factorial(n-1);`
`    }`

#### ... Example factorial() function (v.2)

Execution of `factorial(3)` results in the following sequence of calls:

`    call factorial(3)`
`        evaluate 3 * factorial(3-1)`
`            call factorial(2)`
`                evaluate 2 * factorial(2-1)`
`                    call factorial(1)`
`                    returns 1`
`                finish evaluating 2 * 1`
`            returns 2`
`        finish evaluating 3 * 2`
`    returns 6`

How do these different calls to `factorial()` co-exist?

Each call to `factorial()` creates a new instance of a factorial computation, with its own copy of `n`.

## Scope and Lifetime of Variables

In C, every memory object (variable or parameter) has:

• scope   (a region of program in which it is accessible)
• lifetime   (a period, during program execution, when it exists)

Note: once inside an executing function, parameters can be treated as initialised local variables (initialised with the value of the actual parameter).

#### ... Scope and Lifetime of Variables

Scopes:

• local to a function
• local to a module (`x.c` file)
• global   (accessible everywhere)

• longer than program execution   (files)
• exactly program execution   (static)
• during function execution   (local)
• created/destroyed by programmer   (dynamic)

`int a, b;  `
` `
`main()`
`{`
`        int u, v;   ...`
`}`
` `
`int c, d;  `
` `
`void f(int p, int q)`
`{`
`        int w;   ...`
`}`
` `
`int g(int r)`
`{`
`        int x; `
`        static int e;  ...`
`}`

## C Memory Model ## Exercises

1. Package up the `gcd` algorithm from week 4 labs as a function.
2. Implement a function `int sum(int v[])`, to sum the elements of a list, where the end of the list is marked by a `v[i]` containing a negative value.
3. Implement a recursive function ```int sum(int v[], int n)```, to sum the elements of a list, where `n` is the length of the list

Produced: 26 Mar 2000