Data and processes in computing: 5 Operations and comparisons

5 Operations and comparisons

Seeing processes as functions

Addition of numbers is a process that one would expect a computer to be able to perform. Now we write the result of adding the numbers 5 and 2 as 5 + 2, for example. The symbol +, which represents the process of addition, appears between the two numbers being added. This is known as infix notation. Infix notation may be used for processes that combine two data items of the same type. Addition, subtraction and multiplication of numbers are familiar examples. We also use infix notation when writing a comparison of the size of two numbers, such as 5 < 9.
In this section, we shall show that a process such as addition of numbers is a function. Perhaps more surprisingly, a process such as < can also be seen as a function. This perception is a necessary preliminary to seeing how such a process can be implemented by a computer.

5.1 Arithmetic operations

Processes such as addition of numbers are called binary operations. (The word “binary” here reflects the fact that a binary operation combines two data items.) A binary operation is a particular form of function. To see this, we need to recognise the appropriate signature.
If you add two integers, then the resulting value is also an integer. So addition of integers takes two integers and returns an integer value. Thus adding integers is a function with signature Int × Int → Int. We can add any two integers, so addition is a total function (that is, has precondition true). We can describe a function, +, corresponding to addition of integers, as below.
function (infix) (x + y on Int) return in Int
pre   true.
post   The returned value is the result of adding x and y.
Where we use infix notation to write the value returned by a function, we will set out the signature line in the function description in a slightly different way from that used in Section 4, as illustrated above.

Activity 21

Describe a function, −, corresponding to integer subtraction written using infix notation.

Discussion

Subtraction again combines two integers to produce an integer value. We can subtract any two integers, so this is again a total function.
function (infix) (x − y on Int) return in Int
pre   true.
post   The returned value is the result of subtracting y from x.

End of discussion

We saw in Activity 3 that division of one integer by another does not necessarily result in an integer. For example, 2 ÷ 4 = 0.5 and 0.5 is not an integer. This means that we cannot define a function for what we might call “everyday division” that returns an integer value for integer inputs.
Sometimes, we need a form of division of integers that does yield an integer result. For example, suppose our supermarket features a special ‘buy 4, get 1 free’ order on bottles of wine. If a customer comes to the till with nine bottles of wine, then the till needs to calculate how many free bottles they should receive. Now nine bottles of wine contain two lots of four bottles (with one bottle left over). So the customer receives two free bottles of wine. This is an example of integer division. Integer division of 9 by 4 gives the result 2. (Hopefully, the cashier will point out to the customer with 9 bottles of wine that they are entitled to another free bottle!)
As another example, suppose that we want to perform integer division of 29 by 8. Now 3 × 8 = 24, while 4 × 8 = 32. When we perform integer division of 29 by 8 we obtain the result 3. Since 29 − 3 × 8 = 5, dividing 29 by 8 leaves a remainder of 5. Notice that the remainder, 5, satisfies the condition that 0 ≤ 5 < 8.
Integer division has two integers as input. It is a binary operation on Int, so we could use infix notation to write integer division. Now, many programming languages use / as an infix notation for both integer division and for real number division. In such cases, it is vital to appreciate that these are different processes, whose precise behaviour depends upon the type of the values supplied. To emphasise that integer division is not the familiar process of “everyday division”, we will write it as DIV, and use function rather than infix notation to give its values. For example, DIV (29, 8) = 3.
How can we describe integer division in general? To do this, some vocabulary is useful. In writing DIV (29, 8) = 3, the number 8 is called the divisor, and 3 is called the quotient.
We can generalise the equation 29 = 3 × 8 + 5 to give n = q × d + r (where d is the divisor, q is the quotient and r the remainder). The remainder must not be too large. In this example, the remainder 5 is less than 8. In general, the remainder r must be less than the divisor, d. Also, the remainder r is not negative. We can express these conditions on r algebraically as 0 ≤ r < d. So, in general, the quotient, q, is the largest integer by which we can multiply the divisor, d, while leaving a remainder that is not negative. If we subtract (q × d) from n, the resulting remainder needs to be non-negative and less than d.
Integer division has two integers as inputs and returns an integer. So the integer division function has signature DIV : Int × Int → Int. Since we write DIV using function notation, we can describe this function as below.
function DIV (n in Int, d in Int) return in Int
pre   d > 0.
post   The returned value q is the result of integer division of n by d. It satisfies the condition that if r = n − (q × d), then we have 0 ≤ r < d.
Notice that we only consider the case where the divisor, d, is strictly greater than 0. There is no restriction on the number n that is being divided, though. The examples we have considered so far have n positive.
What do these semantics give if n < 0? As an example, consider n = −29 and d = 8. We have −29 = −4 × 8 + 3 and the semantics give DIV (−29, 8) = −4. (Note that the remainder, r = 3, satisfies the condition 0 ≤ r < d, which is 0 ≤ r < 8 in this case.)
If n = 0, we have DIV (0, d) = 0 for any d that satisfies the precondition.

