Programming Languages: Application and Interpretation

A new release of Shriram Krishnamurthi's programming languages book is available.

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

Instead of fixing protocols, we code around them.

There is a whole chapter on web applications and how continuations can be useful in such an environment. While I do not doubt continuations are clever, I really do not understand why the web protocols are not fixed. They are clearly not appropriate for rich applications over WANs. Instead of fixing the protocols (where the real problem lies), we invent new programming languages and libraries around the problem. Is that good or logical?

It is when there's more

It is when there's more investment in the protocols than the languages and libraries. Changing protocols is high cost.

Quality

It's also worth pointing out that the protocol in question, HTTP[S], is actually quite good, serving its intended purpose of "HyperText Transfer" and, thanks to MIME, quite a bit more than just HyperText. It also serves nicely as a strata for a variety of styles of distributed software; see any of the literature on REST or just start with Waterken's Web Calculus. You really can think of HTTP as a tiny language with a few functions ("GET", "POST", "PUT"...) that are polymorphic across many, many (MIME) types. This works remarkably well: it's extensible, cacheable, scales like a bat out of hell, etc. Best of luck improving on it.

What it revealed, though, is how impoverished the control flow primitives of mainstream programming languages are: they're all things that are expressible in terms of (full upward) continuations, but only Scheme (AFAIK) actually has full upward continuations and a handful of sugared constructs for convenience. It turns out that continuations aren't merely good, but perfect, for dealing with the stateless request/response paradigm of HTTP, so other languages are finally beginning to appreciate the thoroughly pragmatic value of continuations.

Indeed, HTTP is good for 'hypertext transfer'. Not for web apps.

Indeed, HTTP is good for 'hypertext transfer'. Not for web apps though.

It turns out that continuations aren't merely good, but perfect, for dealing with the stateless request/response paradigm of HTTP, so other languages are finally beginning to appreciate the thoroughly pragmatic value of continuations

The need for continuations is not caused by the stateless nature of HTTP, but by the way browsing works. In fact, the stateless part is totally irrelevant to the problem.

Imagine a desktop GUI application that is built with a GUI library that does not invoke operations on objects, but just sends a text message to some receiver. Would this GUI app work if the receiver is not notified about the state changes of the client? nope, it would not. So it is a matter of how browsing works, and not about being stateless.

When an HTML link is clicked, and that link represents a state change in the server, then the server must be notified. If the server is not notified, then the reflection of the client's state to the server's state is broken. Between two state changes, though, there need not be a link between client and server.

So, the problem is not the stateless nature of HTTP, but that the HTTP combination do not always notify the server about the state of a web app.

Instead of solving this problem, it is proposed that we introduce additional complexities in programming languages in order to support continuations...my opinion is that the added complexity does not justify the benefits and does not solve the problem, just bypasses it for any given context (but the problem remains for other contexts).

To put it in other more simple words, the back button means 'see the previous document' and not 'activate previous task'. If it meant 'activate previous task', then it should have been implemented as such.

Using continuations twists the browser, the protocol, the programming language, and the programmer with another one complex concept to master, debug and follow. It also breaks the simple concept of request/response.

Re: The problem is state

From my limited readings, it seems like "what about state?" is clearly known to be a core issue. That is why some folks argue that you choose between REST and continuation-style based on what kind of state you are going to have to maintain; there comes a point where REST makes you do contortions that would be best avoided via the continuation-style, and the other way 'round as well.

It sounds to me like you are perhaps suggesting that the client inform the server more often of state changes so that they are in sync? This gets into a whole big discussion of where the state should be kept, especially in light of all the things HTTP/MIME/REST give us in terms of the *abilities... what thoughts do you have about these issues?

Have you ever used web continuations?

Because the whole point of them is that they're not difficult to master, debug, or follow; particularly not in PLT's server. I can't speak for many other systems (vide infra), but send/suspend and friends hide any continuations used, letting you treat web events like normal input -- simple request/response. That is, in fact, the point.

Another good example is Eleven, a continuation-based form language that compiles into PHP. It, too, is quite seamless and fairly easy to use. It is a very different, but still useful approach -- very database oriented.

Using continuations does not twist the protocol at all. They are a separate layer, just like CGI, PHP, and servlets.

I agree with you that there are problems with the continuation method; one serious question is how long to cache them. This remains an open problem.

While you're right that the back/forward buttons make dynamic service over HTTP more difficult, it's a little late to change the dominance of the browser as a platform. Browsers guarantee a familiar, well-integrated interface with a very high degree of per-software UI customizability (DHTML, XUL); moreover, they're already written and tested.

Don't Maintain State On Both Client And Server

