Data Flow

In short

In this assignment you shall experiment with and extend the material from Chapter 2 of Nielson, Nielson and Hankin, mainly by doing a selection of the exercises similar to those in the book. The various parts are largely independent, and I have indicated when you have the necessary information to complete the assignment.

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 in advance).

Not all of the components below are worth the same number of grade point: Part 1 to 3 are weighted at 20, 40, 40 percent.

The goal of the assignment

A large part of the chapter is devoted to developing a dataflow analysis framework for an imperative language. To get a thorough understanding of what is really happening underneath all that notation you shall work on the following subjects:

• How to develop the transfer functions for a given analysis
• How chaotic iteration should be performed
• How to develop transfer functions for new language constructs and instantiate these for a specific analysis

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: developing a new analysis within the framework

Do Exercise 2.4 for Strongly Live Variable Analysis on page 136 of NNH, formulate your answer similar to Table 2.4 on page 50.

Part 2: performing chaotic iteration

Design a While program of at least five blocks which well illustrates the Strongly Live Variable Analysis (it should contain at least one while loop). Apply Chaotic Iteration to the set of equations that you obtain as a result of applying Part 1 to your program, showing also intermediate values for the iterations (similar to what I do in the slides for Available Expressions). Indicate how SLV is different for this example from the standard LV (and make sure that your example allows you to illustrate this fact).

Part 3: adding new constructs to the While language

Add the following three programming constructs to the While language. Describe, in general, what has to change to accommodate each of the constructs. To avoid too much work: you don't have to give the semantics of the new language constructs, but it is wise to describe it for me. (Hint: sometimes it is sufficient to add new transfer functions, sometimes a change has to be made to a different parameter of the monotone framework. Deciding this is, of course, up to you.)

• A print a statement where a is an arithmetic expression. Show how to adapt the Strongly Live Analysis to accommodate programs which contain print statements. Devise a small program which shows that your extension works as expected. (You do not need to perform Chaotic Iteration. What you should do is give the equations for your program, propose a good (preferably the best) solution, indicate why you think this is a reasonable solution and verify that it fulfills the equations).
• Simultaneous assignments: a simultaneous assignment is of the form v1, ..., vn := a1, ..., an, which assigns the value of a1 to v1, a2 to v2 and so on. The semantics of such a statement is that first the sequence of expressions a1 to an is evaluated, and when this is done, the resulting values are stored in the corresponding variables in left to right order.

  Add simultaneous assignments to the While language and show how to adapt the Strongly Live Variable Analysis to accomodate it.

  Illustrate that your solution works by giving an example.

• The break and continue statement: the semantics of break is to leave the enclosing loop statement, the semantics of continue is to proceed to the enclosing loop condition. What break and continue do when they are outside any loop, I leave up to you. But you have to make up your mind for each what happens and document that well. For testing, devise a small, but suitably complicated program and analyze it to illustrate that your proposed modifications work for Available Expressions Analysis described in the book.

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 your answers.

Experiences from last year

This is a start-up assignment and generally not very difficult.

-- JurriaanHage - 14 Nov 2008