SB CSE 675Fall 2000 Program Transformation \and Program Analysis Annie Liu Exercises 11 Handout E11 Dec. 13, 2000 Due Dec. 20

Data Structure Selection, APTS, and Project Report (Due next Wednesda\y.)

Problem 1. Refining data structures.

Read the Paige 89 paper, and answer the following questions. Be brief.

1. What refinements/optimizations are possible when simulating a set machine using a point machine?

2. Give two typical cases where we can use an ARAM to simulate a set machine.

3. Give a special case where we can simulate an ARAM using a pointer machine, and also say how to do this this in general.

Problem 2. Running the old APTS.

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.

Problem 3. Course project report.

Your project handin should consist of four parts.

1. A description of the problem in English. What's the input? What's the output? What are the applications where this problem can be found? Give references for where you found this problem and known solutions, if any.

2. A formal or semi-formal high-level description of the problem using recursive functions or set expressions, or as formal as you can; this should be the clearest, most succinct, and most precise description of the problem you can think of, without worrying about anything else, including execution efficiency, code reuse, etc.

3. A derivation of an efficient algorithm from the high-level description. What are key design decisions? In particular, how to maintain expensive computation results incrementally? Do this as systematically as you can.

4. An implementation, in a lower-level language, like C, together with documentations explaining how it works and test cases.

Your code, in any programming language, high-level or low-level, needs to be commented, so that anyone who wants to use it can at very least run it without looking at the code, and anyone who wants to know the basic algorithm can look at the comments of each procedure/function without looking at the body. This is like writing/designing interfaces, always needed for good programming practice.

You also need to show test cases and results, including running times. This is also always needed, for showing others that you have something working even if they can not run it.