Data and processes in computing

Introduction

This course provides an introduction to data and processes in software, and provides a basis that enables these fundamental ideas to be developed in a clear and precise way. It has two main aims. The first is to illustrate how we can describe ways in which data may be structured and processed. The second is to introduce you to some vocabulary and concepts that help us to do this. The material is accessible to anyone with a little experience of the use of symbols in presenting ideas.

Section 1 provides a brief introduction to the course. It contains some new language that will be explained more fully in later sections. Read this section without spending too much time on it. The most important material in this course is that in Sections 2 and 4. Section 3 includes some ideas that are relatively difficult. You should read this section, but do not spend a great deal of time on it. Section 5 is of a similar length to Sections 2 and 4.

Overall, do not allow yourself to spend too long on any section while you are studying this course. You can always come back and reread material here if you find later that you need a more thorough understanding of some point.

This OpenLearn course provides a sample of Level 2 study in Computing & IT

Learning outcomes

After studying this course, you should be able to:

• understand ways in which data may be stored and processed

• distinguish between different forms of data, and use notations introduced in the course to show different forms of data

• appreciate that fine details may be important when interpreting formal notation (for example, different types of brackets may be used to distinguish between different forms of data)

• interpret a given function description

• recognise correct syntax in formal expressions.

Key ideas

In this course, we will take an introductory look at two key ideas: forms of data handled by a software system, and the processes that may be applied to that data. These ideas are illustrated by a particular application — a supermarket till — but they are of general relevance in designing software systems. Important terminology will be highlighted in bold.

In this course we will look at some commonly occurring forms of data. We start with fundamental forms, such as numbers and characters (which are symbols that may be typed at a keyboard). We then go on to look at more complicated data structures.

A second crucial feature of data is the processes available to handle it. The processes needed in any particular application are a particular focus in software design. Here, we shall look at how in principle we can describe a process that manipulates data. This initial description will not be concerned with how the process is executed, but only with its effect.

This course will introduce two important mathematical ideas that help in offering clear and precise descriptions of software components relating to data and processes. These ideas are set and function.

