The Old Joel on Software Forum: Part 3 (of 5)

Lisp and Productivity

Please excuse the long and rambling post. I finally found the "killer example" of why Lisp is more powerful than Java, and I'm not smart enough to use fewer paragraphs (I need an editor and to become bettter aquainted with the backspace key).

Paul Graham said "The only programmers in a position to see all the differences in power between the various languages are those who understand the most powerful one."

I have found this to be true. When I try to explain Lisp to a non-Lisper, I get either "If I wanted to, I could do that in Java" or I get "Why would anybody want to do that?"

Well, I have an example to share. Please direct flames to my email and thoughtful responses to this board.

Scheme (and an academic language called Io) has something called first-class continuations. Continuations encapsulate the remainder of a computation. You can use them to roll your own language features like loops and gotos and coroutines and escapes and exceptions and stuff I can't even imagine.

The aforementioned Paul Graham brags about how he used Lisp to write Yahoo Stores. One of the ways Lisp made things easy for Paul's team is that they used a variation of Scheme's continuations to model user state.

The standard J2EE web server looks very much like a CGI script. It's a stateless entity that exits with every HTTP response. You can use various hacks (like the J2EE session and cookies) to track state, but you do it by hand and you wrestle with the back button and other horrors of browser behaviour.

It's like using an old-school programming language that doesn't support recursion to program Towers of Hanoi. If you don't know any better, you don't switch langauges.

How do continuations help? I won't explain the mechanics, because this paper:

http://www.ccs.neu.edu/scheme/pubs/ase2001-gfkf.pdf

Does a great job.

But what you get is the ability to write web scripts with user response inline, such as this pseudo code:

Form f, g;

do {
f = get_response (some_html, some_page_data);
} until f.valid();
if ( f.hasAnEmailAddress() ) {
g = get_response (more_html, f.getEmailAddress());
}
else {
g = get_response (different_html);
}

You also can develop high-powered navigation systems including "breadcrumb trails" much more succinctly. But the main benefit is, you can write user interaction code where the linear flow of the code parallels the linear flow of the web application's UI.

Is this the only reason to use Lisp? No, but it exemplifies what Lispers call bottom-up programming or embedded language design: In Lisp, you start by identifying the programming language you'd like to use, then you implement that langauge in Lisp.

When writing CGIs, I think you'd prefer to have your pages displayed and results obtained in line. It's hard or impossible to do that as Lisp comes out of the box, but thanks to Lisp's macros and widespread reification, you extend the language to do what you need.

Of course, designing a domain-specific programming language is not for your commodity programmers. But a Testarossa isn't for your average driver, either :-)

Reginald Braithwaite-Lee
Wednesday, December 10, 2003

Continuations are to web programming as functional decomposition is to GUIs. That is, an extremely bad idea at the UI level.

Continuations as a concept are useful for maintaining the state machine of a long-term process like a workflow, bug report, that sort of thing. They suck at short-term GUI interactions for the simple reason that they are very attractive to linear-thinking programmers. Thus, the linear-thinking programmer tries to turn the user into a peripheral, rather than leaving the user in control of the UI. This leads to UI that sucks you-know-what.

If you think you need a linear web UI, there's a very strong chance you have no idea how to write a decent web UI. Conversely, event-driven web GUIs are as easy to write as say, Visual Basic apps, if you are using a toolkit that's reasonably REST-aligned.

All of this is entirely incidental to the issue of whether continuations are a useful programming concept in general, of course, or whether Lisp is cool because of it. Frankly, if you read the Pragmatic Programmer, you'll see some pleasant examples of how you can create domain-specific languages in Python that are much more readable than the corresponding DSL in S-expressions. I've noticed that non-programmers (whose eyes would completely glaze over looking at S-expressions) can easily read pseudocode-like Python DSLs.

I will admit to only one significant thing I like about Lisp better than Python, and that's easy programmatic manipulation of other code. I'm hoping the current "ast-branch" of Python development will yield easy-to-use AST objects in Python 2.4, at which point AST-manipulation in Python will be easier (and easier-to-read) than it is in Lisp.

