« October 2005 | Main | December 2005 »
Implemented a rudimentary version of the handle/with construction in Links. Now you can write, e.g.:
handle
<foobar> {string_of_cont(handler)} </foobar>
with
result -> "You gave me " ++ result ++ ", fool!"
The result of this construct is something like
<foobar> (some base64 stuff) </foobar>
and the base64 stuff is a continuation which wraps its argument in "You gave me ..., fool!" This is not quite what I want but it's a start.
Today, I got mutually-recursive functions working at the toplevel in the Links interpreter. I also modified the way pickling is done to make sure that we never try to pickle a first-class OCaml function. Gilles did a weird thing of putting the functions that implement Links primitives. This makes them hard to pickle. I pulled them out of the environment, but we still have the problem that partial applications of primitives won't pickle right: it loses the args and forgets how many have been applied. That should be straightforward to fix, although it requires changing every primitive in the book.
I also want to start creating end-to-end tests that check that our web interface is working OK. There's a lot of untestable stuff there right now, which makes me nervous. I'm looking into using perl's WWW::Mechanize for this.
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.
Why do ML and Haskell insist on having a different syntax when evaluating a file versus interactive mode?
Why can't I simply copy and paste between my program's source and the interactive window? Are they trying to hinder my exploration?
Designers of interpreted languages, take note. Learn from Scheme, Perl, Python, Ruby. . .
To do today:
I've been exploring the idea of a "continuation" as the handler for an http request; to that end I have the Links interpreter working with serializable first class continuations, and an escape construct for creating them. The code is finally in a stable state.
Having created one of these things, which effectively represents a control stack, the programmer can embed such an object in a web form, and posting the form passes the "value" of the form to that continuation.
In trying to program for it, I became convinced that using the escape construct is very confusing. I think my handle ... with ..., or something like it, would be much more natural. There are still some questions in my mind about that, as it still requires some notion of explicit continuation values, which I'd like to expunge. More on that later.
As an alternative, the Links programmer can specify an expression to be evaluated when the form is posted (as always). I call this feature the l:expression feature and the other one the l:handler feature. The difference is fairly subtle and I'm not yet sure how to explain the two; in fact each is as powerful as the other, but they have a difference of intention. With l:expression, the coder is saying, "this expression represents the next page the user will see," whereas with l:handler it's more like, "this handler will process the form and do more stuff, possibly showing many more pages, before dropping the user in a 'neutral' place." The l:handler mode is more natural if you want to handle the form and then return to some dynamic context, for example if you want to display a page that acts like a subroutine, returning to whatever user experience it was invoked from.
It will require a lot more playing around to figure out good ways to present these and a real account of the pros and cons. Ping me if you're interested.
Gripes with OCaml:
let is stranger word than fun (as in SML) for declaring functionsSOURCES; "X and Y have inconsistent assumptions"o (as in SML) or . (as in Haskell)before form as in SML (very useful when debugging, checking return values)Foo of {field : string}).Syntax error)open FooModule is never enough) and they have different conventions: for example, some begin with # and require an exact filename. I never know what file needs to be #loaded.Str.quote needlessly returns a string instead of a regexp, requiring me to then call Str.regexp whenever I use it.Str.string_match needlessly requires an integer argument designating the index at which I'd like to start matching. This should, of course, be an optional argument or a distinct form of the function (Perl seems to have Map module for finite maps provides a map function for transforming the domain of the map, but doesn't provide a way to transform the keys.Some notes from Adam Bosworth, VP of Engineering at Google, in ACM Queue. The key points, I think, are:
Good quotes:
And, corroborating my "anti-database" manifesto:
It is common wisdom in web-programming circles that a web application must be backed by a database. Sometimes the application fundamentally relies on a database per se: for example, flight-booking web sites are interfacing with a database of flight data that's useful as a database even outside of the web context.
Other times an RDBMS is employed simply as a no-think, heavyweight solution to the myriad problems that come up in engineering for the web.
For example, the tricky problem of sharing data between concurrent web requests—call this one the "sharing" problem—is often handled by creating short-lived rows in a database table. To see why this is heavyweight, consider this: It may be that at any given time only two processes need to exchange a particular piece of data, and only fleetingly, but the RDBMS insists on writing it to disk and indexing it into a table to asure full ACID properties.
For another: some data is generated on one web request and is needed by a subsequent request from the same client. Since the client can connect to any one of many identical web servers, and since even the same server could be stopped and started between requests, it would be no good to store this data in local memory. Call this the "persistence" problem in web engineering. Conventionally, web programmers just keep a table for such data, indexed, for example, by a user's session key.
In both of these cases, an RDBMS is a heavyweight solution. A few of the costs incurred by using an RDBMS include:
Oftentimes, you see, the data that needs to be stored is not fundamentally relational; more often its character is like that of some other data structure that one uses in programming: a list, a tree, a polymorphic record, a graph.
Really big web operations (e.g. Amazon, Google, LiveJournal) always end up building a lighter-weight system to provide persistence and sharing. The engineers of these systems all discovered, upon reaching a certain scale, that the conventional RDBMS leads to problems with slowness & contention, not to mention the impediments of converting data to a relational form. At the same time, the strong guarantees of an RDBMS are often unneccessary.
Amazon has built a middle-ware infrastructure for communications & caching, and for its massive catalog data uses lightweight, read-only B-Trees. Google is building a huge, fast, highly-distributed map service. LiveJournal has built a distributed lightweight cache. Yahoo! Stores, to judge by Paul Graham's quote, never used an RDBMS in the first place. The fact that so many of the biggest systems on the web are building alternatives is strong evidence that alternatives are needed.
My proposal: a good web language ought to support easy, flexible sharing and easy, flexible persistence of that language's own data objects, without forcing a conversion to a different form.
What database did you use?
We didn't use one. We just stored everything in files. The Unix file system is pretty good at not losing your data, especially if you put the files on a Netapp.
It is a common mistake to think of Web-based apps as interfaces to databases. Desktop apps aren't just interfaces to databases; why should Web-based apps be any different? The hard part is not where you store the data, but what the software does.
—Viaweb FAQ, Paul Graham
Notes from today's Links Research Group meeting:
Places to store data:
Parameters/issues around these storage types:
The idea was raised by Jeremy of offering different "views" to the same data, particularly data in the database. Ezra noted that this is true to common practice, where oftentimes an Obejct-Relational mapping is used to provide a layer of data abstraction above the database. Phil noted his work on alternate "views" of data structures in a functional language, supported by conversion functions that convert between representations.
Reasons for encryption:
Rodney mentioned that database systems already have the notion of separate read/write authorization for fields; could a similar policy could be used to prevent different pieces code from modifying given pieces of data, even if some code is on the client and some on the server?
My copy of the Links interpreter is now capable of serializing a control stack along the lines of what I called for on Monday.
I have a working demo of a login routine. You can call this routine and it will:
This way, various callers can invoke the login routine and it will keep track of the context where it was called—you don't have to tell it explicitly.
In working with this I've become aware of just how confusing it is to work with explicit first-class continuations. I'll be working on offering a better syntax for that.
To get precisely the feature outlined in Monday's post, I need a way to get and set the cookies—but I'm going to defer that as I think the syntax issue is more interesting.
In a language for the web, one ought to be able to serialize data at will, it ought to be easy to do so, and one ought to be able to write various serializers that have different properties of speed and compactness. In typical statically-typed languages, doing this is rather involved, whereas it's quite easy and commonplace in dynamically-typed languages.
To that end, a HOT language should provide primitives which will accept a value of any type, and return information such as:
If the type system is preventing us from doing something which is perfectly safe, sane and desirable, then the type system should be changed.
I have some ideas how to type operations like the above; I'll work it out and get back to you.