Imperative Programming II: 2011-2012
OverviewThis course starts with an introduction to the basic concepts and techniques of modular program construction and Object-Oriented Programming (OOP). It continues with two modest-sized case-studies that introduce some of the basic OOP programming idioms (Design Patterns) in realistic settings.
There are three main ideas: encapsulation, that programs should be built from objects that satisfy a coherent specification and hide the details of how that specification is implemented; object identity, that each object has a distinct identity, so that multiple objects can co-exist and interact with each other; and polymorphism, that objects that implement the same interface can be used interchangeably to give a variety of behaviours.
There is a correspondingly heavy use of practicals to develop understanding of OOP in general, and the use of Java in particular.
1: Introduction: Objects, Classes and Abstract Data Types
 Object-Oriented Programming. A program for a simple editing task. Abstraction and Decomposition. Rewriting the program to use an abstract data type (ADT). Objects and methods. The Java language.
 How to specify an ADT. Abstract state space. Operations with pre- and post-conditions, illustrated by the Text example. Using the Text ADT.
 How to implement an ADT. Concrete state space, concrete invariant, abstraction function. Implementing operations, illustrated by the Text example.
 Features of object-oriented programming. Encapsulation. Alternative implementations. Exceptions.
2: Case study
[5-7] Introducing the Editor. Object-oriented design. Interfaces. Subtyping, polymorphism. Semantics of parameters in Java. Inner classes.
[8-10] Features of the Editor. Model--View separation, decoupling, inheritance, dynamic binding. The fragile base class problem.
[11-12] Extending the Editor. Undoing commands. Abstract classes; subtyping and polymorphism revisited. Cloning. Using a stack.
3: Immutable Abstract Types, Collections and Generics
 Immutable Abstract Types
 Programming with collections. Accessing all elements of a collection. Iterators.
 The Java Collections framework. Interfaces. Implementing Collections. Hash tables.
 Generic Programming. Type parameters. Generic classes and interfaces. Generic collections. The Map interface.
Lecture slides from the Course Materials part of this site. The 4up-part.pdf variants are suitable for printing.
The closest book in spirit to the course is:
- Barbara Liskov, Program Development in Java, Addison-Wesley, 2000, £41.99, ISBN 0201657686. Chapters 1-10 are especially relevant and provide a useful supplement to the lectures. (However, we shall be using a different convention for writing specifications and we shall emphasize programming examples more than this book. For more details on how to use this book see Mike Spivey's Notes on Liskov's book.)
We will not spend much time on the details of the Java language or libraries, as these are not the main focus of the course (and covering them comprehensively would leave no time for anything else!). A handy reference for language details is:
- Peter Sestoft, Java Precisely (2nd ed.), MIT Press, 2005, £12.95, ISBN 0262693259.
This book will be very useful for the practical exercises. The most recent edition covers the extensive new language features introduced in Java 1.5 (= Java 5.0), including generics.Optional
Mike Spivey's notes are very full, and highly illuminating. They were originally designed as handouts for his lectures when this course was taught in the second year, so they are very slightly out of date with respect to this year's course material. They are available on the Course Materials part of this site.
For reading around the course, I recommend a number of other books. Encourage your college library to get these.
First, some people might enjoy the quirky approach of:
- Kathy Sierra & Bert Bates, Head First Java, O'Reilly, 2005, £31.95, ISBN 0596009208.
This book is a much more serious text book than it appears and you might find it a helpful way to learn.
A sound and thorough introduction to Java is:
- Pat Niemeyer, Learning Java (3rd ed.), O'Reilly, 2005, £31.95, ISBN 0596008732.
Earlier editions of this book will be almost as useful, but only the third edition covers generics.
The following book is about restructuring programs to make them clearer (the program maintenance counterpart of modular design):
- Martin Fowler, Refactoring: improving the design of existing code, Addison-Wesley, 2000, £37.99, ISBN 0201485672.
This book helps to bring home the real distinctiveness of the object-oriented approach to programming, compared to standard procedural programming, and should help you develop the skill of designing for clarity and robustness.
The following books about programming more generally would also be good companions to the course:
- Jon Bentley, Programming Pearls (2nd ed.), Addison-Wesley, 2000, £21.99, ISBN 0201657880.
- Brian W. Kernighan and Rob Pike, The Practice of Programming, Addison-Wesley, 1999, £28.99, ISBN 020161586X.