Lecture 2: Project Structure

In which we discuss the basic ideas of components and how to produce good ones.


What It Does

Not the place to get clever with what you remember from algorithms class

Remember instead the interfaces

What are the operations it must perform?

For a stack:

Don't forget the boundary cases: What happens with an empty stack?

Operational Semantics: A Bad Thing

Specifications are not implementations

"It does what it does" and "Just read the code" are not answers to "Where is the spec?"

Instead of a tree being two pointers, think of the more abstract description:

In fact, the latter is still executable code. However, it divorces itself from questions like memory layout, or even memory addresses. A full spec requires more - a prose explanation of the intent.

A Simple Example

A Tree is a collection containing some kind of data. A Tree is a homogenous, immutable data structure: all data within it must be of the same type, and no tree can be altered once created (new ones can be created from existing ones).

A Tree can either be an empty collection, called a Leaf, or a collection containing three items, called an InternalNode. The three items in an InternalNode are as follows:

If the type of data contained in a Tree is identified by the type variable SomeData, then this collection can be succinctly described with the following Haskell expression:

data Tree SomeData =
  | InternalNode
       Tree SomeData
       Tree SomeData


What is a component?






Distinguished from other components

Handle to "grab on to it"


At very least, existance


Alternatives for behavior


What can it do?

What guarantees does it provide?

Programming by contract: API of a component provides (implicit) warranty

Contract: Pre-conditions and Post-conditions

Pre-condition: What must be true before this behavior can be performed?

Post-condition: What will be true once the behavior is complete?

Some PLs have mechanisms for this

Your spec wants them whether the implementation language has that mechanism or not


What do you do with a button?

Push it!

Presence of a control affords certain actions

Good components afford only the right actions

Affordances: Doorknobs

What's a good design for a doorknob?

Round: It affords turning

But which way?

Then what? Push or pull?



What everyone says is the big deal with encapsulation

Yes, it's important: Don't look under the hood to drive the car

Show only the controls you need for the task at hand

Wait, Sounds Like Affordances!


Ideal: A component can only be used correctly

Poor affordances: A flat API with constraints on the order of the calls

Better affordances: If order is required, build it in

If unknown steps come in between, that's polymorphism....


Literally, Many Shapes

Greek roots poly and morphus

Here, being able to mix and match components

New code using old: Reusing an API

Old code using new: Polymorphism

Ad Hoc: Fitting a New Peg into an Old Hole

Start from a known "shape"

As long as something new "fits", it works

In OOP, this is base classes and inheritance

Parametric: Flexible Holes for Many Kinds of Pegs

Build a structure assuming we'll find something to fit in later

No assumptions about the something

In programming languages, these are template mechanisms

And for Next Week....

Class Mailing List

Please sign up for the class mailing list. This is the place for timely announcements, questions about assignments, and an excellent place to put together a group for your class projects.

Homework Assignment: man ls

Read the Unix manual page for the command /bin/ls.