CS 312: Example Overview Document

This is a sample overview document. You were not actually required to write an overview document for this problem set, but this document should help you write overviews for later problem sets. Because Problem Set 2 was pretty short and didn't involve a lot of design decisions, this overview document is on the short side. You should consult the full overview description to make sure that you aren't missing something from your own overviews.

Problem set 2: “Substituting, folding, stacking, and typing”

Authors: CS 312 staff (your names and netids would go here)


Challenges. This assignment involved a few programming problems and also tested our understanding of the substitution model. Part 3 looked tricky but was easy to get right once we were on the right track. It was easy to make mistakes on Part 4, however.

Major issues. On the substitution problem, it was a little tricky to get the order of reductions right. It was tempting to do reductions inside of functions before the function was applied. For example, the term (fn x => (fn y => y + 2) x) 3 should reduce to (fn y => y + 2) 3 rather than to (fn x => x + 2) 3

Doing reductions inside of function is actually similar to inlining and other optimizations that some compilers do, but in general it cannot be done ahead of time without possibly causing infinite loops that wouldn't have otherwise happened.)

It was important in Part 4 to realize that a variable expression could have any type. Therefore one could not count on subexpressions having any particular syntactic form. They had to be type-checked recursively.

Design issues. The assignment was fairly constrained, with relatively few design choices. One small choice was how to implement the type environment used in Part 4.

Known problems. Our implementation (PS2 solutions) has no known problems.


The specifications in this problem set were given and contained almost no ambiguity. Part 2(e) was ambiguous about whether suffixes were to be returned in any particular order. We chose to return them in decreasing order of length, matching the given example.

We were not asked to produce any specifications for this assignment. If we were, this would be the right place to describe and justify any important specifications. For completeness we include the specifications for the operations on environments (Part 4):

(* extend(e,x,t) is environment e extended with the binding x:t.
   Any existing binding for x is removed. *)
val extend: environment * string * mytype -> environment

(* lookup(e,x) is SOME(t) if environment e contains a binding for x (to t);
   it is NONE otherwise. *)
val lookup: environment * string -> mytype option

Design and Implementation

Modules. We did not need to break any programming tasks down into modules for this assignment. Otherwise this would be a good place to discuss how modularity was achieved, any key invariants maintained within each module, and the inputs and outputs of different modules.

Architecture. Because we did not need to define modules, there is no architecture to be described here.

Code design. There were not many code design issues. One issue was how to implement variable-type environments in Part 4. Our implementation represented this as a simple linked list of pairs of names and types. To maintain some abstraction, our code accesses the environment only through two functions extend and lookup. This implementation has the advantage of simplicity, and although it is asymptotically slow, we don't expect to see large environments in any case.

The stack problem also posed some challenge, particularly in getting started. However, the types in the problem more or less dictated the solution.

Programming. Our code was written by one staff member. A second staff member critiqued the code, proposed some specifications, and introduced the environment abstraction. Because there were no modules, we did not have to employ a particular implementation strategy.


Test plan. Parts 2 through 4 required some testing. We briefly describe the test cases we constructed. For each thing we implemented we had one or two test cases with "typical" inputs. For problems with examples, we used the examples themselves as test cases. However, we added our own test cases on every problem. We tried to cover corner cases for every piece of code. We generated corner cases largely by looking at the spec rather than by trying to get code coverage. Since there was little control structure in the code we wrote, getting code coverage was trivial in any case.

Test results. Our code passed all of our test cases. For brevity of this example document, these test cases are omitted here.

Known problems



This is where we might express opinions about the assignment. For example, that was fun to implement, but we would have avoided some bugs and consequent debugging effort if we had started by writing down a rep invariant for the AST data structure before implementing type checking.