Section 1 gives a brief introduction to how data and processes may arise in an application situation. Section 2 is concerned with fundamental forms of data, and the mathematical idea of a set. Section 3 looks briefly at some more structured forms of data. In Section 4 we look at processes, and the mathematical idea of function. Section 5 is concerned with processes of a particular sort. Examples of these processes are the addition of numbers (as in 5 + 6) and a comparison of two numbers (as in 3 

1 At the supermarket

1.1 Number sequences

Imagine that you are at a modern supermarket and the cashier is processing the items from your basket or trolley. The electronic till (which is a form of computer) records each item that you have bought. Most items are scanned using a device that can read the barcode printed on the item.

Figure 1 An example of a barcode. Today, nearly every product has a barcode, although not all stores use them. A laser scanner is used to convert the pattern of light and dark bars into a number stored in the till. The number, printed as part of the barcode, may be entered manually if an electronic scanner is unavailable. A computerised till uses this code to look up the price that a shop wishes to charge for the item.

Items that need to be weighed (such as loose fruit and vegetables) do not have a barcode printed on them. Instead, the cashier looks up a different sort of code for these items and enters this manually at the till, together with the weight of the item purchased. If an error is made, the cashier may cancel the item just entered and try again. When all the items you have purchased have been processed, your final bill is calculated and you receive an itemised receipt (Figure 2).

Figure 2: An example of a supermarket till receipt. (Note the two weighed items.)

Let us look a little more formally at some of the data that the supermarket computer system must store and use. As we do this, you will begin to get a flavour of the rigour that underpins the design of modern software. You will meet new vocabulary and concepts, try to get a general sense of what each new term means.

Each type of item stocked by the supermarket needs to be identified. As we have seen, this is done either using barcodes or, for weighed items, item codes of a different sort. Associated with each code is a variety of other item-related information. Perhaps the most obvious information is the price, and the description that appears on the receipt. (In the case of weighed items, the price is a unit price, giving the price per kilogram, for instance.) Other information associated with any item code might include the current stock level (so that new stock can be ordered as items are near to being out of stock), the name and address of the supplier, discount rates for multiple purchases, etc

Barcodes such as 5000119004048 can be interpreted as whole numbers. Whole numbers are called integers. Integers may be positive, negative or zero. (The codes for weighed items are also usually whole numbers.)

Prices and weights are not ordinarily presented as whole numbers. In Figure 2, the item price of walnut bread is shown as £1.49; the unit price of organic courgettes is £3.49 per kg and the weight of organic courgettes purchased is 0.41 kg (kg is the standard abbreviation for kilogram).

A number with a fractional part such as 1.49 is an example of a real number. The real numbers include numbers such as 3.497825 (and numbers such as √2, which cannot be expressed exactly as any fraction or decimal). Computers cannot represent such real numbers exactly. When dealing with a real number, we can only rely on a computer storing and manipulating an approximation of the number. Even though the extent of the approximation may seem small, this can present problems to the unwary software developer. To avoid problems here, we will represent prices as a whole number of pence, and weights as a whole number of grams. So, for example, the bill in Figure 2 includes a purchase of 335 grams of walnuts at 299 pence per kg.

As the items in a basket or trolley are scanned one after another, the till stores a sequence of codes. We use a precise notation to indicate a sequence. Suppose that the item codes scanned so far are 50773, 50412, 50330, 33777, 50773. If the codes were scanned in this order, then the till would store the sequence [50773, 50412, 50330, 33777, 50773]. If the same codes were scanned in a different order, then the till might store the sequence [50773, 50773, 50412, 50330, 33777]. Barcodes normally contain more digits. In our illustrative examples, we shall use shorter codes that are easier to read.

A sequence is a collection of items in a particular order. We shall write the items in a sequence between square brackets [ and ], and commas are used to separate the items in it (in other texts, you may see angled brackets 〈 and 〉 used to show a sequence, rather than [ and ]). These items are called the elements of the sequence. The order in which items appear in a sequence is important, so that [50773, 50412, 50330, 33777, 50773] is not the same as the sequence [50773, 50773, 50412, 50330, 33777]. Of course, the order in which the cashier checks your purchases does not matter in terms of the final cost. But, while the items are being entered, the order will often matter. For example, if an error occurs in scanning or weighing, the last item entered can usually be corrected using a ‘Cancel Last Item’ key on the till. Also, the itemised bill that you receive usually gives the items in the order in which they have been processed.

Item descriptions in Figure 2 include “ORGANIC SOUP” and “OLIVE OIL”. These descriptions are formed from characters that can be typed from a computer keyboard (possibly with the Shift key pressed). There are various points to note about characters. For example, upper- and lower-case versions of the same letter, such as ‘P’ and ‘p’, are different characters. A digit such as ‘5’ can be entered from the keyboard as a character, and it is vital to be clear that, in terms of its storage in computer memory, this is not the same thing as the number 5. This means that “SOUP”, for example, also forms a sequence. It is a sequence of characters, and could be written as [‘S’, ‘O’, ‘U’, ‘P’]. However, to do this would be tedious, since we will use sequences of characters frequently. So we often use the notation “SOUP”, just to make life easier! When we do this, we usually refer to the sequence of characters as a string.

Note that we have introduced a number of notational conventions. An individual character is written between single inverted commas, as in ‘P’ or ‘q’. Double inverted commas are used to show a sequence of characters such as “ORGANIC”. If we write out in full the string “ORGANIC COURGETTES 0.41kg @ £3.49/kg”, it is necessary to deal with the spaces between words. This use of double inverted commas only applies to sequences of characters. All other sequences are written using the square bracket notation introduced above. Spaces are characters like any others; they are obtained by pressing the space-bar on the keyboard. It is often desirable to indicate the space character explicitly by adopting a special symbol. We shall use ‘’. Thus, we may write [‘O’, ‘R’, ‘G’, ‘A’, ‘N’, ‘I’, ‘C’, ‘’, ‘C’, ‘O’, ‘U’, ‘R’, ‘G’, ‘E’, ‘T’, ‘T’, ‘E’, ‘S’, ‘’, ‘0’, ‘.’, ‘4’, ‘1’, ‘k’, ‘g’, ‘’, ‘@’, ‘’,‘£’, ‘3’, ‘.’, ‘4’ ‘9’, ‘/’, ‘k’, ‘g’].

Imagine you are at the fifth till in the supermarket, and the data that constitutes your transaction is recorded by the supermarket's computer using the identifier till5. This is the name of an area in the computer's memory devoted to storing your transaction details. The data stored in till5 changes each time an item is scanned or entered, and so we refer to till5 as a variable. We call the data stored in the variable till5 at any moment in time the state of till5. Each time that the data stored by till5 changes, we say that the state of till5 has changed. You do not need to know anything about how the computer's electronic memory actually works.

These comments are not peculiar to the fifth till at the supermarket. The supermarket's computer stores data for each active till. The data for each till can be seen as a variable, and so needs its own identifier — such as till1, till2, and so on. Indeed, the term variable is used for any named area of computer memory, storing data that may change.

Now suppose that the variable till5 stores a sequence of barcodes. When the cashier starts a new transaction, no items have been entered, so the state of the variable till5 needs to start as a sequence with no elements, which we call an empty sequence and write as [ ]. If an item with code 50297 is then entered, then the state of till5 will change to [50297]. If an item with code 50152 is scanned next, then the state becomes [50297, 50152], and so on.

When a new item is recorded, the state of till5 changes, and changes in a way that is predictable. Specifically, the current state is changed by appending the newest item to the end of the sequence, giving a new state.

We have described the change of a till state in a way that is quite general. The description is not peculiar to the fifth till in the supermarket: it applies equally well to a transaction in progress at any till. Indeed, it describes a process that adds a new item to any variable storing data as a sequence.

Now suppose the computer stores the prices of certain items as given in Table 1. To calculate the bill corresponding to purchases read by the cashier as [77502, 53151, 33050, 77502], we need to store the price associated with each item purchased. Let us assume that a second sequence is also being generated as each item is recorded, giving the price of the item. Suppose that this is stored as a variable price5. If the sequence of item codes were [77502, 53151, 33050, 77502], then the sequence of prices would be [89, 440, 299, 89]. Given this sequence, the total bill is obtained by simply finding the total of all the values in the sequence price5:

89 + 440 + 299 + 89 = 917 pence.

For simplicity, assume that there are no weighed items and no special offers.

This calculation does not change the state of the variable price5, but the value calculated certainly does depend upon the state of that variable.

Appending a new item at the end of a sequence, or adding a sequence of numbers, are both examples of the sort of processes that software needs to carry out time and time again. Recognising generality, and forms of data and processes on data that can be reused, are key skills in learning to design large and complex software systems.

Since we use double inverted commas for strings, i.e. sequences of characters, we will use “ ” to denote the empty string in this course. In many computing texts, the symbol ξ is used.

Objectives for Section 1

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

• Recognise the terminology: character; string; integer; sequence; element (of a sequence); variable; identifier (of a variable); state (of a variable).

• Use and interpret the notational conventions:

  • single inverted commas to show a character;

  • double inverted commas to show a string (sequence of characters);

  • ‘’ to make explicit a space character;

  • the brackets [ and ] to delimit a sequence.

Exercises on Section 1

2 Forms of data

2.1 Numbers

The supermarket example discussed in Section 1 involves various forms of data that a computer may need to handle. Some of these, such as numbers and characters, are simple but fundamental. Other forms of data, such as sequences, involve more complicated structure. In this section, we will introduce sets, which are a variety of data collection that is different from sequences. But first we will look more carefully at numbers and characters.

When developing software we need to distinguish between different sorts of numbers, not least because computers represent and process them differently. Whole numbers (positive, negative or zero) are called integers. We shall use Int to denote the collection (or set) of all integers. In principle, digital computers can represent integers exactly, no matter how large or small. In practice, however, most programming languages place restrictions on the size of an integer (positive or negative) that can be stored. Many texts use instead of Int.

Sometimes, we need to work with numbers that are not integers. Measured quantities, such as weights or distances, are often presented as non-integer values. More profoundly, even if one starts with whole numbers, some arithmetic processes, such as division or finding a square root, may yield results that are not integers (see Activity 3). The real numbers are a wider collection of numbers used in mathematics. A real number is conveniently thought of as a decimal, such as 435.5218 or –29.333344, but not every real number can be written as a decimal of a finite length. For example, √2 (the square root of 2) and the number (pi) are real numbers that are non-terminating decimals. Such numbers can never be expressed exactly as a finite decimal.

is approximately equal to 3.142. You may have met it in calculating the circumference or area of a circle.

Digital computers cannot store real numbers exactly. They need to work with approximations to the real numbers. These approximations may be stored in the computer as floating point numbers. You can get a feeling for the sorts of issues that arise through the following example. Suppose (for the purposes of illustration) that we can only store a real number to an accuracy of four decimal places. Then the number 435.5218 might be stored as 0.4355 × 10³. But 435.48336 (a different number) would also be stored as 0.4355 × 10³.

If a software application really does need to deal with real numbers, then great care needs to be taken to ensure that the effects of (repeated) approximations are managed in a way that is well understood. This is especially true for safety critical applications, where people's lives may depend upon the behaviour of the software. However, in this course, we shall largely exclude further consideration of real numbers.

2.2 Characters

Characters are another fundamental form of data. Computers store characters as integers, and system hardware and software translate these integer codes so that monitors and printers can display them.

As well as the familiar characters appearing on a keyboard, the current international standard (UNICODE) includes codes for characters from a variety of languages and alphabets (such as ê and ö). For simplicity, examples in this course will use only a part of this code, as given in Table 2. This is confined to printable symbols that appear on a standard computer keyboard (for an English-speaking user).

We will denote by Char the set of characters appearing in Table 2. We will call the codes in the table the ASCII codes of the characters.

The original ASCII set (developed by ANSI, the American National Standards Institute) was finalised in 1968, and provides a basic (but by no means complete) character set for English. With the development of the Internet and a more global economy, efforts are being made to create a standard character set, catering more completely for many languages, and bringing together hundreds of incompatible standards from different countries. UNICODE is the result of this development, but it still only represents some of the written characters of our languages, currently standing at about 94,000 symbols. No existing character set caters for all languages.

Table 2: The ASCII encoding of characters (in part).

Code	Character	Code	Character	Code	Character
32		64	@	96	'
33	!	65	A	97	a
34	"	66	B	98	b
35	#	67	C	99	c
36	$	68	D	100	d
37	%	69	E	101	e
38	&	70	F	102	f
39	’	71	G	103	g
40	(	72	H	104	h
41	)	73	I	105	i
42	*	74	J	106	j
43	+	75	K	107	k
44	,	76	L	108	l
45	−	77	M	109	m
46	.	78	N	110	n
47	/	79	O	111	o
48	0	80	P	112	p
49	1	81	Q	113	q
50	2	82	R	114	r
51	3	83	S	115	s
52	4	84	T	116	t
53	5	85	U	117	u
54	6	86	V	118	v
55	7	87	W	119	w
56	8	88	X	120	x
57	9	89	Y	121	y
58	:	90	Z	122	z
59	;	91	[	123	{
60		92	\	124	|
61	=	93	]	125	}
62	>	94	^	126	˜
63	?	95	–

The character with ASCII code 32 is the space character, which, when we need to write it explicitly, will appear as ‘’

2.3 Truth values

We will want to distinguish between statements that are true and statements that are false. Another fundamental form of data allows us to do this. This form of data consists of just two values, which we shall write as true and false.

Not all texts use the same notation: some use T and F; others may use 0 for false and 1 for true (or the reverse!).

We may refer to true and false as truth values, or Boolean values. We will denote the collection (set) of truth values as Bool, after the mathematician George Boole. We write:

This shows the collection Bool as a set. We have already mentioned the word set in passing, and now want to look at this concept in more detail.

2.4 Sets

A set is a collection of items, and is a collection of a particular form. The items appearing in a set are referred to as the elements (or members) of the set. Examples of sets mentioned earlier are: Int, Char and Bool.

A set is a collection in which repetition is not significant, nor is the order in which the items are given. For example, the supermarket might sell its own brand of Wheat Flakes in three sizes: large, medium and small. In a situation where we are interested in the types of product that are available, we are interested in the set of sizes. This set of sizes may be written as:

We might choose to name the set:

The order in which the elements are listed is of no significance, so we might equally well have written Sizes = {small, medium, large}.

Notice the use of curly brackets {and} here. These are used as a signal that the collection is a set (as distinct from some other form of collection, such as a sequence). Note too the commas used to separate the elements.

We would not usually give any repetitions when writing a set, but if one were to do so, repetition of an element would be of no significance. We could write a set as

but this set is the same as Sizes and has three members, not five!

We write a ∈ X to mean that the item a is a member of the set X (we say “a is in the set X”, or just “a is in X”). So, for example, we might write small ∈ Sizes.

It was easy to write out the set Sizes in full because it has only three elements. Imagine having to write out the set of all barcodes used at a large supermarket. It would not be practicable! We have another notation for such sets, that is sets whose members can be precisely described. Suppose that, a little unrealistically, a store (YtoZ Groceries) stocks just 90000 items, which happen to have barcodes that are consecutive integers between 10000 and 99999. Then the set of barcodes used by the store may be written:

YtoZBarcodes = { n ∈ Int : 10000 ≤ n and n ≤ 99999}.

A rather literal reading of this notation would be: “YtoZBarcodes is the set of values, n, in the set of integers, such that n is greater than or equal to 10000 and less than or equal to 99999.”. (We read the first curly bracket as “the set of” and the colon as “such that”.) More casually, we might say: “YtoZBarcodes is the set of integers between 10000 and 99999, inclusive.”. (The word inclusive makes it clear that the numbers 10000 and 99999 are each included in the set.)

Alternatively, the condition 10000 ≤ n and n ≤ 99999 can be written as 10000 ≤ n ≤ 99999.

A set need not have any members. (The set {n ∈ Int : n > 100 and n empty set. We will write this as { }.

Sometimes we need to say how many elements there are in a set. For example, the set Sizes, as above, has 3 elements, while the set YtoZBarcodes has 90000 members. The number of elements in a set is called the cardinality of the set. The cardinality of the empty set is 0. (We shall only talk about the cardinality of a finite set. The set Int, for example, does not have a finite number of elements.) If the members of a set have been written out with some elements repeated, then remember to count each repeated element only once when finding the set's cardinality. In other texts, you may see the symbol ∅ used to denote an empty set.

2.5 Sequences

You have already met sequences briefly, and have seen that a sequence contains items given in a particular order, and that repetitions are of significance.

One might have a sequence containing integers, such as [22, −31, 44, 0, 2, 0, 11] or a sequence containing characters, such as [‘W’,‘o’,‘r’,‘d’]. However, we will aim to avoid mixing the forms of data in a sequence. A sequence of characters may also be referred to as a string, and that “Word” is another notation for the sequence [‘W’,‘o’,‘r’,‘d’].

The items in a sequence are enumerated from the left. Thus in the sequence [‘W’,‘o’,‘r’,‘d’], the first item is ‘W’, the second item is ‘o’, and so on. The items in a sequence may also be referred to as the elements (or sometimes members) of the sequence. The number of items in a sequence is called its length. So, for example, the length of the sequence [‘W’,‘o’,‘r’,‘d’] is 4.

We do count repeated items when calculating the length of a sequence. So, for example, the sequence of numbers [22, −31, 44, 0, 2, 0, 11] has length 7, while the sequence of characters “aardvark” has length 8.

Incidentally, we are only concerned in this course with finite sequences. If you study mathematics in other contexts, you may meet sequences that “go on forever”, such as the sequence of real numbers: 1, , , , , ... (where the general term is where n is a positive integer). Any form of data stored on a computer as a sequence will contain a finite number of items, so a sequence describing a form of data stored on a computer will be finite. A finite sequence will have a length that is a positive integer.

We have introduced notations for the set of all integers, Int, and for the set of characters, Char. It is convenient also to have a notation for sequences. This will need to tell us two things: first, that we are referring to a set of sequences; and second, the set from which the members of the sequence come. Thus we write SeqOfInt for the set of all sequences of integers. So, for example, [22, −31, 44, 0, 2, 0, 11] is in SeqOfInt. Similarly, we write SeqOfChar for the set of all sequences of characters. The sequence [‘W’,‘o’,‘r’,‘d’] is in SeqOfChar (and not in SeqOfInt), because it is a sequence that contains characters, not integers.

There are a couple of points to note here. First, the number 22 is not in SeqOfInt, because 22 is not a sequence, it is an integer. However, [22] is in SeqOfInt. This is a sequence that happens to contain just one integer. Second, both SeqOfInt and SeqOfChar include an empty sequence, [].

More generally, we write SeqOfX for the set containing all sequences of items from the set X. Here X might be any set. For example, SeqOfBool contains all sequences whose members are from Bool, that is, whose members are Boolean values.

2.6 Associations: tuples and Cartesian products

Consider an item of shopping that is weighed at the supermarket checkout, such as 335 grams of walnuts. This item of shopping has two features: the type of item purchased (walnuts), and the weight of that item (335 grams). To record a weighed item of shopping we need to note both these features. This can be done using an ordered pair: (“WALNUTS”, 335).

The first item in this ordered pair gives the type of item purchased. Let WeighedItems be the set of items stocked by the supermarket that need to be weighed. The first item comes from this set, while the second item in the ordered pair comes from the set Int.

We call the set containing all such pairs the Cartesian product of the two sets. (‘Cartesian’ after the famous French philosopher and mathematician René Descartes.) This set of pairs is written as WeighedItems × Int. So the set WeighedItems × Int consists of all pairs (w, n), where w comes from the set WeighedItems, and n comes from the set Int. We refer to (w, n) as an ordered pair. The word pair here indicates that there are two items grouped together. The word ordered indicates that the order in which the two items are given matters. The pair (“WALNUTS”, 335) is not the same as the pair (335, “WALNUTS”). Similarly, the set WeighedItems × Int is different from the set Int × WeighedItems, which consists of pairs giving: first an integer, then a type of weighed item.

Use of the symbol × here has nothing to do with multiplication of numbers!

We can form the Cartesian product of any two sets. The Cartesian product of sets X and Y is written as X × Y , and consists of all ordered pairs (x, y) where x is from the set X and y is from the set Y. X × Y can be read as “ X cross Y”.

An ordered pair gives an association between two items. There are situations where we may want to associate more than two things. Consider items stocked by the supermarket that have barcodes. The supermarket will be interested in a number of features associated with each item of this type. Three such features are:

1. The barcode (taken to be an integer).

2. The name of the item, to be printed on the till receipt (as a string).

3. The price of an item of this type (taken to be an integer number of pence).

A natural way to associate these three features is to write them together as an ordered triple, or 3-tuple, such as (13151, “ORGANIC SOUP”, 179). Note the use of round brackets here. These are used for tuples, in distinction to square brackets [ and ] for sequences, or curly brackets { and } for sets. The terminology ‘ordered triple’ indicates that we are now writing three items, each from a specified set, in a given order. We may want to associate four items, or five, or more. The terminology ‘tuple’ extends conveniently to this general case, where we talk about 4-tuples, or 5-tuples, and, in general, n-tuples (where n might be 2, or 3, or any larger integer).

The set of all 3-tuples of the same form as (13151, “ORGANIC SOUP”, 179) is again a Cartesian product, in this case a product of three sets. The barcode is from Int, the item name is a string (from SeqOfChar) and the price is an integer. So this 3-tuple comes from the set Int × SeqOfChar × Int.

As another example, suppose that a shop has just three members of staff, Jo, Jessica and Wesley, and just two tills, T1 and T2. We could represent a situation where Jo is operating the till T2 by the ordered pair, or 2-tuple (T2, Jo). Clearly, there are a variety of ways in which a member of staff can be assigned to a till. If Tills is the set {T1, T2} and Staff is the set {Jo, Jessica, Wesley}, then the set of all possible assignments of a member of staff to a till is Tills × Staff . If we write this set out in full, we obtain:

Tills × Staff = {(T1, Jo), (T1, Jessica), (T1, Wesley), (T2, Jo), (T2, Jessica), (T2, Wesley)}.

Note the use of different brackets: curly brackets delimit the set, round brackets delimit each of the tuples. Note also that the use of Tills × Staff to represent assignment of a staff member to a till means that we must write the till first in each ordered pair.

Objectives for Section 2

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

• Recognise and use the terminology: real number; set; element or member of a set; empty set; length of a sequence; empty sequence, ordered pair, n-tuple, Cartesian product.

• Appreciate that use of precise notation such as the use of different types of bracket conveys important information when using formal notation. For example, square brackets [ and ] denote a sequence, while curly brackets { and } denote a set.

• Use and interpret various pieces of notation:

  • curly brackets to denote a set;

    – definition of a set by using a condition;

  • { } to denote the empty set;

  • [ ] to denote an empty sequence;

  • SeqOfX to denote the set of all sequences with members from X;

  • (x, y) to denote an ordered pair or 2-tuple; (x, y, z) to denote a 3-tuple, etc.;

  • X × Y to denote the Cartesian product of the sets X and Y .

• Determine the cardinality of a given set and the length of a given sequence.

• Given i, determine the ith element of a given sequence.

• Be aware of the ASCII character codes.

• Appreciate that some sets are finite and some are not.

Exercises on Section 2

3 Combining forms of data

Structuring data

In Section 2, we considered integers, characters and truth values. We shall refer to these as primitive forms of data. We also looked at two forms of data collection, sets and sequences, and at the association of different data items in a tuple. In this section, we will look briefly at some other ways in which data may be structured.

3.1 Sets of sets

In Section 2, all the sets and sequences we considered had primitive forms of data as their elements. However, sets and sequences may contain non-primitive forms of data. Let us look first at a situation in which we may find it useful to have a set whose members are themselves sets.

Think again about a shop with just three members of staff, given in the set Staff = {Jo, Jessica, Wesley}. Now let at WorkStaff be the set of staff currently at work. Clearly, at WorkStaff may take a range of values. If just Jo and Wesley are at work, then at WorkStaff is {Jo, Wesley}. If Jessica were to start work and Jo were to leave, then at WorkStaff becomes {Jessica, Wesley}.

Now any combination of staff from the set Staff = {Jo, Jessica, Wesley} might be at work at the same time. Possibilities include all these staff (when at WorkStaff is {Jo, Jessica, Wesley}), and none of them (in which case at WorkStaff is { }). The full list of possibilities (giving the possible values of at WorkStaff ) is given below.

{ }, {Jo}, {Jessica}, {Wesley}, {Jo, Jessica}, {Jo, Wesley}, {Jessica, Wesley}, {Jo, Jessica, Wesley}

Here, we have written out all the sets with members taken from the set Staff = {Jo, Jessica, Wesley}. We can form a set whose members are these sets. We will denote this set by SetOfStaff . So:

SetOfStaff = {{ }, {Jo}, {Jessica}, {Wesley}, {Jo, Jessica}, {Jo, Wesley}, {Jessica, Wesley}, {Jo, Jessica, Wesley}}.

The outer curly brackets here delimit the members of the set SetOfStaff. Each of these members is itself a set, and the inner curly brackets delimit each of these member sets. We will not often need to list the members of a set of sets like this. But it is useful to be aware that we can form a set in this way. We might have a variable atWorkStaff, giving the set of staff currently at work. The set giving all possible states of this variable is then SetOfStaff.

In general, we will use SetOfX to denote the set consisting of all the sets drawn from some given set, X. SetOfX is also known as the power set of X. Various other notations are used for this, including P(X) and 2^X . The latter is sometimes used since, if X has cardinality n, then SetOfX has cardinality 2ⁿ . For example Staff has cardinality 3 and SetOfStaff has cardinality 8, which is 2³.

3.2 Combining data structures

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

Consider a computer system which has a finite set of error messages, each of which may be displayed to a cashier at the till. Suppose these messages are: “Barcode error”; “Item code not recognised” and “System error 1234”. This set of error messages can be represented thus:

Errors = {“Barcode error”, “Item code not recognised”, “System error 1234”}.

Each of these messages is given as a string, that is, as a sequence of characters. So Errors is a set of sequences of characters.

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.

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.

One additional point of importance about any form of data in an application concerns the ways in which we need to be able to manipulate it. We turn to processes on data in the next section.

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

Exercises on Section 3

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.

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:

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:

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:

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.

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:

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

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

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.

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

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.

4.4 Functions returning true or false

Consider a function, say ISIN , associated with following process.

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

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

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

In this section, we shall show that a process such as addition of numbers is a function. Perhaps more surprisingly, a process such as

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.

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

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

If n = 0, we have DIV (0, d) = 0 for any d that satisfies the precondition.

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.

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.

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

5.3 Comparison functions

Another situation where we use infix notation is in writing comparisons, such as x , where x and y are numbers. Such a comparison is either true or false. For example, 5 Bool = {true, false}. Thus the comparison

function (infix) (x 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 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.

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.

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

Conclusion

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

3. The disjoint union of sets X and Y, written X Y, consists of all items that come either from X or from Y (where X and Y have nothing in common). This is useful when we want to mix different forms of data in a sequence.

4. A function is a process that returns a unique value for each permitted input. To give a full description of a function, we give: its signature (name, and input and output sets), a precondition (which may be true), and a postcondition giving its semantics. The semantics should be an unambiguous statement of the relationship between the returned value and the input(s).

   If a function has more than one input, then its input set will be a Cartesian product. If a function returns a value that is true or false, then the output set will be Bool. Usually, the semantics of a function are given by a general rule, or possibly by a formula. However, in some cases we need to list the returned value for each possible input. For example, this would be the case for a function returning the price of each barcoded product stocked by a supermarket.

5. A binary operation is a process, such as addition of integers, that inputs two data items of the same type. A binary operation can be written using infix notation (as in x + y, for example). Addition of integers corresponds to a function with signature Int × Int → Int. We described integer division. Integer division of n by d returns an integer, written DIV (n, d). It also leaves a remainder, denoted by MOD(n, d).

   We noted that binary operations are not confined to those on numbers. We described two binary operations on Boolean values that are frequently useful: ∨ (read as “or”) and ∧ (read as “and”). We also introduced the function NOT on Booleans.

   Comparisons, such as Bool. For example, =_Char , a test of whether two characters are identical, corresponds to a function with signature Char × Char → Bool.

Acknowledgements

Except for third party materials and otherwise stated (see terms and conditions), this content is made available under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 Licence

Course image: Creativity103 in Flickr made available under Creative Commons Attribution 2.0 Licence.

All materials included in this course are derived from content originated at the Open University.

Don't miss out:

If reading this text has inspired you to learn more, you may be interested in joining the millions of people who discover our free learning resources and qualifications by visiting The Open University - www.open.edu/ openlearn/ free-courses