CS217 Assignment 6, Due Monday, May 8, 2000

You may use the call-by-reference interpreter implemented in interp3-8clean.scm.

1. Ex 3.8.1: Test interp3-8 with examples including primitive applications and letrec.

2. Ex 3.8.3: Test with programs that demonstrate aliasing.

3. Ex 3.8.5: Extend implementation of arrays so that array elements can be passed by reference.
   This will be hard, and is optional!

4. Learn the difference between cbv, cbr, cbvr, cbname and cbneed.

5. Implement while-do and do-while, with grammar

   (expression
     ("while" expression "do" expression)
     while-do-exp)
   
   (expression
     ("do" expression "while" expression)
     do-while-exp)
   

   You can add loops to interp3-7clean.scm.

6. Exercise these loops by writing quicksort in our defined language, translating (found in the sort applet at http://www.cs.oswego.edu/~mohammad/classes/csc241/samples/)

   Quicksort (int data[], int left, int right) {
     int mid,tmp,i,j;
     i = left;
     j = right;
     mid = data[(left + right)/2];
     do {
       while(data[i] < mid)
         i++;
       while(mid < data[j])
         j--;
       if (i <= j) {
         tmp = data[i];
         data[i] = data[j];
         data[j] = tmp;
         i++;
         j--;
       }
     } while (i <= j);
     if (left < j)
       Quicksort(data,left,j);
     if (i < right) 
       Quicksort(data,i,right);
   }
   

   You will also have to extend the interpreter to implement primitives / or mod.
   Your program will look like

   letrec quicksort(data, left, right) =
     let mid = 0
         i = left
         j = right
     in begin
          let mid = arrayref(data, /(+(left, right), 2))
            in do begin
                    while less(arrayref(data, i))
                    do set i = add1(i);
                    ...
                  end
               while less(i, add1(j));
          if less?(left, j) then
            (quicksort data left j)
          else 0;
          if less?(i, right) then
            (quicksort data i right)
          else 0
        end
   in let a = array(5)
      in begin
           arrayset(a, 0, 4);
           arrayset(a, 1, 1);
           arrayset(a, 2, 5);
           arrayset(a, 3, 3);
           arrayset(a, 4, 2);
           print(a);
           (quicksort a 0 4);
           print(a)
         end