CSE 526
Spring 2005 Stony Brook |
Principles of Programming Languages
Annie Liu Homework 12 |
Handout H12
Apr. 26, 2005 Due May. 3 |

This assignment has two parts, each worth 50% of the grades. A number of bonus problems are also given, together worth an additional 100% of the grades; the points indicated are based on a decent work, and there is no limit on how many points an exceptionally beautiful solution could get. The assignment is due before class on Tuesday May 3. Please submit your file(s) as a single attachment (made using tar or zip if necessary) in an email to cse526ATcsDOTsunysbDOTedu.

**Note:** All solutions should be written either directly in one
program file, or given pointers in your README file to document files
or code comments where you write the solution.

Note that work in this assignment is also part of the final project. It is given here so that you don't need to do a big job at the end. If you loose points for this assignment, you may still get them for your project if you fix the problems at the end.

**Part I. Programming graph reachability in FLORA2.**

Implement the graph reachability problem using FLORA2 (do both the version that uses attributes and the version that uses classes for source vertices and reachable vertices), and take care of input and output functionalities. For input, slightly modify the parser you programmed in Python to write out the data in FLORA2 syntax, so that you can load them in using FLORA2 easily. For output, simply write out the facts in SETL syntax using FLORA2.

**Part II. Testing and analyzing performance.** You may use and
update utilities from your Homeworks 10 and 11.

**1. Correctness testing.** Test your FLORA2 programs on this input as well as on a number of randomly
generated inputs (report what kinds of inputs you generated, include
size and number) and compare the results.

**2. Running time measurements.** Measure the running times of
your programs systematically (on a number of inputs of a number of
different sizes), plot the results, and conclude what kind of curves
you are getting. Make sure to write explicitly how you did timing, in
particular, what interval you are timing.

**Bonus Problems.**

**B1. Analyzing running time variations** (50%). Varying both
the order of rules and the order of hypotheses of your FLORA2
programs, for both the version that uses attributes and the version
that uses classes for source vertices and reachable vertices, and ran
on graphs of different sizes that contain cycles. For each of the
programs, measure and analyze running times in detail to show the
curves and infer time complexity.

**B2. Generating C from SQ+ for graph reachability, using the old
APTS system** (50%).

Set up to run the old APTS system following the link under Systems. Consider the transformation from SQ2+ to C for the reachability example.

**1.** What is the program in fixed-point form?

**2.** What is the program after dominated convergence?

**3.** What is the program in normal form for finite differencing?

**4.** What is the program after chain rule for finite differencing?

**5.** What is the program after dead-code elimination for
finite differencing and prepared for real-time simulation?

**6.** What is the program after based-representation
declarations are generated for real-time simulation?

**7.** What is exactly the total number lines of C code generated?

All these can be read off from a run of APTS. Recall that dominated convergence, finite differencing, and real-time simulation correspond to "iterate", "incrementalize", and "implement", respectively, as discussed in classes.

**8.** Test and measure the running times of your generated C
program, as required for other programs.

**Note.** Both will be part of the final project, so you will
have to do them at the end anyway, but you get extra credit by doing
them earlier.