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).
  

Hide discussion

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

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 unit.

• 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 ith 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 ith item in s by x.