So, the problem is not the stateless nature of HTTP, but that the HTTP combination do not always notify the server about the state of a web app.

A more serious problem is trying to maintain state on both client and server, rather than choosing one or the other. This is like a man with two watches: he never know what time it is.

My preference is to store state in the client browser and use REpresentational State Transfer (REST). So I second Paul Snively's comments and recommend a look at REST rather than further consideration of alternative protocols.

The W3C Web Services groups have argued about this for years but the de facto WWW standard remains REST. REST is straightforward, is how the WWW works, is dominant in practice (for good reasons, as Paul points out) and that will not change soon.

!(REST vs. Continuations)

A more serious problem is trying to maintain state on both client and server, rather than choosing one or the other. This is like a man with two watches: he never know what time it is.

REST maintains state on both client and server - it advocates maintaining session state on the client, but resource state is maintained on the server. One of the main ways a REST app tends to differ from other kinds of application is that it converts session state to resource state early, so that session continuations can be efficiently represented and serialized as links to resources (URLs).

So I second Paul Snively's comments and recommend a look at REST rather than further consideration of alternative protocols.

Continuations, in general, are not an "alternative protocol" to REST. REST depends on continuations, which it serializes into web pages. This is something that can be handled by an automatic transformation, i.e. it isn't necessary to author programs in REST style "manually".

!(REST vs. Continuations)

A more typical discussion of "REST vs. continuations" and here(search for "continuation").

Anton, I am familiar with your PDF slideshow Continuations continued: The REST of the computation on this topic, also available by following the links from Bill Clementson's blog.

In your above post you say:

  • "REST maintains state on both client and server"
  • "resource state is maintained on the server"
  • "REST depends on continuations"

Most RESTafarians would disagree with at least 2 of these statements. In REST no application state (also termed "session state") is stored on the web server: all application state is stored on the client. Between requests the web server forgets everything about the client browser and about any application state stored in that browser (whether displayed or not). That is one reason REST apps scale: no web server memory is tied up maintaining application state [I find the term "resource state" equivocal: perhaps you can explicate]. And finally, most REST developers have little or no knowledge of continuations or CPS, yet write RESTful apps.

For the reader, here's Roy Fielding's explanation of what REST means by "stateless".

In an earlier LtU post you stated:

"In a REST application, a URL ... represents a continuation, complete with state, but most of the state is stored in the form of resources on the server. The URL (continuation representation) references that state."

REST proponents would say the bolded statement is contrary to REST. Perhaps here also there should be some clarification of terminology, e.g., "state" (i.e., "application state", "resource state", etc.) and "server" (i.e., did you intend "web server", "database server", both, or something else?).

!(REST vs. Continuations)

In REST no application state (also termed "session state") is stored on the web server: all application state is stored on the client.

I agree that this is a common way in which REST is characterized, and within the context of REST itself, it may make perfect sense, but it's very misleading when you try to compare REST applications to other kinds of applications.

If you examine applications that are considered good examples of REST style, they regularly convert data which might otherwise be considered session state, into resources. This allows them to maintain such state (whatever it is called) on the server side (i.e. not on the client), while efficently representing continuations as links which refer to that server-side state. Resources are created and/or mutated throughout the life of an application, and represent persistent state on which the application depends.

So REST's application/session state is a subset of what other kinds of applications tend to consider session state. The fact that the term is further reduced to just "state" makes it difficult to have unambiguous discussions when comparing REST to other application styles, where the term "state" has a much more general meaning.

Between requests the web server forgets everything about the client browser and about any application state stored in that browser (whether displayed or not). That is one reason REST apps scale: no web server memory is tied up maintaining application state

This scaling property is enabled by the fact that any session state that's not appropriate to be maintained by the client is converted into resources which are maintained persistently on the server side (by a database or whatever), so while the web server might cache those resources, it doesn't have to.

[I find the term "resource state" equivocal: perhaps you can explicate].

Fielding uses the term resource state, even in the message you linked to. I believe I mean exactly what he means by it.

And finally, most REST developers have little or no knowledge of continuations or CPS, yet write RESTful apps.

Most programmers in general have little knowledge of continuations, yet depend on them every time they call or return from a function, or use exceptions, or break out of a loop. This doesn't make continuations any less useful as a theoretical tool for understanding and describing control flow in programs.

REST programmers may not know about CPS from a theoretical perspective, but they're used to writing applications in CPS, manually encoding continuations as URLs and HTML forms, and managing a server-side "store" which allows these continuations to be expressed concisely and function correctly. IOW, REST programmers have an operational understanding of continuations and CPS in a particular context.

In an earlier LtU post you stated:

