" /> Ezra's Research: October 2005 Archives

« September 2005 | Main | November 2005 »

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!"

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!"

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."

Links App Work

I'm working on a demo app in Links, our language for web development. It's stimulating me to see lots of things wrong with the language and the implementation, and things that need to be done to make it work really well. I'll note some here; we need:

  • a way to perform redirections. We should, of course, allow redirections to go to Links "continuations" but also to arbitrary URLs. I've got an inkling that the type of continuations should be precisely the same as the type of URLs, or that there should be an easy conversion.
  • a way to load code from other files. I'm already copying and pasting code between different files.
  • call a subroutine which never returns to the caller, but which knows who the caller is & can return on some later request.
  • more helpful error messages
  • error messages that tell you what line the problem occured in
  • a way to freeze an expression so that it will be evaluated when a link is clicked

The above things are fairly desparate; without them we can't prove that Links is good for the web. Lower-priority needs:

  • Ability to interpolate code in {...} with regular old "strings" (why should XML quasiquotes be special?)
  • Ability to send error messages to the browser (exceptions rule)

(Links team at Edinburgh: try this)

October 28, 2005

GHC & Extensible Records

From the GHC FAQ:

Does GHC implement any kind of extensible records?

No, extensible records are not implemented in GHC. Hugs implements TRex, one extensible record variant. The problem is that the record design space is large, and seems to lack local optima. And all reasonable variants break backward compatibility. As a result, nothing much happens.

I have a hunch that extensible records are going to be a condition of bringing functional programming to the masses. I need to learn why they are hard.

October 27, 2005

Web Architecture

While I'm thinking about web architecture, I might as well link to some classics, for my programming-languages friends who are less familiar with the web as a system.

The web is made up of URIs, servers, clients, intermediaries, media types, entities, auto-negotiation, messages, fragments, request methods, and a bunch of other things. Lots of systems are designed on top of the web in complete ignorance of the features and constraints given by the web as an infrastructure.

These documents discuss the details of this architecture and how applications should harness them:

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?

The Annotations Problem

Here is a problem that occurs in statically-typed functional languages, which doesn't come up in dynamic languages (the tradeoff, of course, is static safety). I'll state the problem and give a partial solution, but I'm interested in other approaches.

Frequently we're faced with a complex recursive data structure, which ought to have a rigid type. For example, here is a tree structure that you might define in ML:

type 'a tree = [`Leaf of 'a | `Unary of 'a tree 
                | `Binary of 'a tree * 'a tree]

This forces us to give the right number of sub-trees when constructing a binary node, a unary node, or a leaf. It is good that the type system enforces this.

The problem occurs when we have some functions that wish to add information to this tree, perhaps in a sloppier way. For example, a function that assigns a unique number to each node of a tree, in preparation for some other algorithm that will consume these numbers. It's hard to write such a function in ML: we can either construct a new, parallel, data structure, which has fudged constructor names, such as:

type 'a ntree  = int * [`Leaf of 'a | `Unary of 'a ntree 
                | `Binary of 'a ntree * 'a ntree]

O'Caml's polymorphic variants allow us to re-use the same constructor names, but we still have to define a new type in order to add the annotations.

The problem becomes worse if my program uses a second kind of annotation—for example, a function may take a raw tree and assign type information to it. Now we need four ntree types, since each kind of annotation might be present or not. And we need hideous functions that convert between these functions, throwing away and restoring data just so that you can pass the trees from one utility function to another, depending on which annotations are expected by each one.

This is a place where dynamic languages win big. In Perl and Ruby, for example, almost any value is in fact a dictionary, and so it can be extended with arbitrary annotations at will. Of course, in these languages, there is no way to ensure (statically) that a function receives the structure with the annotations that it expects.

The "Annotations Problem," then, is to give an elegant way of constructing a recursive type which (implicitly) allows arbitrary annotations at every node of its recursive self.

This should be doable with known technology. In a language like OCaml but with extensible record types, you could define the type as follows:

