Data Flow 2
This is for many students a particularly hard assignment, so be sure
to start on time. The assignment may be done alone or, preferably, in pairs.
Every student should be able to explain orally and clearly
every part of the assignment he hands in. The lecturer has the freedom
to ask this explanation at any time, meaning that you might not be warned
Both parts of the assignment have equal weight in the final grade.
The goal of the assignment
To get a really thorough
understanding of what is really happening in Chapter 2,
you shall work on the following subjects:
- How to prove a soundness result for an analysis
- How to deal with the extension for procedures
Sometimes I ask you to give an illustrative, but small example.
The idea is that your example should be as varied and broad as possible,
but on the other hand should be as concise as possible. For instance,
in the case of Strongly Live Variables (see below), I expect an example
where a variable is strongly live, one which is not, one which is live
but not strongly live, and maybe you can think of other cases. The bottom line is that
your example is an alternative for a soundness proof, so the more convincing
your example, the more convinced people will be (actually, a proof also only
does the job when it is convincing).
The general rule is: Motivate your answers
The various parts of the assignment
Part 1: prove a soundness result.
Hint: It may surprise you that Lemma 2.16 does not hold in this case.
Explain in your answer why that is, and modify the analysis so that it
does hold and then continue.
Do Mini Project 2.2 on page 133.
Part 2: procedures and context
Do Exercise 2.18 for the Live Variable analysis.
Work out the fibonacci example of Example 2.42 (page 103)
by giving the resulting embellished monotone framework
with context being call strings bounded by length k=2.
(Beware: there are a few snakes in the grass here.)
Remark: you do not have to work out the iteration itself.
Be very precise when you give the transfer functions, especially
those for call and return.
What, how and when to submit
Details can be found here
In whatever fashion you hand things in make sure things are clear and
readable and on time. Make sure that you motivate
Experiences from last year
Part one is one many that students at first find difficult to do.
Do not be fooled to believe that the
proof is a copy of that in the book: it follows the same line, but
what you actually have to prove is quite different, and asks for
a different point of view. In practice it turned out that most students
did this well.
Part two is also quite difficult, and people tend to forget quite a few details
here. The main complication is how to simulate scoping.
Even if you are unable to give complete formal details, be sure to explain
how you conceptually can solve the problem. This already gets you quite
a few points.
- 14 Nov 2008