Homework 1

Due: Fri 16 Jan 2004

Turn in the following on hard copy in class.
  1. Do Exercise 2.4.2, abcfg in Ullman, pg. 43
  2. Translating ML into Java/C++ : Write the equivalent Java (or C++ if you prefer) code for the following ML code:
    1.     val biscuits = 3 + 4 * 5 div 7;
    2.     val together = fn(a, b, c) => a ^ b ^ c;
          
    3.     fun vegetable x = if x = "tomato" then 
                               "fruity!" 
                            else
                            case x of
                                 "broccoli"  => "yummy!"
                               | "snap peas" => "okay"
                               | "lettuce"   => "useless"
                               | _           => "try it";
          
  3. Writing ML from diagrams: Write the ML code for the following diagrams. The stack is shown from the bottom up, (i.e. most recently added item is drawn at the top of the figure, oldest item is at the bottom), please write your code to reflect this.
    1. When making a list, use the :: operator.

    2. When making a list, use the bracket comma notation (e.g. [1,2,...])

  4. Diagrams and tracing: Trace the execution and draw the box-and-arrow diagrams for the following. Show what is in the stack (top-level environment) and what is in the heap. Be sure that your stack starts at the bottom and goes up (i.e. so that the most recent item is drawn at the top). Your diagram should depict all shared substructures.
    1.     val gorrillas = 20;
          val peach = #"b";
          val donkeys = {legs=4, toes=29};
          val gorrillas = #legs(donkeys);
          
    2.     val dogs = "beagle"::"pomeranian"::"terrier"::nil;
          val mammals = "dolphins"::"cats"::nil;
          val cuteAnimals = (hd(mammals),dogs);
          
    3. val a = { dog = "Fido",
                colors = ["red", "blue", "yellow"],
                random = (334, 3.2, "hi"),
                pi = 3.14 };
      val (b, b'::b'') = ( tl(#colors (a)),
                           [6.3,7.0,8.3] );
      val c = ( #2 ( #random (a) ),	 
                #pi(a) :: b'');
    1. What happens if you execute the following? Why?
          fun happy nil = "no turkeys!"
            | happy (a::b) = b;
            
    2. Let's say you have:
           fun happy  nil = "no turkeys!"
              | happy (a::b::c) = Int.toString (a+b) ^ " baby turkeys";
      What happens if you try to run happy [3]? Why? How could you fix this?

  5. Let expressions: Answer A, B, and C at the points in the code.
    val x = 4;
    val y = 3;
    val z = 2;
    
    let
        val x = 1;
        val y = x + x;
        val z = y * z;
    in 
       x + y + z
    end;      (* A: What is the value of this let expression?*)
    
    val a = 10;
    val b = 
       let
           val a = 2;
           val b = a + a;
       in 
           a * b  
       end + a;  (* B: What is the value of this let expression? What is its value after summing it with a as shown here?*)
    
    val atLast = x + y + z + a + b; (* C: What is the value of atLast? *)