There's also a minor other thing that I'd like: generic functions/multimethods. But that's more Dylan-envy or Cecil-envy than Lisp-envy, as CLOS uses lexicographic rather than pointwise or implication ordering. I'd love to have an implicate-ordered predicate dispatch capability in Python. Of course, there's nothing stopping me from adding it, except having enough spare time.

Phillip J. Eby
Wednesday, December 10, 2003

Your point about linear flow is an interesting tangent, Philip. May I put it in the "why would I want to do that" box?

Although I'd also prefer to see more elegant web UIs that are much, much less linear and much, much more event driven, that's not what I see on the web and that's not what I was been given to implement on a recent 375+ page J2EE project. No, I was not the UI designer.

But choosing popular examples from existing web applications, I'm thinking of things like validating web forms and checking out a "shopping cart" as places to use this technique.

Also, on the aforementioned project we spent a great deal of time handling the requirement for a "breadcrumb trail" and for gracefully dealing with the back button and window cloning, two areas that often cause problems. This technique would have solved these problems for us.

As for S expressions, you are making the popular case against Lisp. FWIW, Lisp was originally envisioned with a front end to translate another syntax into S expressions, but programmers found they liked the ease of implementing macros over S expressions.

So I'm not quite in agreement with you there. It's trivial to write a compiler to, say, translate Java to Scheme (no surprise: Guy Steele founded both languages). But you lose something very important when you obfuscate the syntax tree: you dilute the ability to hack your own language.

I'd rather not argue whether something should be done. I simply wanted to point out that there is something unique and powerful about Lisp that allowed a style of programming that is awkward when conforming to the supplied programming model.

Will you accept this claim: "if you need to build a web application that has a linear design for part or all of its UI, Lisp's continuations provide a powerful tool?"

Reginald Braithwaite-Lee
Wednesday, December 10, 2003

Note: Guy Steele did not solely found Java. That credit is usually given to James Gosling. I retract any suggestion he was the sole founder of the Java programming language. Likewise, John McCarthy is credited for developing a programming language based on Alonzo Church's Lambda Calculus. Guy Steele is usually credited for his pioneering work with Scheme, the Lisp dialect that raised continuations to first class status.

Reginald Braithwaite-Lee
Wednesday, December 10, 2003

There are whitespace lisps out there. Gregory Chaitin has been using one to explain his Goedel-like results with the Halting Theorem. It translates to parenthesis lisp, just as Reg mentions.

So Python's really getting macros? Influential Pythonistas were strongly against them, but I guess things change. I'm glad languages like Java, Python and XML are popularizing what's been in lisp for decades like GC, dynamism, etc. GC was actually considered evil once... then Java changed all that. So when people hear how horrible some random lisp feature is, some language will probably put it back in fashion.

The really nice thing is if the AST stuff is so powerful that you can easily manipulate code in a natural way, using the rest of Python to help out, Python will have become a lisp.

Tayssir John Gabbour
Wednesday, December 10, 2003

So if keep my state in a session object instead
of a continuation, what am i missing out on?

son of parnas
Wednesday, December 10, 2003

You're missing out on the convenience of not having to bundle up your state in a session object, and the convenience of treating web forms exactly like subroutines.

Rob Mayoff
Wednesday, December 10, 2003

Have a look at this example:

http://66.93.79.117:8180/webmaze/index.html

Reginald Braithwaite-Lee
Wednesday, December 10, 2003

The aforementioned example is currently broken. Consider it an example of how a powerful weapon can be used to destroy your foot, yourself, and the villiage around you if you misuse it :-S

Reginald Braithwaite-Lee
Wednesday, December 10, 2003

I really don't see the *problem* with having your session information in the session object. Can someone please explain?

