User-defined data types, file organisation and floating-point numbers

Why user-defined data types are necessary

Every language gives you a set of built-in data types - INTEGER, REAL, CHAR, STRING, BOOLEAN and DATE in 9618 pseudocode - and for much of your data they are enough. A user-defined data type is one you declare yourself, built from the built-in types and from other types you have already declared. You need one either because no built-in type can describe the data at all, or because a built-in type can describe it but cannot stop the program from using it wrongly.

The first reason is a fixed set of values. Some data has only a handful of legal values and no built-in type knows this. An order can be Pending, Packed, Dispatched, Delivered or Returned, and nothing else.

Stored as a STRING, the language will happily accept 'Dispatchedd', 'dispatched' and 'sent', and every comparison in the program will then fail silently. Stored as an INTEGER, it will happily accept 47. An enumerated type declares the five legal values once, so the program can hold nothing else.

The second reason is grouping. A pupil's details are a name, a date of birth, a form group, a set of subject choices and an average mark - five different types that mean one thing together. Without a composite type you would keep five parallel arrays, pass all five to every procedure that needs them, and keep them in step by hand. A record puts them under one identifier, so a single variable can be passed, copied, sorted and stored as a unit.

The third reason is maintenance and reuse. A named type documents itself: StudentRecord tells the next programmer far more than ARRAY[1:40] OF STRING. The definition sits in one place, so adding a field or widening a field changes every use of the type instead of every line of code that mentions it. A type designed for one program can be reused in another program that needs the same structure, which is how libraries of types and classes are built up.

The fourth reason is control over access. A class can keep its attributes private and let the rest of the program change them only through methods, so an account balance can change only through a deposit or a withdrawal that checks the amount. That prevents invalid states and hides how the data is stored, so the implementation can be rewritten without breaking the code that uses it. Pointers are the fifth reason: a structure that grows and shrinks while the program runs, such as a linked list, cannot be built from the built-in scalar types at all.

• Fixed set of legal values: an enumerated type rejects anything not in the list, which a STRING or an INTEGER cannot do.
• Grouping related data: a record or class holds fields of different types under one identifier, so they are passed and stored as one item.
• Readability: a meaningful type name says what the data is, which matters in a program written by a team.
• Maintenance: one definition, changed in one place, updates every use of the type.
• Reuse: a type or class written for one program can be used in another that needs the same structure.
• Controlled access: a class keeps attributes private and exposes methods, so the data cannot be put into an invalid state.
• Dynamic structures: pointers allow memory to be linked and resized at run time, which fixed built-in types cannot do.

Enumerated types: a fixed list of named values

An enumerated type is a non-composite type whose complete set of values is written out in its declaration, in a fixed order. Each value has an ordinal position: the first value is position 0, the second is 1, and so on. It is non-composite because every value of the type is a single item, not a collection of fields.

You define the type once, then declare variables of it. The only values such a variable can be given are the ones in the list, so the compiler or interpreter rejects anything else at the point where the mistake was made rather than at the point where it causes a wrong answer. Because the values have a fixed order, they can be compared with =, <> and <, which is what makes them useful for stages that happen in sequence.

Inside the computer an enumerated value is held as a small integer - its ordinal position - so it takes less memory than a string and compares in a single operation. The names exist for the programmer. That also explains the trap: inserting a new value in the middle of the list shifts every later ordinal, so an ordinal that was written to a file last year no longer means the same stage this year.

An enumerated type is the wrong choice when the list can change while the program runs, when each value needs extra data attached to it, or when the values are numerous and better held in a lookup table. In those cases use a record or class for each value, and hold the set of them in a file or an array.

• Define the type: TYPE OrderStatus = (Pending, Packed, Dispatched, Delivered, Returned)
• Declare a variable: DECLARE ThisOrder : OrderStatus
• Assign a value: ThisOrder <- Packed
• Compare by position: IF ThisOrder < Dispatched THEN ... treats Pending, Packed and Dispatched in that order.
• Use in selection: CASE ThisOrder OF Pending : ... / Packed : ... / Delivered : ... ENDCASE
• Validate input by converting: read a string, then a CASE statement maps 'packed' to Packed and rejects anything else.
• Positions start at 0: Pending is 0, Packed is 1, Dispatched is 2, Delivered is 3, Returned is 4.

Pointers: variables that hold an address

A pointer is a variable whose value is the address of another variable, of a record, or of a block of memory allocated while the program runs. It does not hold the data itself; it holds the location of the data. Reading or changing the data through the pointer is called dereferencing, and a pointer that holds no address at all is set to NULL.

Pointers are what make dynamic data structures possible. A linked list, a stack or a queue implemented with nodes, or a tree, is built from items that are created as they are needed and joined by storing each item's address in the one before it. The nodes do not have to be next to one another in memory, so the structure can grow and shrink without moving anything, and inserting or deleting an item changes two pointers rather than shifting a whole array.

