CSE 503: Software Engineering

Due Friday January 15, 1999
(part is due on Friday January 8, by lecture)

Consider the following description of a simple software system:

The KWIC [Key Word In Context] index system accepts an ordered set of lines, each line is an ordered set of words, and each word is an ordered set of characters. Any line may be "circularly shifted" by repeatedly removing the first word and appending it at the end of the line. The KWIC index system outputs a listing of all circular shifts of all lines in alphabetical order.

By lecture on Friday January 8th, you are to design and implement KWIC in any language that you choose­­YFPL, Your Favorite Programming Language.  (It would be boring, although not a problem, if everyone happened to implement KWIC in the same language, such as Haskell or 68010 assembly language.)  In lecture that day, we plan to look at some of the programs the class produces, focusing on the design decisions that were made. 

For Friday, when the full assignment is due, you should turn in (preferably via a Web page):

1. Your KWIC program, with any other information (such as design documents) you produced while you were writing the program.  If you didn't write any, don't make any up.  If you scratched stuff out by hand, feel free to scan it in rather than retyping anything.

2. A discussion (at most a page or so) about the design you chose, why you initially chose the design, and whether you feel (after the discussion in lecture on Friday) whether your decisions were good or not (and why).

The fundamental objective of this assigment is to get you to introspect about design on a simple but surprisingly rich problem.  It will lay the basis for some lectures and readings on information hiding and other related software design topics.

The Y2K or Millenium problem is of great visibility now.  As you know, the problem is that years were represented by using the final two digits and now, with the year 2000 right around the corner, comparisons between (say) 55 and 00 will give the incorrect belief that David Notkin will turn -55 years old on his 45th birthday, which is January 1, 2000.  Again, as you know, this representation was chosen because memory (both RAM and disk) was expensive.

However, the problem isn't really the representation of years per se, but rather that the representation was exposed.  Therefore, to fix the Y2K problem, all places where the representation was used have to be changed.  In this part of the assignment, you will show how it's possible to both save the space, as desired by those programmers a couple of decades back, and also to hide the representation to allow it to change.

You are to write (again, in YFPL) a date module that has the following properties:

1. It can create, compare, and persistently store and load dates in a range no smaller than January 1, 1950 through December 31, 3000 inclusive (hey, we don't want a Y3K problem, since it might make my 1045th birthday unpleasant).
2. Clients of the module (that is, the code that makes invocations to create, compare, store, and load dates) must be kept blissfully unaware of the representation that the module uses internally.  That is, from their point of view, the clients just deal with days, months, and years in the given ranges and would have no concern about the Y2K problem.
3. Implement the module as you might have in 1960, using only two digits for both the in-memory and on-disk representation of years.  (Note: This implementation will not work properly for clients that use dates out of the 1950-1999 range.)
4. Modify your implementation to handle the broader range of dates, using any representation you choose but ensuring that clients can access dates they've stored using the previous version.  That is, the use of the new implementation should be entirely transparent from the clients' point of view (except for any necessary recompiling and relinking).

There are three papers to be read (I will hand them out in class on Friday, 1/8/99, with the two Parnas papers stapled together):

1. D.L. Parnas. On the Criteria To Be Used in Decomposing Systems into Modules. Communications of the ACM, 15 (12), 1972.
2. D.L. Parnas, Designing Software for Ease of Extension and Contraction. IEEE Transactions on Software Engineering, SE-5, 1979.
3. D. Garlan and M. Shaw, An Introduction to Software Architecture. In Advances in Software Engineering and Knowledge Engineering, 1993.

The first paper covers the basics of information hiding, using KWIC as an example.    It will help you with answering the last piece of Part I.

The second paper covers the basics of layered designs. 

The third paper provides an overview of the recent work in software architecture.  

Briefly (a paragraph or so for each) the following questions:

1. Most operating systems are layered in the sense discussed by Parnas in the second paper.   Most operating systems also use some form of upcalls, where upper layers can provide functions to be invoked by lower layers.  Is this notion of upcalls consistent with or inconsistent with Parnas' view of layered systems, and why?
2. Garlan and Shaw discuss, in Section 3.2, the "data abstraction and object-oriented organization."  Discuss the following two issues.
   1. Do you agree with or disagree with their footnote about why inheritance is omitted from the architectural style?
   2. I view this style largely as a "non-style."  That is, it is basically only a structuring technique, providing almost no promise of the ability to reason in any depth about properties of a system built using this style.  Do you adhere more to their view or my view, and why?
3. Distinguish as well as you can "software architecture" from "software design."