Abstraction and automation revision notes

Abstraction and information hiding

Abstraction removes detail that is not needed for a particular purpose. Representational abstraction removes unnecessary details from a representation. Abstraction by generalisation or categorisation groups things by common characteristics, producing a hierarchical relationship of the “is a kind of” type. Information hiding hides every detail of an object that does not contribute to its essential characteristics.

Types of abstraction

Procedural abstraction represents a computational method. When the actual values used in a computation are abstracted away, the result is a computational pattern or method: a procedure. Functional abstraction hides the particular computation method. It goes beyond procedural abstraction: the method itself is disregarded so that the result is a function rather than a procedure.

Data abstraction hides how data is represented. This allows new data objects to be constructed from previously defined types and separates how a compound data object is used from how it is built. For example, a stack could be implemented using an array and a pointer for the top of the stack. The user of the stack need not rely on those implementation details.

Problem abstraction or reduction removes details until a problem is represented in a form that can be solved, because it reduces to a problem that has already been solved. This is different from information hiding: problem abstraction changes the representation of the problem, whereas information hiding conceals implementation details of an object.

Decomposition and composition

Procedural decomposition breaks a problem into sub-problems. Each sub-problem performs an identifiable task and may itself be subdivided. This supports clearer algorithms and makes it easier to reason about separate tasks. Composition abstraction combines procedures to form compound procedures. Data abstractions can also be composed by combining data objects into compound data, such as a tree data structure.

Algorithms and automation

An algorithm is a sequence of steps that completes a task and always terminates. A simple algorithm can be expressed in pseudo-code using sequence, assignment, selection and iteration. It can be hand-traced, converted into high-level program code, and checked with test data and user feedback. A solution should be explained using logical reasoning about correctness and efficiency.

Automation puts models into action to solve problems. The model is an abstraction of real-world objects or phenomena. The process involves creating algorithms, implementing those algorithms as program-code instructions, implementing the models in data structures, and executing the code. Computer scientists must decide which details to include and which to discard, retaining the minimum detail needed to solve the problem to the required degree of accuracy.

Common errors

• Treating an algorithm as code only; an algorithm is a terminating sequence of steps and may be written in pseudo-code.
• Confusing procedural abstraction with functional abstraction: a procedure abstracts a computational method, while functional abstraction hides the particular method as well.
• Describing data abstraction as merely storing data; its key purpose is hiding representation details and separating use from construction.
• Assuming every real-world detail belongs in a model; abstraction requires selecting only the detail needed for the problem.
• Forgetting to justify correctness, termination or efficiency when explaining an algorithm.