This describes a live transactions, a concept similar to software transactional memory capable to replace model view controller.
Introduction
Over the last two years I have built a number of incremental evaluation systems that use automatic dependency tracking:
Values are defined through methods that depend on each other (hopefully not recursively), and each value evaluation records the evaluated values it depends on in a dependency graph. The graph is then used to decide about what values need to be reevaluated when inputs have changed.
A number of problems
Well, that worked fine, but over the time something felt wrong: There were a number of problems which I instinctively wanted to go away:
- For some algorithms, incremental computations may be chained in such a large number that unpredictable stack space may be used. I was not able to change the evaluation so that it does not uses the stack recursively. When a method gets evaluated and a dependent value is not, the value needs to be reevaluated, with all the consequences.
- In more complex systems, returning one value (object) per evaluation always felt unnatural. Decisions about the value granularity had to made in very early stages of the design. After a while, value granularity seemed undecidable at the time a system is built.
- The most natural way to do things is to have your tools at hand and to apply changes the stuff around you. So computing one value was not enough. It is too constrained, multiple reads and multiple writes must be supported to create methods that actually behave to do something. I wanted one unit of behavior (the method) to resemble this scenario.
- Structural dependencies, like lists or maps were not easily implemented. I had a system working, but the huge effort and complexity of truly incremental collection containers afflicted me by doubts.
A practical solution
After a lot of evolutionary work targeted towards implementing a clearly defined user interface application, the solution turned out to be a system that supports at its core – I called them – live transactions. These are methods that can read from and write to their environment and are automatically rescheduled when input values are changed.
Though introducing some computational redundancy, they seem to be a solution to all of the above problems:
- Scheduling is now explicit, and so chained computations don’t consume stack space anymore. The nature of a defined transaction is that it always ensures that the environment is in a defined state. So if integrity is guaranteed after a transaction has ended, it can be guaranteed before one is started (if they don’t run in parallel), this effectively means that any live transaction may run at any time. And because the order of the execution is not fixed, a scheduler can be used.
- No fixed decisions about granularity are required. Values can be combined and split up depending on the current requirement: Integrity of (implicitly) dependent values is guaranteed by supporting multiple writes in a live transaction.
- Multiple reads and writes enables a live transaction to represent a task or behavior if you wish. It is not about a computing a value anymore, which is boring. Running a live transaction actually does something, it modifies state, it has some power.
- Because the overall integrity is always guaranteed, structural changes of a systems can be executed live. There is no laziness requirement anymore, which simplifies the implementation of containers a lot.
Drawbacks
- Live transactions (and their computational result) must always be computed in an eager fashion. Lazy evaluation is not automated.
- Each live transaction requires a clear lifetime definition, either defined by (object) ownership or by switching them on and off explicitly. In practice, a definition can always be found fast and intuitively.
- Transparent memoization is not supported anymore. For computational intensive systems, this may be an issue.
- A trivial scheduler implementation may introduce redundant invocations of live transactions.
Advantages
Additionally to solving the most immanent problems described above, I’ve found the following – initially unintended – features interesting:
- Live transactions look more natural in their implementation. Their implemented unit of work can represent an arbitrary complex state modification process and so can be easily expressed literally.
- A number of live transactions that are defined using a closure may represent a behavior block that
- is instantiated once and then runs (behaves) for itself
- is a stateful actor
- can be combined orthogonally
Conclusion
My early experience shows that live transactions in combination with closures can be used very easily to build behavior modules without defining or instantiate a class. Applying a specific behavior aspect to some object feels completely orthogonal. For example, I have developed a number of behaviors for a graph editor user interface. They can be combined without showing any interdependency in the implementation.
Further reading
BTW: Though not a hype, there is active research, for example done by Umut Acar about self-adjusting computation.
Interesting that the mechanisms behind software transactional memory are similar, I even think these two concepts fit well together.
yours
armin