Summary

1. We discussed forms of data and processes relevant to an electronic till in a supermarket. In particular, we introduced the idea of a sequence of data items.
   
2. A number of fundamental forms of data were introduced. We distinguished two types of number: integers (positive or negative whole numbers, or 0), and real numbers (thought of as decimal numbers and approximated in computers as floating point numbers). Characters may be thought of as symbols that may be entered from a computer keyboard by a single keystroke. Each character is associated with an integer code and we introduced one such encoding called the ASCII code. The Boolean values true and false form another fundamental form of data.
   Data may be structured in a collection. Different forms of collection are possible. We looked at two: sets and sequences. In a sequence, the order in which the items appear in the collection is important and an item may appear more than once. In a set, one is only interested in the different items appearing in the collection, and the order in which these items are listed is of no significance, nor is repetition of an item.
   The Cartesian product of sets X and Y is written X × Y , and is the set consisting of all ordered pairs (x, y), where x is in X and y is in Y . An ordered pair is also called a 2-tuple. More generally, an n-tuple is an association of n items, each taken from a specified set. An n-tuple is written in round brackets, and is a member of a Cartesian product set combining n component sets. For example, a member of the set Int × Char × Int × SeqOfChar would be a 4-tuple, such as (121, ‘y’, 6, “Qwerty”).
   

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.

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.

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:
  
  • (i) “same”;
    
  • (ii) “different”?
    
• (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.)

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.
  

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.

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.

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

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.

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.

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.
  

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.
  

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.

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.

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

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.

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.

Exercises on Section 3

Exercise 7

Each of (a)–(c) is a member of one of the sets given in (i)–(iii). Say which item comes from which set.
Sets: (i) SetOfSeqOfChar. (ii) SeqOfSetOfChar. (iii) SeqOfSeqOfChar.

• (a) {“error1”, “error2”, “error3”}.
  
• (b) [“error1”, “error2”, “error3”].
  
• (c) [{‘e’,‘1’}, {‘T’}, {‘q’,‘w’,‘e’,‘r’,‘t’,‘y’}].
  

Answer

Solution

• (a) This is a set, as shown by the outer curly brackets. Each member of this set is a string, that is, a sequence of characters. So (a) is a set of sequences of characters. It is a member of SetOfSeqOfChar.
  
• (b) This is a sequence, as shown by the outer square brackets. It is a sequence of strings. So (b) is a sequence of sequences of characters. It comes from SeqOfSeqOfChar.
  
• (c) This is again a sequence. Each member of this sequence is a set of characters. So (c) comes from SeqOfSetOfChar.
  

Exercise 8

Let Mix be the disjoint union Int Char. What is the length of the following sequence from SeqOfMix?

[555, ‘5’, ‘5’, ‘5’, 11, 1].

Answer

Solution

There are six items in the sequence [555,‘5’,‘5’,‘5’,11,1] (three integers and three characters), so the length of this sequence is 6.

Objectives for Section 3

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

• Recognise and use the terminology: disjoint union; power set (of a set); representation (of a data abstraction).
  
• Use and interpret the notation:
  
  • X Y for the disjoint union of the sets X and Y ;
    
  • SeqOfSetOfInt for the set consisting of all sequences whose members are sets of integers (and similar notations).
    

3.4 Representing data in applications

Suppose that you are designing software for some application. You will be working with a programming language that enables you to communicate instructions to a computer. In this programming language, certain forms of data will already be represented electronically. These will include common forms of data, such as numbers, characters and sequences. In any particular application, you are likely also to be concerned with forms of data that are peculiar to that application. Having identified some form of data that you need to be able to handle, you will then need to represent this in terms of what is available; that is, in terms of forms of data that have already been represented electronically.
As a simple example, imagine that integers, characters and strings are available forms of data, and that you want to represent the days of the week.
One natural form of representation is as strings: “Monday”, “Tuesday”, “Wednesday”, and so on. But other forms of representation are possible. The full names can be inconvenient because they involve a lot of writing, so one might choose to use shortened versions, such as: “Mon”, “Tues”, “Wed”, etc. We could be awkward (from the viewpoint of an English speaker), and use the strings: “Lundi”, “Mardi”, “Mercredi”, and so on. Or we could use integers, and represent Monday as 1, Tuesday as 2, Wednesday as 3, etc. This might be very convenient at times, but one then needs to remember which number represents which day.
There are times when it is important to distinguish between a form of data derived from an application situation and the concrete representation you have chosen for it. We might refer to the idea of the days of the week as an abstraction, in distinction to their representation, perhaps as the strings “Mon”, “Tues”, “Wed”, etc.

3.3 Mixing different forms of data: disjoint union of sets

At the supermarket checkout, some items need to be weighed (organic courgettes for example) and some do not. Let BarcodedItems be the set of items that do not need to be weighed, and WeighedItems be the set of items that must be weighed. When a weighed item is recorded at the till, we must record both the item type and the weight of the item that has been purchased. Earlier, we saw that such a purchase can be seen as an ordered pair, such as (“WALNUTS”, 335), that comes from the set WeighedItems × Int.
Suppose now that we want to form the set of all items that might appear in a transaction at a till. We might call this set TillItems. Specifying this set TillItems poses a complication, since there are two different types of element that might appear in it. An item from the set TillItems will come either from BarcodedItems or from WeighedItems × Int. We express this relationship by saying that TillItems is the disjoint union of BarcodedItems and WeighedItems × Int. We write this as:
You can read X Y as “X or Y.”
TillItems = BarcodedItems (WeighedItems × Int).
In general, the disjoint union of sets X and Y , written X Y , is the set consisting of all items that are either from X or from Y . The term “disjoint” reflects the fact that an item could not come both from BarcodedItems and from WeighedItems × Int. These sets contain different forms of data and have nothing in common. (We will only use disjoint union to combine sets containing different forms of data.)
As in Section 1, suppose that till1 is a variable representing a transaction in progress at till 1. The state of till1 will give the items recorded so far, in the order in which they were entered into the till, either by reading the barcode, or as a weighed item. So we can describe the state of till1 as a sequence of till items. The set of all possible states of till1 is SeqOfTillItems, where TillItems is BarcodedItems (WeighedItems × Int).
As noted earlier, we usually want to avoid mixing data of different forms in a collection such as a sequence. But if we need to do this, we can first use a disjoint union to combine the different forms of data into a single set. So, for example, if we needed to form a sequence whose members might be either characters or integers, then this sequence would come from a set SeqOfMix, where Mix is the disjoint union Int Char.
Search Amazon.com for Data and processes in computing,

3.2 Combining data structures

Search Amazon.com Books for Data and processes in computing,
In Section 2, we introduced the notation SeqOfX for the set of all sequences whose members come from the set X. In Section 2, we looked only at sequences whose members were of one of the primitive forms of data (integers, characters or Booleans). We can have sequences whose members are themselves data with a more complicated form. For example, suppose that Jo is working at the till T1 and is replaced by Jessica. We might represent this handover by the 3-tuple (Jo, T1, Jessica). Now suppose that we want to give all the handovers that occur during a particular day, in the order in which they occur. We could give this information in a sequence. This sequence would come from the set SeqOfX , where X is the Cartesian product Staff × Tills × Staff.
As another example, one might think of a sentence as a sequence of words, where each word is seen as a sequence of characters. If we did this, then the sentence would be regarded as coming from the set SeqOfSeqOfChar. We can use notations introduced earlier to show when we want to see a sentence in this way, and when it is to be regarded as a single string (from SeqOfChar).

Search Amazon.com Books for Data and processes in computing,