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

The following review questions from the textbook may appear on the midterm:

3.1-4, 3.14-16, 3.24-25
4.1-2, 4.5-8
7.1-6, 7.13, 7.19
10.1-4, 10.7-8

Definitions and Short Answers

What are the differences between context-free grammars and tree grammars?
What differences does bottom-up versus top-down parsing make for building an abstract syntax tree?
In a one-pass compiler: how does the model of attribute grammar (S-, versus L-attributed) interact with kind of parsing (LL versus LR)? What role does an AST play?
What are the seven binding times according to the book and what general decisions are made at each time?

For each of the possible binding times on the left, match them to a type of binding on the right that would occur during that time:

(1) language design time	(a) joining of modules
(2) language implementation time	(b) precision of floating point variable
(3) program writing time	(c) mapping high-level constructs to machine code
(4) compile time	(d) binding of values to variables
(5) link time	(e) creation of primitive data types (e.g. integer)
(6) load time	(f) mapping of labels to runtime (virtual) addresses.
(7) run time	(g) a variable declaration in a program

What are the two main tasks in static analysis? Explain briefly.
Contrast scope with referencing environment.
Describe the structure of the referencing environment of a Cool expression with regard to all three namespaces.
What is the difference between deep and shallow comparison? What are the (dis)advantages of each? Which does Cool use?
In Cool, a method may be called from anywhere in the program. Given a class and a method, give an example of how this method could be called from any method you write. How does this language feature influence how we semantically check a Cool program?
What are the three type operations (two of which are relations)? Give an example of each how it is used in type-checking Cool programs.
How would the implementation of type compatability in Cool need to change if there were multiple inheritance?
What does strong typing mean?
What is a static type system, a dynamic type system? Why would a language implementor choose one or the other?

How can we avoid cascading errors when a class is unknown, e.g.

declare x : Float := 0;
begin
  ...
    x := x + 1;
  ...
end

Identify, define and describe the important of the three fundamental characteristics of object-oriented programming languages. How do they impact compilation?
What does it mean for a class to be abstract? What causes it? Why do we have abstract classes?

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 is
    x : Integer;
    Main() begin
      declare s : String := new IO.in_string();
      begin
        new Test(s)
      end
    end;
  end;
  class Test : IO is
    id : Integer;
    Test(v : Object) : IO :=
      case v of
        when q:String => out_string("A string!\n")   !HERE!
	when o:Object => out_string(o.type_name())
      esac;
  end;

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

layout equivalence,
structural equivalence,
structural equivalence where field names must be the same,
definitional name equivalence (what C uses),
pure name equivalence.

Type Inference

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

...

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

where

class A is
  k : Object;
  A(v : Object) begin k := v end;
  print(io : IO) : IO := io.out_string(k.type_name());
end;

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

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, what is printed by the last line? Please explain.

{ SymbolTable = new SymbolTable();
  
  Class_ int_class = ...;
  Class_ obj_class = ...;
  Class_ bool_class = ...;
  Class_ str_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();
  cout << (st->lookup(#D) ? "Yes" : "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:

declare 
  a : Array[Integer] := new Array[Integer](10);
  b : Array[Object] := a;
begin
  b[1] := "hello";
  a[1]
end

Suppose that new Array[Integer](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:

declare 
  s : Set := {1,2,3};
  t : Set be {3,4,5};
begin
  if s.union(t).has(5) then ... else ... fi
end

where Set is declared in basic.cl as:

-- immutable set class
-- (Methods return new sets, never change 'self')
class Set is
  size : Integer;
  contents : native;
  Set() begin self end;
  size() : Integer := size;
  insert(i : Integer) : Set native;
  union(s : Set) : Set native;
  has(i : Integer) : Boolean native;
end;

We presume that the parser converts set expressions such as {1,2,3} into calls to the methods above.

Do you need to change anything in name resolution to handle this extension ? Explain.
Do you need to change anything in type checking? Explain.

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] is
  
  l : List[T];
  
  Stack() begin l := void end;

  push(element : T) : Stack[T] := begin
      l := new List(element,l);
      self
  end;
  pop() : T := 
    declare
      top : T := l.hd();
    begin
      l:=  l.tl();
      top
    end
  end;
  isEmpty() : Boolean := l == void;
end;
...
   declare 
     s : Stack[Integer] := new Stack[Integer]();
   begin
       s.push(10);
       s.push(30);
       s.push(s.pop()+s.pop());
       out_string("Result is ");
       out_int(s.pop());
       out_string("\n")
   end
...

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

Constant evaluation

Suppose we wish to write an attribute grammar to do constant evaluation on Cool ASTs for the purpose of replacing expressions with literals at compile time. A design of such an attribute grammar with two synthesized attributes isc (true if the expression is a constant boolean or integer) and val (the value if it was constant, where 0 = false and 1=true for boolean expressions). Write the rules for the following COOL AST nodes:

int_const
bool_const
string_const
null
lt
add
mul
div
cond

Evaluate your attribute grammar over the following example. Draw the AST and show the value of each attribute on every node. Make sure you follow your own rules!

if 3 < 2 then x*(65536/0) else 10*(65536/2) fi

What would be necessary to add if we wished to use the values of variables so that we could replace at compile-time expressions such as

	declare n : Integer := 3 begin n + 10 end

with their values 13? Explain, and give how the rule for add would change.