Activity 22

Give the following values:
(a) DIV (27,4).
(b) DIV (32,17).
(c) DIV (−27, 4).
(d) DIV (0,6).
(e) DIV (3,0).

Discussion

(a) DIV (27,4) = 6, since 27 = 6 × 4 + 3, where 0 ≤ 3 < 4.
(b) DIV (32,17) = 1, since 32 = 1 × 17 + 15, where 0 ≤ 15 < 17.
(c) DIV (−27, 4) = −7, since −27 = −7 × 4 + 1, where 0 ≤ 1 < 4.
(d) DIV (0,6) = 0.
(e) This is undefined (because of the precondition on DIV ).

End of discussion

A second process associated with integer division returns the remainder rather than the quotient. This is again a binary operation. We will write this operation as MOD(n, d). This operation can be described as below.
function MOD(n in Int, d in Int) return in Int
pre   d > 0.
post   The returned value r is the remainder after integer division of n by d. It satisfies the conditions 0 ≤ r < d and r = n - (q × d), where q is an integer. The remainder MOD(n, d) is sometimes called the value of n modulo d, or more briefly n mod d. Many programming languages use the infix notation n % d for this operation.

Activity 23

Give the following values:
(a) MOD(67, 10).
(b) MOD(55, 5).
(c) MOD(−27, 4).

Discussion

(a) MOD(67, 10) = 7 (since 67 = 6 × 10 + 7; the remainder on division of 67 by 10 is 7).
(b) MOD(55, 5) = 0 (since 55 = 11 × 5 + 0).
(c) MOD(−27, 4) = 1 because, as noted in Activity 22(c), we have −27 = −7 × 4 + 1.

End of discussion

Activity 24

(a) Suppose that you buy 335 grams of walnuts at 299 pence per kg, and the price of this purchase is expressed as a whole number of pence by ignoring any fraction. What is the cost of this purchase?
(b) Now consider a general purchase of this form, of weight grams of a product costing price pence per kilogram. Using the function DIV , give a formula for the cost of such a purchase.

Discussion

(a) 335 grams is 0.335 kilograms, so this purchase should cost 0.335 × 299 = 100.464 pence, which will be rounded to 100 pence. (Reassuringly, this is the same as the cost given in Figure 2.)
(b) In general we multiply weight and price, and divide the result by 1000, ignoring any fractional part of the result. So the required value is given by the expression DIV (weight × price,1000).

End of discussion

5.2 Operations on Boolean values

The idea of a binary operation, and the use of infix notation, is not confined to numbers. Infix notation may be used for any process with two inputs from the same set. We look now at two binary operations on Boolean values that are often used.
The first of these takes two Boolean values, and returns true if both of the input values are true and returns false otherwise. It is a binary operation, and we shall write it using the infix notation ∧, where the symbol ∧ can be read as “and”. So a ∧ b is true only when a and b are both true. We can describe the function corresponding to this operation as below (The operation ∧ is also known as conjunction).
function (infix) (a ∧ b on Bool) return in Bool
pre   true.
post   The returned value is true if both a = true and b = true, and is false otherwise.
Alternatively, we could give the semantics of ∧ by listing the returned value in each of four cases, giving the four possible combinations of input values. Using this approach, we could express the postcondition as follows.
post The returned value is c, where
if a = true and b = true then c = true
if a = true and b = false then c = false
if a = false and b = true then c = false
if a = false and b = false then c = false.
A second binary operation on Boolean values returns true if either (or both) of the two Boolean values is true. We write this operation using the infix symbol ∨ , where ∧ can be read as “or”. The corresponding function is described below. The operation ∨ is also known as disjunction.
function (infix) (a ∨ b on Bool) return in Bool
pre   true.
post   The returned value is false if both a = false and b = false, and is true otherwise.

Activity 25

Give the semantics of ∨ by listing the returned value in each of four cases, giving the four possible combinations of input values.

Discussion

We can express the postcondition in the description above as follows.
post The returned value is c, where
if a = true and b = true then c = true
if a = true and b = false then c = true
if a = false and b = true then c = true
if a = false and b = false then c = false.

End of discussion

Another useful process on Boolean values inputs a single Boolean value, and returns the reverse of that value. This process, called negation, is not a binary operation, since it has one input only. We call this function NOT, and we have
NOT(false) = true, and NOT(true) = false.

