Midterm #2: Sample Questions

This page includes questions by the instructor (John Boyland) and others. At least one of the questions will appear on the second midterm.

Review Questions

Review questions from Chapters 3, 7, 9, 14 may appear on the second midterm.

Definitions and Short Answers

Algorithms

Scopes

Provide an example Cool program which shadows the name x four times. Show the point within the program that is in the innermost scope.

Referencing Environments

Give the complete referencing environment for the indicated place in the following Cool program. Include all the predefined classes and their methods, but you won't be penalized if you forget one or two methods in each predefined class.

  class Main() {
    var x : Int = 3;
    {
      var s : String = new IO().in();
      new Test(s)
    };
  }
  class Test(var v : Any) extends IO() {
    var id : Int = 0;
    {
      v match {
        case q:String => out("A string!\n")   !HERE!
	case o:Any => out(o.toString())
      }
    };
  }
Please indicate structure in the method namespace (don't put all the methods in one scope).

Type Equivalence

Given the following declarations

  typedef struct { int i; double val; } test;
  typedef int num;
  typedef double value;
  typedef struct { int x; double y; } mystruct;
  typedef struct { num i; value val; } myrec;
  typedef struct { int x; double val; } test2;
  typedef struct { int q; } istruct;
  typedef struct { double r; } dstruct;
  typedef struct { istruct i; dstruct d; } tests;
  typedef test test3;
For each pair from the set {test,mystruct,myrec,test2,tests}, say whether they would be true under ...
  1. layout equivalence,
  2. structural equivalence,
  3. structural equivalence where field names must be the same,
  4. definitional name equivalence (what C uses),
  5. pure name equivalence.

Type Inference

Complete the following typing tree (given the Cool inference rules):
...

[],M |- new A.A(3).print(new IO.IO()) : ...
where

class A(var v : Any) {
  var k : Any = v;
  def print(io : IO) : IO = io.out(k.toString());
}

Analysis and Synthesis

Capitalization

Given that we have separate namespaces for objects and types, do we need the rule that variables must start with lowercase letters and types must start with uppercase letters? Why or why not ?

Dynamic Scoping

Given the following program, indicate the value printed if (i) static scoping is used (ii) dynamic scoping is used. Explain your work:

program scopeTest;
  var a : Integer;

  procedure p;
    begin
      WriteLn(a);
    end;

  procedure x;
    var a : Integer;
    begin
      a := 23;
      p
    end;

begin
  a := 17;
  p;
  x;
end.

What if we added dynamic scoping to Cool? What would change in the semantic analysis phase ?

Symbol Tables

OUT OF DATE In PA4, we use the SymbolTable class to create several tables. This class has two methods which provide ways to get information out of the table. Give the names of these methods and describe why we need two different functions to see if a given symbol has a mapping in the table. In which cases do these methods have the same result, in which case different results ? Give examples in terms of the tables you have defined.

Given the following (with a hypothetical SymbolTable class), what is printed by the last line? Please explain.

{ var st : SymbolTable = new SymbolTable();
  
  var int_class : Class = ...;
  var obj_class : Class = ...;
  var bool_class : Class = ...;
  var str_class : Class = ...;

  st.enterscope();
  st.addid('A,int_class);
  st.addid('B,obj_class);
  st.addid('C,bool_class);
  st.enterscope();
  st.addid('D,str_class);
  st.exitscope();
  println(if (st.lookup('D)) "Yes" else "No");

Overriding in Cool

In Cool when you override a method you must not change the number or type of the parameters, and you can only change the return type to a subtype (that is, derived class). Give two example Cool programs that are rejected by the Cool compiler for precisely this reason (and for no other reason). The first one should should be flawed so that it would crash at run time if static analysis were to mistakenly let it past. The second one should override in a way that is actually always safe (no matter what the body of the overriding method is, no problems will ensue as long as the body type checks).

Give a relaxed overriding rule that nevertheless only lets through programs (such as the second example) that will not cause problems.

Arrays in Cool

Suppose Cool had a way to indicate the base type of an array. Anywhere a class is used (for example to specify the type of a local variable), we can instead have

	Array[type]
Assume that the object referencing environment O maps names to types (either classes or else Array[type]), complete the following type inference rule:
...

O,M |- e[e'] : T
Make sure your rule requires the index to be an integer, and that it handles the case where a class inherits from an array. Write axion for type-checking array assignment as well.

Should we add the following type rule?
T <= T'

Array[T] <= Array[T']

Consider the following Cool expression:

{
  var a : Array[Int] = new Array[Int](10);
  var b : Array[Any] = a;
  b[1] := "hello";
  a[1]
}
Suppose that new Array[Int](10) creates a new array of integers with 10 cells. What is the static type of the whole expression? (That is, what is the type inferred for the whole expression, assuming we add the above rule?) What is the dynamic type? (That is, what is the class of object that will result from executing this expression?)

Sets in Cool

Suppose COOL has a new type for sets of integers. You may use it in this way:
{ 
  var s : Set = [1,2,3];
  var t : Set = [3,4,5];
  if (s.union(t).contains(5) ... else ...
}
where Set is declared in basic.cl as:
// immutable set class
// (Methods return new sets, never change 'this')
class Set() {
  var size : Int;
  var contents : native;
  def size() : Int = size;
  def insert(i : Int) : Set = native;
  def union(s : Set) : Set = native;
  def contains(i : Int) : Boolean = native;
}
We presume that the parser converts set expressions such as [1,2,3] into calls to the methods above.

Templates in Cool

Supposed we allowed classes in Cool to have parameter types (in the manner of Array in the previous questions). The parameter type could be used wherever class names could be used. One could then write code such as the following:

class Stack[T]() extends IO() {
  
  var l : List[T] = null;
  
  def push(element : T) : Stack[T] = {
      l := new List(element,l);
      this
  }
  def pop() : T = {
      var top : T = l.hd();
      l =  l.tl();
      top
  }
  def isEmpty() : Boolean = is_null(l);
}
...
   {
     var s : Stack[Int] = new Stack[Int]();
     s.push(10);
     s.push(30);
     s.push(s.pop()+s.pop());
     out("Result is ");
     out_any(s.pop());
     out("\n")
   }
...
Assume that type parameters are only visible in their classes (not even subclasses, let alone in the rest of the program).

How would this change affect the form of the referencing environment?

How would the change affect how one infers the type of an expression such as out_int(s.pop()) ?

Attribute Grammars

You should be able to express binding and type issues using attribute grammar notation.