Also, Reginald, I'm wondering how you'd share your "continuation" across multiple web servers, for instance, in a web farm. Everybody knows how to share an object, theres 20 different ways to do it in J2EE alone...is it just as easy in Lisp?

vince
Wednesday, December 10, 2003

Rob, the advantage of the object is at least there's
documentation and interface. No so with continuations,
which is what i have also found confusing.

son of parnas
Wednesday, December 10, 2003

Continuations in a web UI are simply syntactic sugar for sessions. Since they're sessions, that means that all the usual scaling concerns for sessions apply, as some folks above have indirectly inquired about.

I won't continue to get bogged down in the debate over continuations-as-sessions, except to point out that linearity in a web UI is an illusion. The fact that forms may follow one after the other in an ideal world doesn't mean the user will fill them out that way - they may go back and try to change something they already filled in. A session won't necessarily handle this, a continuation *definitely* won't, but a RESTful application always will, because in such an app, the browser's state *is* the UI state, period. (Note that UI state<>app state.)

On to AST's. Python isn't getting macros, AFAIK. It is *probably* getting an AST library, such that you could make objects like 'If(someExpr,block)', where 'someExpr' and 'block' would also be AST objects. Python actually already *has* such a capability right now, but it's based on... wait for it....

S-expressions! (Ah, the sweet irony.)

The reason that (almost) nobody uses Python's current AST system is that it's based on deeply nested lists of symbols and tokens that are ridiculously difficult for a human being to read/understand, and therefore complex to write processing code for. So, right now you could certainly write a Python syntax processing tool, but you'd probably want to write it in Lisp. :)

The new AST model, OTOH, would allow manipulating Python ASTs using an OO paradigm rather than a Lispy one. When Python AST's are cleanly expressible in Python without much syntactic overhead (compared to the code they represent), then Python will be a natural choice for manipulating Python's own program code, just as Lisp is for Lisp.

Now, let's watch the irony come full circle, as I explain *why* I want AST manipulation in Python...

You see, I'd like to be able to use Python as a simple representation of business workflows. Create "while" loops and branches and the like, calling functions to send messages to users and get results back...

Hey, wait a minute! That sounds like continuations. Yep. Exactly like 'em. But I said that was bad for UI's... what the heck is going on?

That's just it. I don't want a continuation to express the *UI* of the workflow. I want it to express the *state* of the workflow. The workflow itself is a persistent object that's part of the application. But as I said, UI state is not application state. The workflow's "continuation" would be saved as a value in the RDBMS, and would be shared among any and all users accessing it. It would *not* be part of the UI state for those users, though, as that would remain browser-based state.

So, now I can answer the question of whether I think continuations are a useful tool. Yes, obviously I do. But they absolutely do not belong in a web UI. Period.

(Of course, I don't really need to wait for the fancy AST library to come out; I could probably bite the bullet and generate my own AST library from the ASDL (abstract syntax description language) metadata that's already available for the Python ast-branch, and then implement my continuation-like workflow system. I just haven't done so yet, because the project I want this for isn't likely to start until the middle of next year.)

(Oh, and if the AST->continuations leap isn't obvious, it's because I intend to either adapt the AST nodes to executable objects, or transform the AST to recompile the procedural code into a state machine.)

Phillip J. Eby
Wednesday, December 10, 2003

<i>The fact that forms may follow one after the other in an ideal world doesn't mean the user will fill them out that way - they may go back and try to change something they already filled in. A session won't necessarily handle this, a continuation *definitely* won't, but a RESTful application always will, because in such an app, the browser's state *is* the UI state, period. (Note that UI state<>app state.)</i>

I think you're misunderstanding continuations as used in web frameworks. Form sequences that would make for a directed acyclic graph (dag) are a perfect match for continuations.

The UI is pretty much just as it would be in a RESTful app (if I understand REST correctly), it's just that the continuation ID is placed in there on the query string, which is similar to a session (from a UI perspective). Continuations come into play for managing the "app state" you refer to, including situations where the UI's state is difficult to follow (back buttons, multiple windows, etc).