They are also used to share a large structure without copying it - pass a pointer to a record rather than a copy of the record - and to allow a procedure to change the caller's variable, because the procedure receives the address rather than a copy of the value.

Dereferencing a pointer that has not been given an address, or that still holds the address of memory which has been freed, is a dangling pointer, and it is one of the hardest faults to find because the program may run correctly for months. A memory leak happens when the address of an allocated block is overwritten before the block is released: the memory is still reserved but nothing can reach it. Two pointers to the same location also mean that a change made through one appears through the other, which is easy to overlook when you are debugging.

• Define the node: TYPE Node / DECLARE Data : STRING / DECLARE Next : POINTER TO Node / ENDTYPE
• Declare the pointers: DECLARE Head : POINTER TO Node and DECLARE Current : POINTER TO Node
• Start an empty list: Head <- NULL
• Follow a link: Current <- Current^.Next - the caret means the value stored at that address.
• Read the data: OUTPUT Current^.Data
• Test for the end: WHILE Current <> NULL ... ENDWHILE, because the last node's Next is NULL.
• Create a node while the program runs and store its address in a pointer, rather than declaring a fixed array of nodes in advance.

Sets and records: two composite types with different jobs

A set is an unordered collection of values of the same base type, in which each value can appear at most once. Order is not part of a set, so {Biology, Computing} and {Computing, Biology} are the same set, and adding a value that is already there changes nothing. Sets are used when the question you are asking is membership: which optional subjects this pupil takes, which permissions this user has, which tags this article carries.

The operations you need are adding a value, removing a value, testing membership, and combining sets by union (everything in either), intersection (only what is in both) and difference (what is in the first but not the second). Testing membership is a single operation on a set, whereas on an array it means searching the whole array with a loop, which is why a set is the natural type for a list of options.

A record is the opposite kind of composite: an ordered collection of named fields, each of which may have a different type, treated as one item. The fields are fixed when the type is declared and are reached by name, as in Pupil.Name or Pupil.AverageMark. Records are how real entities are held: a student, an employee, a product, a booking. An array of records gives you a table, and the field that identifies each record is its key field.

Records can be nested, so a record can contain another record or an array, and records are what a file stores: a file of fixed-length records is the usual way of holding a table on disk. The difference from a class is that a record is passive data with no operations of its own, while a class bundles its data with the methods that work on it.

• Define a set: TYPE Subject = (Art, Biology, Chemistry, Computing, Drama, Economics) then TYPE SubjectSet = SET OF Subject
• Declare and fill it: DECLARE Choices : SubjectSet then Choices <- [Biology, Computing]
• Test membership: IF Computing IN Choices THEN ... ENDIF
• Combine: union gives every subject chosen by either pupil, intersection gives the subjects they share, difference gives the ones chosen by the first but not the second.
• Define a record: TYPE Pupil / DECLARE Name : STRING / DECLARE YearGroup : INTEGER / DECLARE AverageMark : REAL / ENDTYPE
• Declare and use it: DECLARE Student : Pupil then Student.Name <- 'Aisha Khan'
• Make a table: DECLARE Pupils : ARRAY[1:30] OF Pupil, where Name is the key field used to search and sort.

Classes, objects, and choosing a type for a problem

A class is a template that defines a set of attributes (the data) and a set of methods (the procedures and functions that work on that data). An object is one instance of a class, created while the program runs, with its own copy of the attributes. Creating an object from a class is instantiation, and the method that sets up a new object is its constructor.

The point of a class is encapsulation: the attributes are declared private, so code outside the class cannot change them directly, and the public methods are the only way in. A withdrawal method can check that the amount is positive and that the balance is large enough before it changes anything, which a record cannot do because any code can assign to any field. Encapsulation also hides the implementation: the balance could be stored in pence rather than pounds, and the code that calls GetBalance would not have to change.

A class also allows one class to be built on another and inherit its attributes and methods, so a SavingsAccount can reuse everything an Account already does and add its own interest method. That is the practical reason classes are used for large programs, and it is why a class is the right answer when a question describes an entity that has behaviour as well as data.

Designing a type is a sequence of decisions, not a guess. List the data items the problem mentions, give each one a type, decide which of them belong to one entity, then ask what the program must do with them.

If the values are a closed list, use an enumerated type. If the question is membership of a collection, use a set. If it is one entity with several fields, use a record. If the entity also has operations that must protect its data, use a class. If the number of items is unknown until run time, use pointers to link them.

