6.005 Elements of Software Construction | Spring 2010
Problem Set 3: Object Modeling
Due: 11:59:59 PM, April 25, 2010
|
The purpose of this problem set is to give you practice constructing object models. An object model describes the essential state of an application in terms of sets and relations, and is usually the basis of the application's conceptual model.
A. Reading an Object Model
Almost all text layout tools (Microsoft Word, Apple Pages, Adobe Indesign, etc) are based on the notion of paragraph styles. The document is structured as a sequence of paragraphs; each paragraph is assigned a style; and each style has an associated collection of formatting characteristics. This allows the formatting of a document to be easily updated, since all the paragraphs of a given style can be reformatted just by changing the formatting characteristics of the given style. Furthermore, styles can be organized into a hierarchy; when one style is based on another, it inherits that styles formatting characteristics unless explicitly overwritten.
This scheme is represented by the object model below. The formatting is represented by rule objects. A style might, for example, have a rule associating the attribute "font size" with the value "12 points".
Reading the model. For each of the invariants below, say (a) whether the invariant is expressed in the graphical model, and if so how, and (b) if not, whether it could be expressed graphically, and if so how.
- The Normal style is not a user-defined style.
- Every paragraph has an associated style.
- A user defined style is based on at most one style.
- No style is based on itself, directly or indirectly.
- The style hierarchy (defined by the based on relation) forms a tree.
- There cannot be two format rules for a style can that assign values to the same attribute.
- No two styles share a format rule.
- A style has a rule for every attribute.
The basic rule for formatting inheritance is as follows: if a style is not based on another style, it has exactly the formatting given by its rules; if a style is based on another style, we first compute the formatting for the parent style, and then override it by applying the formatting rules of the child. You can therefore let the parent style determine some formatting attribute by simply not setting it in the child -- that is, having no rule.
Now here's a tricky issue. We might have two styles, one based on the other, that assign the same value to a given attribute when used for formatting a paragraph: for example, Section and SubSection might both set size to 12pt. That doesn't mean, however, that both styles contain formatting rules for that attribute. The child style might have inherited the format from the parent, or it might have overridden the parent's formatting rule, but with a rule that has exactly the same effect! You'd notice the difference if you changed the formatting rule in the parent. If the child had no corresponding formatting rule, paragraphs formatted in the child style would change accordingly. But if the child had a formatting rule that was overriding the format, paragraphs formatted in the child style would not change.
Field work. Your task now is to pick a layout application, and see how it implements the object model in a particular respect.
Pick any style-based layout application and perform some experiments to determine how style inheritance works. You'll need to create a little hierarchy of styles, assign them to paragraphs, and then see how changing the parent style of a paragraph's style affects the paragraph's formatting. Then answer the following questions:
- Does the style model in your selected application conform to the object model above, and if not, how does it differ?
- How does your selected application handle inheritance? Does it give the flexibility to override a formatting rule, as explained above, even with an identical formatting rule? If so, how is this done in the user interface?
B. Modeling Problems
For each of the following problems, construct a graphical object model, accompanied by a list of informal textual invariants that cannot be expressed in the diagram. The problem descriptions are intentionally vague; it is your job to expose ambiguities and omissions, and resolve them in your model. Feel free to make (and document!) any reasonable decisions about the problem being modeled that are consistent with the informal description.
Shopping Cart. Model a shopping cart that contains items, with their count, part number, description and price.
Camera Image. Model an image produced by a camera sensor, consisting of an array of pixels, each with a luminosity value for red, green and blue.
Social Networking. Model the relationships between users in a social networking site, in which two users can be unrelated, or related in some specified manner (eg, "colleagues", "just good friends", etc).
Email Repository. Model an email repository in which messages are organized into folders. A folder may contain both messages and subfolders. There are special folders for deleted messages, sent messages and draft messages.
Voting ballots. Model the ballots cast in a voting scheme. On each ballot, the voter makes choices of candidates. There can be multiple elections on a single ballot (ie, for different positions and offices); for some, the voter can pick at most one, but for others, the voter can pick several.
Calendar. Model the state of a shared online calendar application. Users can create and subscribe to each other's calendars; each event belongs to a calendar and occupies fixed slots.
Slide Animation. Model a slide containing textual and graphical elements, along with settings for animation. Include grouping of elements, appearance order and effects.
Object Model Metamodel. Model an object model, as might constitute the state of an object-modeling tool.
Java Object Types. Model the type structure of objects in a Java program, in which there are two kinds of types, class types and interfaces, related by 'implements' and 'extends'.
Infrastructure
No code is provided or required for this problem set. A directory called ps3 will be created for you in your personal repository, containing a copy of this file. You should commit your solutions to the exercises as a single PDF file called pset3.pdf in the pset3 directory.
Hints
Here are some general hints about constructing object models:
- Focus on the essence of the problem, and don't elaborate boring details. For example, if you're modeling a user, you might want to include contact information. For an actual implementation, what exactly this comprises will matter, but it's not important conceptually. On the other hand, how users are named is likely to be critical.
- Beware of singleton sets: an object model of a banking system for a single bank should not have a set called The Bank.
- Remember that an object model captures essential concepts, not implementation structures. It should not include sets that are essentially just collection classes.
- Choosing good names for sets and relations is very important. If the meaning of a set or relation is unclear, write a designation for it that says in a short but careful sentence what membership in the set, or being related by the relation, means. If you're sloppy, it's easy to get confused and into a mess.
- Make your object model as tight as possible: that is, expressing the strongest set inclusions and multiplicity constraints that apply. But don't make it too tight, by ruling out reasonable instances.