Homework 5 Solution

In Java, the following is legal:



String[] Y;




Object[] X;




...




X=Y;




That is, an array of T1 may be assigned to a variable of type array-of-T2 as long as T1 is a subtype of T2. As it turns out, this rule is unsound in the sense that because of it, certain type errors can only be discovered at execution time, requiring a (somewhat) expensive check that slows down some operations. Give an example of how this can happen (by which I mean an actual Java program).




Write a legal Python program that simply prints “static” and that would also be legal if Python used dynamic scoping, but would print “dynamic” instead.



Show how the type rules from slide 18 of Lecture 18 work to determine the types of Y, g, and fact in



def Y
f = f (Y
f)
def
g
h x = if
x
= 0 then 1 else h(x-1) * x fi
def
fact x = Y
g
x



Assume that ‘-’ and ‘*’ obey the same rules as ‘+’. (Aside: for obvious reasons, this particular definition of Y, the “paradoxical combinator,” won’t actually work unless this language uses NORMAL-ORDER EVALUATION, in which expressions are not evaluated until their value is actually used in a primitive operation. However, evaluation is not the point here.)




Let’s look at a very simplified sketch of scope analysis to give you a chance to work out the logic of scope analysis in our project on a simplified language. This language has the following syntax:



program: /* empty */ | program outer_stmt ;




outer_stmt: stmt | def | class ;




stmt: ID "::" type "=" expr ";"




| ID "=" expr ";"




;




stmts: /* empty */




| stmts stmt




| stmts def ;




1


HOMEWORK #5
2









def: "def" ID "{" stmts "}" ;




class: "class" ID "{" stmts "}"




type: ID




expr: /* empty */ | expr ID ;




The skeleton file scoper.py reads this syntax and produces an AST for it (see the skeleton). Fill in the skeleton to




Find all the distinct definitions, according to the rules. The definitions are names defined by def, names defined by class, and names that are assigned to.



Check that definitions are consistent: identifiers may not be multiply defined (no overloading here); multiple assignments to an identifier in the same declarative region result in only one local variable; a name may be defined to be only one kind of thing (local, method, or class) in the same declarative region.



Check that each name defined by an ‘outer stmt’ (via def, class, or assignment) is so defined before any uses of it.



Make sure that all names appearing in ‘exprs’ are defined somewhere in an enclosing declarative region (for inner functions and locals, this can be before or after the use, as in Python.)



If there are multiple assignments to the same variable (i.e., in the same declarative region) using the :: syntax, make sure the type name is the same in each case (no check is needed for other assignments).



Make sure that all ‘type’ identifiers refer to classes (and are defined prior to the use of the type).



As in Python, members of a class are NOT directly visible inside a method of the class (i.e., without ‘.’, which this problem does not address.)



Number each distinct defined local, function, or class, and decorate the identifiers with the appropriate numbers. To make things deterministic, the skeleton has you do this by decorating identifier nodes in the AST with objects (type Decl), so that identifiers that refer to the same entity point to the same Decl. There is machinery in the skeleton to number these decorations.






The skeleton will print out the resulting program and annotations. The files eg.scp and eg.out provide a sample input and output.