Check out Christian Queinnec's paper on the concept, "The Influence of Browserson Evaluators or, Continuations to Program Web Servers." http://www-spi.lip6.fr/~queinnec/Papers/webcont.ps.gz.

Points raised about "scaling concerns" are correct, but if you only use continuations for directed, transactional situations, the scaling becomes more manageable.

Robert Sayre
Wednesday, December 10, 2003

hmm maybe you would want to take a look at a continuation-based web appplicatin framework done in Smalltalk by Avi Bryant.
you can find it here http://beta4.com/seaside2/

more info here by someone who tries it out
http://homepage.mac.com/svc/ADayAtTheBeach/index.html

edd
Thursday, December 11, 2003

If programmers fear S-Expressions, what about their ugly sibling: XML?

Just me (Sir to you)
Thursday, December 11, 2003

You're confusing application state and UI state.

Let's say we're talking about an e-commerce checkout. "App state" there is the contents of your cart, your account object, and other things that one would find in the application's *persistent* state.

Which *form* you are on in the checkout process is "UI state". UI state isn't persistent, it's just where "you" (the user) "are". App state is the state of the objects the server deals with.

Your application objects shouldn't know about UI state. It's not their business to be asking users to fill out forms. Application objects shouldn't even know that there's such a thing as a form. The UI controls the app, not the other way around.

Now, once you've separated app objects and UI objects, then it becomes a lot easier to see that there isn't any point to using continuations in the UI part. Every URL of the application is simply a rendering of some aspect of the current state of the application objects. Every form post invokes a method on a UI object, which either applies changes to an application object, or renders a form that accumulates data from previous forms until there's enough to apply changes to the app objects. But the logic to do this, even for multi-page forms, is a simple series of:

if not screen1Data.isValidAndComplete():
renderScreen1()
elif not screen2Data.isValidAndComplete():
renderScreen2()
# etc...

Which *is* linear logic, it just lives inside *one* page and has no need for a continuation. Of course, if the form has branching, the logic becomes a bit more complicated, but no more so than you would've had with a continuation. And if you regularly have these sorts of forms, you change it to a state machine data structure.

Anyway, this method is:

1. Stateless in the UI (browser keeps all state)
2. Highly scalable (no sessions exist, all application state is in the RDBMS)
3. Impervious to the effects of the back button or user manipulation (because all the data in a multi-step process is validated on every post)

Personally, as a user of web applications I'm horrified by the sudden popularity of this continuations-as-web-UI meme. It's going to greatly increase the number of applications with broken Back buttons, and that break if I take a lunch break in the middle of using them (because of %&3@)&$($% session timeouts).

If you love your users, don't use session-based continuations in the UI. For that matter, don't use sessions in the UI at all if you can avoid it.

Phillip J. Eby
Thursday, December 11, 2003

I've always liked the idea of continuations as a GUI tool. Look at them this way.

/------------->
---- App Logic
\------------>

HTML
^
+
+
++++++++
+ /----------------->
++++ /+++++++++
-------- +
++++ \ ++++++++
+ \----------------->
+++++++++
+
\/
HTML

You can make your GUI a function over your application logic
then app logic doesn't have to interface to the GUI.

----->App State+++++>HTML
|
|++++++++>HTML
|
\/

This get rid of all the boiler plate stuff with observers, and actions being sent around.

A N Other Student
Thursday, December 11, 2003

You've missed the point entirely. A REST style lets you do this naturally, and can be implemented without language level continuations.

The first time I saw the idea of continuations as web UI state, I thought it was cool - until I thought about what it would mean for both web tier scalability and application usability.

Oh well, I guess we'll see it run its course like so many other fashions in how to program web apps. It blows my mind that a full five years after Jim Fulton's "object publishing" revolution, people are *still* trying to force the web genie into a procedural bottle. It's quite ironic, given that the solution is practically spelled out in the HTTP spec.