"In a REST application, a URL ... represents a continuation, complete with state, but most of the state is stored in the form of resources on the server. The URL (continuation representation) references that state."

REST proponents would say the bolded statement is contrary to REST. Perhaps here also there should be some clarification of terminology, e.g., "state" (i.e., "application state", "resource state", etc.)

The bolded statement is not contrary to REST, but it is characterising what REST actually does using terminology as it is used outside REST. I used the term "state" in its more general sense. When it is meant in a more specific sense, I think that should be made clear. If one is talking purely within the context of REST, then it might be understood that "state" means "REST application/session state", but I believe that this even tends to confuse many RESTafarians, judging by some discussions I've seen.

and "server" (i.e., did you intend "web server", "database server", both, or something else?).

By "server", I essentially meant "not the client". I assume we can take it for granted that resources are are stored external to the web server, so there's no controversy at that level how things are managed.

To summarize by addressing the bullet-pointed quotes you listed: The issue with the first one, "REST maintains state on both client and server", is that I used the term "state" in a more general and common sense than it's used within REST, to refer to the combined application plus resource state in the REST sense. The second one, "resource state is maintained on the server", is accurate and matches Fielding's terminology, although "on the server" might be clarified to taste. The third one, "REST depends on continuations", is true in multiple senses: first, the conceptual sense in which continuations are an abstraction of control flow; and second, in the sense of first-class continuations, as I have said, REST programmers, or the frameworks they use, create explicit representations of continuations, upon which the control flow of REST applications depend.

It turns out that

It turns out that continuations aren't merely good, but perfect, for dealing with the stateless request/response paradigm of HTTP, so other languages are finally beginning to appreciate the thoroughly pragmatic value of continuations.

Continuations are perfect for dealing with stateful request/response. The server maintains state on behalf of each client, represented by the continuation.

This is no different from RPC. In an RPC call, a client sends a request to a server and blocks until it receives the reply. E.g. it stores a continuation to be passed the result of the call; the middleware invokes the continuation when it receives the reply message. In RPC calls in normal imperative languages that don't expose continuations to the programmer (e.g. C or Java), the calling thread blocks in a monitor waiting for the middleware to put a response into and signal the monitor. Conceptually it's the same thing.

In a stateful web app, the web server sends a request to the web client and waits for a reply. From a request/response point of view, the web server is the client sending a request and the web client is the server handling the request and sending a response. So continuations in the web server are a natural fit, as are lightweight (user-space) threads.

Not quite

Web applications in general have to allow for users to revisit the same web interaction point multiple times.; see Queinnec's original paper for an example. Userspace threads don't allow that (or at least they're not a great semantic fit). This point is made in Queinnec's original paper introducing the notion of continuations for web programming, The Influence of Browsers on Evaluators or, Continuations to Program Web Servers.

Good point. That damned

Good point. That damned back-button!

Isn't a new language/framework just as (or more) costly?

It would be cheaper to define a new protocol for web applications rather than changing all frameworks and programming languages. All it takes to change a few browsers (IE, firefox, mozilla, opera, and a few others). Whereas there are 100s of frameworks and 10s of programming languages, some of which can not be altered to support continuations.

This is, unfortunately, not

This is, unfortunately, not the case. Assuming you want to change HTTP(S) rather than creating a new protocol whole-cloth, more than a few browsers have to change---there are more than hundreds of frameworks in tens of languages implementing the client-side of the protocol. For web applications especially, those are what need changing.

Then, your new servers have to be capable of dealing with clients that have not been changed, and vice versa. There are still version 1 browsers in use, for whatever definition of "browser" you have.

If you want to create a new protocol, you are facing fewer technical issues, but you are looking at a much bigger non-technical problem. There are, in fact, quite a few protocols around like BEEP and SCTP that claim better application usage. None of them seem to have reached the critical mass to replace HTTP(S), however.

Another perspective

Having just taught this material, I think the above discussion is, while important in the grand scheme of things, missing the point with respect to this PL text. Web programming provides a very nice motivation for introducing the language feature of continuations, and it is usually better to have the motivation precede the introduction rather than the other way around (as is depressingly common in introductory programming courses). It can also be seen as an exercise in the natural expression of a computation that, at first glance, does not appear to be suited to natural expression, at least in the given language. Both of these have benefits beyond the particulars of Web programming. --PR

Awesome

About two four days ago I decided to write an interpreter, I struggled to find good resources and now this appears, what a coincidence! :)
I have programmed a lot and I have studied HTDP up to section 18, half of SICP lectures, etc. Do you think I am up to this text ?
Thanks.

Probably. Good luck!

Probably.

Good luck!