Main

October 13, 2008

ECMAScript 4 & Apple's resistance

Because I'm out of the loop with my head in a thesis, I was surprised to hear about the dropping of tail calls in the plans for ECMAScript 4. There's a bit of interesting discussion on tail calls on that thread before it wanders off into general pure/impure flames. One gem is a Google Docs spreadsheet which shows the ECMA industrial members' votes on various proposals, including Apple's bleeding-red No column. That reads to me as an uncharacteristic resistance to innovation from Apple.

September 12, 2008

Formlets; Idioms, arrows and monads

[UPDATE: The broken link to "The Essence of Form Abstraction" has been fixed. Sorry!]

For the first time in three years of research, I'm really proud of a paper that I worked on with my research group: The Essence of Form Abstraction, by Ezra Cooper, Sam Lindley, Philip Wadler and Jeremy Yallop, to be published in APLAS 2008. The paper shows how you can create compositional HTML forms which package up their data in any desired type. It shows an OCaml implementation but we also use the idea in our web-centric language, Links.

Though this is the first good group work that I've contributed to, the others have been doing some great work. In particular, Jeremy, Sam, and Phil did some nice work characterizing the expressive power of idioms, arrows, and monads. They first defined a metalanguage, like Moggi's monadic metalanguage, which can encompass all three notions, in The Arrow Calculus, by Sam Lindley, Philip Wadler and Jeremy Yallop (unarchived). Then they showed the hierarchy of the three, under which idioms are the loosest interface but therefore their language is the strictest to program with, and monads are the strictest interface, therefore their language is the most free, and arrows can be seen as lying in between. The work is described in Idioms are Oblivious, Arrows are Meticulous, Monads are Promiscuous (ibid.), MSFP 2008.

To summarize this, you can see the arrow calculus as a syntax like the do notation of Haskell:

do y <- f x
   z <- g y x
   return (h x y z)

Now to put the result crudely, monads allow expressions like the above, where the value bound at each step can be used in all future steps (this makes them "promiscuous"). The use of arrows restricts this so that the value bound at each step can be used only at the next step, as in:

do y <- f x
   z <- g y x
   return (j x z)  -- y cannot be used here

You can still use arrow operations to manually pass data forward through each step, but this is a nuisance. Hence Lindley, Wadler and Yallop coined the term "meticulous" to describe arrows.

The idiom laws restrict this further so that each value can be used only in a final return clause (the return clause is "oblivious"):

do y <- f x
   z <- k x        -- y cannot be used here
   return (h x y z)

An astute reader will note that return is not required in do syntax. What happens if there is no return clause? Then you can add one:

do y <- f x
   z <- k x
   q

is equivalent to

do y <- f x
   z <- k y x
   result <- q
   return result

But either way the idiom laws require that q cannot depend on y or z.

This shows that the three notions progressively restrict (and fairly naturally) the ways that you can program with them. But, in a familiar appearance of contravariance, the notions are reverse-ordered in how restrictive they are to create. An idiom, being the most restrictive on its user, is least restrictive to its writer. Thus you can model some computational notions as idioms which you could not model as monads. This fact came in handy in our latest paper, where we used idioms to model form abstraction.

I encourage you all to read about idioms, arrows and monads, as it's turning out to be a very nice theory.

April 24, 2008

null == undefined

(Salad with) Steve Jenson lays it down for you: the null vs. undefined nonsense in JavaScript. Better recognize.

April 14, 2008

Yhc : Haskell -> JavaScript

A note on compiling Haskell to JavaScript, and interfacing with the DOM, in Yhc.

September 18, 2007

Is too valid

Grrr:


And yet:

