Study Homework #4: scoping, call graph construction
4/10/2016


I. Examine the following program pseudocode. 
    a.  Assume that this language uses static scoping. What values will be output
by this program.
    b.  Now assume that this language uses dynamic scoping. What values will be output
by this program. (Note: what we have been calling dynamic scoping is what the Scott textbook
calls dynamic deep scoping.) 

1.  procedure main:
2.  	      a: integer = 1
3.	      b: integer = 2
4. 	      c: integer = 3
5.	      procedure P():
6.	      		b: integer = 5
7. 			procedure S()
8.				  print a,b,c
9.			---end S
10.			procedure T()
11.				  b: integer = 4
12.				  a = 5
13.				  S()
14.				  print a,b,c
15.			---end T
16.		       Q()
17.		       T()
18.		---end P
19.		procedure Q():
20.			  print a,b,c
21.		---end Q
22.		P()
23.	        print a,b,c
24.  ----end main

II.  (this is derived from problem #3.13 in Scott textbook). Given the following 
Scheme program, (a) what will be printed when it is evaluated? (b) what would
be printed if Scheme used dynamic scoping?
(Note: A,D,E do not need their parameters but with our verison of DrRacket the program will not 
run without these useless parameters... just ignore them.)

(define A (lambda (z)
            (let* ((x 2)
                   (C (lambda (P) (let ((x 4)) (P 0))))
                   (D (lambda (q) x))
                   (E (lambda (r)
                       (let ((x 3)) (C D)))))
              (E 0))))



(A 0)

III. Given the following class hierarchy in C++ or Java:

A has methods foo(), bar() and direct subclasses: B,C
  B has methods foo(), bar() and direct subclasses: D,F
    D has direct subclass E
      E is a leaf class in the hierarchy and has method foo()
    F is a leaf class in the hierarchy and has method bar()
  C has direct subclass G
    G is a leaf class in the hierarchy and has method bar()

Your task is to examine the following pseudocode and determine
the possible virtual call resolution at the 4 method calls (#1-#4)
(a) using the CHA algorithm and then (b) using the RTA algorithm.

        A a1,a2;
    	B b;
    	C c;
    	a1 = new A();
    	a2 = new A();
    	c = new G();
    	d = new F();

#1:	a1.foo();

#2:	a2.bar();

#3.	d.foo();

#4.	b.bar();

IV. We will reuse the pseudocode from question III and add some 
reference assignment statements after call #4. 

a. Assuming that the method calls, have no side effects on the reference (i.e., points-to)
relations in the program, draw the points-to graph that would be calculated 
for this program by a flow-insensitive, context-insensitive points-to analysis.

        A a1,a2;
    	B b;
    	C c;
    	a1 = new A();
    	a2 = new A();
    	c = new G();
    	d = new F();

#1:	a1.foo();
#2:	a2.bar();
#3.	d.foo();
#4.	b.bar();

	a2 = a1;
	b = d;
	a1 = b;
	a2 = c;


b. What if we used a flow-sensitive points-to analysis and still assumed that the called
methods have no side effects on teh reference relations in the program. Draw each of the
points-to graphs that would exist, at the point in the execution directly AFTER
each these 4 reference assignments.