Principles of Programming Languages
Apr. 19, 2005
Due Apr. 26
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 April 26. 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 XSB.
Implement the graph reachability problem using XSB, and take care of input and output functionalities. For input, slightly modify the parser you programmed in Python to write out the facts/relations in Prolog syntax, so that you can load these facts in using XSB easily. For output, simply write out the facts in SETL syntax using XSB.
Part II. Testing and analyzing performance. You may use and update utilities from your Homework 10.
1. Correctness testing. Test your XSB programs, with and without tabling directives 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, e.g., from before loading in facts in XSB till after writing output facts.
B1. Analyzing running time variations (50%). Varying both the order of rules and the order of hypotheses of your XSB programs, both with and without tabling directives, 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, or indicate that a certain limit on the running time is exceeded and confirm that the program does not terminate.
B2. Programming your own fast graph reachability in C (50%). You may do this by defining the data structures in C for our result of data structure selection from last week, and then translating the low-level SETL2 into C and optimizing it. You could also first try to optimize the low-level SETL2 as much as possible. Compare the running time of your program with your Python programs from the previous homework; make sure that you first show your code is correct by giving a formal argument or doing the test, or both.
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.