A famous problem, first raised by R. Hamming, is to enumerate, in ascending order with no repetitions, all positive integers with no prime factors other than 2, 3, or 5. One obvious way to do this is to simply test each integer in turn to see whether it has any factors other than 2, 3, or 5. But this is very inefficient, since, as the integers get larger, fewer and fewer of them satisfy the requirement. As an alternative, let's call the desired stream of numbers H and notice the following facts about it:
Now all we have to do is combine elements from these sources. To do this, write a Scheme function called merge that combines two ordered streams of numbers into one ordered result stream, eliminating repetitions. Use merge and the other definitions in final-streams.ss to construct the stream H. What is the 500,000th H number?
Transform your Ploy interpreter into a trampolined register machine. Do this in several stages, making sure after each one that your program is completely correct before going on to the next stage. Test your code thoroughly at each stage! Once it is correct, save a working copy as a backup, so that if you get bogged down at the next stage, you can go back to the previous stage and try the transformation again. It is difficult to debug register machines by hand, so if you find yourself spending more than a few minutes hunting down a bug, you'll probably save more time in the end by just going back and doing the transformation again.
Use the following code as your starting point. This code uses a functional representation for continuations, exception-handlers, and closures/primitives, and a data structure representation for environments.
You do not need to change the parser code. In the environment code, you will only need to modify apply-env and the lookup functions.
Here is a series of examples showing each stage of the transformation process applied to the remove program from Homework 10.
Exception-handlers are represented as Scheme procedures of the form (lambda (e raise-k) ...). Change the representation of exception handlers to data structures. You'll need to define an apply-handler function for this. Test your code! Save a working copy!
Primitives and closures are currently represented as Scheme procedures of the form (lambda (args handler k) ...). Change this representation to data structures. You'll need to define an apply-func function for this. Test your code! Save a working copy!
Continuations are represented as Scheme procedures of the form (lambda (v) ...). Change the representation of continuations to data structures. You'll need to define an apply-cont function for this. Test your code! Save a working copy!
Add an action_reg register to the interpreter and convert it to trampolined style. Test your code! Save a working copy! Rejoice at being done!
You should test your code thoroughly after completing each of the above transformation steps. Here is a test program to make this easier. To use it, load it into Scheme along with your interpreter. To run all of the tests at once, just type (test) at the Chez Scheme prompt. The test program calls your m function on a variety of test expressions (there are 36 in all) and reports the results. You can look at the detailed results of individual tests by including the name of the test case in the call to test. For example, to see the results for the test cases labeled letrec3, if1, and fun2, type the following (no quotes or extra ()'s are necessary):
> (test letrec3 if1 fun2)
These tests are designed to exercise all aspects of your interpreter. However, they are not necessarily exhaustive, so you should make up your own tests as well. Be sure that your interpreter works correctly on all tests before moving on to the next transformation step. Transforming an incorrect program is pointless, because the new program is guaranteed to still be incorrect, and is surely harder to debug.
Get rid of define-datatype and cases by defining your own data structure constructor and accessor functions. Test your code! Save a working copy!
Using a few extra registers, linearize all nested primitive calls and get rid of any remaining let expressions. All assignment statements should be of the form (set! <register> (<primitive-function> <register> ...)) or (set! <register> <register>), and all conditional tests should be of the form (if <register> ...). See remove4.ss for an example of this. Test your code! You're all done! Rejoice anew!
Files to submit:
If you have questions about anything, just ask!