Amusingly, this puts me in roughly the same position as a Lisp advocate, bemoaning how years after a perfect solution has been realized, everybody else is still evolving towards it. :)

Phillip J. Eby
Thursday, December 11, 2003

Phillip,

Is this what you mean by REST?

REpresentational State Transfer
http://www.c2.com/cgi/wiki?RestArchitecturalStyle
http://internet.conveyor.com/RESTwiki/moin.cgi/FrontPage

Ged Byrne
Thursday, December 11, 2003

Yep, although I've been doing REST since before the term REST was invented. In 1997, Jim Fulton (the CTO at Zope Corp) developed a technique he called "Object Publishing", and implemented in a library called the Python Object Publisher (aka Bobo). The object publishing metaphor is found in many Python toolkits today; in other languages it's found only in crippled form, at best.

Some aspects of object publishing are part of the REST canon now, others might be considered mildly controversial by REST-heads. I only use the term REST when discussing object publishing because it has *some* small name recognition outside the segment of the Python community that has heard of "object publishing".

Anyway.. the idea of object publishing is that every URL represents an object. In a language like Python, where methods and attributes are also objects, this is an easier idea to understand than in less-than-OO languages like Java.

Loading a particular URL in a browser means to "invoke" or "call" the object at that URL, thus invoking the method. Parameters supplied by a form or URL query string are parsed and converted to the proper call signature for the method or other object. The return value is a web page.

Now, so far, this might sound no different than say, ASP or JSP. At least, if you think that URLs are filesystem paths. But they're not. The base URL of the application refers to the "application" object. Any path below there is accessing sub-objects of the application object. You might have a URL like 'Orders/4375495/addShipment', representing the addShipment method of Order object #4375495. (This is where REST purists will object that the only methods should be GET, PUT, POST, and DELETE, and that there should be a /shipments URL that you POST to to add a shipment. Me, I'm not always so picky. Practicality beats purity.)

About this point, some Java folks will likely jump in and say that you can do that in Struts. For all I know, maybe you can now. But often in the past people have told me they can do all this in Struts, until I try a few examples of what you can do when there's no central "URL map" to tie you down, and don't have to create "action" classes and all that other stuff. At that point, they usually admit that Struts isn't exactly the same as the object publishing approach, though I'll admit it's one of the closer things to it that I know of in the Java world.

Phillip J. Eby
Thursday, December 11, 2003

Im intrigued by this:

"Orders/4375495/addShipment', representing the addShipment method of Order object #4375495. "

Is 4375495 an object ID assigned by the system at construction, like a pointer, or a unique identifier like a records key in a relational database?

Is it possible to access multiple objects with a single URI, or is it necessary to do so through a container object?

Ged Byrne
Thursday, December 11, 2003

"""Is 4375495 an object ID assigned by the system at construction, like a pointer, or a unique identifier like a records key in a relational database?"""

That depends on how the object whose URL is '/Orders' wants to interpret it, which is one of the approach's big benefits.

Think of it this way. Let's say you have an interface "ITraversable" with a method "traverseTo(name)" that returns the object for that name. Now, the "application" (root) object's traverseTo() would return the "orders" object when you go to /Orders. That object would then interpret the next part of the path, to return an order object. The order object interprets the next path component to select a method. Finally, the system "invokes" the final result of the traversal process. (You can think of this as another interface, IRenderable, with a 'render' method to output the resulting resource.)

In a practical system, both the traverseTo() and render() operations would take an additional parameter to get context objects like a request, response, or session objects as applicable. There's also usually a mechanism to add a "default method", in case you stop on an object that is not itself renderable, but has a default representation.

And, the objects implementing the traversal and rendering interfaces may be "view" classes rather than "model" classes. That is, you may not have your business objects implement those interfaces directly, instead defining a set of simple wrappers to manage the traversal, and to point to things like JSP or ASP pages to implement the "render"-ing of certain objects.

