In this assignment, you will implement the ACI (Automatic Callback Insertion) transformation we have discussed in class. Since this is a program transformation, you will implement it using macros (define-syntax and syntax-rules).
After doing so, you will extend and use it to simulate a multi-tab/window Web interaction, to see the effects we have discussed in class.
Chapter 14.1—14.2 of PLAI 2/e, where ACI is called “CPS”.
You will define a macro, aci, that takes an expression and returns the same expression converted to ACI-form.
Your macro should handle the following source forms:
primitive values (numbers, strings, and booleans)
function application (of one argument)
lambda (of one argument)
begin, with two sub-terms
+ and string-append, both of two arguments
Be mindful of the order you define these cases in your macro to ensure that the correct one is evaluated for any given input.
7.3.1 Web Extension
Notice the parallels between what you’re implementing here and the Web programming model we discussed in the Web Programming assignment.
Next, you will simulate a multi-tab Web interaction. To do this, you should create a global association between tab numbers and continuations. Each tab has a continuation associated with it, corresponding to the state of execution in that tab.
Define a macro, run, which converts a program to ACI form and runs it in the current tab. The first time run is called it will be run in a tab numbered 0. This is the first tab of your program. Once the program execution finishes, run should return its result.
To allow a user to interact with a tab, extend aci with the following source form:
which consumes a string, prints the string, saves the current continuation as the current tab, and then halts the program entirely using raise-web-read-error (having, of course, first stashed the continuation).
To resume execution of a tab, define a function restore, which takes two parameters: a tab number and a value. This sets the current tab to that tab number and restores that tab’s computation with the supplied value. You may assume that restore will never be called with an undefined tab number or on a tab whose execution has already completed.
run uses the current tab and restore continues an existing tab. To create new tabs, you will define a function clone, which takes a single number representing which tab to clone. It returns a fresh tab number, which should be one higher than the largest tab number used so far. This fresh tab has (for now) the same continuation as the tab that was cloned. Calling clone also sets the current tab to the new one. Like restore, we will only call clone on a valid tab number in our tests.
Finally, implement a function reset-tabs, which (if necessary) resets any temporary variables you set for yourself to keep track of tab numbers and/or restoration points. We will be running it in-between tests so that tabs set in previous tests do not interfere with later tests, i.e., there’s a pristine “browser” environment between tests.
Consider the code
(run (+ (web-read "Input first number:") (web-read "Input second number:")))
When we run this, we should first get to the first web-read. It should print out "Input first number:" and then halt (by erroring).
To input a number and continue, we can enter (restore 0 2). 0 is the current tab number as this is our first tab, and we are inputting 2 as the first number.
After doing so, we’ll hit the second web-read, which will prompt us to input a second number. We can do this in the same fashion, as (restore 0 3), if 3 were our second number. As there are no more web-reads, the execution of the continuation will continue until completion, and we’ll get back the two inputted numbers added together, 5.
clone will copy a specified tab. In the example above, let’s say that we had called restore once, and the program just printed out "Please input the second number:". If we now enter (clone 0), we would copy that continuation into a new tab and return the tab number, in this case 1.
Having done so, we could enter (restore 1 4) which will resume the copied continuation by inputting 4 as the second argument for the addition. As the first number we inputted was 2, this will output 6. The original continuation should not be affected, as this one was just a copy, so we can also enter (restore 0 3) to output 5.
After all this, entering reset-tabs would set our tab number back to 0 and remove all saved restoration points.
Your final aci macro implementation should handle the following grammar:
<aci> ::= (aci <expr>)
<expr> ::= <num>
| (<expr> <expr>) # function application
| (lambda (<id>) <expr>)
| (set! <id> <expr>)
| (begin <expr> <expr>)
| (+ <expr> <expr>)
| (string-append <expr> <expr>)
| (web-read <string>)
In addition to the testing forms documented in the Testing Guidelines
, we provide the test-aci
macro in the test-support.rkt
takes a collection of one or more calls and runs them in sequence, catching the ’halt
errors raised by web-read
in between. For instance, using the example above, we could write
(test-aci ((run (+ (web-read "Input first number:")
(web-read "Input second number:")))
(restore 0 2)
(restore 0 3)))
which would output the final result of these calls, 5. test-aci also calls reset-tabs, so you have a fresh environment between each test.
If you are using set! to modify your global association of tab numbers and continuations, you may run into an error as Racket does not allow one file to directly mutate something defined in another. If this error occurs when you run your test file, you can define a wrapper function in your code file to call set! rather than calling set! itself in a macro.
You’ll be reusing your aci implementation in the forthcoming Generators assignment! Therefore, if you falter in this assignment, you’ll want to make sure you understand what you did wrong.
7.8 Starter Code
We’ve provided starter code for your implementation at aci.rkt
. You are not allowed to change the signature of any required functions, but you are welcome to add any helper functions that you need for your implementation.
We’ve also provided a stencil for your test cases at aci-tests.rkt
and testing support code at test-support.rkt
. You should check that you can run your aci-tests.rkt
file successfully in DrRacket before submitting—if you can’t, it means that a definition is missing or you’re trying to test a function that you shouldn’t be testing.
7.9 What to Hand In
You will submit two files for this assignment:
aci.rkt, which should be uploaded to the “Code” drop on Gradescope.
aci-tests.rkt, which should be uploaded to the “Tests” drop on Gradescope.
You can update your submission as many times as you want before the deadline.