Class Project

Step 6: Cached precision functions

Deadline: Hand in either Step 5 or Step 6 on Wednesay 3 December 2003, 11:59 PM, and the other at the end of the quarter (TBA when I work out grading deadlines).

In this step, create the cachefunc implementation of xreal: modify the precfunc implementation to save each computed interval in a cache, and avoid recomputation.

The essential point of this step is to reduce the inefficiency in precfunc due to the repeated calculation of an interval, ignoring the information in an already calculated interval.

Cached precision functions

The basic way to implement a function with a cache depends on a careful understanding of the frame/environment/state model of computation that we are just discussing. The method is particularly interesting because it combines the performance benefit of procedural programming with the conceptual transparency of functional programming. Fortunately, there's a recipe all set up, so you don't have to stumble through errors as you figure it out.

Last year, several people implemented precfunc by applying a higher-order function to convert each precfunc function into a cachefunc function. Ben Singer provided particularly nice code (make_cache_func.scm), with some commented instrumentation that you can activate for testing as needed.

Use make_cache_func to convert your precfunc implementation to a cachefunc implementation of xreal. Perform timing tests to demonstrate as well as you can the extent to which cachefunc improves the performance of precfunc when the same xreal is invoked repeatedly. Functions that depend on an iteration to reach the appropriate precision should be especially interesting. Try to find examples that show a better rough rate of performance for cachefunc. Since the cachefunc contain the precfunc definitions, with a bit of extra conditional code, precfunc should be faster by a tiny bit if the cacheing doesn't help. Any case where cachefunc is reliably faster than precfunc is probably significant, but there should be some cases where the difference affects the rough efficiency.

What to hand in

• An appropriately named file containing your definitions of xreal functions in your cachefunc implementation.
  
  
• One or more files demonstrating the apparently correct operation of your xreal functions---not thorough tests but just a quick sanity check of the conversion from precfunc to cachefunc.
  
  
• One or more files of timing inputs, using my timetest from progutils-3.scm or test code of your own if you like it better.
  
  
• A file called README.txt or START.txt containing very short and simple instructions how to execute your tests. If this takes more than 2 lines, you probably need to write a Scheme file to automate things more for the grader.
  
  
• A text file called comments.txt, or a variant in another format, containing a discussion of your observations.

Copyright Michael J. O'Donnell <michael_odonnell@acm.org>. Licensed for free use.
This page is generated from PHP source code, with supporting files.