Object Relational Mappers have a dream. Their dream is that the mechanics of creating, reading, updating and deleting can be abstracted away and need not be thought about.

I have a dream, too. My dream is that the fact that creating, inserting, updating and deleting is going on can be abstracted away and need not be thought about.

The ORM dream has a big ol’ flaw, to the extent that I am sceptical about the use of ORMs in general. The flaw is that the right way to do CRUD operations depends rather heavily on the domain and the application in question.

My dream should not be vulnerable to that particular flaw, though, because I’m trying to abstract away those operations entirely. Or so I thought right up until yesterday, when I realised that since my approach is to first convert the programmer’s code into a form that does have CRUD operations, I’m going to have the ORM problem from then onwards.

And it’s worse, because when you call the CRUD operations yourself you can exercise a fair degree of control over what goes on. When the CRUD invocations are automatically generated, that control would have to be exercised by hints and indirect suggestions.

Bugger.

In today’s fantabulous outing, marvel at three approaches to efficient implementation!  Ride the wave of perplexity that is the function from a list of inputs to the current state! Gaze in wonder at the persistent storage of that current state!

Option 1 – incrementalisation

In this approach, we take a state function f, that takes a list of inputs and produces current state, and produce an incrementalised state function, that takes a change in the list of inputs to the resulting change in the current state. Liu gives a systematic approach for deriving the incrementalised versions of functions.

Advantages

• It enables a neat way of making a highly responsive UI. As well as incrementalising the state function, you also incrementalise the view function (a function from state to HTML). On the client, you can run the incrementalised state function, pass its output to the incrementalised view function, and apply the resulting change to the DOM. (this works)
• It lends itself to a really cute way of integrating with a data store: write a function that takes the system state and returns a relational representation of that state. Then incrementalise that function. Any time the system state changes, you can pass that change into the incrementalised relational representation function and hit the database with its output. Shiny! (I haven’t done this yet)

Disadvantages

• The wording of Liu’s paper is very careful. What they have is a systematic approach for deriving incrementalised versions of functions. What they don’t have is a fully-automated approach. There needs to be some user interaction or some hinting (in the general case) in order to produce an incrementalised version of a function.
• When you have an inner function that uses free variables, and the values of those free variables can be affected by a change, the incrementalised versions start to get pretty hairy and potentially rather inefficient. The current version of my code assumes that any free variables used will not change, which is obviously not true in general.
• At the moment I have an informally specified bug ridden implementation of less than half of Liu’s technique.

Option 2 – Partial Evaluation

Partial evaluation is where you take a program of n inputs, then provide some subset of those inputs and evaluate the program with respect to those inputs. This isn’t immediately applicable to this state-updating shenanigans, because there’s no provision there for changing inputs.

Instead of running the partial evaluator directly on a program that takes a list of inputs and returns a state, we can augment the program with a new top level function:

return state(cons(new_input, inputs))

Assuming the partial evaluator unfolds that cons, we’re in with a chance of getting a program that incorporates a new input without doing too much stuffing around. It’s not at all clear how you might get the state into a persistent data store with this approach, but worse then that, the resulting program won’t know how to capitalize on existing bits of state. This is probably surmountable by memoizing computation of bits of the state, but if you’re going to go there…

Option 3 – Adaptive Computation

Adaptive computation (after Acar) is where you think of a program as building up a dependency graph of values. The final output depends on a bunch of intermediate values, which depend on other intermediate values, which ultimately depend on the program’s inputs.

There’s no obvious barrier to storing that whole dependency graph in some sort of persistent store. Obviously, this is going to be a much weirder database than Option 1 gives you; but on the other hand, this approach naturally gives you much more fine-grained change propagation behaviour. That means you don’t have to worry about free variables making stuff confusing. More importantly, it is fully automatable. You just feed your program into the madhouse, and off it goes.

Similar AJAXyness to that of Option 1 is imaginable, but vastly more intricate: you must ship the portions of the dependency graph relevant to the client’s computation down to it. Determining in advance which portions will be relevant is quite likely to be vulnerable to the halting problem, so you’ll have to either send too little (and have a lazy loading strategy to get other data that you need on the client) or too much (and clog the intertubes, OMG).

This option is closest to the approach taken by Asana’s Luna and by Meteor.

Parenthetically: I was amused to discover that with Option 1, the efficient thing to do is to cons a new input onto the head of the list. With this option, the efficient thing to do is to replace the empty list at the end of the input list with a singleton list containing the new input.

Conclusion

I’m sticking with Option 1 for now. I’m about to attempt integrating with a database; if that goes badly, Option 3 is going to start looking much better. Again.