Control Flow Assignment

In short

In this assignment you shall experiment with and extend the material from Chapter 3 of Nielson, Nielson and Hankin, corresponding roughly to Mini Project 3.2 Data Structures on page 201. Furthermore, you should complete a few of the exercises in the book, which are of a more theoretical nature. 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.

Part 1 of this assignment is 70 percent of your grade, each of the exercises in part 2 is worth 10 percent.

The goal of the assignment

A large part of the chapter is devoted to developing a control flow analysis for a small functional language. To get a thorough understanding of what is really happening underneath all that notation and to fully grasp the meaning of the tables 3.5, 3.6 and the algorithm of Table 3.7, we extend the programming language with a fixed but arbitrary set of data constructors (besides the primitive boolean and integer types). In addition, I expect you to complete a number of exercises taken from the book and hand answers to them in as well, to avoid focussing too much on a single aspect of the chapter.

The general rule is: Motivate your answers

The various parts of the assignment

The first part of this assignment is quite a bit of work.

Part 1: analyzing data structures during control flow analysis

In a first approximation, this assignment is Mini Project 3.2, which adds data structures to Fun. Given some fixed set of constructors, for instance Constr = { cons, nil, just, nothing }, the programmer is allowed to construct data using these constructors. Examples are just (cons(1,nil)) and nothing(). Note that every constructor has a fixed arity (number of arguments) and every constructor always has all its arguments: cons(1) is not valid.

The case expression allows us to patternmatch on constructed data items and to bind the arguments of the constructor to different variables which can then be used. Note that for simplicity the case statement handles only one pattern at the time. If you have a datatype with more than two possiblities, then a nested case must be used. This is not an essential difference, but makes things easier to specify (for you).

The next step is to modify Tables 3.5, 3.6 and 3.7 to handle the new cases, and also to modify parts of the table to cope with the fact that the sets of values computed for each identifier and expression has changed to include also constructed items (as explained in the exercise). The construction should be general enough to deal with arbitrary named constructors (of fixed arity).

Essentially it amounts to finding a good solution to the following problem: control flow analysis wants to find out which functions can be applied where. However, what if we construct a list with functions, and then write a function that takes such a list, retrieves all the functions in it and applies those?

In addition to extending the tables to cope with the new construct, I also expect you to perform an analysis of the following program.

(let 
    length = (fun ln xs => 
               (case xs[1] of 
                 cons (z,zs) => (1[2] + (ln[3] zs[4])[5] )[6] 

                 or ys       => 0[7]
               )[8]
             )[9]
 in ( (fn x => (x[10] * x[11])[12] )[13] 
      (length[14]
         cons(3[15], cons(3[16],nil()[17] )[18] )[19]
      )[20]
    )[21]
)[22]

As always the subexpressions have been labelled, the label in this case written between [ and ], following the expression which it labels. Identifiers which have not been labelled are as usually newly bound ones. When you follow the steps below, do not (I repeat: do not), modify the numbering of the expressions.

Construct and give your answer in a structured fashion:

1. Give the abstract syntax tree for the program.
   You have some freedom of choice here, although it is best if follow my method of drawing the tree in the lectures.
2. List the function definitions (lambda abstractions) present in this program.
3. List the constructed data items present in this program
4. Construct a list of constraints by first decorating the tree, i.e., putting the constraints in the tree at the node where they are generated. You do not need to repeat a constraint originating in a certain node, in all the sets of constraints of the nodes from that node up to the root. As was explained in the lecture, this is understood.
5. List the values of D[p] and E[p] after the step of building the graph as described in your possibly modified Algorithm 3.7 (ordered similarly to Figure 3.4).
6. Perform the iteration of Step 3 showing also intermediate results including the value of the worklist W along the way (for instance similar to Figure 3.5).
7. Convince yourself that your final answer to the iteration is what it should be.

You may forget about considering Table 3.1 (in the project description in the book described as being for the more ambitious).

Part 2: the additional exercises

Do exercises 3.3, 3.10 and 3.11 from the book. In the case of Exercise 3.3, your example should be type correct and not contain any free variables (this does make it hard to come up with an example).

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

It turned out last year that students have a hard time getting started with this assignment. All I can say is: visit the practice hours and ask me questions. And try to read everything carefully, working out examples based on the Tables in the book, before modifying the tables.

-- JurriaanHage - 20 May 2005