Final Exam Study Aid

Answering these questions should help you prepare for the final exam.

1. 
   

   Be able to define and give examples of the terms listed here

   
   
2. 
   

   Be able to answer the questions on the midterm study aid

   
   
3. 
   

   Show an ML function and an invocation of it (a call to it) that would execute to completion under lazy evaluation, but would get into an infinite recursion under eager evaluation.

   
   
4. 
   

   Using a Pascal-ish notation (or any language, as long as you can declare parameter by-value and by-reference), show a procedure, and an invocation of it (call to it) that will produce different results when one or more of the parameters is passed-by-reference, than when passed-by-value.

   
   
5. 
   

   (a) Show an ML function to raise a real number to an integer power. Write it in curried form.

   (b) Write an ML function that will accept one argument: an integer function (that is a function with type int -> int). It will return another function that produces the same result as the one passed in, except it adds 5. For example, if I pass in the function square, the new function passed back will take an integer N and produce N^2 + 5. This is a higher-order function.
   
   
6. 
   

   Consider this ML program:

     fun foo (bar) = 
        if bar = nil then 0
        else 1 + foo(tl(bar))
     ;
   
     val foo = fn : ''a list -> int
   

   As you can see, our function foo has type

      ''a list -> int.
   

   Re-write the function so it computes the same thing, but has type

      'a list -> int.
   

   
   
7. 
   

   Describe the symbol table structure needed by the ML interpreter to manage the scope rules of the language. What are the scope rules of ML?

   
   
8. 
   

   Compare the type system of ML to the type system of Java.
   Compare the type system of Java to the type system of Perl.
   Describe the type system used in most Prolog implementations.
   Describe the scope rules used in Prolog.

   
   
9. 
   

   Consider this Prolog program:

   female(jane). female(cindy).
   male(bob).    male(jack).
   parent(cindy,ann).  parent(bob,arnold).
   parent(jane,tom).   parent(jack,mike).
   father(A,B) :- male(A), parent(A,B).
   father(X,Y).
   

   Show how the intepreter goes about using unification and backtracking to produce the results for the query (the last line of the program). Draw an annotated tree to support your explanation.

   
   
10. 
    

    Explain how dynamic dispatch (dynamic method binding) enhances polymorphism of programs.

    Show some sample C++ code that has dynamic dispatch.

    Show the same sample but in Java.

    Using your code, and discussing it in terms of the type system, show how it is polymorphic.

    
    
11. 
    

    Draw a diagram showing the main components of the Java virtual machine.

    Explain what each of the major parts does, or why it is there.

    
    
12. 
    

    Draw a diagram of the stacks area of the Java VM, showing two active threads. SHow the details of a stack frame, and explain what items are stored there and how they are used.

    
    
13. 
    

    Consider the following code fragment:

    TYPE
      t1 = array[1..10] of int;
      t2 = array[11..20] of int;
      t3 = array[1..10] of real;
      t4 = real;
      t5 = array[1..5][1..2] of int;
      t6 = int;
      t7 = array[1..10] of t4;
    VAR
      x: t1;
      y: t2;
      z: t3;
      r: t4;
      a: t6;
      b: t7;
      d: t5;
      k: real;
      m: array[1..10] of int;
    

    If the type system used structural equivalence, which of the variables would be judged to have the same type?

    If the type system used name equivalence, which of the variables would be judged to have the same type?

    
    
14. 
    
    
    
15.