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



Provide an example Cool program which shadows the name x four times (assuming shadowing is legal for all kinds of declarations). 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()) : ...

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

(Make sure you can handle the kinds of examples show on Handout 45.)

Feature offsets

Calculate the method and attribute offsets for the following program:

  class A(var x : Int, var y : Int) extends IO()
    // don't forget the constructor!
    def type_name() : String = ...;
    def getx() : Int = ...;
    def gety() : String = ...;
    var z : Boolean;
    def testz() : Boolean = ...;
    def in_int() : Int = ...;

  class B() extends A(0,0)
    // don't forget constructor!
    var a : String;
    def testz() : Boolean = ...;
    def seta(s : String) : Any = ...;
    def geta() : String = ...;
    def copy() : Any = ...;

  class Main() extends IO()
    // don't forget the constructor!
    var a : Int;
    def seta(i : Int) : Any = ...;
    def geta() : Int = ...;
    var b : Boolean;
    def copy() : Any = ...;

	// the following two classes are from basic.cool

  class Any() extends native {
    // don't forget constructor!
    def toString() : String = native;
    def equals(x : Any) : Boolean = native;

  class IO() {
    // don't forget the constructor!
    def abort(message : String) : native;
    def out(arg : String) : IO = native;
    def is_null(arg : Any) : Boolean = ...;
    def out_any(arg : Any) : IO = ...;
    def in() : String = native;
    def symbol(name : String) : Symbol = native;
    def symbol_name(sym : Symbol) : String = native;

Analysis and Synthesis


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;

  procedure x;
    var a : Integer;
      a := 23;

  a := 17;

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

Symbol Tables

Given a particular referencing environment, one may ask two questions about whether a symbol is defind in it. The difference is related to the concept of a "contour." Name the two questions 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 specific COOL situations.

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 = ...;

  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

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";
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. Set union and intersection can be written using arithmetic operators + and * respectively.

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);
  def pop() : T = {
      var top : T = l.hd();
      l =  l.tl();
  def isEmpty() : Boolean = is_null(l);
     var s : Stack[Int] = new Stack[Int]();
     out("Result is ");
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, for example: attribute grammar notation, for example: