1. Using one of the sources in the [ML learning guide](../readings/ml.html), read about structures, signatures, and matching. Then answer questions about the structure and signature below. The following structure contains definitions that should be familiar from the [ML homework](ml.html) and from code you may have seen in the course interpreters: structure ExposedEnv = struct type name = string type 'a env = (name * 'a) list exception NotFound of name val emptyEnv = [] fun lookup (name, []) = raise NotFound name | lookup (name, (x, v) :: pairs) = if x = name then v else lookup (name, pairs) fun bindVar (name, value, env) = (name, value) :: env end Here is a signature: signature ENV = sig type name = string type 'a env val emptyEnv : 'a env val lookup : name * 'a env -> 'a val bindVar : name * 'a * 'a env -> 'a env end Answer these questions: (a) Does the signature match the structure? That is, if we write structure Env :> ENV = ExposedEnv does the resulting code typecheck? (b) Does the signature expose enough information for us to write the following function? Explain why or why not. fun extendEnv (names, vals, rho) = ListPair.foldrEq Env.bindVar rho (names, vals) (c) Does the signature expose enough information for us to write the following function? Explain why or why not. fun isBound (name, rho) = (Env.lookup (name,rho) ; true) handle Env.NotFound _ => false (d) If in part (b) or part (c), it is not possible to write the function given, explain how you would change the code to make it possible. (e) Suppose you change the `ENV` signature to make the `name` type abstract, so the signature reads signature ENV = sig type name type 'a env ... end Is more abstraction better here? Or does the change have unfortunate consequences? Justify your answer. You now have the basic ideas needed to understand what is being asked of you in this assignment, and you know enough to implement most of the "pick up the last stick" game ([problem S](#stick)). 2. An ML _functor_ is a function that operates on the module level. Its _formal_ parameters, if any, are specified by a _sequence of declarations_, and its _actual_ parameters are given by a _sequence of definitions_. Its result is a structure. Read about functors in Harper, as recommended in the ML learning guide. Here's a typical application of functors. To keep track of the thousands of tests we run on students' code, I need an efficient "test set" data structure. But not all tests have the same type. To reuse the data structure with tests of different types, I need a functor. Here is what my "test set" functor needs to know about a test: - A string identifying the student who wrote it - A comparison function that provides a total order on tests - A function that converts a test to a string, for printing Using this information, answer parts (a) and (b): (a) Write down the information needed for a test set in the form of _formal parameters_ for the functor `TestSetFun`, keeping in mind that a functor's formal parameters are written as a sequence of declarations: functor TestSetFun( ... fill in formal parameters here ... ) :> TEST_SET = struct ... end (* ignore this part *) (b) Now focus your attention on one particular test, the `check-type` test: - The test is identified by a student's user ID and a sequence number 1, 2, or 3. - The test contains an expression of type `exp` and a type of type `ty`. - Comparison can be implemented using code like this: case String.compare (uid1, uid2) of EQUAL => Int.compare (seqno1, seqno2) | diff => diff - A test can be converted to a string code like this: concat ["(check-type ", expString e, " " , tyString tau, ")"] Show how to create a set of `check-type` tests by filling in the _actual parameters_ for the `TestSetFun` functor: structure CheckTypeSet :> (TEST_SET where type test = check_type_test) = TestSetFun( ... fill in actual parameters here ... ) You now understand functors well enough to use them in problems 1 and 2. 3. Read about "signature refinement or specialization" in the [ML learning guide](../reading/ml.pdf). Now, (a) Explain what, in part (b) of the previous question, is going on with the `where type` syntax. (b) Explain what would go wrong if we wrote this code instead: structure CheckTypeSet :> TEST_SET = TestSetFun(...) You now understand functors well enough to know how to refine the result signature of your Abstract Game Solver in problem A. 4. Many useful abstractions can be implemented using the humble binary tree. Let's consider how we might use a *binary-search tree* to store a large data structure containing all of the software testing results from 105. I want to know for each test, for each student, did the student's submission pass the test. Read Ramsey, section 8.1, on abstractions, representations, and invariants. Focus on places where binary trees are mentioned. Also read the first three pages or section 8.8.4 on hash tables, which represent a similar abstraction. (Skip all the code parts.) (a) In informal English ("the world of ideas"), what is the abstraction represented by the binary-search tree? (b) Suppose a binary-search tree is represented as follows: datatype tree = EMPTY | NODE of tree * (test * student * bool) * tree Using some combination of ML code and informal English, write the *abstraction function* which maps this representation onto the abstraction that it stands for: (c) Using ML code, and assuming whatever functions you need on types `test` and `student`, write the *representation invariant* of the binary-search tree. (The representation [invariant of a binary-search tree is the *order* invariant which guarantees the correctness of `insert` and `lookup`.]{.new}) You now know enough to design an abstraction function and representation invariant for your chosen representation of natural numbers in problem 2. 5. In ["Mastering Multiprecision Arithmetic"](../readings/arithmetic.pdf), read the sections on addition, subtraction, and multiplication. - Given that you may be adding two numbers of different lengths (e.g., 1777944 + 903), what sort of case analysis do you expect to need to implement addition? - Given that you may be subtracting two numbers of different lengths (e.g., 1777944 - 903), what sort of case analysis do you expect to need to implement subtraction? - Given that you may be multiplying two numbers of different lengths (e.g., 1777944 * 903), what sort of case analysis do you expect to need to implement multiplication? You are now prepared to tackle the implementation part of problem 2.