4 Processes
Processes that can be applied to data
Having looked at some forms of data, we now turn our attention to processes that can be applied to data. Each process that we consider in this section will input data of a specified form, and will result in a corresponding value. For example, one process, which we will call ASC, takes a character as input, and has as its resulting value the integer giving the ASCII code of the input character (as listed in Table 2). Another process, which we will call SIZE, takes a sequence as input, and has as its resulting value the length of the sequence (which will be an integer).It is important to distinguish between a description of the outcome required when a process is applied to a form of data, and a description of the exact steps to be taken to achieve the desired outcome. Here, we are concerned only with the first of these; that is, with providing an overview of a computing process. You might like to think of this as a “black box” view of the process. We do not, at this stage, care how one obtains the output value.
Certain processes change the state of a named variable. For now, though, we shall not think about processes in that way. Each process that we are concerned with here simply produces a value that depends on one (or more) input value(s). Another important feature of the processes that we shall consider is that they result in a value that is entirely predictable. One can envisage a process that takes a string as input, and which results in a value that is a character that appears in the string. With input “This”, the value resulting from such a process might be any of the four characters ‘T’, ‘h’, ‘i’ or ‘s’. We will not consider a process such as that. Our attention will be confined to processes that, if given the same input twice, will produce the same resulting value each time.
Below, we give a number of examples of processes that may be applied to numbers, characters or sequences. Focus first on Example 1(a) below This process is applied to an input, comprising data of a specified form (a sequence of integers). Application of the process results in a value (the sum of the integers in the input sequence). This resulting value will be referred to as the value returned by the process. Similar comments apply to each of these examples. Each process takes data of a specified form as an input, and each process returns a value, based on this input data. The returned value may also be called the output of the process.
Example 1
(a) Given a sequence of integers, return the sum of all the numbers in the sequence. For example, given [6, 2, 5, 6] the value returned is 19.(b) Given a string, return the first upper-case letter that appears in the string. For example, given the string “my name is Bob”, the value returned is ‘B’.
(c) Given a string, return the first character in the string. For example, given the string “This is a sentence.”, the value returned is ‘T’.
(d) Given some integer, x, say, return the integer x 2 + x. For example, given the number 4, the value returned is 42 + 4 = 20.
(e) 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].
(f) Given a string and a character, return the position in the string where the given character first occurs (counting characters from the front of the string). For example, if the string “This is a sentence.” and the character ‘s’ are given, then the value returned is 4, since the first occurrence of ‘s’ in the string is at the fourth place in the sequence [‘T’,‘h’,‘i’,‘s’,‘
’,‘i’,‘s’, . . . ].Here are some key questions to consider about each process.
· How many inputs are required, and of what type?
· What type of value does the process return?
· What is the relationship between the returned value and the input(s)?
· Are there any restrictions on the input(s)?
· Does the process always produce an output? Given any permitted input, is there an associated returned value?
· Is the output produced predictable? Given the same input, will the process always return the same value?
For example, consider Example 1(b) above. In that case the questions can be answered as follows. The process has just one input and this is a sequence of characters. It outputs a character. The output value is the first upper-case letter that appears in the sequence of characters. For this description of the output to yield any value, the input sequence needs to contain at least one upper-case letter. Given that restriction on the input, there will always be an output. The output is predictable.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 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.
End of discussion
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:
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:
End of discussion
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:(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.
End of discussion
4.2 Functions defined through cases
In each of the examples considered so far, the function has had its semantics expressed using a formula or a general rule. Some functions have their semantics expressed simply by listing the output for each possible input. For example, let Days be the set of days of the week, and the function TOMORROW have signature Days → Days, and return the day following the input day. If we represent Days using the strings {“Mon”, “Tues”, “Wed”, “Thurs”, “Fri”, “Sat”, “Sun”}, then we can describe the corresponding representation of the function TOMORROW as below.function TOMORROW1(d in SeqOfChar) return in SeqOfChar
pre d is in the set {“Mon”,“Tues”,“Wed”,“Thurs”,“Fri”,“Sat”,“Sun”}.
post The returned value is t, where:
if d = “Mon” then t = “Tues”
if d = “Tues” then t = “Wed”
if d = “Wed” then t = “Thurs”
if d = “Thurs” then t = “Fri”
if d = “Fri” then t = “Sat”
if d = “Sat” then t = “Sun”
if d = “Sun” then t = “Mon”.
We distinguish the abstraction (the function TOMORROW) from its representation (the function TOMORROW1), because different representations of the set Days will lead to different representations of the function TOMORROW (see, for example, Exercise 2).
Activity 17
Suppose that a particular breakfast cereal is sold in sizes Small, Medium and Large, and that we choose to represent these by the characters ‘S’, ‘M’ and ‘L’. Their respective prices, in pence, are 89 for ‘S’, 119 for ‘M’ and 159 for ‘L’. Describe a function CEREALPRICE that takes a size as input and returns the associated price.Discussion
We can describe this function as follows.function CEREALPRICE(c in Char) return in Int
pre c is in the set {‘S’, ‘M’, ‘L’}.
post The returned value is p, where:
if c = ‘S’ then p = 89
if c = ‘M’ then p = 119
if c = ‘L’ then p = 159.
End of discussion
4.3 Character code functions
Many programming languages provide two functions associated with the character codes (see Table 2). We shall call these functions ASC and CHR. ASC takes a character as input, and returns the integer giving the ASCII code of the input character. CHR returns the character whose ASCII code is the input integer. These functions are described below. We have set a precondition on CHR to conform to our earlier restriction on the set of characters that we will consider in this unit.function ASC(c in Char) return in Int
pre true.
post The returned value is the ASCII code of c, as given in Table 2.
function CHR(n in Int) return in Char
pre 32 ≤ n ≤ 126.
post The returned value is the character with ASCII code n, as given in Table 2.
Activity 18
Find each of:(a) ASC(‘j’);
(b) CHR(43);
(c) ASC(CHR(43));
(d) CHR(ASC(‘j’)).
Discussion
(a) Referring to Table 2, ASC(‘j’) = 106.(b) CHR(43) = ‘+’.
(c) ASC(CHR(43)) means the result of applying the function ASC to CHR(43). So ASC(CHR(43)) = ASC(‘+’) = 43.
(d) CHR(ASC(‘j’)) = CHR(106) = ‘j’.
Looking up the ASCII code of a character, and then looking to see the character corresponding to the number you just found, will always take you back to the character you started with. We can express this in a general equation, as CHR(ASC(c)) = c. (This holds for any character c.)
End of discussion
As illustrated in Activity 18, the two functions ASC and CHR are closely related. Each reverses the effect of the other. We can express this relationship by writing the two equations below (which hold for every c in Char and for every n in Int satisfying the condition 32 ≤ n ≤ 126).ASC(CHR(n)) = n
CHR(ASC(c)) = c
We say that ASC and CHR are inverse functions.
Not every function can be paired up with an inverse function in this way. For example, the function FIRSTCHAR returns the first character in a string. Now different strings may have the same first character. (“This” and “The” both start with ‘T’, but are different strings.) With input ‘T’, a process attempting to reverse the effect of FIRSTCHAR would not know whether to return “This” or “The” (or “To”, or “Tom”, etc). The function FIRSTCHAR has no inverse function.
Activity 19
A simple cipher replaces each lower-case letter with the next one in alphabetical order. So ‘a’ is replaced by ‘b’, ‘b’ by ‘c’,. . . , ‘t’ by ‘u’, and so on. The letter z ‘ ’ is replaced by ‘a’. The function NEXT, specified below, corresponds to this coding.function NEXT(c in Char) return in Char
pre c is a lower-case letter.
post If c lies between ‘a’ and ‘y’ then the returned value is the letter following c in alphabetical order. If c = ‘z’ then the returned value is ‘a’.
Does the function NEXT have an inverse function? If it does, describe this inverse function.
Discussion
We can reverse the effect of NEXT by moving each character back one place in alphabetical order. This time, the special case is ‘a’, which must be moved to ‘z’. So NEXT does have an inverse function. If we call it BEFORE, it can be described as below.function BEFORE(c in Char) return in Char
pre c is a lower-case letter.
post If c lies between ‘b’ and ‘z ’ then the returned value is the letter preceding c in alphabetical order. If c = ‘a’ then the returned value is ‘z’.
End of discussion
4.4 Functions returning true or false
Consider a function, say ISIN , associated with following process.Given a character and a string, determine whether the character appears in the string.
This function has two inputs, a character and a string (sequence of characters), so we can take the input set to be Char × SeqOfChar. But what is the output set? If the character does appear in the string, then the function can return the value true, and if the character does not appear in the string, then the function can return the value false. So a suitable output set is Bool. Then ISIN has signature Char × SeqOfChar → Bool. We can describe the function ISIN as below.
function ISIN (c in Char, s in SeqOfChar) return in Bool
pre true.
post The returned value is true if the character c appears in the sequence s at least once, and is false if c does not appear at all in s.
(If s is the empty string, then it contains no characters, and ISIN (c, s) will be false whatever the character c is.)
Activity 20
Suggest a description for a function ISEMPTY corresponding to the following process.Determine whether or not a given sequence is empty.
Discussion
The function will input a sequence (which might contain elements from any set, say X). It can return true if the sequence is empty, and false if it is not empty. So we can use the following description of ISEMPTY.function ISEMPTY (s in SeqOfX ) return in Bool
pre true.
post The returned value is true if the sequence s contains no members, and is false if s contains one or more members.
End of discussion
Objectives for Section 4
After studying this section you should be able to do the following.· Recognise and use the terminology: function, signature, domain, semantics, input set, output set, precondition, postcondition.
· Suggest appropriate signatures and preconditions for functions corresponding to a variety of processes on numbers, characters and sequences, including those with more than one input and those that return a Boolean value.
· For given inputs, give the value returned by various functions described in this section, in particular: AT, PUT, SIZE, ASC, CHR, ADDLAST.
Exercises on Section 4
Exercise 9
For each of the following functions, give the signature and suggest a suitable precondition.(a) TOUPPER, which changes a string, containing only lower-case letters, into the corresponding string consisting of upper-case letters. (So, for example, TOUPPER(“word”) = “WORD”.)
(b) REMOVELAST, which, given a sequence, deletes its last member.
(c) LAST, which returns the last member of a sequence.
Answer
Solution
(a) This function inputs a string and outputs a string, therefore it has signature TOUPPER : SeqOfChar → SeqOfChar. It requires a precondition that the input sequence consists entirely of lower-case letters.(b) The members of the sequence may come from any set, which we will denote by X. The input is a sequence and the returned value is also a sequence. So the signature is REMOVELAST : SeqOfX → SeqOfX . The input sequence should contain at least one member (otherwise there is no last member to delete), so we need a precondition that the input sequence is not empty.
(c) This is similar to (a), except that the returned value is an item from X, rather than a sequence. The signature is LAST : SeqOfX → X. We again need the precondition that the input sequence is not empty.
End of answer
Exercise 10
Suppose that the days of the week are represented by numbers, with Mon-day represented by 1, Tuesday represented by 2, and so on, with Sunday represented by 7. Describe a function TOMORROW2, giving the next day with Days represented in this way.Answer
Solution
You may have given this description.function TOMORROW2(d in Int) return in Int
pre d is in the set {1,2,3,4,5,6,7}.
post The returned value is t, where:
if d = 1 then t = 2
if d = 2 then t = 3
if d = 3 then t = 4
if d = 4 then t = 5
if d = 5 then t = 6
if d = 6 then t = 7
if d = 7 then t = 1.
Or you may have given a shorter description, such as:
function TOMORROW2(d in Int) return in Int
pre 1 ≤ d ≤ 7.
post The returned value is t, where:
t = d + 1 if 1 = d = 6;
t = 1 if d = 7.
Either of these answers is fine.
End of answer
Exercise 11
(a) With s = “abcd”, evaluate each of:(b) For a general sequence s, describe how the sequence PUT(2, s, AT(1, s)) is obtained from s.
The functions AT and PUT were described in Activity 16.
Answer
Solution
(a)(i) With s = “abcd”, AT(1,s) = ‘a’.(ii) Then PUT(2,s,AT(1,s)) = PUT(2,“abcd”,‘a’) = “aacd”.
(b) In general, PUT(2,s,AT(1,s)) is formed by replacing the second member of the sequence s with a copy of the first member of s.
End of answer
No comments:
Post a Comment