Elements of Software Construction

Course Description

This course provides an introduction to the fundamental principles and techniques of software development that have greatest impact on practice. Topics include capturing the essence of a problem by recognizing and inventing suitable abstractions; key paradigms, including state machines, functional programming, and object-oriented programming; use of design patterns to bridge gap between models and code; the role of interfaces and specification in achieving modularity and decoupling; reasoning about code using invariants; testing, test-case generation and coverage; and essentials of programming with objects, functions, and abstract types. The course includes exercises in modeling, design, implementation and reasoning.

Lecture Notes

This section contains documents that are inaccessible to screen reader software. A "#" symbol is used to denote such documents.

Review Handouts

State machine syntax and semantics (PDF)
Graphical object model notation (PDF)

Topics by Session

Notes for lecture 21 are not available.


JSP = Jackson Structured Programming
DPLL = Davis-Putnam-Logemann-Loveland (algorithm)
SQL = Structured Query Language
lec #


Basic Java syntax and semantics; overview of objectives and structure of the course


More Java: exceptions, input/output, classes, access control, static

Subclassing and interfaces

Subclassing, inheritance, overriding, interfaces, packages; distinction between declared type and actual type; downcasting; anonymous classes

Designing state machines

State machine design; graphical and textual notation; state machine semantics; parallel combinations of machines

Implementing state machines

State machine implementation patterns; concurrency and queues; modularity and interfaces

State machine invariants

Safety and liveness properties; state properties and invariants; inductive reasoning; computing the product machine of a parallel combination; state explosion; fault tolerance; interlocks and the idea of a trusted base

Designing stream processors

Stream processing programs; grammars vs. machines; JSP method of program derivation; regular grammars and expressions

Decoupling and interfaces

Modularity, decoupling, information hiding; module dependence diagrams; using interfaces for decoupling

Testing and coverage

Why software testing is hard; input space partitioning, boundary testing, state machine coverage, code coverage; test-first development and regression testing

Designing a SAT solver, part 1

The SAT problem and SAT solvers; a new paradigm of functions over immutable types; use datatype productions to model structured values; patterns for implementing datatypes (Variant as Class, Interpreter)

Designing a SAT solver, part 2

Review of basic datatype patterns; a naive solver with backtracking search; design improvements with Facade, Option types, and a 3-valued logic


Techniques for avoiding debugging: assertions, modular development with unit testing, code reviews; strategies for debugging: reducing test cases, hypothesis-driven debugging, binary search; Heisenbugs

Designing a SAT solver, part 3

Abstract data types; representation independence; characterizing types by operations; encapsulation; examples of types used by DPLL solver; Factory Method pattern

Rep invariants, equality, visitors

Advice on implementing types; rep invariants and abstraction functions; equality for immutable types; Iterator and Visitor patterns

Little languages

Representing behavior using data structures; language datatypes, visitors, functional objects, higher-order functions; solving a problem by creating a domain-specific language

Basics of mutable types

Heap semantics (aliasing, assignment, field setting); reachability and conceptual storage leaks; the Object Contract and equality properties; hash maps and their representation invariant; problems caused by mutation of keys

Event-based programming

Fundamentals of programming graphical user interfaces; view hierarchy, Composite pattern, Publish-Subscribe pattern, Model-View-Controller (MVC); pitfalls of event-based programming

Designing a photo organizer

The relational paradigm; conceptual modeling; object model syntax and semantics; Mitchell and Webb on "unity of purpose"

Implementing a photo organizer

Implementation as object model transformation; key issue of where state resides; standard patterns; navigation, immutability and encapsulation; MVC considerations


Shared-memory and message-passing paradigms; race conditions and deadlock; using threads and blocking queues in Java; concurrency issues in graphical user interfaces


User interface design principles: learnability, visibility, efficiency, errors, simplicity; iterative design; sketching and paper prototyping; user testing

Relational databases

Using a database to represent an object model; relational algebra and SQL; transactions


Final words; courses and internships that might follow 6.005; winners of Project 3 awards; 6.005 quiz game

No comments: