Assignments

These assignments constitute the examination in the course. You are supposed to hand in written solutions, preferrably by email. Handwritten, snail-mailed solutions are also allowed, but you then risk delays in my grading in case I'm out of office for some reason and cannot pick up the solution from my mailbox. Handwritten, scanned and emailed solutions are also OK: however, then make sure the scanned document is legible before you submit!

The solutions should be clear and complete enough: just answers aren't enough, I must also see how you arrived to the answers. However, obvious steps need not be displayed: if, for instance, a solution requires a fixed-point iteration, then it is likely that showing one ot two representative iterations in detail will suffice. What matters most is that I can see that you understand the principles and master the techniques.

For programming assignments, you should also hand in the source code (email required). This code must then be possible to compile and run on various platforms, so I can test it (i.e., don't use any platform-specific language extensions or similar).

Chapter 1

Exercise 1.8 (p. 32). Also analyze the example program using the annotated type systems of Section 1.6.1 (Tables 2 and 3).

Let us extend the While language of the book with pointers, which can point to program variables. More specifically, we add two operations: referencing &x of program variable x, creating a pointer to x, and dereferencing *e of pointer-valued expression e, retrieving the current value in the variable pointed to by e. We also add assignments of the form *e := e', which assigns the variable currently pointed to by e the current value of e'.
Now extend to Reaching Definitions analysis of Chapter 1.3.1 to the extended While language! You may assume that we already know, for each label l and pointer expression e, a set points-to(l,e) which contains (at least) the variables e possibly can point to immediately before executing the statement with label l.

Chapter 2

Exercise 2.4 (p. 136). Also implement your "strongly live variable analysis" using PAG/WWW!
Note: you must assume that all variables are strongly live at exit. (Otherwise, all variables will be faint everywhere in the program.)

Exercise 2.11 (p. 137). Also construct an example program, where a hypothetical reaching definitions analysis, which uses the increased information about conditions, could calculate a more precise flow information than the analysis given in the book.

Exercise 2.14 (p. 138), with the following simplifications. You need only consider the first version of the analysis. Your analysis does not have to use information from conditions to improve the precision. You can restrict your analysis to programs with arithmetic expressions containing the operators + and - only.

Hint: you must define an abstract semantics for arithmetic expressions, which calculates sets of signs rather than numbers.

Optionally, you may also implement your analysis with PAG/WWW, but this is not required for the examination.

Use your Detection of Signs Analysis from the previous assignment to perform an interprocedural, context-sensitive analysis of the Fibonacci program in Example 2.33 (p. 83)! Use call strings of length at most 1 as contexts. Assume that x is non-negative in the call in the main program. (Note: you cannot use Example 2.40 right off, since that example is based on the more complex Detection of Signs Analysis from Exercise 2.15.)

Chapter 3

Exercise 3.1 (p. 205). However, instead of guessing the result, calculate it using the constraint based control flow analysis of Section 3.4.

Chapter 4

Exercise 4.1 (p. 276).

Exercise 4.6 (p. 277).

Exercise 4.13 (p. 279).

Chapter 5

Exercise 5.1 (p. 359). In addition to performing an "ad-hoc" control flow analysis using Table 5.2, also analyze the program systematically using the algorithm in Section 5.3.2.

Calculate the "best" annotated types and effects for the fib program in Example 5.24 (pp. 319-320), using the type inference system for side effect analysis of Table 5.9 (p. 322)!

Analyze the program in Example 5.28 (p. 326) with respect to exceptions, using the type inference system of Table 5.10 (p. 328)! As usual, try to find the tightest solution (smallest sets of possible exceptions).

Chapter 6

Redo Exercise 1.8, first using the Round-Robin Algorithm and then by iterating through strong components.

Mini Project

Either do the mini project below, or suggest another mini project of comparable size, which you can do instead if approved.

Miniproject 2.3 (pp. 134-135). You are not allowed to use PAG/WWW (since you would be able to snatch a solution right away, and furthermore I want you to understand the basic function of the worklist algorithm well enough to be able to implement it). Apart from that, you are free to use whichever implementation language you want (however, a language like the suggested ML or Haskell is likely to give you a simpler solution). You don't have to write a frontend for the While language: rather, your analysis can take as input an instance of the monotone framework for the live variable analysis and the program to be analyzed. (That is: basically the control flow graph of the program, plus transfer functions for the blocks.)
Try out your implementation on a few examples, and hand in the results with your solutions.

Björn Lisper
bjorn.lisper#mdh.se