(web-read/k ”Second number: ”
(lambda (•2)
(web-display
(+ •1 •2))))))
Now, when the program finally generates the sum, it can safely halt without having registered any receivers,
because there aren’t any computations left to perform. Relative to the original source program, however, the
structure of this application is considerably more intricate.
16.3. TESTING WEB TRANSFORMATIONS
153
Exercise 16.2.1 To be entirely pedantic, there is one thing left to do, which is to explicitly halt the program.
Extend the program to do this, then transform it to correctly employ web-read/k.
16.3
Testing Web Transformations
One of the subtle problems with transforming interactive programs for the Web is that they are difficult to
test. This difficulty has at least two facets. First, the use of HTML makes programs unwieldy, so we would
rather defer its use until the end, but without it we cannot interact with a Web browser. Second, testing a
program at the console can be misleading: a computation may not have been properly moved into a receiver
but, because Scheme programs do not terminate after every interaction, we would never notice this problem
until we ran the program on the Web.
Fortunately, it is easy to simulate the Web’s behavior at the console with the following code. The fol-
lowing implementation of web-read/k stores the receiver and prompt in a box, and terminates the program’s
execution using error:
(define the-receiver (box ’dummy-value))
(define receiver-prompt (box ’dummy-value))
(define (web-display n)
(printf ”Web output: ˜a˜n” n))
(define (web-read/k p k)
(begin
(set-box! receiver-prompt p)
(set-box! the-receiver k)
(error ’web-read/k ”run (resume) to enter number and simulate clicking Submit”)))
The procedure resume uses the values in these boxes to resume the computation:
(define (resume)
(begin
(display (unbox receiver-prompt))
((unbox the-receiver) (read))))
We can therefore test a program such as the addition application as follows:
Language: PLAI - Advanced Student.
web-read/k: run (resume) to enter number and simulate clicking Submit
>
This means the program has arrived at web-read/k for the first time. We run
> (resume)
which prompts us for the first input. Providing an input results in the same terminating “error” message,
corresponding to the next interaction point. Running (resume) prompts for the second input. When we
provide the second, we see the sum of the two numbers printed to the console.
154
CHAPTER 16. THE STRUCTURE OF WEB PROGRAMS
Exercise 16.3.1 Use this testing harness to execute the incorrectly transformed versions of the addition
program to explore their behavior.
16.4
Executing Programs on a Traditional Server
Suppose we must run our Web application on a traditional Web server, which does not provide support for
the hash table used by web-read/k. This doesn’t mean we must waste the effort we expended transforming
the program: that effort was a direct consequence of the Web’s protocol, which the traditional server also
obeys (even more slavishly!).
What’s the problem with executing this program on a traditional server?
(web-read/k ”First number: ”
(lambda (•1)
(web-read/k ”Second number: ”
(lambda (•2)
(web-display
(+ •1 •2))))))
If web-read/k cannot behave in a privileged fashion, then its receiver argument will not be invoked automat-
ically by the server. Instead, the entire computation will terminate with the first interaction.
To reflect this problem, let us use a different primitive, web-read/r in place of web-read/k. The suffix
indicates that it will be given the name of a receiver as a second argument. web-read/r uses this name
in the URL inserted in the action field of the generated form. To do so, however, each receiver must be a
named Web application that the server can invoke directly (whereas the receivers are currently anonymous
procedures nested within other procedures).
The process of making nested procedures into top-level ones is known as lifting. That is, each anony-
mous procedure is moved to the top-level and given an unique name. In the example program above, the
innermost procedure might become
(define (f2 •2)
(web-display
(+ •1
•2)))
which the outer procedure can refer to:
(define (f1 •1)
(web-read/r ”Second number: ”
”f2”))
The main program then becomes
(web-read/r ”First number: ”
”f1”)
16.4. EXECUTING PROGRAMS ON A TRADITIONAL SERVER
155
Because of this transformation, web-read/r can safely terminate after using the procedure named in the
second argument in the action field’s URL. All the remaining work must be completed by this named top-
level procedure. Each top-level procedure consumes one argument, which is the data provided by the user.
Unfortunately, by sloppily lifting the procedures to the top-level, we’ve created a problem: •1 is a free
identifier in f2! The problem is that we were simplistic in the way we lifted the procedures. (A different sim-
plistic method—failing to keep the two instances of • separate—would, of course, have created a different
problem, namely that f2 would have just added • to itself, ignoring the user’s first input.)
In general, when lifting we must add parameters for all the free variables of the procedure being lifted,
then pass along the values for parameters from the point of closure creation. In general, procedure lifting re-
quires the computation of a transitive closure (because lifting one procedure may render another procedure’s
previously-bound identifiers free). That is, the Web program ought to become:
(define (f2 •1 •2)
(web-display
(+ •1
•2)))
(define (f1 •1)
(web-read/r ”Second number: ”
”f2”))
(web-read/r ”First number: ”
”f1”)
But how is f2 to get this extra argument? Recall that each top-level procedure takes only one argument: the
user’s input. The (traditional) Web server can’t know that it has to hold on to this value and communicate it.
In practice, these values become the source of values to be stored in hidden fields. Every top-level
receiver has to be sensitive to creating and extracting these form values. Specifically, the converted Web
application has the following form:
(define (f2 user-input)
(local ([define •1 (get-form-field user-input ’n1)]
[define •2 (get-form-field user-input ’n2)])
(web-display
(+ •1
•2))))
(define (f1 user-input)
(web-read/r/fields ”Second number: ”
”f2”
user-input
(list ’n1)))
(web-read/r ”First number: ”
”f1”)
where n1 and n2 are the names used in the form. The procedure web-read/r/fields takes the same first
two arguments as web-read/r. The third argument is the data structure representing the user’s input. This is
156
CHAPTER 16. THE STRUCTURE OF WEB PROGRAMS
followed by a list of field names; these fields are extracted from the user input and inserted into the generated
HTML form using hidden fields.
How would f1 know which parameters must be passed to f2 using the hidden fields? These are precisely
those identifiers that are free in the receivers.
Exercise 16.4.1 Automate this transformation, i.e., write a program that implements it without the need for
human intervention.
Chapter 17
More Web Transformation
We have already seen how the application
(web-display
(+ (web-read ”First number: ”)
(web-read ”Second number: ”)))
must be transformed into
(web-read/k ”First number: ”
(lambda (•1)
(web-read/k ”Second number: ”
(lambda (•2)
(web-display
(+ •1 •2))))))
to execute on the Web. Let us now examine some more applications of a more complex flavor.
17.1
Transforming Library and Recursive Code
Suppose we have the procedure tally. It consumes a list of items and prompts the user for the cost of each
item. When done, it generates the sum of these items, which a programmer could display on the Web. The
code for tally is as follows:
(define (tally item-list)
(if (empty? item-list)
0
(+ (web-read (generate-item-cost-prompt (first item-list)))
(tally (rest item-list)))))
This version of tally is clearly not Web-friendly, due to the use of web-read, which we do not know how to
implement. We must therefore transform this code.
157
158
CHAPTER 17. MORE WEB TRANSFORMATION
The first thing to observe is that on its own, tally is not a complete program: it doesn’t do anything!
Instead, it is a library procedure that may be used in many different contexts. Because it has a Web inter-
action, however, there is the danger that at the point of interaction, the rest of the computation—i.e., the
computation that invoked tally—will be lost. To prevent this, tally must consume an extra argument, a re-
ceiver, that represents the rest of the pending computation. To signify this change in contract, we will use
the convention of appending /k to the name of the procedure and k to name the receiver parameter.
(define (tally/k item-list k)
(if (empty? item-list)
0
(+ (web-read (generate-item-cost-prompt (first item-list)))
(tally (rest item-list)))))
What is the first thing this procedure does? It checks for whether the list is empty. Does this involve any
Web interaction? Clearly not; all the data and primitives are available locally. If the list is not empty, then
tally prompts for a user input through the Web. This must happen through web-read/k. What is the receiver
of this Web invocation? That is, what computation remains to be done? Clearly the recursive invocation of
tally; but there is also the receiver, k, which represents the rest of the waiting computation. Therefore, the
Web-friendly version of tally appears to become
(define (tally/k item-list k)
(if (empty? item-list)
0
(web-read/k (generate-item-cost-prompt (first item-list))
(lambda (v)
(+ v
(tally/k (rest item-list)
k))))))
We can read the second argument to web-read/k as saying: “Consume the value provided by the user and add
it to the value generated by the recursion. The receiver in the recursive invocation is the same k as before,
because the computation pending outside the procedure has not changed.”
This may look reasonable, but it suffers from an immediate problem. When the recursive call occurs, if
the list had two or more elements, then there will immediately be another Web interaction. Because this will
terminate the program, the pending addition will be lost! Therefore, the addition of v has to move into the
receiver fed to tally/k. In code:
(define (tally/k item-list k)
(if (empty? item-list)
0
(web-read/k (generate-item-cost-prompt (first item-list))
(lambda (first-item-cost)
(tally/k (rest item-list)
(lambda (tally-of-remaining-costs)
(k (+ first-item-cost
17.2. TRANSFORMING MULTIPLE PROCEDURES
159
tally-of-remaining-costs))))
That is, the receiver of the Web interaction is invoked with the cost of the first item. When tally/k is invoked
recursively, it is applied to the rest of the list. Its receiver must therefore receive the tally of costs of the
remaining items. That explains the pattern in the receiver.
The only problem is, where does a receiver ever get a value? We create larger-and-larger receivers on
each recursive invocation, but what ever invokes them?
Here is the same problem from a different angle (that also answers the question above). Notice that each
recursive invocation of tally/k takes place in the aftermath of a Web interaction. We have already seen how
the act of Web interaction terminates the pending computation. Therefore, when the list empties, where
is the value 0 going? Presumably to the pending computation—but there is none. Any computation that
would have been pending has now been recorded in k, which is expecting a value. Therefore, the correct
transformation of this procedure is
(define (tally/k item-list k)
(if (empty? item-list)
(k 0)
(web-read/k (generate-item-cost-prompt (first item-list))
(lambda (first-item-cost)
(tally/k (rest item-list)
(lambda (tally-of-remaining-costs)
(k (+ first-item-cost
tally-of-remaining-costs))))
Now we have a truly reusable abstraction. Whatever the computation pending outside the invocation of
tally/k, its proper Web transformation yields a receiver. If this receiver is fed as the second parameter to
tally/k, then it is guaranteed to be invoked with the value that tally would have produced in a non-Web (e.g.,
console) interaction. The pattern of receiver creation within tally/k ensures that no pending computation
gets lost due to the behavior of the Web protocol.
Exercise 17.1.1 There is a strong formal claim hidden behind this manual transformation: that the value
given to the initial k fed to tally/k is the same as that returned by tally in the non-Web version. Prove this.
17.2
Transforming Multiple Procedures
Suppose we have the procedure total+s&h. It consumes a list of items to purchase, queries the user for the
cost of each item, then generates another prompt for the corresponding shipping-and-handling cost,1 and
finally prints the result of adding these together. The procedure total+s&h relies on tally to compute the
sum of the goods alone.
(define (total+s&h item-list)
1The term shipping and handling refers to a cost levied in the USA by companies that handle long-distance product orders
placed by the mail, phone and Internet. It is ostensibly the price of materials to package and labor to dispatch the ordered goods.
This rate is usually a (step) procedure of the cost of items ordered, and must hence be calculated at the end of the transaction.
160
CHAPTER 17. MORE WEB TRANSFORMATION
(local ([define total (tally item-list)])
(+ (web-read (generate-s&h-prompt total))
total)))
Just as we argued in the transformation of tally, this procedure alone does not constitute a computation. It
must therefore consume an extra parameter, representing a receiver that will consume its result. Likewise,
it cannot invoke tally, because the latter performs a Web interaction; it must instead invoke tally/k, passing
along a suitable receiver to ensure no computation is lost.
(define (total+s&h/k item-list k)
(local ([define total (tally/k item-list ??? )])
(+ (web-read (generate-s&h-prompt total))
total)))
Reasoning as before, what is the first thing total+s&h/k does? It invokes a procedure to compute the
tally. Because this procedure involves a Web interaction, it must be invoked appropriately. That is, the
transformed procedure must take the form
(define (total+s&h/k item-list k)
(tally/k item-list
(lambda (tally-of-items)
??? )))
What is the pending computation? It is to bind the resulting value to total, then perform another Web
interaction:
(define (total+s&h/k item-list k)
(tally/k item-list
(lambda (tally-of-items)
(local ([define total tally-of-items])
??? ))))
(Notice that the Web transformation has forced us to give names to intermediate results, thereby rendering
the name total unnecessary. We will, however, leave it in the transformed program so that the transformation
appears as mechanical as possible.) With the pending computation, this is
(define (total+s&h/k item-list k)
(tally/k item-list
(lambda (tally-of-items)
(local ([define total tally-of-items])
(web-read/k (generate-s&h-prompt total)
(lambda (s&h-amount)
(k (+ s&h-amount
total))))))))
Notice how total+s&h/k had to create a receiver to pass to tally/k, the transformed version of tally. Reading
this receiver, it says to consume the value computed by tally/k (which it binds to tally-of-items), ask the user
17.3. TRANSFORMING STATE
161
to enter the shipping-and-handling amount, compute the final total, and convey this amount to the initial
receiver.
It’s easy to forget this last step: to apply k, the initial receiver supplied to total+s&h/k, to the final value.
Doing so would effectively “forget” all the computation that was waiting for the result of total+s&h/k, i.e.,
the computation awaiting the result of total+s&h in the original program. This is obviously undesirable.
You might worry that the local might be “forgotten” by the web-read/k that follows. But all we care
about is that the name total be associated with its value, and the receiver will take care of that (since it is a
closure, it must be closed over the value of total).
17.3
Transforming State
Suppose we want to write a program that keeps track of an account’s balance. On every invocation it presents
the current balance and asks the user for a change (i.e., deposit or withdrawal, represented respectively by
positive and negative numbers). We would like the Web application to look like this:
(define account
(local ([define balance 0])
(lambda ()
(begin
(set! balance (+ balance
(web-read
(format ”Balance: ˜a; Change” balance))))
(account)))))
Note that account is bound to a closure, which holds a reference to balance. Recall that mutable variables
introduce a distinction between their location and the value at that location. The closure closes over the
location, while the store is free to mutate underneath. Thus, even though balance always refers to the same
location, its value (the actual account balance) changes with each interaction.
How do we transform this program? Clearly the procedure bound to account must take an additional
argument to represent the remainder of the computation:
(define account/k
(local ([define balance 0])
(lambda (k)
(begin
(set! balance (+ balance
(web-read
(format ”Balance: ˜a; Change” balance))))
(account/k ??? )))))
More importantly, we must move the web-read to be the first action in the procedure:
(define account/k
(local ([define balance 0])
(lambda (k)
162
CHAPTER 17. MORE WEB TRANSFORMATION
(begin
(web-read/k (format ”Balance: ˜a; Change” balance)
(lambda (v)
(begin
(set! balance (+ balance v))
(account/k ??? ))))))))
What’s left is to determine what argument to pass as the receiver in the recursive call. What new pending
activity have we created? The only thing the procedure does on each recursion is to mutate balance, which
is already being done in the receiver to the Web interaction primitive. Therefore, the only pending work is
whatever was waiting to be done before invoking account/k. This results in the following code:
(define account/k
(local ([define balance 0])
(lambda (k)
(begin
(web-read/k (format ”Balance: ˜a; Change” balance)
(lambda (v)
(begin
(set! balance (+ balance v))
(account/k k))))))))
The closure created as the receiver for the Web interaction has a key property: it closes over the location
of balance, not the value. The value itself is stored in the heap memory that is kept alive by the Web server.
Exercise 17.3.1 If we wanted to run this application without any reliance on a custom server (Section 16.4),
we would have to put these heap data somewhere else. Can we put them in hidden fields, as we discussed
in Section 16? If so, test and make sure this works correctly, even in the face of the user interactions we discussed in Section 15. If it fails, find an alternative to hidden fields that does work appropriately!
17.4
The Essence of the Transformation
By now we have performed the Web transformation often enough that we should begin to see a clear pattern
between the original and transformed procedure. Essentially, given a procedure f and its transformed version
f/k, we have that if the application
(f v1 . . . vm)
would have computed the answer a, then executing
(f/k v1 . . . vm k)
results in k being applied to the value a. This invariant ensures that, provided k is properly stored somewhere,
applying it to the value when it becomes available will leave the result of the computation unaffected.
17.5. TRANSFORMING HIGHER-ORDER PROCEDURES
163
17.5
Transforming Higher-Order Procedures
Suppose our Web program were the following:
(define (get-one-temp c)
(web-read (format ”Temperature in city ˜a” c)))
(web-display
(average
(map get-one-temp
(list ”Bangalore” ”Budapest” ”Houston” ”Providence”))))
(Assume we’ve define average elsewhere, and that it performs no Web input-output.) In principle, converting
this program is merely an application of what we studied in Section 17.1 and Section 17.2, but we’ll work through the details to reinforced what you read earlier.
Transforming get-one-temp is straightforward:
(define (get-one-temp/k c k)
(web-read/k (format ”Temperature in city ˜a” c)
k))
This means we must invoke this modified procedure in the map. We might thus try
(web-display
(average
(map get-one-temp/k
(list ”Bangalore” ”Budapest” ”Houston” ”Providence”))))
Unfortunately, map is expecting its first argument, the procedure, to consume only the elements of the list;
it does not provide the second argument that get-one-temp/k needs. So Scheme reports
map: arity mismatch for procedure get-one-temp/k: expects 2 arguments, given 1
It therefore becomes clear that we must modify map also. Let’s first write map in full:
(define (map f l)
(if (empty? l)
empty
(cons (f (first l))
(map f (rest l)))))
Clearly we must somehow modify the invocation of f . What can we pass as a second argument? Here’s one
attempt:
(define (map f l)
(if (empty? l)
empty
(cons (f (first l) (lambda (x) x))
(map f (rest l)))))
164
CHAPTER 17. MORE WEB TRANSFORMATION
That is, we’ll pass along the identity procedure. Does that work? Think about this for a moment.
Let’s try testing it. We get the following interaction:
Language: PLAI - Advanced Student.
web-read/k: run (resume) to enter number and simulate clicking Submit
>
This means the program has arrived at web-read/k for the first time. We run
> (resume)
which prompts us for an input. Suppose we enter 25. We then see
Temperature in city Bangalore: 25
25
>
It stopped: the program terminated without ever giving us a second Web prompt and asking us for the
temperature in another city!
Why? Because the value of the receiver stored in the hash table or box is the identity procedure. When
computation resumes (on the user’s submission), we expect to find the closure representing the rest of the
computation. Since the stored closure is instead just the identity procedure, the program terminates thinking
its task is done.
This gives us a pretty strong hint: the receiver we pass had better make some reference to map, and
indeed, had better continue the iteration. In fact, let’s think about where we get the first value for cons. This
value is the temperature for a city. It mu