Lecturer	Michael Spivey
Degrees	Schedule S1(CS&P)(3rd years) — Computer Science and Philosophy Part A Core — Computer Science Part A — Mathematics and Computer Science Schedule A — MSc in Advanced Computer Science
Term	Michaelmas Term 2015  (16 lectures)

Overview

This course aims to prepare undergraduates for the programming work they will undertake during their time in Oxford and subsequently, including subsequent programming-heavy courses such as Compilers and Database Systems Implementation, in addition to the group project and later individual project work. The course contains few topics that have not been mentioned in previous courses, but the defining aim in this course is to illustrate those programming techniques put to work in a sequence of case studies of carefully chosen size, each of them big enough to have significant internal interfaces, but not so large as to be overwhelming.

The course will introduce standard tools and techniques for software development: use of a version control system, an automated build process, an approriate framework for automated unit and integration tests, and profiling tools for studying performance. Participants will be able to choose between an IDE and a traditional editor/compiler setup.

Learning outcomes

After taking the course, participants will be able to

• Specify simple abstract data types and design implementations, using abstraction functions to document them.
• Recognise features of object-oriented design such as encapsulation, polymorphism, inheritance, and composition of systems based on object identity.
• Name and apply some common object-oriented design patterns and give examples of their use.
• Design applications with an event-driven graphical user interface.

Prerequisites

This is not a first programming course; neither is it a course about Scala. Most undergraduates taking the course will have had a previous introduction to Scala in the course Imperative Programming 2 that they took in the first year. Since we will be using mostly those features of Scala that are also present (in slightly more clunky form) in Java, it should not be too difficult for those already familiar with Java to pick up the language they need to follow the course. Familiarity with elementary notions of program correctness will be assumed, such as pointer-linked data structures and the use of invariants to reason about programs containing loops.

Synopsis

This page gives a lecture-by-lecture synopsis of the course, supplemented by links to printed lecture notes and handouts.

Abstract Data Types

The first part of the course concentrates on the structuring of large programs by means of abstract data types (ADT's). An ADT is a program module that satisfies a specification expressed in abstract terms, while hiding the details of how the specification is implemented.

[1] Programming with abstract data types. What do we mean by a 'large' program? A program for a simple editing task. Rewriting the program to use an abstract data type. Programming for change by separation of concerns.

[2] How to specify an ADT. Abstract state space. Operations with pre- and post-conditions, illustrated by the Text example and others. Invariants for a program that uses the Text ADT.

[3] How to implement an ADT. Concrete state space, concrete invariant, abstraction function. Implementing operations, illustrated by the Text example.

[4] Rules for specifying and implementing ADTs. Additional examples of refinement. General formulation of the correctness criteria.

Designing with objects

This part of the course is organised around a programming case study: a text editor written in about 2,500 lines of Scala.

[5] Features of object-oriented programming. Encapsulation, object identity, polymorphism – but not inheritance.

[6-7] Introducing Ewoks. Commands as methods and as objects.

[8] Subclasses and inheritance. Relationship between Text and PlaneText, dynamic binding.

[9] Fragile base class problem.

[10] Model/view separation. Specifying by programming, benign side-effects, narrowing the interface between Editor and Display.

[11-12] Undo/redo.

Another case study

[13] Dijkstra's algorithm. Representing the model.

[14] Implementing Dijkstra's algorithm. Priority queues. Speeding up the program.

[15-16] A graphical interface. for animating Disjkstra's algorithm.

Note for tutors: the schedule given here is an ideal. Because of unplanned discussion in the lectures (a good thing), we will sometimes run up to half a lecture behind the plan.

Syllabus

Software architecture. Object-oriented design principles. Design by contract and proof of correctness of data representations. Event-driven programming. Common design patterns. Case studies.

Reading list

Essential

There is no set text for the course, in the sense of a book that we will work our way through, lecture by lecture. The closest book in spirit to the course is

Barbara Liskov, Program Development in Java, Addison-Wesley, 2001, £47.99, ISBN 0201657686.

except that we shall be emphasizing programming examples much more than that book – and our programs will be written in Scala not Java.

As a guide to Scala, we will use

Martin Odersky, Lex Spoon and Bill Venners, Programming in Scala.

Optional

For reading around the course, I recommend a number of other books. The structure of our programs will resonate with some of the 'design patterns' that have become a popular way to think about object-oriented programs. A chatty and accessible introduction to design patterns is this book:

Head First Design Patterns

The design patterns movement started with the book,

GOF

Also helpful as an account of design by contract is

Bertrand Meyer, Object-Oriented Software Construction, SAMS, 1997, £35.37, ISBN 0136291554.

This book is based on the Eiffel language invented by the author rather than Scala.

Here is a book about restructuring programs to make them more clear, the program maintenance counterpart of modular design. It resonates well with the lecturer's experience of designing for clarity and robustness.

Martin Fowler, Refactoring: improving the design of existing code, Addison-Wesley, 2000, £37.99, ISBN 0201485672.

Also the following books about programming more generally would 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, £22.99, ISBN 020161586X.

Feedback

Students are formally asked for feedback at the end of the course. Students can also submit feedback at any point here. Feedback received here will go to the Head of Academic Administration, and will be dealt with confidentially when being passed on further. All feedback is welcome.

Taking our courses

This form is not to be used by students studying for a degree in the Department of Computer Science, or for Visiting Students who are registered for Computer Science courses

Other matriculated University of Oxford students who are interested in taking this, or other, courses in the Department of Computer Science, must complete this online form by 17.00 on Friday of 0th week of term in which the course is taught. Late requests, and requests sent by email, will not be considered. All requests must be approved by the relevant Computer Science departmental committee and can only be submitted using this form.