10 Assignment 10: Defunctionalized Interpreter
In this assignment, you will continue the project of building an interpreter that runs on a low-level machine. In the CPS interpreter you made in Assignment 9, environments, closures, and continuations are all represented by functions. But the low-level machine doesn’t support functions, so the goal of this assignment is to defunctionalize them all.
Defunctionalization is a program transformation that you practiced in Assignment 5 already. You may find it helpful to refer to some old and older notes on making continuations representation-independent methodically.
Assignment
This assignment begins with your value-of-cps from Assignment 9. You should do each step below in a separate file. Turn in a file containing the last step, and call it a10.rkt. But you must keep each step. We will ask to see them.
You must keep each step. We will ask to see them. |
After each step, your value-of-cps should pass the same tests as in Assignment 9, including Autograder tests as well as your own. But if you trace your interpreter, you should see the #<procedure>s go away.
Define apply-env, apply-closure, and apply-k, and add all the calls to those functions. Notice that after CPSing, your apply-closure and apply-env now take three arguments.
Defunctionalizing Environments
Define extend-env and replace all 3 of your explicitly higher-order representations of environments with calls to extend-env. Don’t just copy extend-env from earlier in the course such as Assignment 5, because this interpreter uses de Bruijn indices.
Add a ^ to each of the formals of extend-env (not the inner function, mind you). Ensure that the inner functions in both extend-env and empty-env use the same formals as the second argument to apply-env (here, typically y and k^).
Replace your higher-order function representation of environments with a tagged-list data structure representation. Consider first ensuring that the last two formals to apply-env (y and k) are the same as the formals to the inner functions in extend-env and apply-env. Remember, if you add (else (env-cps y k)) as the last line of your match expression, you can test each transformation one at a time.
If you used it, remove the (else (env-cps y k)) as the last line of your match expression in apply-env.
Defunctionalizing Closures
Define make-closure and replace your explicitly higher-order representation of a closure with a call to make-closure.
Replace your higher-order function representation of closures with a tagged-list data structure representation. Consider first ensuring that the last two formals to apply-closure (a and k) are the same as the formals to the inner function in make-closure.
Defunctionalizing Continuations
Define constructors for your continuations, and replace your explicitly higher-order function continuations with calls to these constructors. For nested continuations, you should consider working from the inside out. Remember, if you transform your constructors one at a time, you can test your program after each replacement.
Add a ^ to each of the formals of your continuation helpers, and change the body to correspond with these changed variable names (that is, do an alpha conversion). Then, ensure that the inner function in each of your continuation helpers uses the same formal as the second argument to apply-k (typically, v).
Replace your higher-order function representations of continuations with a tagged-list data structure representation. Remember, if you add (else (k v)) as the last line of your match, you can test each transformation one at a time. If you’re good, you can do almost all of this step with a keyboard macro.
Remove the (else (k v)) line to ensure that you’ve properly removed all higher-order function representations of continuations.
Your value-of-cps should pass the same tests as in Assignment 9, including Autograder tests as well as your own. But if you trace your interpreter, you should not see #<procedure> anywhere.
Just Dessert
Write a short screenplay set in the world of Primer (2004) in which the characters implement generators using first-class continuations.