Control Flow Programming Assignment

In short

In this assignment you must implement the theory of Chapter 3, corresponding roughly to a combination of Mini Project 3.3 (A Prototype Implementation) augmented with the data structures of Mini Project 3.2 (added in the way of Section 3.5.2). 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. Of course, you can ask questions during the practice sessions.

The assignment may be done alone, but preferably in pairs. Every student should be able to explain orally and clearly every part of the assignment he/she 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 construct a system that works similar to that explained in Chapter 3, with a few extensions.

You shall, at least, have to think about

• how to represent a FUN program in your language (but see the book)
• how to generate and efficiently solve constraints (as explained in the book)
• how to add data structures as an extension to the basic language
• how to make sure data flow information helps control flow analysis and vice versa

In the book they tend to keep the expression language for dealing with integers and boolean values abstract. You may make this language as rich as you like, but it should at least include integer constants, the boolean values, the usual arithmetic operators +, - and *, and the equality comparison operator =.

You may assume that your program is only applied to programs that are type correct!

Materials which you can use

You need a compiler for the language you want to build the system in, and various assorted tools. You may use Java or Haskell. If you want to use a language different from these then ask me first. If parser generators exist for the language of your choice, then you may use these, but if I need them to compile the system, please send them along with your submission. 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. You may assume I have a working installation of GHC and Java.

A question that somebody posed was: can we reuse a parser that we made in the course IPL/IPT? The answer is yes, but do make sure that you accept at least all the programs in the FUN language as defined in the book and the mini project.

What should you do?

I see at least the following steps:

• decide which expression language to support
• define an AST type for your language and build a parser
• take Table 3.9 as a starting point and develop an analysis that performs control flow analysis (as usual), but instead of sign analysis performs Parity Analysis (which variables are always even, which are odd, which are neither and which are both). Consider which parts should change and how.
• take the outcome of the previous item and add the new language construct for dealing with case as described in Mini Project 3.2. In addition develop the necessary analogons of Table 3.5, 3.6 and 3.7 and implement the resulting system (try to be clever and efficient, but not at the price of losing much of the elegance). Although the book suggests to add constructed items to the C(..) and r(..) sets, this is not so wise, because you should use the dataflow formulation of Section 3.5.2. anyway, and it is cleaner to add them to your D(..) and d(..) values.
• try your implementation on a collection of suitably chosen examples.

In addition to the necessary functionality, the resulting code should be elegantly architectured, and easy to modify.

Deliverables

For this assignment I expect:

• the full working implementation
• 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 also 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. In some cases, you may also demonstrate the program to me, for example if a good environment for your language does not exist for MacOSX? .
• a high level description of the architecture of your program: What do the modules represent? What are they responsible for? What is your AST like? Etcetera. Everything you think I need to know to be able to understand the program easily at a high level.
• a description of how you modified the analysis in the book to cope with Parity Analysis
• a full textual description of what you did to add data constructors, including the two rules (each both declaratively as in 3.5, as in how constraints should be generated comparable to 3.6) that specify how these new language constructs should be handled. If necessary describe how you had to change the way constraints are solved.
• at least five illustrative examples that show that you have implemented the analysis well. Make sure you capture the corner cases. Also, include a discussion for two of these examples that the outcome from your program is as you expect. Hint: make sure there is an example program in which the parity analysis helps the control flow analysis and vice versa, and one in which data structures play a role.

When and how to hand things in

See Course Assignments

Experiences from last year

Students start too late to work on this assignment.

-- JurriaanHage - 13 Feb 2007