Prelim 2 solutions: Problem 1. (a) From expressions 'n = 0' and 'n - 1' we infer that the type of n must be int. From expression !x we infer that x must be of a reference type. The base type of x is not constrained; thus the type of x is 'a ref. Now, in the declaration of marvin (i.e. in 'marvin(n, x, y)') x is in the second position. On the other hand, we have 'ref y' in the second position in the recursive call. Hence the type of x, already determined to be 'a ref, must be the same as the type of ref y. We immediately infer that the type of y must be 'a. Putting everything together we get the type of marvin: int * 'a ref * 'a -> 'a ref (the return type is the same as the type of x; see the 'then' branch). (b) +--------+ | global | +--------+ ^ | +--------+ ++---++ +-----+ | a |---->|| ||---->| 5 | +--------+ ++---++ +-----+ ^ | +--------+ +-----+ | b |---->| 7 | +--------+ +-----+ ^ | +--------+ /--\/--\ | marvin |----------->| || | +--------+ \--/\--/ ^ args: ... | | body: ... | +----------------------- (c) Function 'marvin' will call itself recursively 312 times before returning the then-current value of x. At every recursive call, the function switches the position of its last two arguments. The ref and ! operators are applied to the switched arguments, but these don't change the 'true' underlying value, rather, they change the way we refer to these values (i.e. directly or through a reference). After two switches arguments get back to their initial position; each of them has been referenced once, and dereferenced once. Thus the third recursive function call will be identical to the first one, the fourth call to the second one, and so on. By expanding a bit on the previous argument we can establish that marvin(0, a, b) = marvin(2, a, b) = ... = marvin(312, a, b) = a. But a = ref 5 in our case. (d) Reasoning like we did above, we establish that marvin(1, a, b) = marvin(3, a, b) = marvin(5, a, b) = ... = marvin(2003, a, b). But marvin(1, a, b) = marvin(0, ref b, !a) = ref b = ref 7. Problem 2. From the description of argv we note that it behaves like a 'virtual' function argument. It is as if each function would have an additional argument, argv, whose value would be determined by a suitable combination of the values of the other arguments. Does the position of argv in the list of function arguments matter? In our problem, no. Why? Because the problem states that no function arguments can be named argv, which in turn means that argv can not be affected by shadowing at the point of the function call (the problem allows for argv to be redefined inside a function's body). For convenience, we can choose to insert the binding defining argv before any bindings corresponding to the function arguments, just after the environment has been retrieved from the relevant closure. This makes argv to be the first (invisible) function argument of any function. Where in the evaluator can we insert the binding for argv? Well, we should do it when it is clear that a function call will occur, and when the values of all function arguments are available. We identify such a location in line 249 of the handout, the line of function apply when the environment retrieved from the closure is expanded with bindings for the arguments. For easier reference here are the critical lines: val fullEnv = foldl (fn ((id, v), e) => insertBinding e id v) env (ListPair.zip (names, args)) Our plan requires that we modify env before we add the parameter bindings: val fullEnv = fold (fn ((id, v), e) => insertBinding e id v) (insertBinding env "argv" (List_v args)) (ListPair.zip (names, args)) Note that the lists we associate with argv are not necessarily type-homogeneous. For example, argv could take the value [1, "alpha"], which would clearly be illegal in SML. In Mini-ML, however, this is not a problem. Problem 3. (a) We are searching the list representing the environment in reverse order. This means that we first examine the oldest bindings first, and the newest bindings last. (b) If all names in an expression are unique in the current environment, then the direction of the search is not relevant. If, however, name redefinitions occur in some environment, then the search direction is significant. In particular, if we search in the 'normal' order (as in the unmodified lookupBinding function), then newer bindings will shadow the older ones. If we search in reverse order, however, the newer bindings will never shadow the older ones. let val x = 3 val x = 7 in x end The expression above illustrates the previous ideas. Using the unmodified lookupBinding the value of this expression will be 7 (since the second binding shadows the first one). When lookupBinding is modified no such shadowing occurs, and the value of the expression will be 3. It is as if the second binding did not even exist! Problem 4: Based on material presented in lectures and section you should have recognized Z as the stream of natural numbers. Also takeN is the familiar implementation of a function that returns the first n elements of a stream with at least n elements (or all the elements of the stream, if the stream is shorter). (a) It should be easy to see that function ford maps empty streams to empty streams. For non-empty streams, an output stream is created whose first two elements are identical to the (current) first element of the input stream. The following elements of the output stream are produced by calling ford on the remainder of the input stream. Our intuition (or even better: a simple inductive argument) convinces us that ford returns a stream in which every element of the input stream is duplicated while the order of the elements is preserved (except, of course, for the duplication). Thus, if Z is the stream of natural numbers 0, 1, 2, ..., then (ford Z) is the stream 0, 0, 1, 1, 2, 2, 3, ... In turn takeN(ford(Z), 8) will produce the list [0, 0, 1, 1, 2, 2, 3, 3]. (b) It is clear that the key function is zaphod. Within zaphod, it is easiest to understand the role of variable marvin. We notice that unless marvin is equal to (or greater than) k (the second argument of ford), marvin is incremented. If marvin is at least equal to k, then it is reset to 1. Since marvin starts at its upper limit (k), such a reset occurs the very first time zaphod is called, unless s is an empty stream. It should be clear from this discussion that marvin is a counter, which, ignoring any stopping conditions, will have the following sequence of values: k, 1, 2, 3, ..., k, 1, 2, 3, ..., k, ... But what about arthur? Arthur is set to a new value (that of h, the head of stream s) whenever marvin is reset. No other changes affect arthur. Arthur's value is used on both branches of the 'if' to produce the first value of the output stream. While the first element of the output stream is the same for both branches of th e 'if,' the rest of the output stream differs. The key observation is that on the 'then' branch the recursive call to zaphod refers to the same stream we got in the input, while on the 'else' branch the recursive call refers to the tail of the input stream only. In other words, the argument to the recursive function calls to zaphod changes only when counter marvin is reset. Since marvin is reset once in k steps, it means that zaphod's argument changes only once every k calls. Because we add the current head of the input stream to the output stream at every recursive call, this means that the output stream will repeat every value of the input stream exactly k times. All these imply that the result of evaluatind ford(Z, 3) is the stream 0, 0, 0, 1, 1, 1, 2, 2, 2, ... Taking the first 9 elements of this stream we obtain the list [0, 0, 0, 1, 1, 1, 2, 2, 2]. (c) This function is very similar to the one above. The main change is that the definitions of arthur and marvin are now outside the body of function ford. This makes arthur and marvin global variables; they will be shared by all calls to function ford. In the previous implementation of ford each call to ford generated its own private instances of arthur and marvin; there was no risk of sharing. The global and shared nature of marvin and arthur is 'dangerous' in the sense that various function calls to ford might leave these variables with inconsistent values from the perspective of subsequent calls. The real important variable is marvin, since arthus is set only when marvin reaches a specific value (k). Fortunately, we notice that line 'val () = marvin := k' sets the value of marvin to the same value that the previous implementation set it to. Thus no inconsistent value left by a previous function call survives to modify the behavior of ford. This means that the two versions of ford implement the same algorithm. It is now easy to realize that ZaphodsHead1 = ZaphodsHead2 = [0, 0, 0, 1, 1]. The final result is then obtained immediately: [0,0,0,1,1,0,0,0,1,1]. Note: eliminate line 'val () = marvin := k' and see whether you can determine the answer to the same question.