Is too valid. Check the spec, y'all. Cf. the grammar for "." In particular:

     ::= any one of the 128 ASCII characters, but not any
               or 
     ::= "<" | ">" | "(" | ")" | "[" | "]" | "\" | "."
              | "," | ";" | ":" | "@"  """ | the control
              characters (ASCII codes 0 through 31 inclusive and
              127)

August 5, 2007

Memoizing pages

Tim Bray, "On Being for the Web":

What do ETags do? They allow you, when you fetch a Web resource, to send a short string along with the request saying “this is the signature you sent me for the version I know about”; then the server can look and see if the signature is still good, and if so not bother sending the data redundantly. Which is potentially a big, big win.

But also potentially not. If you look at actual real-world servers that are maxed out, they’re mostly maxing out on computation or back-end database traffic, not on bandwidth to the Net. So the saving that would be really valuable would be if you didn’t have to rebuild the requested page. Unfortunately, both Rails and Django rebuild the requested page, then compute the signature, then check the ETag. Which is extra run-time work in order to conserve a resource (Web bandwidth) that probably isn’t the problem.

This is sharp. Maybe web frameworks (or <cough /> web-centric languages) should provide support for easy memoization.

June 18, 2007

Missing Features of HTML

I've just been looking at this position paper, "Declarative Models for Ubiquitous Web Applications" [1]; amongst other things, it makes some criticisms of HTML that are in line with my goals for the Links project:
  • A declarative expression language notation is not specified in (X)HTML. As a result developers have to code dynamic aspects of the user interface by means of server side scripts or Javascript DOM [DOM] manipulation.
  • (X)HTML classic forms [Forms] are severely limited in terms of typing information. For example, It cannot be specified that an input element accepts a date, a number or a patterned text. Furthermore, due to limitations in the submission formats, applications have to convert everytime, typically at server side, strings to the correct type expected by the application logic.
  • Lack of data binding mechanisms. Data binding is a technique that allows to associate data between the model and user interface components in a declarative way. Developers typically write server side scripts or Javascript AJAX-based code to populate user interface components with data. As a result, in (X)HTML-based user interfaces there is no clear separation between the model, the view and the controller.
It looks like the authors are concerned more with the phenomenon of web apps deployed on mobile devices and inside other web apps, rather than "ordinary" browser–server apps. Who knows what will come of it. [1] Fonseca, J. M. C., Prendes, I. M., Soriano, J., Hierro, J. J. Declarative Models for Ubiquitous Web Applications. April, 2007.

May 6, 2007

Time to market

The finance business is all about information handling; unlike most modern big businesses, they employ legions of developers to build applications in-house ... My messages: ... no matter how maniacally focused on performance you are, you can’t ignore the time-to-market advantages we’re seeing from modern Web frameworks; if my app gets to market before yours, it just might not end up mattering that yours runs faster on the same hardware.
—Tim Bray, ongoing

March 21, 2007

Published slides from Amazon talk 16 Mar 07

Herewith I'm making available the slides from the lunchtime talk I gave at Amazon's Edinburgh office last week (16 March 2007). Thanks again to Andrew Birkett for inviting me.

It might be hard to gather much information from these slides without the accompanying performance, but you might enjoy looking at the drawings or trying to run the code samples.

March 17, 2007

Links Talk at Amazon in Edinburgh

So yesterday I went down to Amazon's development office in Edinburgh, and gave a talk on Links, at the invitation of Andrew Birkett. The talk went well and I was quite pleased with the response and the sharp questions.

One of the biggest concerns that the Amazon people had, which we haven't tried to address in Links, is failure: how the language allows them to handle failure. In Amazon's systems, there are loads of interdependent services that depend on each other to display a single page, and any of them might go wrong; the developers described to me a wide variety of alternate responses that they might want to give, depending on the situations. For example, in some instances, a page feature might collapse down to nothing (disappearing from the page) when it fails. Other times, if a service doesn't respond, the front-end web software might use cached data to display a feature.

This came up in regard to Links because of the way we're making client-server (Ajax) calls simple RPC calls. The question there is, what happens if the remote call doesn't finish successfully, either because the server code couldn't get the right data, or because the network mechanisms themselves failed; how in Links can we handle that anomaly? Part of the answer might be an ordinary exception mechanism, which we can support fairly easily, but we should think more about how Links programmers deal with exceptional situations.

The crowd was very friendly and engaged with the talk quite deeply, I think. They fed me plenty of questions on particular points. Many of these had to do with various kinds of possible failure, as I mentioned; another theme was metaprogramming, prompted because they noticed a certain amount of repetition in my slides (e.g. (foo=foo, bar=bar) when constructing records; I do hope we can improve on that).

I gather they [present-day Amazon developers] do most of their work in Java, but they weren't thrown off when I started talking about continuations or any of the functional-programming idioms that we use in Links. There were a few self-confessed language afficionados in the crowd, but they weren't the only ones who didn't miss a beat at the functional idioms, the tuple types, or the unusual kinds of variable binding we use for our "formlets" (oh, reader—you don't know about our formlets—I'll have to post about that soon).

Between the talk itself and chatting with developers outside of it, I had a quite nice time. Thanks to Andrew and all of the others for listening so well & treating me nicely, even though I'm an academic!

UPDATE: Slides from the talk are available.

January 23, 2007

Programming Graphics and Getting Eyeballs

The language called "Processing" is a Java-like language, designed for coding up lovely interactive graphics. It compiles to Java and it's easy to deploy your apps on the web for people to enjoy them. Many of the demos on the site are mouth-wateringly impressive—check them out before you read on.

What the Processing people have done really well is to think about all the primitives that you'll want when coding up graphics demos—so they have good ways of playing with color, controlling the opacity of a shape, getting nice bezier curves, rotating and skewing, plus fairly good type-drawing and 3D operations. They've also thought through the programmer startup cost, making it easy to sit down and start using the thing without much knowledge.

The area where Processing is weaker is in the ergonomics of development. It uses an imperative style where you have to build up values and images in sequential steps. It is clumsy, for example, to create a list of dots and then render each one to the screen; clumsier still to express how they change or move over time, since you need to write out the frame-by-frame changes, rather than writing it as a function of time or a system of equations. Many facets of the API are controlled using peculiar beginFoo() and endFoo() calls, which affect how the statements in between behave. Heaven help you if you call beginCamera() and leave off the endCamera() call. These drawbacks make errors likely and have a cost in debugging time and code-reading time.

There is an alternative way to make such demos, in the name of "functional reactive animation" (FRP). In the FRP style, you write the behavior of each thing and each shape as a function expressing how it changes over time. You have at your disposal the raw parameters of time, and various input values, such as mouse position and key presses, so you can make the shapes react to these things.

I'll describe briefly what FRP programs look like (if you already know, skip the next few paragraphs). In the imperative style, you forcibly update persistent variables and so to understand the behavior you need to look at all the ways those variables can be updated over time, which can be quite complex. By contrast, in the FRP style, the behavior of an object is completely defined by an expression, so you can understand that behavior just by studying that expression—a more compact way of appreciating the behavior.

For example, to define a dot that moves at a constant rate in a circle around a point (centerX, centerY), I might write it something like this:

dotPosn = (centerX, centerY) + (radius * (sin time), radius * (cos time))

(I'm positing an operation of summing two vectors—a simple thing to define in many languages, though a bit cumbersome in Java.) The above defines the moving center of the dot I want to draw; drawing it at each animation frame would require just an expression as simple as this:

myDot = circle(dotPosn, 1, redColor)

That is, draw a circle centered at the value determined by dotPosn, with radius 1, in the color red (defined elsewhere). Objects can also be defined in a mutually-recursive way, so that their behaviors depend on one another.

So FRP is an appealing paradigm for writing interactive graphical demos. But none of the existing implementations are as appealing as Processing. The original implementation, Fran, is a closed-source Windows-only application (How's that for a conversation killer?) and is no longer being actively developed. The newer FrTime (part of DrScheme) is a much more serious contender, as it is open-source and runs on all the major platforms. Yampa is another, which I haven't had the chance to dip into.

These are good efforts; but there are still some pieces missing. Processing apps can be deployed on the web very easily—which makes the pay-off for writing them so much higher. Writing a graphics demo and showing it to your friends at your next pizza party might be fun. Writing a graphics demo and slapping it on the web is a whole lot more fun. See Linerider and the great popularity it has had over the last few months.

Another problem is that most FRP implementations are very conservative: they tend to offer the minimum set of tools that makes it theoretically possible to implement anything in the space. Processing takes a different approach: it tries to offer the minimal toolbox that you're likely to reach for in the course of making a demo. So FrTime gives you accum-e, which can probably be used to express any discrete time-changing behavior imaginable; but Processing gives you shininess (for setting a solid object's surface properties) and strokeCap (for adjusting the shape of the ends of lines).

A great Summer of Code project, or Master's project, would be to compile FRP code from one of the above languages down to the JVM, so you can deploy it over the web. Another one: take FrTime or Yampa and beef it up with all these nice graphics operations, to add the kind of vocabulary that graphic designers and animators like to use. The latter project would be straightforward from a CS point of view, but it would require attention to detail and a good sense of visual aesthetics. The former is more of a CS research project, and might require some clever thinking because of the apparent mismatch between functional-style code and the JVM's computational model. But there are plenty of other languages that compile to the JVM, so it's not beyond the pale.

If I were just starting now on my PhD, I'd find a way to include this in my work, or I'd put off the PhD until I could get this done! Tinkering with graphics demos and slapping them up on the web is the kind of hacking I'd really like to be doing. As it is, I'll have to leave it to some young whippersnapper, alas.

December 31, 2006

The Ebay Architecture

Here's a presentation on EBay's system architecture. Lots of wisdom and experience about building up a really large website is captured in documents like these. [via glinden]

September 25, 2006

Bloody Semicolons

Tim Bray, who is writing Ruby code for a comment-management system on his weblog:


The only downside is that I have to make a few adjustments to the current publishing engine, which is Perl, and to the client-side stuff, which is of course JavaScript. I keep putting : in front of constant strings. And forgetting parentheses. Especially empty parentheses. And semicolons. Especially semicolons. Bloody stupid useless semicolons.

Tim sounds like the ideal user for Links.

Oh, but Links has semicolons.

May 22, 2006

Web Continuations Considered Not So Harmful

Ian Griffiths mounts a useful attack on web continuations. He's thought this through, and I appreciate it. Critical thinking is a help to those of us working hard on research in the area.

Most of his objections don't hold for Links, though. Let me go through them one by one.

Abandoned Sessions

Griffiths says that code with web continuations will simply stop executing at some points, when the user walks away, and that will cause (a) debugging confusion and (b) problems with resource management. In Links, the latter is not a problem, since we store all the state of a continuation on the client.

The confusion that might result from having functions that just silently quit in the middle may indeed cause trouble. Griffiths offers that at least it'ss predictable where this will occur; but not necessarily. I may write a function one day that always completes, and I'd be happy with that. But then some function that I call may change so that it serves a page and doesn't return until the user does something. My own function will now have the same problem, and I may not understand why. This is an issue, but it may be possible to add some language feature that forces programmers to declare this kind or behavior, thus being aware of the problem and catching it at compile time.

Thread Affinity

I don't know what Thread Affinity is, but it sounds like a problem that crops up in Java specifically. I know there's a lot of voodoo around how to treat threads in Java.

In Links we haven't decided exactly how to present threads on the server, but we don't expect any voodoo. Links shoud be purely functional except with respect to IO (files and databases will be mutable, of course). As a result, the identity of the thread that runs a piece of code shouldn't matter.

Web Farms

Griffiths worries that web requests can generally come in to any machine in a farm, but the freezing of continuations might not be so fluid. In Links, they are fluid: continuations are serialized completely to the client, so when the request comes in to a farm, it doesn't matter what machine it's assigned to.

Back Button, Branching

The issue here is that user's behavior is not essentially linear, and thus a control construct that assumes a linear path for the user would be inappropriate. The particular problems are that: (a) a user can go back, causing code to be executed any number of times, and (b) a user can branch in multiple directions.

In Java, of course, this is a major worry, since Java code tends to be quite dependent on mutable objects. In that context, it could be really hard to figure out why x = 0; y = f(x); x = x + 5 ended up with, say, 15 in x. Links greatly mitigates this problem by encouraging a functional style, so that the only possible value for x after that sequence would be 5. Links libraries will be written in a pure-functional style, so you won't be required to run into the above problems just by using basic libraries.

On the other hand, he has a point: user behavior on the web is not fundamentally linear, so why do we propose a linear control construct? This is a very good question, and it's one that we don't have a great answer to, yet.

My own thinking is that a linear page flow is occassionally the right abstraction, and it would be very pleasant if we could give you a super-simple way to write such a page flow. You'll never have a page that has only one way out—you'll always have a Cancel button or a Help link or something, so we've got to figure out the right way to handle the edge cases. There's research to be done, for sure.

Summary

To summarize, Griffiths makes some good points about problems with web continuations in Java and in general. With Links, we're creating a new language, which we hope will prove that certain language features make these problems much much easier. The Java community won't be able to go right out and implement these features, but it might influence future decisions, and perhaps whatever comes after Java will learn from these problems and from our solutions.

May 3, 2006

Web Architecture

Yesterday I gave a presentation on web architecture to the people of LFCS at Edinburgh.

The slides are made with S5. S5 is just a set of stylesheets and scripts for making a slideshow in HTML, with navigation. The experience of working in S5 was pretty good (it was my first time), although I don't enjoy writing HTML. I'd like to have a simple Wiki-like syntax for making S5 decks: headings, bullet lists, blockquotes and images account for just about everything I want to do in a deck so it should be possible to make such a language. If only I knew someone who could write a parser. . .

May 1, 2006

Please refer to this Uri

A modest proposal: a future W3C or IETF conference should be held in the town of Uri, Sardegna.

March 22, 2006

Browser Internals

Rob Sayre: "I wonder why it's considered acceptable for Web engineers to be totally ignorant of browser internals."

Not that I'm doubting, Rob, but can you give an example of something you learned from those browser internals that changed your web development?

Update: Rob replied with some good teasers. Some interesting ones include: "I learned exactly how much each piece of Web content costs the client." and "[C]lient-side storage will bring the wonderful world of data migration and versioning to web pages." My interest is piqued.

March 8, 2006

ISBNdb Web API

ISBNdb.com (IMDb for books?) has a web API.

February 21, 2006

The Week in Web Languages

This was a hot week for web-language news.

Generators (yield and next statements) were implemented in FireFox's JavaScript a few days ago, in what looks like about two weeks of work by one guy. Cheers to Brendan Eich.

Tim Bray posted a round-up of arguments for and against PHP (mostly against). I was interested to read the Zend CEO's claim that half the websites of the world are powered by PHP. I'm disappointed that the Netcraft survey doesn't seem to be tracking that data.

Speaking as a language designer and as someone who briefly coded PHP for money, I'm pretty convinced that PHP is a bad language design. Yet, it's not entirely clear that language design matters.

Joe Armstong, the Erlang doyen, announced Jaws, a web framework for Erlang this week. It has some of the features of Links, such as easy calls from client to server. One difference I note right away is that finding a server method from the client is, in Jaws, a matter of tacking on the right string to a URL. Links treats the method definition, as a name binding, and calls from client to server have to be to bound names. Not that mis-typing the function name is a great source of error amongst web programmers!

Finally, a bit off-topic, Greg Linden of Findory writes about Blogger losing data and asking its users to cut-and-paste their entries from the web into their posting interface. The irony is astounding, of course. Greg thinks the problem is lax data-management at Google. They might be lax, but this tells me that they don't care much about the Blogger product. It's free, after all.

February 14, 2006

Idiots are a Lot Smarter

Simon Willison (et al.) took some nice notes on a talk by Josh Schachter, developer of del.icio.us. Speaking from my experience developing web applications at Amazon.com and Six Apart, I agree with every one of these points. A lot of these are easy no-brainers that lots of web apps don't get right—like dropping users back where they were after registering.

Some particularly nice tidbits:

Scaling: avoid early optimization. SQL doesn't map well to these problems—think about how to split up data over multiple machines. Understand indexing strategies, profile every SQL statement. Nagios or similar for monitoring.

There's no explanation what "these" problems are. Still, I think it's the right sentiment. The relational model is a weird model that was foisted on computing decades ago. It's become a crutch that developers—and particularly web developers—rely on excessively.

"Idiots are a lot smarter than you"—wait to see what breaks before you fix it.

There's little I hate more in engineering that attempts to fix unbroken stuff. Christopher Alexander's best line is, "Every act of building is an act of repair." We're here to make the world better, only.

January 19, 2006

Raw Data Lacking on the Web

Why isn't there more data on the web?

There seems to be a lot of news stories and opinion articles, but comparatively little data.

For example, I was just reading a piece asserting that book sales were up over the last decade, and provided a link. At the end of the link, I was hoping to find a nice graph showing this supposed spike in book sales. Instead, it was a USA Today article with a bunch of, you know, text. Why would I want to read a bunch of text with nothing more behind it than the editorial voice of USA Today?

Surely some reputable institute has counted the total number of books sold in each of the last ten years. Why isn't that study available for free on the web?

I'd expect to see the raw numbers, a graph displaying them, and ideally the full study which puts those numbers in context and describes the methods, etc. Sometimes you can get this kind of data; for example, in government studies like these power industry statistics. But most of the time, bloggers and others are pointing at news reports, which has at least two problems: first, it has too many layers of editorialism (adding the news editor and journalist besides just me, the blogger, and the original scholars), and second, it breaks down valuable raw data into a journalist's tag lines and pull quotes.

Why isn't more of this available?

One issue is probably that lots of data is owned; it's gathered at some cost and the institute wants to sell it to people who can get some business use out of it. I'd like to see more intellectual property owners open up the access to at least some of their property. I get a lot out of the New York Times online even as a non-subscriber, and I'm glad that they show as much as they do, though I wish there wer more.

Leaving that aside, another issue is that it's hard to search for raw data. It's easy to search the web for a topic, but hard to specify that you're interested in a certain level of detail. Words like "data," "table" and "figures" aren't likely to help. Perhaps a search engine could specialize in recognizing stuff that looks like tabular numerical data, and offer a way to say you want that kind of stuff.

January 11, 2006

Browsers are [not] quick; more on functional GUIs

UPDATE: This was complete rot. My test code was buggy, which caused the flicker. I patched it up and my draggable list moves smoothly now. Jeremy reports that he once tried an app that would re-create an entire (small) DOM tree on every keypress, and it worked reasonably fast. How do browsers manage to redraw pages as smoothly as they do?

An observation: web browsers move very fast when executing calls that modify the DOM.

For example, suppose list is a list of items, of which x is one, and you delete the item, then immediathttp://homepages.inf.ed.ac.uk/s0456219/ely insert it in the same place:

y = x.nextSibling;
list.removeChild(x);
list.insertBefore(y, x);

This will typically cause the whole list to be redrawn in the intermediate state, so the list gets shorter for a fraction of a second before the element is reinserted.

However, if you delete an element and reinsert it in a different place, the browser seems to redraw it smoothly, as if the element just moved:

y = x.previousSibling;
list.removeChild(x);
list.insertBefore(y, x);

That seems to be a difference of behavior, which I'm at a loss to explain.

In any event, this seems to rule out the "whole component replacement" that I talked about before, in implementing a purely-functional web GUI.

How to work around this difficulty? I still like the scoped, conditionalized structure that I outlined in that post. I suppose we could still have an inner function return a complete component, and have the runtime system compare it with the existing state of the component, executing a minimal series of DOM instructions to make the two agree.

Another approach, which I'm prefering, is to have the inner function return a "delta"—an expression representing how the component should change, something like a list of DOM instructions. I wouldn't want to allow the instructions in such an object to depend on one another, so I'd like to cook up a set of "deltas" which would be mutually independent, if possible. This would amount to a new mini-language for manipulating DOM trees, one that had no notion of sequential execution.

January 10, 2006

On Not Designing XML languages

Tim Bray discusses what he calls the "big five" XML languages and argues that whatever you're trying to do, you probably don't need to design a new one, particularly if your application falls anywhere near one of these. I'm inclined to agree.

Language design is hard work, and new languages almost never get any uptake (cf. Esperanto). The same seems to be true for spoken languages, programming languages, and data-description languages.

Tim says that "any non-trivial" XML language is going to have constraints that can't be checked with existing schema languages. That sounds like an interesting problem. Is there a list of such constraints somewhere?

January 5, 2006

Reference Draggable List

Worked up a reference implementation of a draggable list in the raw JavaScript today. This reminded me of the language hurdles to doing such a simple thing, and gives me something that's as close to the functional style as I can presently imagine. It does use global data and mutable locations a bunch, so it will be fun to tear it apart and give a truly functional way of writing it. In all, it's about a 100 lines, though it's not terribly flexible, so it will want some smithy.

December 22, 2005

Simplifying XML

Don't give up hope, Tim. A simplified/revised XML spec would make some of our lives much easier.

I'm working on a programming language for the web which integrates XML syntax into the language. This is dandy except that there are times when we need to look at the Doctype in order to be able to parse a program. In our language, for example, you can't use &nbsp; until you've indicated a Doctype of XHTML, and until our wee little parser has fetched and parsed that whole mess and made a big table of entities.

Also, DTD doesn't do much for us. The newer models for validating documents (e.g. Relax) fit better with the kind of validity that programming-language people are inclined to think about (namely, "regular trees").

We do integrate XML Namespaces, so having that pulled in probably wouldn't hurt, either.

December 16, 2005

What Web Apps Are

Let's all get on the same page about what makes up a web app. Here are some concepts and terms for talking about it. Users have a clear conceptual model of a web app; this model should be well-understood by web developers and tools should take it into account. The below is a first draft and probably will need revision—I'm interested in feedback from active web app developers. Is this accurate from your point of view? Any nuances of the web it doesn't take into account?

What Web Apps Are

Every web app has a model, which is some body of information that the user wants to interact with (view and alter). To the user, the app offers a particular experience of interaction with the model.

The fundamental experiential units of the web are requests. This unit issues from the infrastructure of HTTP. A "request," for present purposes, is a round-trip exchange of data with the server which results in the browser (a) adding a new item to its history and (b) completely redrawing the page contained in the response. It is possible to redraw the page without such a request, and it is possible to get data from the server without redrawing the page, but it is not possible to add an item to the browser's history without a request.

Different application designs (in particular, ways of breaking down into requests) may offer different experiences over a model.

From an application designer’s point of view, a web experience is composed of two distinct kinds of requests, actions and views.

An action transforms the app's model and redirects the user to a view; an action should not display a page by itself (see below for an exception).

A view should not modify the model, but it does display a page to the user. This separation guarantees an important user expectation: that hitting “reload” will merely refresh the information I’m looking at; it never has consequences beyond my browser.

An action may display a page directly, if something has gone wrong in performing the action. In this case, hitting “Reload” has a clear meaning to the user: it means that the app should “retry” the action that failed. If an action succeeds, however it should redirect to a view, rather than display a page directly. Otherwise reloading the page will retry an already-performed action, when the user would expect it merely to refresh the displayed information.

What the designer or the user thinks of as an (informal) “action” may in fact display several pages to the user, accumulating local state over the course of that interaction, and modifying the model only at the end of the series of requests. For example, an “action” that deletes some object from the model may first confirm that the user really wants to do so, or a flight-booking app may have several pages of questions to collect before recording the ticket as booked. Call this series of requests a pipeline rather than an action; the intermediate pages are merely views in our terminology, and the final request is the only action. These intermediate views may need to store intermediate state information; but this state is ancillary to the model.

Sticking to this discipline (which, broadly speaking, good web apps already do) ensures that the browser's history accumulates a list of things the user saw, and not a list of actions taken. It is impossible to take unintended action by using the browser's history.

December 14, 2005

Del.icio.us Technology Revealed

del.icio.us uses HTML::Mason, the Perl web framework. I got a Mason error message today when the database was unreachable.

November 11, 2005

Functional Reactive Web GUIs

Here's a bit of syntax for doing a kind of "functional reactive web programming." This example aims to implement the draggable list problem.

fun dragList(origWidget) : mouseIsDown => DOM -> DOM {
    draggingElement = findHitElement(mousePos);
    fun updateIndicator(widget) : mouseMoved => DOM -> DOM {
        reorderNodes origWidget mousePos.y;
    }
    finally {
        # updates the widget once the behavior's condition 
        # finally becomes false
        reorderNodes origWidget draggingElement mousePos.y
    }
}

This defines a "behavior" called dragList which could be applied to a node in a DOM tree. The dragList widget has a type mouseIsDown => DOM -> DOM. Here the small arrow -> denotes an ordinary function type (arg on the left, result on the right). What comes before the big arrow (=>) denotes a condition. This is something which must be true for the runtime system to invoke this function. So the type mouseIsDown => DOM -> DOM says, "if the mouse is down, you can call this function with a DOM tree and expect another DOM tree." The runtime system will repeatedly pass the current DOM of the relevant widget and replace it with the result of the function.

You might apply the behavior to an HTML element something like this:

<ul l:behavior=dragList>
  <li>Yorick</li>
  <li>Horatio</li>
  <li>Rosencrantz</li>
  <li>Guildenstern</li>
</ul>

The same behavior can be attached to many page components this way. Conceivably, more than one component's behavior could be active at a given time. But within a behavior, internal functions should be serialized. In this system, a behavior can only destructively affect the component on which it is invoked—it follows from this that concurrent behaviors on distinct components cannot interfere. It remains to be seen whether every desirable GUI experience can be implemented this way.

Now, diving into the body of the dragList behavior:

    draggingElement = findHitElement(mouseDownPos);

The dragList behavior begins by letting draggingElement refer to the element where the mouse is originally clicked; we'll use it later.

Next dragList gives an internal function which has its own condition; as long as the outer block is active, the inner block stands to be called.

    fun updateIndicator(widget) : mouseMoved => DOM -> DOM {
        reorderNodes origWidget draggingElement mousePos.y
    }

The inner function's condition only applies while the outer function's condition is true. So what this block expresses is that, while the outer condition is true, whenever the mouse moves, the runtime system should call updateIndicator. In order to implement the nested conditions, the compiler will write code to register and unregister the inner function with the appropriate event handlers whenever the outer function's condition is satisfied/falsified.

Finally, the use of the inner function, like that of the outer function, is to update the component. The runtimes system passes the current DOM for the component and replaces it with whatever the function returns. In this way, we model changes over time without destructive operations.

Now to progress to the next level of sophistication, we can observe that the type annotations are unneccessary and the compiler should be able to derive both the argument types and also the conditions under which the function needs to be called. This works because there are special thunks which refer to environmental variables that can change. Omitting the type annotations from the original figure, we get:

fun dragList(origWidget) {
    draggingElement = findHitElement(mouseDownPos);
    if (not(childOf(origWidget, draggingElement)))
        return origWidget 
    fun updateIndicator(widget) {
        reorderNodes origWidget draggingElement mousePos.y
    }
    finally {
        # updates the widget once the behavior's condition 
        # finally becomes false
        reorderNodes origWidget draggingElement mousePos.y
    }
}

the compiler could still determine, making use of referential transparency, that updateIndicator will not return a distinct result unless the value of mousePos has recently changed. Thus it can infer the condition type of mouseMoved and behave as before, registering the function with the mouseMoved event at the javascript level. Similarly, the outer function, dragList, should be invoked whenever the mouseDownPos special thunk has changed its value. In fact, the value returned will not change as long as draggingElement is a null value—that is, as long as mouseDownPos lies outside the elements within this widget, and findHitElement returns some node which is not a part of this widget. (In fact this explicit test is ugly, and in a moment I'll look at ways of eliminating it.)

This can be seen as a declarative approach to web GUIs, because each function, inner or outer, is essentially just "giving the value" of the widget as a function of some environmental conditions. Besides the mouse button and position, other environmental variables could be used (keys down, wall-clock time, a changing signal from the server, etc.). These "special thunks" are analogous to what Hudak and Elliott call "signals" in the area of Functional Reactive Animation [1].

Now ideally, the compiler should determine when two inner functions of one behavior would compete—when their conditions overlap; then there would be a race to update the component, possibly with different values. This is a mistake and the programmer should be prompted to change the code so that only one value of the widget is implied by any given set of environmental changes. Perhaps this derivation could be by means of a condition type on the special thunks, and a typing rule which bubbles these conditions up to any containing expressions.

Lexical scoping is an important factor here, which needs to be pinned down. In this case the inner function was a function of origWidget, that is, the original structure of the component—rather than its own paramter, widget, which would give the current structure of the widget at the time of invocation. This is just a design choice for the behavior-designer; under other circumstances it may be more natural to use the current widget instead. Of course, the runtime system should take care not to destroy the lexically-scoped origWidgetvalue while this behavior is active.

A lot needs to be pinned down. The condition types have been presented a bit too breezily. After all, mouseIsDown has a clear truth value at any moment; but mouseMoved describes an instantaneous change in a sort of continuous variable. Some care should be taken in defining these conditions. The question of how to handle an instantaneously-changing variable and its downstream effects has been looked at in functional reactive programming.

Also, a bit more expressivity would be useful. Above, we would prefer to describe the condition of the dragList function more finely as: "mouse is down and its original hit point is within me." This calls for some way to parameterize the condition type, e.g. "mouseIsDown && firstHit(insideMe)." It's not obvious that all the natural conditions and parameters will be easily and soundly expressible.

Finally, in talking to Phil about some of these ideas, he suggested that rather than operate on successive values for the view of the widget, the behavior functions should instead operate on a model of the widget; another set of viewing functions should be automatically invoked to transform a model into its realization in DOM form. I think this is a good idea and I need to explore this further.

[1] Elliott, C. and Hudak, P. 1997. Functional reactive animation. In Proceedings of the Second ACM SIGPLAN international Conference on Functional Programming (Amsterdam, The Netherlands, June 09 - 11, 1997). A. M. Berman, Ed. ICFP '97. ACM Press, New York, NY, 263-273.

November 7, 2005

On Loosely-Joining Small Pieces

Some notes from Adam Bosworth, VP of Engineering at Google, in ACM Queue. The key points, I think, are:

  1. Extensible, sloppy data formats are good, and
  2. Loose coupling is good for protocols: use indirection, set clear and simple interfaces, and don't rely on server state when possible.
  3. XML and RDBMSes don't support the above very well.

Good quotes:

  • "Elements in XML with values that are unlikely to change for some known period of time (or where it is acceptable that they are stale for that period of time, such as the title of a book) should be marked to say this. XML has no such model.
  • "We shouldn’t over-invest in making schemas universally understood."

And, corroborating my "anti-database" manifesto:

  • "Today databases violate essentially every lesson we have learned from the Web."

October 31, 2005

Why We Need a Web Control Stack

Web applications almost universally have a notion of "authenticated user" which flavors the pages they serve up. Typically the logic to support this notion is built into frameworks, so that programmers don't have to deal with it on an action-by-action basis; they can just mark which actions are required to be authenticated, and presume that the user is authenticated and her credentials are handy when the handler is running.

There are at least two decent ways of writing the standard authentication check. One is to handle failure explicitly:

fun my_handler() {
    user = validate_user();
    if (!user) {
        return login_page(retun => my_handler);
    }
    # from here on down we assume that "user" holds a valid user object
    if (!can_do(user, foo)) {       # can user perform the current action?
        return "You can't do this!"
    }
    do_foo(...);
}

But the intention is, you'd like to say "Show the user a login page and come back here when it's done." In the code aboev, you have to spell out where "here" is.

Ideally the programming system should know where to come back to. Here is a more attractive syntax:

fun my_handler() {
    user = validate_user();
    # from here on down we assume that "user" holds a valid user object
    if (!can_do(user, foo)) {       # can user perform the current action?
        return "You can't do this!"
    }
    do_foo(...);
}

To sketch an implementation, suppose that the validate_user routine has a way of returning a page to the browser, and embedding a token in that page which knows how to come back to the calling routine, preserving its context (call stack, lexical variables, etc.). Call this feature a "web stack": a call stack which is representable in a web page.

The first approach has the limitation that "my_handler" must be a top-level function and, in traditional web languages, you need to provide a table showing how to dispatch from the string "my_handler" to the function my_handler. Some languages/frameworks will automatically create a dispatch table that gives an external name to every top-level function, but this presents a security question, since you're implicitly exposing all functions to the network, leaving the programmer to remember to close them up. One way to patch that difficulty is to support decorators, which can be used to register a function with a dispatch table; this makes it easy to check which functions are externally-callable.

Still, these approaches require the programmer to be explict about what "here" is when telling a subroutine "come back here." Links should support the second approach.

With the "web stack" example, there is still some risk of inadvertently exposing a program point that can be invoked from the network. As a bulwark against that, one can imagine statically checking and tainting such "holes." The programmer could then be required to declare that a function may open up an entry point, and any routines which call such a routine would also be tainted—forcing the programmer to acknowledge the "hole."

October 27, 2005

The Utility of PUT

Mark Nottingham muses about why PUT isn't used much on the web:
When you move beyond using HTTP for just storing and viewing documents, it requires a lot of co-ordination regarding URIs. Just as two-phase commit isn’t such a hot idea in Internet-scale transactions, where you cross administrative boundaries and are exposing non-trival resources to the whim of others, giving clients control of the URI space is a commitment that, to date, few servers have been willing to make.
Why Just GET and POST?

October 24, 2005

My Research

Before getting too much into the thick of things, I should should say who I am and what I'm doing.

I'm working on a doctoral project to help make a new language for web development at the University of Edinburgh. The thrust of the project is to combine best practices from a number of domains and present them in one coherent language—essentially, we want to mitigate the so-called "impedance mismatch" between different technologies that make up a given web system.

For example, web applications typically are backed by a database, but the database comes with its own language, SQL, for extracting data; one typically has to write a lot of glue code to repackage the data that comes from the DBMS for use within the main language that the system is coded in. Then, in order to create a rich user experience, you typically have to code in JavaScript, and again you have to repackage your data to make it work with JavaScript & the DOM. All these multiple representations for the same data wastes a lot of web developers' time. We hope to bring all these technologies in under one linguistic umbrella, and provide a more convenient way to express a complete web system.

Along the way, we might come up with some ideas and approaches that are useful in other contexts. So if these issues are interesting to you, even if you don't expect to adopt a new programming language anytime soon, I hope you'll subscribe and follow along.

The Draggable List: a Benchmark Widget for Web Languages

Here's a nicely-defined problem that comes up repeatedly in web development, and serves as a simple example of some of the problems that come up in programming client-side web applications. We can measure web languages by how well they can express a solution to this.

The goal is to create a "draggable list." Here the user is shown a list of things—for example, to-do items—and has the opportunity to re-arrange them by dragging & dropping. While the user is dragging, the UI must indicate where the dragged item would be placed if the user let up the mouse at that moment. When the user lets go of the mouse button, the list should, of course, be permanently reordered on the page; afterwards the user can do more drag actions, or not.

The behavior should be abstracted from the concrete HTML/CSS representation so that the behavior is reusable with respect to a wide variety of visual treatments.

A side condition is that it should be easy to get the reordered list data *itself*, not by scraping the DOM tree. In this case it's easy, but the approach ought to extend directly to more complex widgets with more complex models.

How to visually indicate where the item would be dropped should be up to the coder. It's worth noting that there are generally two good ways of doing it. One way is to leave all the existing items in place but to display a solid line between the two elements where this one would be inserted. Only after the user lets go are any of the other elements moved on the screen. The other approach is to move around a representation of the dragged element—in this case, the other elements are displaced while you drag. This approach is taken in the best-known ready-made example of the Draggable List (if anyway knows of other good examples, please let me know).

Looking at the source of that implementation, JavaScript performs poorly on the Draggable List benchmark problem. Any other contenders?

UPDATE: Another implementation, very appealing to the user. But, appealing to the programmer?