1.  (24 points).    Assuming the simple Hoare logic as presented in class in which x, y, and z are names/variables, identify which of the things below are valid Hoare triples (valid), well- formed Hoare triples (wff HT) but not valid, or neither (not).  For each statement below, circle the one best answer of the three choices. Correct answers are worth one point, incorrect answers lose one point. (The symbol ^ stands for logical disjunction, and ⊥ for false.)

(a) valid / wff HT / not   { y = 5 } if  x > y  then  x  :=  8  else  y  :=  5 { y = 5 } (b) valid / wff HT / not   { z = 8 } while  z > x  do  x :=x + 1  od { x = 8 ^ y = 8 } (c) valid / wff HT / not   { x = 0 } while  z = x  do  x :=x + 1  od { x = 8 ^ y = 5 } (d) valid / wff HT / not   { ⊥ } y, z  :=  x, y { x = 8 }

(e) valid / wff HT / not   { x + 1 = 2 } y  :=  2 ;  x  :=  x + 1 { x = y }

(f) valid / wff HT / not   { x > y } if  x > z  then  x  :=  8  else  y  :=  5 { y = 5 } (g) valid / wff HT / not   { y = 5 } if  x > y  then  x  :=  8  else  y  :=  5 { x = 8 } (h) valid / wff HT / not   { x = 2 } y  :=  2 ;  x  :=  x + y { x = y }

(i) valid / wff HT / not   { 8 = 8 } x  :=  8 { x = 8 }

(j) valid / wff HT / not   { z > 8 } if  x > z  then  y  :=  x  else  y  :=  8 { y >= 8 } (k) valid / wff HT / not   { x ≤ 8 } x  :=  8 { }

(l) valid / wff HT / not   { x := 8 } x  :=  8 { z = 2 }

2.  (10 points).   What does it mean that arrays are covariant in C# and Java?

3.  (10 points).    Generally speaking, what is bounded quantification polymorphism and what problem does it solve?

4.  (10 points).    Write a simple, Algol-like program that distinguishes dynamic scoping from static scoping. Explain.

5.  (10 points).   Considering the scope of names in a program, the C programming language is “flat,” but Algo-like languages, Ada for example, are “hierarchical” or nested.

(a) Explain what this means with a small example or illustration.

(b) What are the advantages of “flat?”

(c) What are the advantages of “hierarchical?”

6.  (10 points).    Suppose you are writing a compiler for a language like Modula-3 which has procedure variables. In the program Main, x is a procedure variable.

MODULE   Main ;

TYPE   f   =   PROCEDURE   ( z :   INTEGER );    (*   procedure   type   *) VAR   x :   f ;

PROCEDURE   P   ( z :   INTEGER )   =   BEGIN    (*   ...   *)   END   P ;

BEGIN

x   :=   P ;         (*      assignment      *)

x (2);               (*      call                       *)

END   Main .

Explain exactly how the assignment gets implemented and how the call gets implemented so that non-local variable access works correctly.

7.  (40 points).   For each statement below, circle either “true” or “false” as appropriate. Correct answers are worth one point, incorrect answers lose one point.