$Revision: 1.12 $ $Date: 2010/04/07 07:57:43 $
Software Construction is not a science (or is it?)
What is Abstraction?
Oops and beyond
Kinds of Abstraction
ANTLR, DOM, and SAX
Layers
An Organising Principle
Abstractions in programming: data, type, procedure, contracts
Abstractions in the Java language: class inheritance, generics, enhancements
The Java library Collections
framework
Design patterns: visitor, strategy, composite, model-view-controller
© These notes support 1 or 2 lectures based on material created by Chris Johnson for the ANU COMP2100 and COMP2500 Software Construction course in 2009. There is a separate presentation in Open Document Presenter.
A "science" is a body of organised knowledge, with predictive power. The classical sciences: physics, chemistry, biology are based on deep underlying theories (not always just one theory: physics has two areas of theory at present, General Relativity which accounts for interactions and motions of macro bodies, at normal speed up to extremely fast speeds, and accounts for gravity; and the Standard Model of atomic and sub-atomic scale particles and forces, which accounts for all the strong nuclear, weak nuclear, and electromagnetic forces, but not for gravity.) Biology has the underlying grand theory of Natural Selection which explains and predicts a grand sweep of the realm of living things. A science need not be experimentally based: a common view of the sciences as inductivist (reasoning from observation to explanatory theories) fits the natural sciences to this, and sees them as having paradigms that rely on relating theory to measurement of the natural world or constructed experimental situations. But mathematical sciences have modelling and constructive power that can describe quite unnatural or artificial – constructed – situations. Computer science ("the study of algorithms" [Schneider and Gersting p. 4]) has limited explanatory power (algorithms: complexity and computability, formal languages and grammars as a mathematical description). It does include a constructive aspect ("the task of the computer scientist... includes... design and develop algorithms to solve important problems... computer systems that are able to execute [them]...[and] programming languages and translating algorithms ... so that they can be executed by the hardware."[Schneider and Gersting p.4], but Computer Science does not have any useful predictive or explanatory power for much of what we need to know and apply to construct software (apart from stating what kind of software we should not try to construct: things that are non-computable, such as a program that tries to solve the Halting Problem.) So I will use the term "computing" rather than "computer science" from now on. It's a broader discipline.
What Computing does have is an organising principle – not as strong as a grand theory, and without predictive power, but it serves to unify many aspects of software and other aspects of computing as well. This principle is twofold: that of abstraction and decomposition.
Steve McConnell (of Code Complete and IEEE Software Best Practices column) starts from what we use abstraction for in programming:
Hierarchies and Abstraction
Two of the most effective general means of managing complexity are the use of hierarchies and abstractions.
A hierarchy is a tiered, structured organization in which a problem space is divided into levels that are ordered and ranked. In a hierarchy, you handle different details at different levels. The details don't go away completely; you simply push them to a different level so that you can think about them when you want to rather than all at the same time. Hierarchies come into play most obviously in the module hierarchy of a functional design, but they also come into play in inheritance hierarchies in object-oriented design, nested data-structures, and in many other cases.
Using hierarchies comes naturally to most people. When people draw a complex object, such as a house, for example, they draw it as a hierarchy. First they draw the outline of the house, then the windows and doors, then additional details, as desired (Herbert Simon, The Sciences of the Artificial, MIT Press, 1969). They don't draw the house brick-by-brick, shingle-by-shingle, or nail-by-nail.
Abstraction is also a mean of reducing complexity by handling different details at different levels. Any time you work with an aggregate entity, you're working with an abstraction. If you refer to an object as a "house" rather than a combination of glass, wood, and nails, you're making an abstraction. If you refer to a collection of houses as a "town," you're making another abstraction. Abstraction is a more general concept than hierarchy. It can reduce complexity by spreading details across a loose network of components, for example, rather than among a hierarchy’s strictly tiered levels.
Abstraction means: "to forget information and consequently to treat things that are different as if they were the same... in the hope of simplifying our analysis by separating attributes that are relevant from those that are not." [Liskov p.4]
Decomposition means (systematically) breaking our views and descriptions into parts. In computing we describe parts of many different systems in a fundamentally similar way: as closed entities (containing complexity within them) with a restricted interface, and relate different entities through these interfaces. The networks of entities are our descriptive tools, whether they are classes, types, programs, methods, or objects, depending on our point of view. We decompose our descriptions into separate entities. We group these entities into layers or larger scale closures, as one way of doing abstraction on the description: the groups of entities are combined to usually have a smaller interface to the outside world than the sum of their individual interfaces. That's abstraction.
Some other points of view:
A model is an abstract representation of some real object or situation. By abstract we mean that the model does not attempt to represent every single feature of the object or situation. Instead it presents a simplification of the real situation by focusing just on certain features that are deemed appropriate for the problem the model purports to solve.
[Morelli p.13]
In general, abstraction is the process of focussing only on the essential characteristics of an entity. A class provides a powerful abstraction mechanism for object-oriented design and programming. A class defines an abstraction in the problem or solution domain. ... Because it defines both state and behaviour, a class provides a more powerful abstraction mechanism than a procedure or a data record does.
[Richter, p 5]
Abstraction is a mechanism by which we understand things. Expressing a solution in terms of math, for instance, means we really did understand the problem. We didn't just hack a bunch of loops to try out special cases. There is always the temptation to provide just the solution to a particular problem. However, unless we try to generalize and see the problem as an example of a general class of problems, we may miss important parts of the solution to our particular problems and fail to find concepts and general solutions that could help us in the future. If somebody has a theory, such as a theory for matrix manipulation, you can just work at the level of those concepts and your code will become shorter, clearer, and more likely to be correct. There's less code to write, and it's easier to maintain.
I believe raising the level of abstraction is fundamental in all practical intellectual endeavors.
Stroustrup, inventor of the C++ language
The Oops program system provides many examples of abstraction and it also supplies several pointers to the wider domains of what is known about computing.
The Oops program is described in the specification and design documents in some detail, and you are familiar with it at the detailed level of knowing something about the program code. Here we take a look zoomed further back, looking at its abstractions.
Firstly: Oops is really a processing box that takes as input a document in ODF, which is an archive containing XML representation of a document, and processes it to produce text, HTML, and other forms of output. That's the most abstract black box view.
A slightly closer look: Oops has an input side (the scanner and parser), a data component (the tree), and produces output in a set of renderers.
The scanner and parser in Oops are hand-coded. This is not usually a good idea when constructing programs like this; there are many tools that can do this job more reliably and for less programmer effort. See the descriptions of ANTLR, SAX and DOM below.
fig 0.2. The Oops tree data structure for XML:
an example of
Composite design pattern
When we look a bit closer we see the internal
data structure. The tree package defines the data structures
used to represent the document in memory.
This tree is very similar to the expression trees we studied in
earlier lectures, except that the leaf elements contains String
data, rather than integer values, and the non-leaf nodes can have
any number of children instead of being fixed at one, two, or
three. In the Oops tree the there is only one type of
XmlContainerElement nodes rather than the different
Expression tree types (Addition, Multiplication, Conditional etc), but
they conceal different types in a further abstraction: each one has a
Strategy object that tells us which type of ODF node it represents.
But in both the Oops tree and the Expression tree the children are also the same tree node
types: they are examples of the same abstract recursive data structure.
We studied different ways of defining the abstract procedures for traversing the tree
structures (preorder, inorder, postorder, breadth-first) over
Expression trees. We implemented those procedures in different ways,
showing how "traversal" is an abstraction over several different
implementation choices. In Oops we used the Visitor procedural
abstraction to do inorder traversals (for example, HTMLRenderer's
visitDocument method produces output for the head of the document,
then visits its children – the contents of the document – and then
produces output for the tail.
You can now see how in general Visitors could be
applied to either of these trees, or to other tree structures of
similar kind.
exam hint
Some of these abstractions are seen and done in the features of the programming language: defining methods, using generics, using inheritance. Others are not directly supported by the languages we use, but are described in general by Design Patterns [Gamma]
The basic form of procedural abstraction is to collect a group of programming language statements together and give it a name. This is what Dijkstra calls the "closed subroutine" in 1970s terminology, and says (in a deep discussion on this topic in 1972) "if closed subroutines had not been invented twenty years ago, this would have been the time to do it!". [Dijkstra p46]. A "closed subroutine" is exactly what goes under the name of "method" in Java.
Describing and defining methods is a form of abstraction that is sometimes called procedural abstraction. By defining a certain sequence of actions (a procedure) as a method, you encapsulate those actions under a single name that can be invoked whenever needed.
[Morelli, p.78]
This is also extended to the addition of parameters to the routine, whether these are data values, variables, or types: this is what Liskov calls abstraction by parameterisation: "it generalizes modules so that they can be used in more situations". [Liskov p.7].
I extend this notion to include the kind of abstraction represented by the Visitor design pattern (Design Patterns describes this as a behavioural pattern [Gamma p.331]).
This interface is actually defined in Oops in the abstract class
XmlContainerStrategy, called from the
XmlContainerElement.accept method.
There are other ways this could be defined.
A single visitor is a collection of operations over a disparate collection of data types, that are unified under a common interface, to state that the class implements a method
public void accept(Visitor v);
The visitor is a class that I write that by the pattern of
the interactions between its methods and this collection of other
classes (following the visit and accept
methods) weaves the complex operation of visiting and operating on
each object of these types in a connected graph structure to achieve
my goal: that is, I have created an abstraction which encapsulates a
complex sequence of operations in a very generalised way, and one that
can be given a name, and invoked. In Oops:
interface Visitor {
public void visitAnchor(XMLElement a);
public void visitHeading(XMLElement h);
public void visitParagraph(XMLElement p);
}
class HTMLRenderer implements Visitor {...}
// HTMLRenderer is my named procedural abstraction
...
root.accept(new HTMLRenderer())
// this invokes that procedural abstraction - and it executes
Although the use of visitor corresponds to a procedural abstraction,
unfortunately its implementation is very exposed. The various forms of
traversal are implementations of a higher level abstraction, that of
"traverse and operate". The abstraction has several different
implementations that we have studied: whether by the Visitor pattern
of methods defined in an
external visitor class, or by recursive methods defined in the visited
nodes, or an iterative method defined for the group of nodes.
We study the different implementations not because they have
significantly different run-time performance (they don't, though the
Visitor might have twice the number of method calls in its
alternating accept and visit calls.) We
studied them because they have different properties in the domain of
software construction: they have different flexibility and ability
for reuse of the program and classes in changing circumstances, such
as adding more types of visited nodes, or more types of operations;
and for the comparison between the explicit management of context in
the iterative form versus the implicit management in the recursive
forms.
But exposing the implementation is unfortunate. The OO programming languages we use do not support Visitor traversal easily (which is why Design Patterns is an important book for OO programmers: they need to know how to do these things, not just the abstraction of what to do for the program. It's as if we had the concept for the closed subroutine as an abstraction, but were still forced to write the implementation in assembler code every time (create a stack frame structure, evaluate and save the values of parameters, save a return address, and jump into the subroutine code...). Here we are at a higher layer of abstraction, but we have to write clumsy methods and alternating calls for something which should surely have a more powerful way of being expressed. This is a reminder to keep the abstract concept distinct from the implementation and to make as much use of the supporting features of the programming language as we can; the abstraction provides us with a powerful way to think about solutions to problems, even though the languages we use lag behind. (Using a first rate functional language may provide implementations of many behavioural patterns more directly, and avoid the need for a "Book of Patterns" altogether, but that's another path to abstractions that I won't travel here [thanks to Clem Baker-Finch for this observation].)
Why do I say it's clumsy and exposed? compare what you have to do
to program a visitor with what you do to use an iterator.
The iteration abstraction is
a well defined abstract idea: do something to each member of a
collection in turn. It is well-supported in Java,
being defined in the Iterable and
Iterator interfaces and directly accessible in the enhanced
for-each statement (see below, Java Collections Framework). You can
hide the details of how the iteration is done for a new type that you
define. You can't hide things in the same way for a visitor.
Data abstraction is what Liskov calls abstraction by
specification: it "abstracts from the implementation details (how
the module is implemented) to the behavior users can depend on"
[Liskov p. 7].
This is the form of abstraction we
have seen in many class definitions, in particular the
Stack example: the behaviour is made visible and
available to users of the class through visible methods such as
push, pop, top and
isEmpty; the implementation is hidden inside the class
(applying the principle of information hiding). We have
tended to study both the behaviour and the implementation at the same
time, but you need to keep this difference in intention very clear.
The Oops program is a demonstration piece, for teaching purposes. Although it's fun to write programs like this (even more fun when they're smaller), for production purposes a programmer should know the appropriate tools that have already been written and tested. The front-end of Oops has the job of turning an XML document into an instance of a tree data structure. This is a classical problem in two ways: (1) recognising and transforming structured input text data is the domain of formal language recognisers, which implement algorithms generally known as (lexical) scan and parse; (2) recognising and handling XML in particular is a popular requirements in recent times, and has its own special purpose tools.
Scanning and parsing has been implemented in the scanner and
parser modules in Oops, where special cases of the
general purpose algorithms have been hand written.
Compilers for programming languages use exactly similar methods: the
first phase generally is lexical analysis, recognising tokens in the
input that can be described by regular expressions; and the second
stage is parsing, recognising structures in the sequence of tokens,
usually building an abstract syntax tree as a result. Ancient Unix
tools lex and yacc (which stands for Yet
Another Compiler Compiler) exist to do this, using formal
mini-languages to describe what is to be recognised, embedded with
action statements (written in C) saying what to do when a particular
construct is successfully recognised. A modern version of these tools is
ANTLR (the "LR" derives from the name of the particular
"LR" parsing algorithm that it uses, in common with yacc). I
have written most of the Oops front end in ANTLR, and it may be part
of the distribution version in future.
The box labelled "scanner and parser" in the diagram would then be replaced by a box labelled "ANTLR", driven from a mini-language specification of ODF tags in XML. This is pre-processed by the ANTLR tool and turned into Java code, which is then compiled and executed with the Oops program.
The second alternative is to focus on the fact that it is XML input
and use an XML tool.
Two of these are DOM and SAX, which can handle the entire job
of reading, parsing and tree building for XML. We did not use these
for Oops because it's a good idea to understand the fundamental
processes involved in handling a specific example like ODF in our
own tree structure, before learning to use the more advanced abstract
tools. Again, note that a production programmer might well choose to
learn and use DOM and/or SAX for the Oops task.
They come in a few variants; here is one description from Java documentation:
The Document Object Model (DOM) is a set of interfaces defined by the W3C DOM Working Group. It describes facilities for a programmatic representation of a parsed XML (or HTML) document. The DOM Level 3 specification defines these interfaces using Interface Definition Language (IDL) in a language independent fashion and also includes a Java Language binding.
The JavaTM API for XML processing specification includes by reference both the abstract semantics described for the DOM Level 3 Core Recommendation interfaces and the associated Java Language binding.
The Simple API for XML (SAX) is a public domain API developed cooperatively by the members of the XML-DEV mailing list. It provides an event-driven interface to the process of parsing an XML document.
An event driven interface provides a mechanism for "callback" notifications to application's code as the underlying parser recognizes XML syntactic constructions in the document.
These tools are supplied in
the Java library: DOM (Domain Object Model) in org.w3c.dom
and SAX (Simple API for XML) in org.xml.sax.
The Java API for XML Processing (JAXP) is for processing XML data using applications written in the Java programming language. JAXP leverages the parser standards Simple API for XML Parsing (SAX) and Document Object Model (DOM) so that you can choose to parse your data as a stream of events or to build an object representation of it. JAXP also supports the Extensible Stylesheet Language Transformations (XSLT) standard, giving you control over the presentation of the data and enabling you to convert the data to other XML documents or to other formats, such as HTML.
The description I quote above also mentions XSLT (Extensible Stylesheet Language Transformations). XSLT is a transformation specification language in its own right, defined by the World Wide Web standards group W3C [W3C Specification of XSLT]. There are several implementations of XSLT as a standalone tool as well as embeddings in various programming languages. XSLT can be studied in the ANU course COMP3410 COMP3410 IT in eCommerce.
The third alternative for implementing OOPS is to use XSLT to replace the whole
Oops program. An XSLT specification
says how to transform an XML input such as ODF document into an XML or
HTML output, selectively: which is the whole function of
Oops. See fig. 4
In this
sense, using XSL as a specification of the transformation raises the
level of abstraction as far as we can go for this problem. The XSL
specification has almost no implementation concerns, only the relationship of
input to output. How much more abstract can you get?
Layering of abstractions is a very common way to structure a problem. In a layered architecture each component contains inner complexity; it has a simple interface. In the usual way each component only interacts with other components through their interfaces. But there is an additional constraint here: the components are in a sequence bottom to top, and each one only interacts with its immediate next up and immediate next down.
An important example is the layering of network protocols, as seen in the TCP/IP protocol stack.
| applications |
| transport |
| network |
| datalink |
| physical |
| mail, ftp, http etc. | |
| TCP | UDP |
| IP | |
| 802.11g | |
| wireless | |
Another example is the layering described in Daniel Frampton's guest lecture: the Java application program over the Java Virtual Machine over the assembly language/register transfer view of an actual computer, and then further layers down, over digital signalling, over electronic components and connectors, over solid state physics, over quantum mechanics of electrons...
The organising principle? Computer science makes very wide use of organising collections of things of many kinds and at many levels, into sets of closed entities with well-defined interfaces, and limiting the entities to interact through the interfaces. The description of the interfaces, and the relationships of the entities through them, are the key paradigm of so much of what we use in computing. This is not a grand rigorous predictive theory, it is not quantifiable, it can't be experimented with as a natural science. It's just a description of the kind of designs and descriptions that we use extensively, and the urge to draw boxes (or blobs of other shapes) and lines connecting them, with attributes labelling them, is very widespread.
Bertrand Meyer is an important contributor to software engineering and inventor of a object-oriented programming language Eiffel that carries a lot of good and powerful ideas. He has a lot of useful argument on abstraction in chapter 6 Abstract Data Types of his book Object-Oriented Software Construction [Meyer, p121 ff] which is available in the ANU library. Recommended.
We don't go into pre- and post-conditions in this course in 2009, but probably should have: see the additional lecture notes on Code Quality with Static Code Analysis.
Meyer is a strong exponent of Design by Contract, which is
the concept that a method and class should be characterised not only
by its type signature (that is, the name of the method, its return
type, and its parameter types; or the class by its name and collection
of methods) but by a statement of logical pre-conditions,
post-conditions, and invariants. The pre- and post-conditions of a
method form a contract: they state what the method expects to hold
true before it starts executing (for example, that the stack is not
empty) and what it will ensure becomes true after it has executed (for
example, that the stack contains one less element, and furthermore
that it is the "top" element that has been removed. I'm describing
the method stack.top, of course. This contract is what
the implementation of the method should conform to, that is, the
detailed design and coding of the method body. This idea can be
extended to methods at all layers of abstraction. The chain of
contracts forms a description of the properties of the program in the
more abstract
domain of mathematical logic, and it is in principle able to be checked by processes of
mathematical proof.
You are already familiar with class inheritance: "the type hierarchy which allows us to abstract from individual data types to families of related types" [Liskov p. 12]. The type hierarchy is a defining characteristic of object-oriented programming languages.
Generic classes are a quite distinct idea. Generics in Java are an example of abstraction by parameterisation: a general class definition is defined with one or more of its component types provided as parameters, just as a method with parameters provides named values as parameters. Just as the naming of method parameters with types gives us type safety in the method, it is possible to constrain a generic type parameter to belong to a group of types, with properties that can then be used in the body of the generic class with full safety and no further type checking.
A simple example is our class Tree for binary trees:
class Tree -- programmer defines the class with a specific type of element e.g. Integer or String -- TreeInt and TreeString are different classes
Generic:
class Tree<T> -- T is a generic type of the tree elements
-- elements will be of any type T
Tree<Integer> and Tree<String>
are different classes.
If we want to do ordering in the tree we will need to make comparison
of elements for less than, equals, greater than: we need to have
defined (or predefined, provided)
some kind of ordering over the element type.
If the tree is defined specifically to be a tree of Integers we can
use '<'; if it is a tree of Strings we can use the
String function compareTo. For a generic tree we need
some way to generalise – to abstract over the idea of
"comparison" that these two different types provide.
For a generic tree the element type needs to be compared. We can
specify that it extends a class (or implements an interface, using the
same extends notation)
class Tree<T extends Comparable>
...
T element;
...
public boolean find (T target) { ... switch
(target.compareTo(element))...
The predefined class Integer implements the interface
Comparable, and so does String. Any type
that I want to define for myself and use as an element type in my
generic tree class only need to be written to implement
Comparable, which is quite easy [see the interface
definition
Java 5 Comparable interface]
There is time for only a brief mention of the Collections framework here. More details are in the Java API.
The Collections framework provides a group abstraction. One significant feature is iteration, which allows us to use the Java 5 language feature of the enhanced for-loop:
Vector XX;
for (e : XX) { .. do things with e ... }
In this control structure the variable (e) takes on values from the
Vector XX, and there is no need to handle the initialisation,
completion test, and increment steps explicitly. The for-loop has been
abstracted to this form, which is the very simplest expression of the
intention: "do this for every element of the collection XX".
The implementation only requires the
structure to implement the interface Iterable.
interface Iterable<T> {
// allows an object to be the target of a foreach statement
Iterator<T> iterator();
// returns an iterator over a set of elements of type T
}
interface Iterator<E> {
boolean hasNext(); // returns true if the iteration has more elements
E next(); // returns the next element in the iteration
void remove(); // removes the last element returned by the iteration
}
[Java Platform SE 5 Iterator and Iterable]
The other important aspect of the Collections framework is the systematic separation of behaviours, using their common names (Map, vector, List, Set), from a variety of implementations. The program constructor can choose a behaviour for its use by the rest of the program, and choose an implementation for its performance (particularly its speed and space requirements). This is behavioural abstraction raised to a systematic level. The Collections framework is about as far as the Java paradigm can go with this. In future, I speculate that we might expect a much more refined and systematic approach that perhaps allows users to create their own frameworks in a systematic, named way: as far above this first attempt at a framework as generic types are above assembly code procedures. This is a real challenge for research into programming language design.
Extracts from the Java 5 Collections overview.
Collection Interfaces
There are nine collection interfaces.
The most basic interface isCollection.
Five interfaces extend Collection:
- Set
- HashMap
- List
- SortedSet
- Queue
- BlockingQueue
The other three collection interfaces, Map, SortedMap, and ConcurrentMap do not extend Collection, as they represent mappings rather than true collections. However, these interfaces contain collection-view operations, which allow them to be manipulated as collections.
Java Collections Framework Overview
The Map interface provides three collection views, which allow a map's contents to be viewed as a set of keys, collection of values, or set of key-value mappings.
- Collection Interfaces
- Represent different types of collections, such as sets, lists and maps. These interfaces form the basis of the framework.
- General-purpose Implementations
- Primary implementations of the collection interfaces.
- Legacy Implementations
- The collection classes from earlier releases, Vector and Hashtable, have been retrofitted to implement the collection interfaces.
- Special-purpose Implementations
- Implementations designed for use in special situations. These implementations display nonstandard performance characteristics, usage restrictions, or behavior.
- Concurrent Implementations
- Implementations designed for highly concurrent use.
- Wrapper Implementations
- Add functionality, such as synchronization, to other implementations.
- Convenience Implementations
- High-performance "mini-implementations" of the collection interfaces.
- Abstract Implementations
- Partial implementations of the collection interfaces to facilitate custom implementations.
- Algorithms
- Static methods that perform useful functions on collections, such as sorting a list.
- Infrastructure
- Interfaces that provide essential support for the collection interfaces.
- Array Utilities
- Utility functions for arrays of primitives and reference objects. Not, strictly speaking, a part of the Collections Framework.
The design of Oops includes several examples of Design Patterns:
Visitor, Composite, Strategy. We have
discussed Visitor above. The Composite pattern is what was used to
define the tree data structure. The data represented in the tree is
Open Document Format (ODF), which is an instance of XML, but the
tree data structure is a data abstraction: it
hides the differences between different XML element types in a
simpler structure using only three classes: XmlElement,
XmlContainerElement, and XmlDataElement.
The elements in ODF are represented by another abstraction: we
used the
Strategy pattern to associate a meaningful set of node types
(paragraphs, headings etc) with particular
XmlContainerElements, using a mapping we defined for
the purposes of Oops (check out the different tags for
headings and other elements described in the notes on
Specification of OOPS).
Another design pattern is called Iterator: it's a way of doing what the Java Collections framework does, but with other types, and in other languages. It's an abstract generalisation of the iteration idea of doing something to each member of a collection of things in turn (see above).