• Class name and attributes: CLASS Account / PRIVATE Balance : REAL / PRIVATE Owner : STRING
• Constructor: PUBLIC PROCEDURE New(OwnerName : STRING, Opening : REAL) sets Owner and Balance.
• Method that protects the data: PUBLIC PROCEDURE Withdraw(Amount : REAL) checks the amount and the balance before subtracting.
• Accessor: PUBLIC FUNCTION GetBalance() RETURNS REAL returns Balance without letting the caller change it.
• Create an object: DECLARE MyAccount : Account then MyAccount.New('J. Patel', 250.00)
• Call a method: MyAccount.Withdraw(40.00) - the attributes are never touched directly from outside the class.

File organisation: serial, sequential and random

Two ideas are examined together and must be kept apart. File organisation is the way records are arranged on the storage medium: the order they are written in and where each one sits. File access is the way the program finds a particular record when it wants it. A file can be organised one way and accessed in more than one way, and most lost marks in this section come from answering one question with the other.

A serial file is the simplest: records are written one after another in the order they arrive, with no ordering by any key. A new record is appended at the end. To find a record you must start at the beginning and read forward until you meet it, so on average you read half the file. Serial organisation is ideal for a transaction log or an audit trail, where every event must be kept in the order it happened and nothing is ever searched for by key; writing is fast because the record simply goes at the end.

A sequential file holds its records in order of a key field, such as an account number or a surname. Records are read in that order, and finding one record means reading every record before it, so the cost depends on where it sits. Inserting a record into the middle means rewriting the file, so in practice updates are done in a batch: a sorted transaction file is merged with the master file to produce a new master file. Sequential organisation suits payroll, billing and end-of-term reports, where most records are processed anyway.

A random file (also called a direct file) stores each record at an address calculated from its record key using a hashing algorithm. Records are fixed length so that the address can be computed exactly, and a record can be read or written without touching any other. The price is wasted space, because the file must have more slots than records to leave room for collisions, and the order of records is meaningless, so a sequential report has to be produced some other way.

Access follows from the organisation. Sequential access reads records one after another in the order they are stored and cannot skip any, which is the only way to read a serial file and the normal way to read a sequential file. Direct access jumps straight to a calculated location. A random file always uses direct access, because the hash computes the address.

A sequential file can also be read directly if the records are fixed length, because the position of record n is the header length plus (n - 1) times the record length. What it cannot do is find a record from its key without an index or a calculation.

Hashing: turning a key into an address

Hashing is the process of applying an algorithm to a record key to produce a record address, so that the record can be stored and found without searching. A good hash function is quick to calculate, always produces the same address for the same key, and spreads the keys evenly over the available addresses so that few of them land in the same place.

The commonest method is division: divide the key by the number of addresses and take the remainder, written key MOD n. Choosing n as a prime number, and not as a number that shares a factor with the keys, spreads the results much better; if every account number ends in 0 and n is 100, every record lands on an address ending in 0 and the rest of the file stays empty.

Folding splits the key into parts, adds the parts and takes the remainder, which uses every digit of the key. Mid-square squares the key and takes digits from the middle of the result. Truncation simply ignores part of the key and uses the rest, which is fast but distributes badly when the ignored part is the part that varies.

Here is the division method used on four account numbers with 97 addresses and a record length of 64 bytes. The record number is the remainder, and the byte address is the record number multiplied by the record length.

To write a record, hash its key, go to that address, and store the record if the slot is empty or already holds that key. To read a record, hash the key, go to the address and compare the key stored there with the key you hashed. If they match, that is the record; if they do not, the record you want was displaced by a collision, so you follow the same collision rule as the program used when it wrote the record. Storing the key inside the record is what makes this check possible, and it is why the key field is never omitted from a hashed file.

A collision happens when two different keys hash to the same address, and it is unavoidable because there are more possible keys than there are addresses. The usual fixes are to probe forward to the next free slot (open addressing), to keep an overflow area at the end of the file with a pointer chain from the collided slot, or to apply a second hash function and try again (rehashing). The more full the file becomes, the more collisions occur, which is why a hashed file is kept well short of full. Deleting a record needs care too: marking the slot empty breaks every later search that probes through it, so the slot is marked as deleted instead.

Binary floating point: mantissa, exponent and conversion

A fixed-point binary number with a fixed number of bits after the point cannot hold both very large and very small values in a useful range. Floating-point notation solves this the way scientific notation does in denary: the number is stored as a mantissa (the significant digits) multiplied by a power of two given by an exponent. In 9618 both parts are held in two's complement form, and the split between the bits given to each part is stated in the question - a common format is an 8-bit mantissa followed by a 4-bit exponent.

The mantissa is a fraction with the binary point assumed immediately after its sign bit, so a mantissa of m bits holds a value between -1 and just under +1. The exponent is a signed integer that says how far to move the point and in which direction: a positive exponent moves it right, making the number larger, and a negative exponent moves it left, making it smaller. The value is therefore mantissa x 2^exponent, and the same bit pattern means a different number if the split between mantissa and exponent is different.