Activity 26

(a) Give a full description of the function NOT.
(b) If a = true and b = false, evaluate each of:

Discussion

(a) A description is given below.
function NOT(a in Bool) return in Bool
pre   true.
post   The returned value is false if a = true and is true if a = false.
(b) (i) Substituting for a and b, we have true ∨ false = true.
(ii) We should evaluate the term in brackets first: true ∨ false = true. Then NOT(true) = false. So NOT(a ∨ b) = false.
(iii) Again, evaluate the term in brackets first: (true ∨ false) = true. Then the given expression becomes true ∧ true which evaluates to true.

End of discussion

5.3 Comparison functions

Another situation where we use infix notation is in writing comparisons, such as x < y, where x and y are numbers. Such a comparison is either true or false. For example, 5 < 9 is true but 5 < 2 is false. To describe a corresponding function, we take the output set to be Bool = {true, false}. Thus the comparison < on integers corresponds to a function, which we can describe as follows.
function (infix) (x < Int y on Int) return in Bool
pre   true.
post   The returned value is true if x < y and is false otherwise.
Equality is also a comparison function. This is normally written using the infix symbol =. If x and y are numbers, then x = y is true if the numbers x and y are the same and is false if they are not. If one is working with real numbers on a computer, then one needs to be very careful with tests of equality. There will be an element of approximation in the way real numbers are stored, and this may result in a computer reporting real numbers as equal when they are only approximately equal. However, we shall confine our attention to integers, where there is no such problem in deciding whether two numbers are the same.
Sometimes we may wish to test to see whether two characters are the same. (This can be done by comparing their ASCII codes, for example.) A computer will need to work in a different way when comparing two integers for equality from that needed when comparing two characters for equality. These are different processes. Equality of numbers is a function with signature Int × Int → Bool; equality of characters, on the other hand, has signature Char × Char → Bool. Since these are different functions, we will give them different identifiers. We will write = _Int for equality of integers and = _Char for equality of characters.
function (infix) (x = _Int y on Int) return in Bool
pre   true.
post   The returned value is true if the integers x and y are equal and is false otherwise.
function (infix) (x = _Char y on Char) return in Bool
pre   true.
post   The returned value is true if the characters x and y are the same and is false otherwise.
One could give a binary operation < that compares characters by comparing their ASCII codes. Again, this is a different function from that of comparing integers (which is why we used a subscript Int in the identifier < _Int for comparison of integers above).
Note that in mathematics the term binary operation would only be used for a total function whose return type is the same as the type of the inputs.

Activity 27

Give a full description of an infix function corresponding to < _Char comparing two characters by comparing their ASCII codes.

Discussion

A description is given below.
function (infix) (x < _Char y on Char) return in Bool
pre   true.
post   The returned value is true if ASC(x) < _Int ASC (y) and is false otherwise.

End of discussion

In practice, a variety of different comparisons are used on integers (and other forms of data, such as characters), including: > (strictly greater than), ≤ (less than or equal), ≥ (greater then or equal), and ≠ (not equal). Functions may be described for each of these, but we shall not do so here.

5.4 Expressions

In computer code, one may want to formulate an expression to achieve some particular purpose, such as to express some condition about the states of variables involved in the code. For example, suppose that you want to express the condition that a sequence s contains at least two members, and that the second member of s is not the space character (with ASCII code 32). This condition holds when the expression below is true.
(SIZE(s) > _Int 1) ∧ (NOT(ASC(AT(2,s)) = _Int 32))
When writing expressions involving functions and binary operations, there are some points to be careful about. One needs to be careful to use brackets as necessary to ensure that operations are applied in the desired order. This is particularly important in expressions using infix notation. You also need to apply each process in a way that is consistent with its signature. And you must apply each process in a way that is consistent with any precondition that it has. We say that an expression is not valid if it uses a function in a way that is inconsistent with its signature or its precondition. For example, ‘Q’ = _Int 32 is not valid, since = _Int compares two integers, and ‘Q’ is a character, while PUT(7, “This”, ‘Q’) is not valid, since 7 does not satisfy the precondition of PUT. (The precondition of PUT requires that 7≤ SIZE(“This”), but SIZE(“This”) is 4.)
The functions SIZE and AT were described in Activity 16, and the function ASC was described in Section 4.3. The binary operations = _Int , > _Int and ∧ are defined earlier in this section.

Activity 28

(a) With s = “I#am.”, evaluate each of the expressions:
(b) Let s be a general string. Under what circumstances does the expression in (a) (v) give the value true? Under what circumstances is that expression valid?
(c) With s = “I#am.”, why is it not possible to evaluate the expression
(ASC(AT(2,s)) = _Int 35)?

