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`. 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, Implementation, and Testing ----------------------------------- **Specifications.** 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. **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. **Test plan.** Parts 2 through 4 required some testing. 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. Division of labor ----------------- We did Part 1 together. Person A produced a design for Parts 2 and 3, and Person B designed Part 4. We wrote all the code together, i.e., pair programming. We swapped roles for testing, with Person B writing the test cases for Parts 2 and 3, and Person A writing them for Part 4. Afterwards we independently read through the code and specification comments, then met to critique and improve it. Person A spent about 5 hours on the assignment, and Person B spent about 4 hours. Known problems -------------- None. Comments -------- We had fun implementing Parts 3 and 4 but found Parts 1 and 2 a little dull. 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.