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)

Summary

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.

Specification

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.

Testing

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.

2(a): We tested lists of different lengths including length 1.
2(b): We tried both even and odd lists, and a list of length 1.
2(c,d,e): In addition to a longer list or two, we tried lengths 0 and 1.
3: in addition to the examples in the problem set and the stub file, we wrote test cases that exercised every operation in the stack language. We made sure to write a test case not only for every normally functioning operation, but also for every case in which a StackException could be generated. For operations that made the stack smaller, we wrote test cases that would completely clear the stack and test cases that would try to pop off more elements than were contained. We also tested whether npop worked when zero was on the top of the stack.
4: We wrote test cases that included at least one instance of every kind of expression in the language, both in the case that that expression type-checked, and in the case that it failed to. We tested whether variable shadowing worked correctly, and whether unbound variables were detected. We tested the corner cases of length-0 and length-1 tuples.

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

Known problems

None.

Comments

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.