# 4.1 Functions

A **function** is a process that, when given an input of a specified type, yields a **unique** output. This is a key idea in providing a precise, mathematical, description of processes in computing.

To describe a particular function, we first give the set from which the input will be drawn and the set from which the output is drawn. This information is called the **signature** of the function. An example will make this clearer. Example 1(b), on the previous screen, requires an input that is a string, that is, a sequence of characters. The set containing all possible sequences of characters is *SeqOfChar*. Example 1(b) produces an output that is a character, so this output is in the set *Char*. We write the signature of this function as *SeqOfChar* → *Char*. The set to the left of the arrow is called the **input set** of the function and the set to the right is called the **output set**. Some texts use **source set** rather than input set, and **target set** rather than output set. It is usual to include an identifier for the function itself in the signature. Suppose we call this function *FIRSTCAP*. Then its full signature is:

FIRSTCAP:SeqOfChar→Char.

*SeqOfChar* comprises all sequences of characters, and so includes some sequences that have no upper-case letters.

The second piece of information required in describing a function is any restriction on the input(s). The informal description of *FIRSTCAP* states only that the first upper-case letter is returned. It does not specify what happens if there is no upper-case letter in the input. Accordingly, a sensible condition on the set of inputs to *FIRSTCAP* is that the input sequence must contain at least one upper-case letter. This condition on the input value is called the **precondition** of the function *FIRSTCAP*.

The third and final piece of information required is the relationship between output and input values. This relationship is referred to as the **semantics** of the function. The semantics must ensure that there is a unique output for any given input. We can describe the function *FIRSTCAP* like this:

FIRSTCAPhas signatureSeqOfChar→Char; its input sequence must contain at least one upper-case letter, and it returns the first upper-case letter appearing in the input sequence.

However, it is not always easy to extract key pieces of information from such a description. We shall usually describe functions using a standard layout, as in the description of *FIRSTCAP* given below. In exercises, to signal that we want the description of a function to be laid out as below, we will ask for a **full description** of the function.

**function** *FIRSTCAP*(*s* **in** *SeqOfChar*) **return in** *Char*

**pre** *s* contains at least one upper-case letter.

**post** The returned value is the first upper-case letter appearing in s.

The signature of the function *FIRSTCAP* is implicit in the first line of this description. (The signature is *FIRSTCAP* : *SeqOfChar* → *Char*.) This line shows that the function has an input (with identifier *s*) that comes from *SeqOfChar*. So its input set is *SeqOfChar*. The function returns a value in *Char*. So its output set is *Char*. We refer to the first line in the full description as the **signature line**.

The input value *s* must satisfy the condition given in the line starting **pre**. This line gives the precondition of the function. The semantics of the function are given in the line starting **post**. The statement in this line is referred to as the **postcondition** of the function.

Here, “pre” and “post” are used in the sense of “before” and “after”. Before *FIRSTCAP* can be applied to a value, that value must satisfy the precondition. After *FIRSTCAP* has been applied, the returned value will satisfy the postcondition.

Sometimes, we want to refer to the set of input values for which a function is defined. This is called the **domain** of the function, and is the set of values in the input set that satisfy the precondition of the function.

A function that is defined for all elements in its input set is called a **total function**. For a total function, no precondition is required on the input value (beyond requiring that it is in the input set). We show this by writing **pre true** (since the precondition is automatically true).

As another example, consider the process 4.1(d) given earlier. It stated:

given some integer,

x, say, return the integerx^{2}+x.

A full description of this function is given below. We will give it the identifier *FORMULA*. The rule for producing an output works for any integer, so we can write **true** for the precondition.

**function** *FORMULA*(*x* **in** *Int*) **return in** *Int*

**pre** ** true**.

**post** The returned value is *x* ^{2} + *x*.

## Activity 14

(a) Call the function associated with Example 1(c) on the previous screen,

*FIRSTCHAR*. Give the signature of this function. Write out a full description of it.(b) Suggest a full description of a function

