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.