Thinking abstractly

Overview

Recall questions on abstraction and why it is needed, representational abstraction and generalisation, layers of abstraction, abstract data types, models that discard the wrong detail, devising abstract models, and abstraction compared with decomposition.

What you need to know

Answer each one before you reveal it.

Questions from this subtopic

Each one with the model answer underneath.

1. 1

   What is abstraction?

   Model answer

   Abstraction is the process of removing or hiding detail that is not relevant to the problem in hand, so that what remains is only what you actually need to reason about or to work with. It is deliberate and selective: the discarded detail still exists in the real system, it is simply not represented. The London Underground map is the standard illustration. It throws away true distances, the curvature of the tunnels, the surface geography above them and everything about the streets, and keeps only stations, the lines they sit on, their order along each line, the interchanges and the fare zones. That is exactly the information a passenger needs to decide which train to board and where to change, and it is far easier to read than a geographically accurate map would be. Two related senses of the word also appear in computing: procedural abstraction, where a subroutine hides how a job is done behind a name and a parameter list, and data abstraction, where a structure is described by the operations it supports rather than by how it is stored.

2. 2

   Why is abstraction necessary? Give reasons that go beyond making things simpler.

   Model answer

   Because of human limits: a modern system is far larger than any person can hold in mind at once, so it can only be worked on if most of it can be safely ignored while you concentrate on one part. Because of tractability: a full-detail model of a real situation is often impossible to build, too slow to compute, or requires data nobody has, so a simplified model is not a compromise but the only option, as with weather forecasting, which models the atmosphere as a grid of cells rather than as individual molecules. Because of division of labour: an agreed abstraction is an interface, and once two teams agree on it they can work independently. Because of change: if the detail is hidden, it can be replaced without disturbing anything that depends on the abstraction, so a database can be moved to different hardware without every application being rewritten. Because of reuse and generality: a sorting routine that takes any comparable items is useful everywhere, whereas one written for a specific record layout is useful once. And because of communication: an abstraction gives people a shared vocabulary, so saying queue conveys a precise set of behaviours without describing an implementation.

3. 3

   Distinguish between representational abstraction and abstraction by generalisation.

   Model answer

   Representational abstraction means producing a representation of a situation with unnecessary detail removed, keeping only what matters for the purpose. A wiring diagram of a house is a representational abstraction: the wires and sockets are shown, the colour of the walls is not. Abstraction by generalisation, sometimes called categorisation, means grouping things by shared characteristics and working with the group rather than the individuals. Recognising that a bus timetable, a train timetable and a ferry timetable are all instances of a scheduled service with a route, a set of stops and a set of departure times is generalisation, and it lets you write one program that handles all three. The two do different jobs. Representational abstraction reduces the detail within one thing; generalisation reduces the number of distinct things you have to handle. Both appear in ordinary programming: defining a class for Vehicle with subtypes for Car and Van is generalisation, while deciding that the Vehicle record needs a registration and a load capacity but not the colour of the upholstery is representational abstraction.

4. 4

   Explain what is meant by a layer of abstraction, using a real example.

   Model answer

   A layer of abstraction is a level of description that presents a defined interface to the level above and relies on the interface offered by the level below, without either level needing to know how the other is implemented. Networking is the clearest example. An application sends a message to a named service; the transport layer turns that into a reliable stream of numbered segments and handles retransmission; the network layer turns segments into packets and decides which router to send each one to; the link layer turns packets into frames on a particular medium; and the physical layer turns frames into voltages, light pulses or radio. A web browser is written entirely in terms of the top layer and works unchanged over copper, fibre, WiFi or a mobile network, because each layer hides the one below. The same pattern appears in the progression from a high-level language, through the compiler, to machine code, to microarchitecture, to logic gates, to transistors; and in file systems, where a program opens a file by name and never learns which blocks on which platter hold it. The benefit is independence: any layer can be replaced as long as its interface is preserved.

5. 5

   How does writing a subroutine count as abstraction?

   Model answer

   Because it separates what a piece of code does from how it does it, which is procedural abstraction. Once a routine is written and named, the caller works with three things only: the name, the parameters it expects and the result or effect it produces. Everything inside is hidden. A programmer calling a routine that finds the shortest route between two junctions needs to know what to pass in and what comes back; whether it uses a particular search algorithm and what data structure holds the frontier is not their concern, and if the routine is rewritten to use a faster algorithm every caller benefits with no change. The abstraction is also what makes reasoning possible: a program of forty thousand lines cannot be understood line by line, but a program built from named routines each of which can be understood in isolation can be. The requirement for this to work is that the routine really does hide its internals, which means no hidden dependence on global state and no surprising side effects; a routine whose behaviour depends on something the caller cannot see is a leaky abstraction and gives back most of the benefit.

6. 6

   A stack is described as an abstract data type. What does calling it abstract actually mean here?

   Model answer

   It means the stack is defined by its behaviour rather than by how it is stored. The definition says there are operations to push an item on, to pop the most recent item off, usually to peek at the top and to test whether it is empty, and that items leave in the reverse of the order they arrived, last in first out. Nothing in that definition says how the items are held. Underneath, the same behaviour can be provided by a fixed array with an integer index recording the top, by a dynamically sized array, or by a linked list where pushing means adding a node at the head. A program written against the abstract definition works with any of them. The practical value is twofold. First, you can reason about correctness at the level of the operations, so you can argue that a bracket-matching routine works without knowing the storage. Second, the implementation can be swapped for performance reasons without touching the callers, for example moving from an array to a linked list because the maximum depth turned out to be unpredictable. The abstraction does still leak in one respect worth stating: an array-backed stack has a fixed capacity and can overflow, and that is a real difference the caller may need to handle.

Other ways to work this

The same content, four other ways.

What is inside Levo

Six ways to work the same material.