Discussion

(a) (i) AT(2, s) = ‘#’.
(ii) ASC(AT(2, s)) = 35.
(iii) ASC(AT(2, s)) = _Int 35 becomes 35 = _Int 35, which evaluates to true.
(iv) NOT(ASC(AT(2, s)) = _Int 35) becomes NOT (true) = false.
(v) We have SIZE(s) = 5 (the number of characters in the string “I#am.”), so (SIZE(s) > _Int 3) becomes (5 > _Int 3) which is true. So the expression in (v) becomes true ∧ false = false.
(b) The given expression will be true only if each of SIZE(s) > _Int 3 and NOT(ASC(AT(2, s)) = _Int 35) is true. The first of these is true if the string s contains at least four characters. The second is true if the second character is s is not the character ‘#’. So the expression in (a) (v) will be true if:
the string s contains at least four characters and its second character is not ‘#’.
The precondition of AT requires here that the string s contains at least two characters. The expression in (a) (v) will be valid so long as this is true. (All the other functions in the expression are total. The example in part (a) indicates that the expression is put together in a way that is consistent with the signatures of the functions.)
(c) AT(2,s) = ‘#’. Then AT(2,s) = _Int 35 becomes ‘#’ = _Int 35. This expression is not valid, since = _Int requires two integers as inputs, and ‘#’ is a character. So the given expression is not valid.

End of discussion

Notice how important the brackets are in a complicated expression. The order in which the bits of the overall expression are to be evaluated is determined by the way the brackets appear in the expression. We need to follow this carefully in evaluating an expression such as that in Activity 28 (a) (v). A slip in placing one bracket can easily lead to an expression that is not valid, as in (c) above. On the whole, it is good practice when writing computing code to seek to avoid writing complicated expressions. Usually one can split the code into intermediate steps, as indicated by the steps in the evaluation in (a) above.

Objectives for Section 5

After studying this section you should be able to do the following.

· Recognise and use the terminology: binary operation, infix notation, quotient and remainder (associated with integer division).

· Use the notation for various binary operations introduced in the text, in particular DIV and MOD on integers; and ∧ (and) and ∨ (or) on Boolean values.

· Suggest appropriate signatures and preconditions for functions corresponding to binary operations, including comparisons that return Boolean values.

· Evaluate expressions involving functions and binary operations introduced in the text. Take note of where brackets appear in an expression.

· Recognise an expression that is invalid because it uses a process in a way inconsistent with its signature or precondition.

Exercises on Section 5

Exercise 12

Give a full description of a function (using the infix notation ×) corresponding to multiplication of integers.

Answer

Solution

A suitable description of integer multiplication is given below.
function (infix) (x × y on Int) return in Int
pre   true.
post   The returned value is the result of multiplying x and y.

End of answer

Exercise 13

With n = 966, evaluate each of:
(a) MOD(n, 10);
(b) DIV (n, 10);
(c) MOD(DIV (n, 10), 10).

Answer

Solution

966 = 96 × 10 + 6. So (a) MOD(966, 10) = 6 (the remainder when 966 is divided by 10), and (b) DIV (966,10) = 96. Then (c) MOD(DIV (966, 10), 10) becomes MOD(96, 10). This evaluates to 6, which is the remainder when 96 is divided by 10.

End of answer

Exercise 14

The function LAST is described below.
function LAST(s in SeqOfX ) return in X
pre   s is not empty.
post   The returned value is the last element in s. For example, LAST([1, 2, 3]) = 3.
Consider the expression NOT(LAST(s) = _Char LAST (t)).
(a) What is the value of this expression if s is “the” and t is:
(b) Under what circumstances does this expression have the value true?
(c) Is this expression valid with s = [1,2] and t = [1,8,4,2]?

Answer

Solution

(a) If s = “the” then LAST(s) = ‘e’. (i) With t = “same”, we have LAST(t) = ‘e’, and the given expression becomes
NOT(‘e’ =_Char ‘e’) = NOT (true) = false.
(i) With t = “different”, we have LAST(t) = ‘t’, and the given expression becomes
NOT(‘e’ =_Char ‘t’) = NOT (false) = true.
(b) The given expression is true if the strings s and t have different last letters.
(c) With these values of s and t, the given expression becomes NOT(2 =_Char 2). Now =_Char compares two characters, and 2 is an integer. So this expression is not valid. (For the given expression to be valid, we need s and t to be sequences of characters, and to be non-empty, so that the precondition of LAST is satisfied.)

End of answer