- Recent Changes 新聞
- History 歷史
- Preferences 喜好
- Discussion 討論
In the ICFP 2000 paper The influence of browsers on evaluators or, continuations to program web servers Christian Queinnec offered a compelling view of web interactions as browsers’ operating on continuations of server computations. He exhorted web application programmers to use first-class continuations to write interactive (web) programs in direct style. “Instead of thinking in terms of state and transitions from page to page, we propose an alternative view where a program is suspended and resumed, continuations automatically reifying the state of the computation.”
The popular introductory example of a dynamic web page asking
for two numbers and showing their difference can be programmed
essentially as get_int "n1" - get_int "n2"
. The
library function get_int
should make a web form and
embed into it some representation of the current continuation. The
continuation is resumed when the form is submitted. The above web
program appears conventional (with inputs seemingly coming from a
“file”) relieving the programmer from worrying about page
transitions and state maintenance. This style also makes dynamic
pages do the right thing when the user pushes the “Back” or
“Forward” buttons one or more times, or bookmarks a form and comes
back to it later.
Queinnec’s paper proved influential and has inspired the development of many continuation-based servers: Yahoo’s query: continuation-based web servers
The original approach was restricted in that the answers were
solicited one-by-one. When running our example get_int "n1" -
get_int "n2"
, the server sends a web form asking the user
for the first number. After that form is submitted, the server
sends the next form asking for the second number. Upon submission
of the latter, the web page with the answer is generated. We
observe that the two questions are independent and could have been
asked together. The notable benefit of bundling the
questions is reducing the traffic between the server and the
browser and resources for storing continuations. Most of the forms
on the web typically contain more than one question.
This message presents a uniform mechanism for flexible and
automatic bundling of questions into forms. We still write our
server code essentially as get_int "n1" - get_int
"n2"
. Our library automatically groups the questions into
one web form. The library takes care of parsing multiple responses,
matching them with the questions and validating the replies. Should
some inputs turn invalid, the library automatically generates an
error form with the questions, the given answers and the
corresponding error messages, asking the user to edit the answers
and re-submit the form. The error handling is automatic and
transparent for the servlet.
Our mechanism relies on call-by-need: the library delays asking
questions until their answers are demanded. When a question really
needs to be answered, the library collects all outstanding
questions, makes a web form and sends it to the client as the
response of the server computation so far. When the form is
submitted and the computation resumes, the library parses all the
replies and stores them for future answer demands. Since our
particular implementation language (OCaml) is strict, call-by-need
is not automatic: The programmer does have to write
Lazy.force
explicitly. The type system ensures that
the programmer does not forget the forcing, thus making the data
dependencies apparent. OCaml type checker will tell the programmer
the points where a value is demanded. The programmer should insert
Lazy.force
there – or at some earlier point, if the
programmer so chooses. If the programmer forces the answer after
asking each question, we get back the sequential behavior of asking
questions one-by-one.
Our framework may be regarded as a different mode of composing questions: not serially (one-after-another) but in parallel. A follow-up message will draw the correspondence with monads (which embody sequential composition) and arrows.
Note on examples
To fully demonstrate our approach we need a web browser and a continuation web server. Although many such servers exist, they are not fully compatible, may require special privileges to install and may conflict with the web server already installed on readers’ computers. That makes it impractical to demonstrate any real servlets. Therefore, we emulate web interactions by those at the OCaml top level prompt. To invoke a server computation, rather than entering a URL into a web browser, we type the corresponding expression at the prompt. When the computation finishes, the top level prints its result (in the “natural” rather than HTML format). The result, which may be a “web form”, can be “bookmarked” (that is, bound to a top-level variable) and then reinvoked none or many times. Our emulation thus captures all attributes of web interactions: taking turns, interactivity, back-and-forth navigation, bookmarking.
The complete OCaml code for this article is available at http://okmij.org/ftp/ML/ask-by-need.ml
Warm-up: asking questions one-by-one
As a warm-up and the illustration of our “web interactions” and
for contrast with the next section, we reproduce here the standard
example of using continuations for web programming: we ask the user
for two integers n1
and n2
and send the
“page” showing their difference. Each question comes on its own
“form”. This is essentially the example from the Queinnec paper
(only he used currency conversion).
First we define the type of “web pages” shown to the user
type 'a req =
| Done of 'a
| Req of string * (string -> 'a req)
One should read the value Done x
as if it were a
web page showing the result x
. If the “server”
computation gave the result Req str k
, imagine it were
a web form containing the string str
, with the
continuation k
embedded as a hidden form parameter. We
should use the procedure answer req reply_str
to
“submit” such a form.
The servlet library is so simple that we can show the whole code.
let topp = new_prompt ()
let run th = push_prompt topp th (* how to run the servlet *)
The servlet calls exit v
to send the “final web
page” with the computed answer:
let exit v = abort topp (Done v);;
The following is a procedure to ask a question. The second
argument is the conversion function, from string to the desired
reply type. The function may raise an exception
Scanf.Scan_failure
if the conversion fails. The
library then repeats the question.
let question (str:string) cnv =
let rec loop errstr =
let ans = shift topp (fun k -> Req ((errstr ^ str),k)) in
try cnv ans with Scanf.Scan_failure e -> loop e
in loop ""
A sample conversion function, to convert user’s answer to an int:
let read_int (str: string) : int = Scanf.sscanf str "%i" (fun x -> x)
If req
is a “web form” sent by a “server
computation”, we should use answer req reply_str
to
“submit” the form with our reply.
let answer (Req (_,k)) reply_str = k reply_str;;
Here is the servlet itself, asking for two numbers and computing their difference:
let test1 () =
let n1 = question "Enter 1st number" read_int in
let n2 = question "Enter 2nd number" read_int in
exit (n1 - n2);;
Let us show a sample interaction (the replies from the server are indented)
We type the test1 “URL” and get the form in reply
let it = run test1
val it : int req = Req ("Enter 1st number", <fun>)
let bookmark1 = it;;
let it = answer it "456";; (* Submit the web form, get another one *)
val it : int req = Req ("Enter 2nd number", <fun>)
let it = answer it "123";; (* Submit it too, get the answer *)
val it : int req = Done 333
let it = answer bookmark1 "111";; (* Go back to bookmarked form 1 *)
val it : int req = Req ("Enter 2nd number", <fun>)
let it = answer it "xyz";; (* If the answer is unacceptable, we are *)
(* asked to repeat it *)
val it : int req =
Req ("scanf: bad input at char number 1: xEnter 2nd number", <fun>)
let it = answer it "10";;
val it : int req = Done 101
Asking several questions at once: ask-by-need
Let us now show the code that uses the extended servlet library, which asks questions lazily. First we reproduce the old sequential behavior: we force the answer right after asking a question:
let test21 () =
let n1 = Lazy.force (question "Enter 1st number" read_int) in
let n2 = Lazy.force (question "Enter 2nd number" read_int) in
exit (n1 - n2);;
Not surprisingly, the servlet test21
behaves
exactly as test1
above.
We now demonstrate the asking several questions at once. We insert Lazy.force only where the typechecker tells us to, but not earlier. We emulate call-by-need.
let test2 () =
let n1 = question "Enter 1st number" read_int in
let n2 = question "Enter 2nd number" read_int in
exit (Lazy.force n1 - Lazy.force n2);;
If we “enter the URL”, we see the form with two questions
let bm2 = run (fun () -> topqq test2);;
val bm2 : int req =
Req
("Enter 2nd number: ; Enter 1st number: ;
Needed 2 answers. Separate with & character",
<fun>)
let it = answer bm2 "xxx";;
val it : int req =
Req
("incorrect number of ansEnter 2nd number: ; Enter 1st number: ;
Needed 2 answers. Separate with & character",
<fun>)
Below, both numbers failed validation, and so two error messages are given:
let it = answer it "xxx&aaa";;
val it : int req =
Req
("Enter 2nd number: scanf: bad input at char number 1: x in xxx;
Enter 1st number: scanf: bad input at char number 1: a in aaa;
Needed 2 answers. Separate with & character",
<fun>)
If one number was acceptable, we still include it into the error form:
let it = answer it "xxx&123";;
val it : int req =
Req
("Enter 2nd number: scanf: bad input at char number 1: x in xxx;
Enter 1st number: 123;
Needed 2 answers. Separate with & character",
<fun>)
Finally we give an acceptable answer, and the servlet may proceed:
let it = answer it "456&123";;
val it : int req = Done (-333)
The new servlet library is the extension of the above code. To
keep track of outstanding questions and not-yet consumed replies,
we maintain the queue of qq
values, identified by
qid
.
type qid = int;;
type qq = {qq_str : string; (* question string *)
qq_answer : string option; (* received answer, if any *)
qq_id : qid;
qq_validate : string -> string option}
The following data type defines the protocol within the library,
between the lower-level and the QnA supervisor. The lower-level may
submit a question, receiving qid
. The lower-level may
ask the supervisor to provide the answer to the question identified
by qid
.
type qreq =
| QReq of string * (string -> string option) * (qid -> qreq)
| QRes of qid * (string -> qreq)
We re-define the question
function, keeping its
interface. This function no longer sends any form to the user.
Rather, we submit the question to the QnA supervisor and make the
promise to resolve the received qid
into the real
answer.
let question (str:string) cnv =
let qq_validate =
fun str -> try cnv str; None with Scanf.Scan_failure e -> Some e in
let qid = shift qp (fun k -> QReq (str, qq_validate, k)) in
lazy (cnv (shift qp (fun k -> QRes (qid,k))))
The URL given earlier contains the complete code.