[PEAK] PyCells and peak.events

[Phillip J. Eby]

So I found out today (via James Tauber's blog) about an effort called 
PyCells: a Google Summer of Code project to implement a Python version of 
the Cells library for Common Lisp.

I had never heard of Cells before, but I checked it out because the 
description sounded roughly like peak.binding hierarchies, but with an 
event-driven flavor to make them updateable.  And the GUI angle mentioned 
sounded like something that might make them useful to a possible Chandler 
MVC refactoring, so I checked it out some more.

What I discovered is quite cool.  The Cells system *automatically 
discovers* dynamic dependencies, without having to explicitly specify that 
X depends on Y, as long as X and Y are both implemented using cell 
objects.  The system knows when you are computing a value for X, and 
registers the fact that Y was read during this computation, thus allowing 
it to automatically invalidate the X calculation if Y changes.

These cell objects are roughly like an events.Value object in peak.events 
(and some are more like an events.Broadcaster), in that they are observable 
values or "events" (i.e regular or "ephemeral" cells).  But that's 
basically where the similarity ends.  Aside from the automatic dependency 
detection, the cells system has another trick that is able to significantly 
reduce the complexity of event cascades, similar to what I was trying (but 
failing) to do using the "scheduled thread" concept in peak.events.

Specifically, the cells system understands how to make event-based updates 
orderly and deterministic, in a way that peak.events cannot.  It 
effectively divides time into "propagation" and "non-propagation" 
states.  Instead of simply making callbacks whenever a computed value 
changes, the system makes orderly updates by queueing invalidated cells for 
updating.  Also, if you write code that sets a new value imperatively (as 
opposed to it being pulled declaratively), the actual set operation is 
deferred until all computed cells are up-to-date with the current state of 
the universe.

In other words, imperatively changing values is what separates one logical 
"moment" from the next, and it thus avoids some of the thread-like race 
conditions that can occur when event dependencies are complex.  In 
peak.events now, updating a value (e.g. releasing a semaphore) can cause 
arbitrary code to run, including other tasks being resumed.  But in a 
Cells-like system, the change merely indicates that the at the next logical 
"moment" of updating, which in most cases will be a moment *after* the 
currently executing code in a Task has suspended or exited.

Thus, in Cells one ends up with a kind of CSP (Communicating Sequential 
Processes) scenario being simulated.  Not in terms of any actual threading, 
mind you, but just for the microthreads being run inside of a real thread.

Nonetheless, a CSP model is *much* easier to understand than the "anything 
can happen at any time" model of threads or even the "anything can happen 
when you touch something" model of events.Task microthreads.  Some of the 
trickiest subtleties I found in peak.events had to do with race conditions 
of updated variables due to this very issue.

Anyway, between the built-in CSP model and the automatic dependency 
tracking, implementing something like Cells for peak.events would be a 
major win for ease-of-development.  One especially interesting bit is that 
the Cells system can "optimize away" dependencies or subscriptions when 
their subjects are known to be constant values.  If you declare something 
constant (or set it up so it computes only once like peak.binding 
attributes do), then the things that depend on it (including recursive 
dependencies) won't actually have any event subscriptions at runtime, 
cutting down on the memory usage and the amount of time it takes to update 
things.

I don't know whether the planned PyCells implementation will be reusable 
for peak.events, although I tend to doubt it because after further study of 
the original system, I realized that there are some pieces that could be 
added if you base a Cells-like system on generic functions and the 
Contextual library, that aren't as easy to do otherwise.  For example, 
Contextual would make it easy to have an active Action (transaction-like 
operation) or Resource (object used within an Action) that would be able to 
manage the "virtual clock" so as to multitask e.g. I/O event monitoring 
between "ticks", or to do transaction rollback, undo/redo logging, or other 
context-global adjustments to the system's behavior.

(By the way, this is one of the ways in which Contextual will be superior 
to the peak.binding and config-based machinery for event loops used by 
peak.events currently; Contextual makes it easy to scope an object (such as 
the event loop in use, e.g. Twisted or an events.EventLoop) as being chosen 
according to the current logical thread of invocation, whereas binding 
allows only object-hierarchy scoping, which is pretty much irrelevant to 
the issue of what event loop you're being run from at the present moment.)

I'm also wondering if a Cells-like system couldn't also be used to 
implement STM (Software Transactional Memory) to allow for atomic 
operations even in the presence of threads.  All reads and writes are 
controlled by the cells system, so it can in principle abort and retry a 
"transaction", by waiting until *something changes* that would affect the 
transaction's ability to succeed.

There's a paper I read in the last couple of years about an STM system like 
this for Haskell that was ultra-cool, in that it didn't require anything 
like "yields" to do asynchronous programming.  If you tried to do something 
that would block, it just threw an error and backed out anything you did 
back to the previous committed point, and then waited until there was a 
change, either in something that the attempted transaction read, or in the 
thing that caused it to block.

Among other things, this approach makes deadlocks impossible, because an 
atomic operation doesn't sit there holding locks while blocking on another 
one.  As soon as it would block, boom!  It gets killed and the locks are 
released.  Then, as soon as the lock it *was* waiting for becomes 
available, the transaction is rerun.  Voila - no deadlocks.

I don't know whether taking it that far is possible or practical with a 
Python system.  In Haskell, imperative code is wrapped in monads that allow 
you to avoid unintended side effects, and static typing allows you to 
ensure that an "atomic" computation cannot contain any side-effects.  I had 
previously thought this would be entirely impractical in Python, because 
there's no way to guarantee you're not writing code that produces "side 
effects" (such as I/O, or updates to non-transactional state).

However, seeing how the Cells paradigm works, it seems to me that it should 
be pretty easy to establish the convention that side-effects should be 
confined to non-rule "observer" code.

With Python, there is no way to guarantee that side-effects don't exist, so 
you're relying on conventions to ensure that side-effects only occur in 
observer functions that get called "between the moments" of change to the 
system.  But it doesn't seem like that should be too difficult to manage; 
experience w/e.g. peak.binding attributes shows that it's rare to want to 
put side-effects into pull-oriented rules.

Really, the principal downside to Cells is wrapping your head around the 
idea that *everything* should be treated as pull-oriented rules.  There are 
some operations (such as receiving a command and responding to it) that 
seem to be more naturally expressed as pushing operations, where you make 
some decisions and then directly update things or send other commands out.

Actually, you can still do that, it's just that those updates or commands 
force another "virtual moment" of time into being, where if you had made 
them pull-driven they could've happened in the *same* "virtual 
moment".  So, it's more that pull-based rules are slightly more efficient 
than push-based ones, which is nice because that means most developers will 
consider it worth learning how to do it the pull way.  ;)

Anyway, there is a *lot* of interesting food for thought, here.  For 
example, you could create object validation rules using cells, and the 
results would be automatically recomputed when something they depended on 
changed.  Not only that, but it would be possible to do atomic updates, 
such that the validation wouldn't occur until *after* all the changes were 
made -- i.e., no false positives.  Of course, you'd get the resulting 
validation errors in the *next* "time quantum", so you'd need to make the 
response to them event-driven as well.

I'm not 100% positive how that would work, exactly, any more than I am 100% 
clear on the STM or CSP cases.  And there are many other possible uses that 
I'm even less certain of, but are potentially quite exciting 
nonetheless.  For example, this deterministic model of computation seems to 
resemble "object prevalence" (e.g. Prevayler) in that everything (even the 
clock) is deterministic, changes are atomic, and I/O occurs between logical 
moments of time.  I haven't thought this particular link through very much 
yet, it's just an intriguing similarity.

For now, though I just wanted to dump my current thoughts on the subject, 
and to give a heads-up regarding what will take place when peak.events is 
refactored to become Eventual.  I had already planned to make it use 
Contextual so that the current event loop is dynamically determined rather 
than bound using a component hierarchy, but now it's clear to me that it 
should also use a quantum scheduling system (ala Cells) to ensure that 
system changes can only occur *between* logical moments of the system.

There are still some details to work out, but it seems to me that the 
system could make all changes occurring during one "moment" be atomic as 
far as the next "moment" is concerned, and also detect any conflicting 
changes; i.e., by raising an error if more than one piece of code 
imperatively sets a value for the same cell during a given "moment".  (Thus 
eliminating any nondeterminism due to update order; no race conditions, in 
other words.)

The head-exploding part is figuring out how to get errors to propagate 
backwards in time, so that validation rules (which run in the "next 
moment") could appear to cause an error at the point where the values were 
set.  It's not unlike the issue one finds in Twisted Deferreds, when you 
don't want a callback to happen later, you want it *now*.  Probably the 
best solution is similar, by replacing a function with a Task and yielding 
to a validation ITaskSwitch, so that when your code resumes you are "in" a 
different "moment".  (I.e., instead of sending events backward in time, you 
effectively send code forward.)

The main problem with that is that you may no longer have consistent read 
values for other data in the task's state; other atomic operations may have 
been interleaved.  It's the sort of thing that you really need the full STM 
model for -- that is, you need to be able to roll back the system state.

I'm going to have to think through these issues some more, but there seems 
to be a lot of potential to be explored here.