That is, if the 'order' object returns wrappers around JSP pages for most of its traverseTo() targets, then voila, you now have a mechanism for easily implementing all an object's "viewing" methods. (The wrapper is needed so the JSP page knows what object it's being used as a "method" of.)

To do this well in Java, you'd also want to have some kind of wrapper you can use around a Java method to take input parameters from a form and invoke the method, perhaps using Java reflection. Or maybe you'd just define interfaces that you want to make traversable, so that the /addShipment URL could be mapped automatically to the addShipment method of the class. (That sort of reflection is trivial to do in Python, which is probably why the idea of doing things this way appeared there first. In Java, a framework would need to provide some utility classes to do some of the gruntwork that you'd otherwise be doing over and over.)

Oh, anyway, here's one of the nifty benefits of this approach. URLs are *relative*. Let's say I'm at the URL /Orders/123456/, which displays the "default rendering" of the order. That page can have a link that says <a href="addShipmentForm"> to go to /Orders/123456/addShipmentForm. There's no need to compute funky absolute links or redo query strings in order to refer to related objects or methods of the current object. It's just plain hardcoded text -- unbelievably natural, compared to other approaches.

To me, this is the most natural way in the world to write web applications. The programming model matches the user model: your location is your URL, you navigate by links, and you can change the state of the objects you interact with. Either you've changed their state or you haven't.

You can take this further and eliminate the concept of "sessions". Instead, you simply have cookies that may identify objects other than the current location. So, you have a "shopper ID" cookie that lets your objects look up a "user" object or "cart" object, or whatever. I call this using a "session-specific object", as opposed to using a "session object" (which in most frameworks is a weakly typed bag of data that may or may not be well-replicated across the web tier, may or may not be backed up with the business data, etc.)

Anyway, at that point, all the business data goes in the business data storage tier; none of it sits in the web tier. Thus, no replication or backup issues, and no scattered/conflicting policies about how long data is kept or what business rules apply to it.

But I digress, obviously. :)

Phillip J. Eby
Thursday, December 11, 2003

I guess I don't see how continuations are being used for the UI. I've only seen them used as a replacement for state machines in the app state, as in Cocoon.

http://cocoon.apache.org/2.1/userdocs/flow/

Robert Sayre
Thursday, December 11, 2003

The page you linked talks about "application state", but they *mean* what I'm calling "UI state".

What I'm calling "application state" is the state of the persistent business objects (aka "problem domain" objects, aka "model" objects, etc.) And that is not what they're talking about there, at least from my reading of the page. They are assuming there that the "application" is the web UI itself. Note this passage:

"""Any request received by the application transitions it into a different state. During such a transition, the application may perform various side-effects, such as updating objects either in memory or in a database. Another important side-effect of such a transition is that a Web page is sent back to the client browser."""

This makes it pretty clear that by application, they mean the web UI itself, since they say here that the application updates objects. Presumably these are the business objects, PDOs, or model objects, according to your preferred buzzword du jour.

I'm cool with using continuations inside your (insert buzzword here) objects to manage *their* state. But that doesn't appear to be what Flow is for.

The digression about REST and object publishing was to support my point that such approaches to developing UIs are a very "thin layer" over the business objects, and thus don't *need* continuations in order to be written cleanly. Conversely, using continuations or continuation-like mechanisms to manage the state of business objects is quite reasonable. It just belongs in the right tier of the application environment.

Phillip J. Eby
Thursday, December 11, 2003

I was thinking of GUI in general, possibly more as a way to avoid the death-by-thousand-cuts issue with programmatically hooking up objects.

It is true that doing this sort of thing is only necessary because HTML cannot control its own GUI behaviour on the client-side. If we all used XUL browsers, or JavaScript worked in a simple compliant way, or even if XForms+CSS2 were supported, then you could use the single url as a single object approach all the time. But for some complex apps that's not feasible :-(

A N Other Student
Thursday, December 11, 2003

"""But for some complex apps that's not feasible"""

Show me one.

Phillip J. Eby
Friday, December 12, 2003