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:

FIRSTCAP has signature SeqOfChar → 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 integer x ² + 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 ² + 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).

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 nth 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’)?

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.