This is a closed book, no-computer, no calculator, no smart-phone, no cow, do it all by

yourself exam.

There are seven questions, most with sub-questions. Make sure to answer all of them.

Write your answers in the provided books (or if you’re taking the exam with a proctor, use

whatever paper you brought with you.) Make sure to write your name on each book that

you use to record your answers. Make sure to write legibly. Good luck!

 

1. [3 points each, 21 points total] Using a sentence or two, explain each of the following
   terms in the context of this class.
   1. higher-order function
      Answer: A Higher Order Function is a function that takes a function as a parameter and produces another function
   2. mutex lock
      Answer: Mutex Lock - Mutual Exclusion Lock, so that threads do not access the same resource at the same time.
   3. sub-classing (also known as inheritance)
      Answer: Inheritance is so to speak a way to 'inherit' methods from another class so as to reuse code.
   4. parametric polymorphism
      Answer: A function that allows any type as a paremeter (e.g. 'a in ocaml)
   5. busy waiting
      Answer: Occurs when a thread repeatedly checks if an action occured (e.g polling) which can be bad since it uses resources.
   6. overriding
      Answer: Overriding refers to the 'redefining' the method implementation of an inherited class, therefore overriding the parent's definition.
   7. event listener
      Answer: A Listener for Events! A function that is called whenever an event fires.
2. . [2 points each, 16 points total] Answer True or False for each of the following questions.
   1. If a computation runs in O(2n+3n2+10) time, then it also runs in O(n) time.
      Answer: false
   2. We can implement an imperative queue where the enqueueand dequeue
      operations take worst case time O(1).
      Answer: true
   3. The parallel merge-sort algorithm shown in class takes time O(lg n) if we have n
      processors.
      Answer: false
   4. A deadlock occurs when two or more threads try to acquire the same lock.
      Answer: true
   5. Suppose class D does not inherit from class C. Suppose further that objects
      generated from class C have type T. Then objects generated from D cannot have
      a sub-type of T.
      Answer: false
   6. It's impossible to get a race condition when we use purely functional code.
      Answer: true
   7. Suppose f is a purely functionalOCaml function with type unit->int. Then
      f returns the same integer each time we call it.
      Answer: true
   8. Determining whether two balanced, binary trees of n bignums are equal can be
      done in O(n) time.
      Answer: false
   9. [0 points] The answer to this question is "false".
      Answer: Paradox!?
3. [4 points each, 24 points total] For each of the following OCaml expressions, give code
   that when substituted for the ‘???’ causes the whole expression to evaluate to 42, or
   else argue that the program cannot be made to evaluate to 42. Your code should avoid
   shadowing any of the defined variables (e.g., your code should not include a “let”.)
   1. let x = ref 0 in
let f () = !x in
let x = ref x in
??? ; f()
      Answer:  (!x) := 42
   2. let x = ref 0 in
let f () = !x in
let x = ref 42 in
??? ; f()
      Answer: Cannot be made to 42, x in line is 
   3. let f x = x := (!x) + 1 in
let y = ref 0 in
List.map f ???
      Answer: []; 42 
   4. type ilist = Nil | Cons of (int * ilist) ref 
let f (x:ilist) =
match x with
| Nil -> 0
| Cons r -> (let (i,t) = !r in
              match t with
              | Nil -> 1
              | Cons s -> if r == s then i else 2) 
in
f (let f = ??? in ???)
      Answer: let f = Cons(ref(42, Nil)) in (match f with | Cons r -> r := (42, f) | Nil-> Invalid_argument "Impossible"); f
   5. class c = object 
method x = 41
end
class d = object 
??? 
method x = bob#x + 1
end
(new d)#x
      Answer: inherit c as bob
   6. class c = object
val mutable x = ref 0
method get = !x
method set y = x <- y
end
let v = new c in ??? ; v#get
      Answer: v#set (ref 42)
4. [15 points total, 5 each] Consider the following module interfaces for numbers.
   module type SIMPLE_NUMBER = 
   sig
   type bignum
   val from_int : int -> bignum
   val minus : bignum -> bignum -> bignum
   val less : bignum -> bignum -> bool
   end
   module type EXTENDED_NUMBER = 
   sig
   include SIMPLE_NUMBER
   val plus : bignum -> bignum -> bignum
   val equal : bignum -> bignum -> bool
   end

    

   1. Write a functor that takes a SIMPLE_NUMBER module as an argument and
      returns an EXTENDED_NUMBER module as a result. Keep your code as simple as
      possible. We will even get you started: 
      Answer: module Extend(S : SIMPLER_NUMBER) : EXTENDED_NUMBER =
                        struct
                          open S
                           (* your definitions go here... *)
                           let plus x y = minus x (minus y (from_int 0))
                           let equal x y = not (less x y) && not (less y x)
                     end
   2. In the Bignum problem set, we asked you to represent numbers with a very
      strong representation invariant:there should be no leading zeros in the list of
      digits, and the "negative" flag should never be set for zero. Explain how this
      made some operations easier to implement, and others harder
      Answer: (* Wasn't the negative flag of type bool!? *)
                     The lack of leading zeroes made it easier to compare the bignums otherwise we would have to take the leading zeroes into account (which are for all intents and purposes nil). Made it harder for some operations which produced bignums though, since we have to make sure no leading zeros are produced.
   3. Suppose we asked you to build an implementation of Rational numbers
      (fractions) using a pair of Bignums (one for the numerator, one for the
      denominator). What representation invariant(s) might you impose on your code
      to make equality on Rationals easier?
      Answer: Always Lowest Terms
5. [13 pointstotal] We can describe an infinite, 2-dimensional plane of values using the
   following recursive type definition:
   open Lazy;;
   type 'a plane = {
   contents : 'a ; 
   north : 'a plane lazy_t ; south : 'a plane lazy_t ; 
   east : 'a plane lazy_t ; west : 'a plane lazy_t
   };;
   Each point contains some contents and links to the points north, south, east, and west.
   Recall that applying the built-in primitive lazy to an expression e of type t yields a t 
   lazy_t, and delays the evaluation of e, whereas the primitive force takes a t 
   lazy_t, and forces the expression to be evaluated to produce a t.
   1. [3 points] Write a map function which when given a function f from 'a to 'b,

      and an 'a plane, produces a 'b plane.
      Answer: let map (f:'a->'b) (a:'a plane) = {
                        contents = f a.contents,
                        north = lazy (map f (Lazy.force a.north)),
                        south = lazy (map f(Lazy.force a.south)),
                        east = lazy (map f(Lazy.force a.east)),
                        west = lazy (map f(Lazy.force a.west))
                        }
   2. [5 points] Write code to build the Cartesian plane. The Cartesian plane is an

      (int * int) planewhere the pair of integers represents the X and Y

      coordinates respectively of a point in the plane. Your plane should start with the

      origin (0,0), and as we move east, the X coordinate should increase, while as

      we move west, the X coordinate should decrease. Similarly, moving north should

      cause the Y coordinate to increase, while moving south should cause the Y

      coordinate to decrease.
      Answer: let cart = {
                        contents = (0, 0)
                        north = lazy (map (fun (x,y)-> (x, y+1)) cart),
                        south = lazy (map (fun (x,y)-> (x, y-1)) cart),
                        east = lazy (map (fun (x,y)-> (x+1, y)) cart),
                        west = lazy (map (fun (x,y)-> (x-1, y)) cart)
                        }
   3. [5 points] Suppose we are given a bool plane and we wish to determine

      whether there is a true value in it somewhere. That is, we wish to write a

      function that returns true if and only if the plane includes a true value anywhere

      in the plane. Describe (in English or code) how you might do this, guaranteeing

      that the function always terminates when there is a true value somewhere in the

      plane. (Warning: there is no guarantee that moving one direction (c.f., east) and

      then the opposite direction (c.f., west) gets you back to the a node with the same

      contents.)   
      Answer: If going back to a step lead to the same node, it would be easy to do the same idea as if we were to fold the nodes. However, because we do not have this luxury, I guess what is possible is to use the same idea used on problem set 6, checking if a list is cyclic. What we could do is store nodes we have visited and their neighbors, and traverse them recursively and returning when we see true.
6. . [10 points] Recall our interface for events:

   type id

   type 'a event

   val new_event : unit -> 'a event

   val add_listener : 'a event -> ('a -> unit) -> id

   val add_one_shot : 'a event -> ('a -> unit) -> id

   val remove_listener : 'a event -> id -> unit

   val fire_event : 'a event -> 'a -> unit

   val run : (unit -> unit) -> unit

   Suppose we are building a soda machine and the machine has a set of devices and

   actuators with the following interface:

   type soda = Coke | DietCoke | Sprite | MooJuice

   val coin_inserted : int event 

   val cancel : unit event 

   val soda_requested : soda event

   val return_money : int -> unit

   val dispense_soda : soda -> unit

   When the user inserts a coin into the machine, the coin_insertedevent is triggered
   with the value of the coin (e.g., 5 for a nickel, 10 for a dime, etc.) If the user wishes to
   cancel the transaction, then she presses the cancel button, triggering the cancelevent,
   at which point, any money she has deposited should be returned to her via the
   return_moneyoperation. When she presses a button for a soda, the
   soda_requestedevent is triggered with the kind of soda she requested. If she has
   deposited at least $1, then the soda should be given to her via the dispense_soda
   operation, and any additional money should be returned to her via return_money.
   Write a set of Ocaml definitions so that when we call the event run function, we get the
   right behavior for the soda machine. 
   Answer: 
(*Writing Ocaml here, I realized how much I love emacs!*)
let money = ref 0 in
Event.add_listener coin_inserted (fun coins-> money := (!money+coins));
Event.add_listener cancel (fun () -> return_money (!money); money:=0);
Event.add_listener soda_requested (fun soda->
if !money > 100 then
(dispense_soda soda; return_money (!money - 100));
money :=0)
7. [1 point] What is the super secret bonus answer?

    

   Answer: Cow!?