Monotone Frameworks Part One

This is a preliminary version of this assignment. After the first week you have all the information you need to complete the assignment.

In short

In this assignment you shall implement the monotone frameworks of Chapter 2 as general as possible, corresponding roughly to Mini Project 2.3 A Prototype Implementation in the extended version which can be found in Nielson, Nielson and Hankin.

In a second phase of the assignment, you should add procedures and context as in Section 2.5. Relatively little information will be given, which means that you have quite a degree of freedom filling in the details. One of the criteria for grading, is how you have handled these choices.

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.

The goal of the assignment

The book of Nielson, Nielson and Hankin is quite theoretical. However, underneath all that theory is a practical framework which can be implemented in, for instance, Haskell. The goal is to write a program which can take a monotone framework and a program as its input and generate the MFP solution corresponding to the data flow equations (see Table 2.8). In a second phase of the assignment, you should add procedures and context as in Section 2.5, and generalize your program accordingly Details. The first part is graded separately to serve as an indication, but after part two you will get an overall grade.

In this assignment you may use Haskell or Java as a programming language (if you want to use yet another language, contact the lecturer first). In the case of languages other than Java, you are on your own when writing a parser for the source language (you may use some Java library for this part however).

You shall, at least, have to think about

• how to represent a Monotone Framework in Haskell
• how, for a given analysis, can you automatically construct the monotone framework for a given program
• how to use it to compute the MFP solution
• how to represent solutions
• how to build the transfer functions easily and efficiently.

A recent innovation in this programming assignment is the addition of the break statement to the while language. This also implies that you should add support for this language construct in your entire implementation.

Materials which you can use

You can download a parser for the programming language under analysis from the Course Software page. This implementation can only be used when you program in Haskell. The parser generates an abstract syntax tree similar in style to the one in ML given in the book. The parser was written with Daan Leijen's Parsec, which is also included in the file (since I am not sure my version is compatible with one currently being distributed along with various Haskell compilers).

If you want to use a different programming language instead, you are on your own for writing the parser. However, you may use available parser generators for that language. It is important to remember that your program should work as handed in and not depend on anything that I might have to install. This is your responsibility.

Deliverables

For this assignment I expect:

• the monotone framework implementation, fulfilling all the usual prerequisites such as being well-structured, well-documented and so on,
• a (short) manual describing how to use the program. If you use a programming language different from Haskell, you should tell me how to run your program. In the case of Java, I would like to hear what version you used. If you used a different language I need specific instructions, including how to compile your program on a MacOSX platform, where to get the compiler from and how to compile it.
• a high level description of the architecture of your program including how you encoded monotone frameworks, transfer functions and the various other concept from the chapter,
• an example instance of a monotone framework which computes the Faint Variable Analysis (Exercise 2.4), including at least one example program which illustrates the correctness of your analysis. Additionally, I expect a discussion on paper that the answers computed by your program are reasonable for this example. Also, list the equations that should be generated, and fill in the answer to show that it at least fulfills the equations for the program.

  I shall often ask this of you in the programming assignments to make sure that you actually test your implementation and verify that the answers correspond to what you expect.

• give an example instance of a monotone framework which performs the Detection Of Signs as in Exercise 2.15 on page 136 (extended to cope with the break statement of course).

  On top of that, you have to prove that you have defined a monotone framework, by showing that the transfer functions are monotone and that the data structure underlying the analysis forms a complete lattice with ACC.

  Finally, give two example programs, one which gives the same results for the lattice of Exercise 2.14, and one where the lattice from Exercise 2.15 gives better results. Show that this is the case, by giving the equations and corresponding solutions for these programs and verify that the solutions fulfill the equations.

When and how to hand things in

See Course Assignments

Experiences from last year

The addition of the break statement is new this year and hopefully adds some flavour to the assignment.

Avoid being too provincial, for instance, by insisting that all transfer functions are of the form that use kill and gen sets. Take for example the non-distributive example of 2.3.3: this example does not follow that form. Hence, transfer functions can be more general than this, and your implementation should be able to deal with that. Follow the definition of monotone framework in Section 2.3 as closely as possible to avoid making your implementation to restrictive.

On the other hand, if you do happen to have an analysis which use kill and gen sets in the sense of Chapter 2, then it would be nice to be able to 'generate' the transfer functions 'automatically'.

The main thing is to decide/understand what parts should be flexible (i.e, which parts are parameters of the framework) and which should be fixed (which parts are hard-coded into the framework). The more parameterization the better, but keep in mind that the program should be easy to use when you put it to easy uses.

For example, you can have a function called makeMonotoneFramework which can construct all possible monotone frameworks. However, since a large class of monotone frameworks instances use kill and gen sets, you should also include a function makeMonotoneFrameworkWithKillAndGenSets which may use the general function with some of the parameters to the general function computed in an easier way. For instance, in the latter case the transfer functions take a rather simple form, and hence should be easier to construct after which they can be used to instantiate a general monotone framework.

A student of last year remarked that this is the first assignment he ever made in which using Haskell was preferred over using Java. This was after he had done the assignment in Java, and saw how the people who chose Haskell fared. Doing it in Haskell is likely to be a lot less work (the amount of code is about 15 percent of a Java assignment). However, there have been students that handed in excellent work done in C# and Java.

-- JurriaanHage - 15 Apr 2005