*SUMSEQ*, associated with the Example 1(a).

### Discussion

Suitable descriptions are given below.

(a) *FIRSTCHAR* inputs a string (sequence of characters), and returns a character. So its signature is *FIRSTCHAR : SeqOfChar* → *Char*. To have a “first character”, the input sequence needs to contain at least one character, so the function needs a corresponding precondition.

**function** *FIRSTCHAR*(s **in** *SeqOfChar*) **return in** Char

**pre** *s* contains at least one character.

**post** The returned value is the first character appearing in *s*.

The choice of identifier for the input is arbitrary. You may well have used some identifier other than s in your answer.

(b) Note that *SUMSEQ* inputs a sequence of integers, and returns an integer. A suitable description is given below.

**function** *SUMSEQ*(*s* **in** *SeqOfInt*) **return in** *Int*

**pre true**.

**post** The returned value is the total of the numbers appearing in *s*. If *s* contains no members, then the returned value is 0.

You might have chosen to say that the input sequence should not be empty, since the idea of “the total of the numbers” might seem unclear if there are no numbers to add up! That would be fine. We have chosen to regard the “total of no numbers” as 0, and have said so explicitly in the semantics. Sometimes, one needs to make more precise an informal idea of a process. Deciding whether to add a precondition, or to explain what happens in special cases, is the sort of clarification that may be needed.

The value obtained when some function *F* is applied to an input *x* is written *F*(*x*). So, for example, *FIRSTCAP*(“a1wQ2*”) means the result of applying the function *FIRSTCAP* to the string “a1wQ2*”. The value obtained in that case is the first upper-case letter in “a1wQ2*”, and so is ‘Q’.

The example process 1(f), given earlier, was:

Given a string and a character, return the position in the string where the character first occurs.

For example, if the string “This is a sentence.” and the character ‘s’ are given, then the value returned is 4. This function requires two inputs: a string (a sequence of characters), and a character. We can describe the function as below.

**function** *FIRSTAT*(*c* **in** *Char*,*t* **in** *SeqOfChar*) **return in** *Int*

**pre** The character *c* appears at least once in the sequence *t*.

**post** The returned value is the integer *n* satisfying the condition that the *n*th character in the sequence *t* is *c*, and this is the first occurrence of *c* in *t*.

Where a function requires more than one input, the input set is taken to be a Cartesian product of sets, one for each input. For this example, the input set is *Char × SeqOfChar*. The output set is *Int*, so the signature of the function is *FIRSTAT* : *Char × SeqOfChar* → *Int*.

We can, for example, apply this function in the form

*FIRSTAT*(‘s’, “This is a sentence.”). However, we cannot apply it in the form *FIRSTAT*(“This is a sentence.”, ‘s’). The order of the two inputs given in the signature line in the description of *FIRSTAT* must be adhered to.

(We could have described a function accepting the inputs in a different order, with the sequence first and the character second. But this would be another function, different from *FIRSTAT*, just as reversing the order in which two sets are written in a Cartesian product produces a different set.)

Look now at Example 1(e), repeated below.

Given a sequence of items from a set *X*, and another item from the set *X*, return the sequence formed by placing the item at the end of the sequence. For example, given the sequence of integers [6,2,5,6] and the integer 1, the value returned is [6,2,5,6,1].

Note that this description is not confined to sequences of numbers. It can be used for sequences with members from any set. This general set is represented here by *X*. We can describe a function *ADDLAST* corresponding to this process as below.

**function** *ADDLAST*(*x* **in** *X* , *s* **in** *SeqOfX* ) **return in** *SeqOfX*

**pre true**.

**post** The returned value is formed by placing the item *x* at the end of the sequence *s*. For example, *ADDLAST*(1,[6, 2, 5, 6]) = [6, 2, 5, 6, 1].

## Activity 15

(a) Give the signature of the function ADDLAST.

(b) What are the values:

