COMP 144 Midterm Exam (Spring 2004)

1. 
   

   Consider this program:

   program midTerm {
   
   01   // globals
   02   int x = 5;
   03   real y = 2.5;
   
   04   proc P1 (int x, ref real z) {
   05      boolean b = false;
   06      real r2;
   
   07      proc inP1 (real p1) {
   08         int x;
   09         boolean flag = false;  
   10         x = (p1 + z) * y ;  
   11         p1 = x * 1.3;
   12      }
    
   13      /* body of P1 */
   14      r2 = x/z;
   15      z = r2 * r2;
   16      inP1 ( r2 );
   17      P2(r2,x); 
   18      print r2;
   19   }
   
   20   proc P2 (real m, int k) returns int {
   21      // locals for P2
   22      int d = 3;
   23      real zz;
   
   24      proc inP2 (ref int x) {
   25         // locals for inP2
    
   26         proc ininP2 (real s) {
   27            // locals for ininP2
   28            // body of ininP2
   29            s = s * 1.2;
   30            print s;   
   31         }
       
   32         // body of inP2
   33         x = 5;
   34         ininP2(m);
   35      }
        
   36      // body of P2
   37      inP2 (k); 
   38   }
   
   39   main {
   40      P1(x,y);
   41      print x;
   42   }
   

   Draw a diagram of the runtime stack that exists the first time line 30 is reached during execution. Assume this program executed with call-by-value parameter passing unless the keyword "ref" appears before a parameter definition (like in lines 4 and 24 and above), in which case it is call-by-reference for that parameter. Make sure to show the contents of the stack frames... variable, parameters, other stuff that belongs in there to allow static scope rules for finding non-local references at runtime to work correctly. For return addresses, you may use the line numbers given next to the code. You may draw your stack with either static chain pointers or a display, your choice.
   
   
2. 
   

   (a) Write a simple ML function called rev2 to reverse a list pairwise, meaning reverse the 1st and 2nd elements, and also the 3rd and 4th, and also the 5th and 6th, etc.

     Example:  rev2 [1,2,3,4,5,6,7,8]  is  [2,1,4,3,6,5,8,7]
     Example:  rev2 [1,2,3,4,5]  is [2,1,4,3,5]
     Example:  rev2 [6] is [6]
     Example:  rev2 [] is []
   

   Use curried notation, and write it as a collection of partial functions defined with the pattern matching facility of ML. Make the function as polymorphic as possible.

   (b) Explain when you are done how polymorphic it is, and if there are any limitations. Do this by discussing the type information given by the interpreter when you define the function.

   Remember you can use the ML interpreter to check your work. Hand in some interpreter output that shows how your solution works.

   
   
3. 
   

   Write a higher-order ML function called "maker" to do the following.

   "maker" takes 2 arguments: an integer "n", and a function "f".

   The function "f" takes one argument of its own, an integer "k".

   "maker" will produce a function then computes f(f(f(...f(k)...) nested applications of f to k, where there are f(n) nested applications.

   Example: fun sq x = x * x ;
            val R = maker sq 4 ;
            R 3 ;
     R will first find that sq 4 is 16, and will then do sq(sq(sq...sq(3)...)
     for 16 nested applications.
   

   Remember you can use the ML interpreter to check your work. Hand in some interpreter output that shows how your solution works.

   
   
4. 
   
   Write, in a syntax of your choice, a program that will have 3 different outputs depending on whether parameters are passed to subprograms by

   1. value
   2. reference
   3. value/result

   Make to sure to clearly indicate what output your program gives for each method.