type 'content 'annot atree =
    'annot * 
      [ `Leaf 'content
      | `Unary of 'content 'annot atree 
      | `Binary of 'content 'annot atree * 'content 'annot atree]

The 'annot type parameter can be used to supply the type of annotations that you are interested in. You can do this today in O'Caml; to solve the problem, though, you need to instantiate'annot as an extensible record type. Then, any given function will use only certain labels in the record. If I have a richer annotated-tree, I can easily pass it into a utility function that needs only a subset of my annotations (maybe none of them). At the same time, if my function uses a label foo from the annotation the type system will ensure that any tree given to the function has a label foo on every node—which is generally the guarantee that I want.

I'm not sure whether any current language supports polymorphic variants, extensible records, and recursive types, which allows this solution. Even then, the solution is a bit cumbersome, because a function which cares not about the annotations still needs to mention the annotations in its pattern matching, and on its result constructions, in order to ensure that the annotations are preserved (what to do if a function changes the structure of the tree is out of scope!). A further, and more serious problem, is that any type needs to be declared in this special way in order to admit annotations: if I want to annotate a library-provided structure, I need to ask the library author to rebuild with this in mind, and that will break all other consumers.

Is it sensible to speak of annotations always being available for any recursive data structure? It exists in dynamically-typed languages.

The statement of the problem calls for elegance. My solution would be an improvement, but it's not perfect. More elegant solutions are welcome.

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?

October 23, 2005

Ruby DSLs & Juggling

Here's an interesting set of slides on using Ruby syntax to define DSLs within Ruby.

I was pleasantly surprised at the language for defining juggling patterns.


"He [Larry Wall] won the International Obfuscated C Code Contest twice..." (State of the Onion)

Ah. Suddenly it's all clear to me.

October 11, 2005

Setting Up CVS

No, Tim, setting up a CVS repo is astonishingly obfuscated and nowhere explained. Since I did it recently, I'll recount the steps.

Each time I go to set one up, it takes me half an hour just to remember how to do it the easy way. That's when the repo will be local or network-mounted. The answer is very simple:

$ mkdir /path/to/the/repo             # (if you need to)  
$ cd /where/the/code/is/now  
$ cvs -d/path/to/the/repo import module-name VENDOR INITIAL  
... chugs away ...  
$ cd ..     # because the next command will create a dir called module-name  
$ cvs -d/path/to/the/repo checkout module-name

What you use for VENDOR and INITIAL is unimportant. You'll be stuck doing cvs checkout module-name for a long time, though, so choose module-name carefully.

If you forget the three parameters to import, just doing cvs import will remind you.

If you want to use the :pserver method, I think that's relatively easy, as it just does ssh to the given box and tunnels all the traffic over that. I haven't done this recently, so I won't give a recipe. If you want to use the cvsd method, it's much more involved—you have download and run the cvsd server; I did it once and it wasn't worth it.

October 10, 2005

Recursive Types in Ocaml

Why can I not have a type like this in OCaml?

type t = string * (Left of t | Right of t)

Is there a type-theoretic reason for it?

Continuation Typing Questions

What should be the type of a continuation object, if we know only that that continuation object will be used somehow within an HTML page?

There are various ways in which a continuation may be placed in a page, to create different kinds of web interactions. Is it possible to infer something from the HTML structure about how the continuation is used? Our current l:action syntax gives one constrained way in which the continuation can be used, and in that one case we can scan out the form fields that will feed to that continuation.

If we allow continuations to be used in unlimited ways, can we still type the continuations?

October 9, 2005

Links on MacOS X

UPDATE: This post originally refered to the version of Links that was current at the time. Updates made Jan 31, 2007 are in parens.

I got Links running on MacOS X today. Here are some things you have to do:

  • Install PostgreSQL from source. To do this, download the source and follow the instructions, but after ./configure and before make, you (no longer) have to:
    • undefine HAVE_POLL in src/include/pg_config.h (change the relevant line to #undef HAVE_POLL )
  • Install postgresql-ocaml (latest version in Markus Mottl's directory). Note that you don't want the postgresql-ocaml library that comes up first in the Google search; that's an older version. You want Markus Mottl's version.

    In one case, I had to modify OCamlMakefile to set INCDIRS and LIBDIRS to point to /usr/local/pgsql/include and /usr/local/pgsql/lib, respectively.

  • (No longer required.) Install pcre (get it via FTP). To do this, follow the instructions, but after ./configure and before make, go into the file libtool and change the line
    allow_undefined_flag="-flat_namespace -undefined warning"
    (it appears twice in the file)
  • (No longer required.) Install pcre-ocaml (latest version found in this directory)
  • >(No longer required.) Install findlib (ocamlfind)
  • (No longer required.) Install equeue
  • Install ocamlnet
  • (No longer relevant) Don't install curl (ocurl). At least, I couldn't get it to install—I got some kind of mismatch between it and the libcurl headers that were installed on my MacOS 10.3 system. Instead, I redefined the grab_url function in sl_import.ml so that it wouldn't use curl for now.

October 7, 2005

Representable Continuations

(Remind me to explain this more clearly at some point). Why representable continuations are important for Links:
fun do_something()
  creds = validate_user();     # if the user isn't signed in, throw a login page, continue from here when finished
                                              # if user never validates, this never returns
  if (user_can_do_something(creds) then
  else display_error()

fun validate_user()
    user_cookie = get_cookie('user')
    (username, password) = regex.match("(.*):(.*)", user_cookie);
    if not valid_creds(username, password) then
        (username, password)

fun login_screen(handler) {
This can't be done if the l:action must always be a complete expression. "validate_user" needs to be like a subroutine that can be invoked from anywhere, even though it has its own handler (its own l:action). That means the serialized form action must include the complete continuation, not just an expression.

More on the "handle ... with ..." construct

Phil pointed out that this syntax doesn't do much different from what Links already does, where you can just embed a function call, using form fields as free variables.

I realized after talking to him that there's one thing this might allow, which is the treatment of multiple submit buttons in one form. Let's try an example where the search box has a "Search Species" button, to search some database of animal species, and a "Help" button to search a certain help database instead.

fun search_feature() {
       <form action="{handler}">
       <input name="search_term" />
       <input type="submit" name="submit" value="Search Species" />
       <input type="submit" name="submit" value="Help" />
      {submit="Search Species",search_term=term} -> species_search(term)
    | {submit="Help",search_term=term} -> search_help(term)

Here we're matching on specific values for the submit argument and both cases are binding the value of search_term to a variable.

With the other syntax, you could do this, but you'd have to write a glue function which does the pattern matching and dispatches to the right handler function. So, call it sugar, but call it nice sugar. . .

October 5, 2005

Representing continuations

Yesterday Jeremy Y. and I discussed the representation of continuations. We have a method in mind for doing it without actually embedding code in the continuations, but we could see a way out of passing environments around.

Naively, continuations do contain delayed expressions to be evaluated later on; for example if you apply a function, which is the result of an expression, to an complex expression argument, we need to delay the argument (on the continuation stack) while we evaluate the function. This is particularly comes up when you have curried functions, which is how Links' primitive functions are applied. So just evaluating 1 + (2 + 3) requires us to delay the evaluation of (2+3) while we find out what is + applied to 1. Perhaps some optimizations could be done which eliminate the problem in a lot of cases, but the problem still exists.

Our method for banishing the code is like defunctionalization, but I'm not sure whether it should be considered the same thing. Our idea is to take the tree (perhaps forest) which represents the program and assign an identifier to each node. One problem is in assigning those identifiers in a stable way, so that if I change an unrelated part of the program, the identifiers for the unchanged part remain the same; that should not be hard, just using good hash functions.

Constructs for Composable Web Page Features

I've been thinking about how to get an appealing syntax for using continuations in the web environment.

Here is my guiding priniciple:

Page features should be composable: I should be able to take a feature that you've designed, along with your feature's control threads, and embed it in my page, even though my page has other features with other control threads.

This accords well with real web practice; for example it is common place to see an app having multiple screens, where each screen is designed independently, but a certain module is used on each one—for example, a search box which is available across the app. So, the goal is not merely to allow multiple buttons on one page but also to allow features to be designed separately and brought together in a modular fashion.

I played around with a bunch of different constructs that would help with this. This is my favorite so far. The handle body with handler construct binds the name "handler" within the body to a continuation that represents the handler. The result of the expression is just the value of body.

fun search_feature() {
       <form action="{handler}">
       <input name="search_term" />
       <input type="submit" value="Go" />
      {search_term=term} -> do_search(term);

I'm treating the handler portion as a pattern matching expression which expects as argument a record; the fields of the record are just the form fields. My reason for wanting to use pattern matching is that we might then embed multiple submit buttons in there, which could be recognized as different cases in the pattern match. I'm not sure the details of how that pattern matching works out.

But the handle construct itself should be relatively easy to implement. I've got continuations as first-class objects in Links with the syntax escape e in expr. Excepting the pattern matching, we should be able to implement handle as sugar for escape.

In the above example, the do_search() function ought to be one that never returns. Why? Because if it did return, the natural continuation for it would return to the caller of search_feature, which is not the desired behavior. The caller of search_feature is out of the picture once this particular handler is invoked. This implies two things: one, we must *force* do_search to be a non-returning invocation (perhaps using the type system) and two, we must not wrap up the surrounding continuation as part of the one called handler. That would be a needless waste.

October 3, 2005

Hazards of continuation-passing

So I've been working on converting the Links interpreter to continuation-passing style. It's pretty straightforward but there are some subtleties and it's easy to make a mistake, so I've been writing up little tests and trying those.

The Links interpreter has 30 distinct kinds of expressions, and the old interpret function has an evaluation case for each one. I asked myself how many kinds of continuations we'd need, each with its own handler, and how small I could make that set.

I had the insight (and I think this might have been noted in Definitional Interpreters or someplace) that you need one kind of continuation record for each method of evaluating subexpressions. For example, evaluating binary operators entails evaluating the left operand and the right operand, independently. We only need one kind of continuation record for all binary operators, and the apply_continuation routine basically handles them all the same way. We still need to switch on the specific operation, of course, but we can plug-and-play as many particular binary operators as we want just by writing the code that combines the evaluated sub-expressions.

Let expressions have only two subexpressions (not counting the identifier, which isn't evaluated) but they are different from binary operators, because the subexpressions are not independent. You have to evaluate one of them, then bind an identifier for the evaluation of the other. So Let expressions call for their own kind of continuation record.

List comprehensions require another distinct kind of continuation record, because you have do an unknown number of sub-evaluations. Altogether I have just 12 different continuation records, and I suspect that could be trimmed a bit with some more clever thinking.

For the edification of anyone else out there who's doing a CPS transformation on some code, the most common error is to forget to apply the continuation when you've got a final result. It's easy to write x + y when you mean apply_continuation cont (x + y). To guard against this, I made test cases that don't just test a given operation, they test it in context, to make sure that the operation correctly passes off its result to the surrounding code.

Links Bug

This program doesn't seem to infer a type for arg:

fun fact(n) { if (n == 0) then { 1 } else { n * fact(n-1) } }
fun factpair(n) { (arg=n|(fact=fact(n))) }
r = factpair(12);

(arg=12,fact=479001600) : (arg:'28,fact:int)
479001600 : int
12 : '34