(i) ADDLAST(7,[1, 4, 3, 2]);

(ii)

*ADDLAST*(‘y’,“qwert”);(iii)

*ADDLAST*(“qwert”,‘y’)?

### Discussion

(a) The signature is

*ADDLAST : X × SeqOfX*→*SeqOfX*. (The order of the sets in the Cartesian product corresponds to the order of the inputs given in the description above.)(b) We have:

(i)

*ADDLAST*(7, [1, 4, 3, 2]) = [1, 4, 3, 2, 7];(ii)

*ADDLAST*(‘y’, “qwert”) = “qwerty”;(iii)

*ADDLAST*(“qwert”,‘y’) cannot be formed. The inputs are given in the wrong order.

## Activity 16

This activity concerns the three functions on sequences given below. In each case, the sequence members come from an arbitrary set, *X*. You will meet these functions again later in the course.

A function

*SIZE*, which, given a sequence, returns the number of members in it (that is, it returns the length of the sequence). So, for example,*SIZE*([1, 11, −32, 4, 12, 1]) = 6.A function

*AT*, which returns the item that is at a specified position in a sequence. So, for example,*AT*(4, “author”) = ‘h’.A function

*PUT*, which replaces the item that is at a specified position in a sequence with an item supplied as an input. So, for example,*PUT*(4,“author”,‘q’) = “autqor”.

(a) Give the values of:

(i)

*SIZE*(“author”);(ii)

*AT*(3,[1, 11*, -*32, 4]);(iii)

*PUT*(3,“paan”,‘i’);(iv)

*PUT*(2, [1, 8, 2, 4], 3).

(b) Give the signature of each of the three functions.

(c) Give full descriptions of each of the three functions.

### Discussion

(a) (i) 6 (the number of characters in the string “author”).

(ii) −32 (the third item in the sequence [1, 11, −32, 4]).

(iii) We replace the character at the third place in the string “paan” by the input character ‘i’, to get “pain”.

(iv) The first number gives the position of the item to be changed and the final number is the replacement item. So the value is [1, 3, 2, 4].

(b) *SIZE* has one input, from *SeqOfX* , and returns a value in *Int*. The signature is *SIZE : SeqOfX* → *Int*.

The function *AT* inputs an integer and a sequence and returns a value from *X*, so the signature is *AT : Int × SeqOfX* → *X*.

For the function *PUT*, the input set is a Cartesian product of three sets, one for each of the three inputs.

The signature is PUT : Int × SeqOfX × X → SeqOfX .

(c) Suitable descriptions are given below.

For *SIZE*, recall that the number of elements in the empty sequence is 0, so this is a total function.

**function** *SIZE*(*s* **in** *SeqOfX* ) **return in** *Int*

**pre** **true**.

**post** The returned value is the number of items in the sequence *s*. If *s* contains no members then the returned value is 0.

For *AT*, the semantics only make sense if the integer input gives a position actually in the sequence. So we give a precondition that the input integer is at least 1 (when the first item in the sequence will be returned), and that the input integer is not bigger than the number of items in the sequence. If we use another function in a description, as we use *SIZE* here in describing *AT*, then we must describe that function too. *SIZE* was described above.

**function** *AT*(*i* **in** *Int*, *s* **in** *SeqOfX* ) **return in** *X*

**pre** 1≤ *i* and *i*≤ *SIZE*(*s*).

**post** The returned value is the *i*th item in the sequence *s*.

The function *PUT* has three inputs, an integer (giving the position of the item to be changed), the sequence to be modified, and the replacement item (from the set *X*). It requires the same precondition as *AT*.

**function** *PUT*(*i* **in** *Int*, *s* **in** *SeqOfX* , *x* **in** *X* ) **return in** *SeqOfX*

**pre** 1 ≤ *i* and *i* ≤ *SIZE*(*s*).

**post** The returned value is the sequence formed by replacing the *i*th item in *s* by *x*.