Home » forums » LtU Forum

Piecewise functional programming

I am looking for feedback about the following programming model (more details are available on my blog).

This is a simple transactional programming model where the code is always executed in the context of a transaction. Transactions are executed in complete isolation (all variables are versioned) from other transactions. The effect of a write operation is only visible after a transaction has committed, i.e. it can only be observed from within another transaction that was started after the transaction has committed its writes. The effect of modifying a variable has no observable effect inside the transaction itself, it will become visible only after the transaction has committed. Because of this delayed mutability I call my variables semi-mutable.

Validation at commit time guarantees consistency by verifying that the reads at commit time return the same result as during the execution of the transaction. Read-only transactions always commit (well there is nothing to commit...), write-only transactions always commit too (there is nothing to validate...) New versions are created when write operations are committed.

Spurious conflicts are much reduced or sometimes entirely avoided by leveraging as much as possible the semantics of the variables, for example counters can only be incremented or decremented rather than being read from and assigned to; they also support e.g. isGreaterThan methods. Writes are either merged (e.g. set.Add) or the last write wins (e.g. map.Set). Transactions are not automatically re-executed in case of conflicts.

Multiple threads running concurrently within a single transaction can be either merged or joined. Merging will combine the write operations if they commute, joining will append the write operations of the joining thread (last-write wins).

IO operations are also supported. External reads can be either checked (read operation is re-executed during validation) or unchecked (read operation is not re-executed during validation). External writes are only ever executed if the validation phase succeeds.

A contiguous transaction sees the system in the state a (parent) transaction put it in. Notification transactions are contiguous transactions that contain a reference to the writes performed by the parent transaction.

Transaction-local immutable (mutable could also be supported) variables are supported.

Overall the level of immutability of the state of the system within a transaction is reminiscent of pure functional programming. The state of the system mutates only when a transaction commits but this mutation is not observable by any running transaction. I am tentatively calling the resulting programming model Piecewise Functional Programming.

I am also looking at combining join-calculus with this model in a new language or by adapting an existing one. In particular I am wondering how to best express the commit operation in a language in which all code is executed in the context of a transaction. Most language constructs are based on some form of scope and their compositions, while the commit operation is more of a barrier which defines the progress of time.

By Gabriel Horvath at 2011-09-23 09:20 | LtU Forum | previous forum topic | next forum topic | other blogs | 5398 reads

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

See XQuery Update

The XQuery Update Facility provides something like this. Base-level XQuery is pure functional; executing a query produces a sequence of immutable objects. XUF allows the query to execute inserts, deletes, replaces, renames, and arbitrary transformations, which have the effect of generating a second result, a "pending update list". After the query terminates, the underlying database is updated appropriately (outside the scope of the language) and other newly started queries can see the changes.

By johnwcowan at Fri, 2011-09-23 14:47 | login or register to post comments

Order and conflicts

Thanks, the XQuery Update does indeed look very similar to my model seen from a client's perspective. I like the idea of the writes being order independent, feels much more functional, but that comes at the risk of failing an update in case of conflicts. For sure something I should consider.

By Gabriel Horvath at Mon, 2011-10-03 09:36 | login or register to post comments

You might also enjoy Esterel

You might also enjoy Esterel and, more recently, Revisions. Interestingly, and you might want to think about, support for merging conflicts is a big deal -- eg, cillk's hyperobject and reducer APIs. Conflict is a useful thing for data parallelism, so it's funny that we still use a negative name :)

By lmeyerov at Fri, 2011-09-23 16:28 | login or register to post comments

Consistency and determinism

Thanks, Esterel does seem to have some very interesting similarities; e.g. I suppose I could look at using a synchronous clock in my model.

Revisions, do you mean Microsoft's Concurrent Revisions? I briefly compared my model to Microsoft's on my blog. Like Cilk, it feels to me more oriented towards parallelizing code than concurrency in general.

My model focuses on consistency and determinism, so conflicts are treated as errors. But there are plenty of applications which have weaker consistency and determinism requirements that allow for faster and easier implementations. In such cases some conflicts can be safely ignored. But what do you exactly mean by conflicts being useful for data parallelism?

By Gabriel Horvath at Mon, 2011-10-03 09:38 | login or register to post comments

Transactional Memory Coherence and Consistency

Your model seems very similar to Transactional Memory Coherence and Consistency. The state in TCC is also only updated when the transaction commits, producing the semi-mutable behaviour that you describe.

By Andrew Moss at Mon, 2011-10-03 11:08 | login or register to post comments