CSE 341 : Homework 1

Due: 2 April 2001, at the beginning of class

Directions: Submit a typed, stapled hard copy with your name(s), section(s), and the answers to each of the questions below.

Update 31 March: Question 5 updated with sample box and arrow diagrams

1. Consider the following code in ML and C++ respectively:

   (* ML version *)
   val whale = {name="Orca", length=24}; 
   my_function(whale);
   // --- PROGRAM POINT A ---
   
   // C++ version
   struct Whale {
       char * name;
       int length;
   };
   Whale * whale = new Whale;
   whale->name = "Orca";
   whale->length = 24;
   my_function(whale);
   // --- PROGRAM POINT B ---
   

   What is known about the whale record's value at the line labeled "PROGRAM POINT A" in the ML version? What is known about the whale record's value at the line labeled "PROGRAM POINT B" in the C++ version?
2. Consider the following C++ code to declare, initialize, and manipulate structs:

   char * concat(char * first, char * second); // defined elsewhere
   
   struct Whale {
       char * name;
       int length;
   };
   
   Whale * whale = new Whale;
   whale->name = "Orca";
   whale->length = 24;
   
   Whale * big_whale = new Whale;
   big_whale->name = concat("Big ", whale->name);
   big_whale->length = whale->length * 2;
   

   Write ML code that has an effect equivalent to the above---that is, write ML code that binds equivalent values to whale and big_whale.
3. Consider the following C++ code:

   struct Whale {
       char * name;
       int length;
   };
   Whale * whale = new Whale;
   whale->name = "Orca";
   whale->length = 24;
   
   whale->length = whale->length + 10;   // Whale grows
   

   Why can't code equivalent to the line labeled "Whale grows" be written in ML?
4. Consider the following C++ list interface:

   class IntList {
   public:
      IntList(int head, IntList * tail);
      int hd();
      IntList * tl();
      bool null();
   private: // ... etc.
   };
   

   1. Translate the following C++ code to ML code that has the same effect, using the ML list built-in data type.

      IntList * otter = new IntList(3, new IntList(4, new IntList(5, NULL)));
      IntList * sea_otter = otter->tl();
      IntList * river_otter = new IntList(2, sea_otter);
      

   2. Now, translate the following ML code to C++ code (using the above IntList class) that has the same effect:

      val walrus = 30 :: 40 :: 50 :: nil;
      val seal = 10 :: 20 :: walrus;
      val porpoise = hd(seal) :: tl(walrus);
      

5. Draw clean and clearly labeled box and arrow diagrams of the variables and data structures produced by the following code:

   1. val kelp = [1,2,3];
      val seaweed = tl(kelp);
      val algae = 5 :: 6 :: seaweed;
      

   2. val urchin = { greetings=["hi","hello","howdy"],
                     days=365,
                     birthday=("February",29,2000) };
      val anemone = #greetings(urchin);
      val starfish = (hd(anemone), "there");
      

   3. val a = 1;
      val b = a :: [2];
      val c = (b, "foo", ("hello", "world", ["bye"], tl(b)));
      val d = #4(#3(c));
      

   Make sure your diagram shows clearly which structures are lists, tuples, and records.
   Update 31 March: Here are some sample box and arrow diagrams, in case you are unsure how these should be drawn.
6. [Challenge] None of the lectures slides or homework questions have mentioned anything about the order in which expressions are evaluated. Why don't we need to talk about order of evaluation, in the subset of ML that we have learned so far?

The most recent version of this document can be found online at the following URL:

http://www.cs.washington.edu/education/courses/cse341/01sp/homework/hw1.html