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.

Abbreviations

JSP = Jackson Structured Programming

DPLL = Davis-Putnam-Logemann-Loveland (algorithm)

SQL = Structured Query Language

lec #	TOPICS	LECTURE NOTES
1	Introduction Basic Java syntax and semantics; overview of objectives and structure of the course	(PDF)
2	Classes More Java: exceptions, input/output, classes, access control, static	(PDF)
3	Subclassing and interfaces Subclassing, inheritance, overriding, interfaces, packages; distinction between declared type and actual type; downcasting; anonymous classes	(PDF)
4	Designing state machines State machine design; graphical and textual notation; state machine semantics; parallel combinations of machines	(PDF)
5	Implementing state machines State machine implementation patterns; concurrency and queues; modularity and interfaces	(PDF)
6	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	(PDF)
7	Designing stream processors Stream processing programs; grammars vs. machines; JSP method of program derivation; regular grammars and expressions	(PDF)
8	Decoupling and interfaces Modularity, decoupling, information hiding; module dependence diagrams; using interfaces for decoupling	(PDF)
9	Testing and coverage Why software testing is hard; input space partitioning, boundary testing, state machine coverage, code coverage; test-first development and regression testing	(PDF)#
10	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)	(PDF)
11	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	(PDF)
12	Debugging Techniques for avoiding debugging: assertions, modular development with unit testing, code reviews; strategies for debugging: reducing test cases, hypothesis-driven debugging, binary search; Heisenbugs	(PDF)#
13	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	(PDF)
14	Rep invariants, equality, visitors Advice on implementing types; rep invariants and abstraction functions; equality for immutable types; Iterator and Visitor patterns	(PDF)
15	Little languages Representing behavior using data structures; language datatypes, visitors, functional objects, higher-order functions; solving a problem by creating a domain-specific language	(PDF)
16	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	(PDF)
17	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	(PDF)
18	Designing a photo organizer The relational paradigm; conceptual modeling; object model syntax and semantics; Mitchell and Webb on "unity of purpose"	(PDF)
19	Implementing a photo organizer Implementation as object model transformation; key issue of where state resides; standard patterns; navigation, immutability and encapsulation; MVC considerations	(PDF)
20	Concurrency Shared-memory and message-passing paradigms; race conditions and deadlock; using threads and blocking queues in Java; concurrency issues in graphical user interfaces	(PDF)#
21	Usability User interface design principles: learnability, visibility, efficiency, errors, simplicity; iterative design; sketching and paper prototyping; user testing
22	Relational databases Using a database to represent an object model; relational algebra and SQL; transactions	(PDF)#
23	Conclusion Final words; courses and internships that might follow 6.005; winners of Project 3 awards; 6.005 quiz game	(PDF)