Binary to denary. Split the pattern at the point given in the question, convert the mantissa as a two's complement fraction, convert the exponent as a two's complement integer, then multiply. For 01011000 0011 the mantissa is 01011000, which is positive and equals 0.1011 in binary, or 0.5 + 0.125 + 0.0625 = 0.6875. The exponent 0011 is +3, so the value is 0.6875 x 2^3 = 0.6875 x 8 = 5.5.

For 10011000 0011 the mantissa begins with 1, so it is negative: invert 10011000 to get 01100111, add 1 to get 01101000, which is 0.8125, so the mantissa is -0.8125. The exponent is +3, so the value is -0.8125 x 8 = -6.5.

Denary to binary reverses the process. Take -6.5: the magnitude 6.5 is 110.1 in binary, which as a fraction is 0.1101 x 2^3, so the exponent is 0011. Write the fraction as eight bits with a 0 sign, 01101000, then negate it by inverting and adding 1, which gives 10011000. The stored pattern is 10011000 0011.

Changing the allocation of bits changes two different things, and exam questions turn on keeping them apart. The mantissa bits set the precision: with m bits there are m - 1 significant binary digits, and values near 1 are spaced 2^-(m-1) apart. The exponent bits set the range: with e bits the exponent runs from -2^(e-1) to 2^(e-1) - 1. Giving bits to the mantissa takes them from the exponent, so the numbers become more precise but the largest and smallest values that can be held get closer together.

Normalisation, overflow, underflow and rounding error

A floating-point number is normalised when its mantissa has no redundant leading bits: the first bit after the sign bit is significant. For a positive mantissa that means the pattern starts 01; for a negative mantissa it starts 10. To normalise, shift the mantissa left one place at a time and decrease the exponent by 1 for each shift, until the required pattern is reached - which keeps the value the same, because moving the point one place right in the mantissa is balanced by halving the multiplier.

Take 00010110 0100. The mantissa is 0.0010110 = 0.171875 and the exponent is 4, so the value is 2.75. The mantissa starts 00, so shift left twice: 01011000, and the exponent falls from 4 to 2. Check it: 0.1011 x 2^2 = 0.6875 x 4 = 2.75.

For a negative number, 11011000 0101 has mantissa -0.3125 and exponent 5, giving -10.0; it starts 11, so shift left once to 10110000 and drop the exponent to 4, and -0.625 x 2^4 gives -10.0 again.

There are two reasons for normalising. The first is precision: every leading zero (or leading one, for a negative number) occupies a bit that could have held a significant digit, so an unnormalised number stores fewer useful bits than its mantissa allows and loses accuracy. The second is that normalisation makes the representation unique, so each value has exactly one bit pattern; without it, the same number could be stored in several ways, and comparing two floating-point numbers by comparing their patterns would give the wrong answer.

Overflow happens when the exponent needed is larger than the exponent field can hold, so the number is too large to represent; in the 8/4 format anything above 127 or below -128 cannot be stored and the program must raise an error rather than store a wrong value. Underflow happens at the other end: the exponent needed is below the smallest the field can hold, so the number is too small in magnitude to represent and becomes zero. In the 8/4 format the smallest positive normalised value is 0.1 x 2^-8 = 0.001953125, so a calculation that produces 2^-10 underflows to zero.

Rounding error is the third consequence and the most common in practice. Only fractions that are sums of powers of two can be stored exactly, so most denary fractions are approximations. The denary 0.1 is 0.0001100110011... in binary, a recurring fraction, so with an 8-bit mantissa it is held as 01100110 1101, which is 0.099609375 - close, but wrong by about 0.00039. Add it ten thousand times and the error is visible in the answer; test whether two such values are equal and the test can fail although the arithmetic was correct.

Rounding (choosing the nearest representable value) is more accurate than truncation (discarding the extra bits), but neither removes the error, and adding a very small number to a very large one can lose the small number altogether.

• Normalise: shift the mantissa left, decrease the exponent by 1 each time, stop at 01 for a positive mantissa and 10 for a negative one.
• Never shift so far that the sign changes: 01111111 shifted left becomes 11111110, a negative number, so that value cannot be normalised further.
• Largest positive in 8/4 is 0.1111111 x 2^7 = 127; smallest positive normalised is 0.1 x 2^-8 = 0.001953125.
• Overflow: the exponent needed is too large for the exponent field - raise an error.
• Underflow: the exponent needed is too small for the exponent field - the value becomes zero.
• Rounding error: the stored pattern is the nearest representable value, not the exact number, so equality tests and long sums of fractions can be wrong.