Posted on by Jonathan Edwards

Coherent Binding

Abstract for my talk at Emerging Languages Camp:

We cannot evolve beyond imperative programming until we solve the problem of coordinating changes to state. Functional programming and transactions segregate the problem, but don’t solve it. I am exploring a new kind of language, inspired by modern “Model-View-Binding” application frameworks. The language uses bidirectional data binding as its fundamental mechanism, generalized into arbitrary change-triggered actions. Bindings propagate changes coherently: execution order is determined automatically based on the interdependencies between bindings. The programmer does not have to worry about execution order. A side benefit is the automatic discovery of parallelism. Unfortunately coherence doesn’t work in a conventional heap of objects with arbitrary dynamic pointers to each other. I propose a data model in which objects and collections of objects are nested to form trees. Pointers are replaced with cursors constrained within a collection. This richer structure permits coherent and deterministic execution of bindings. Coherent binding offers the simplicity of declarative programming while maintaining complex dynamic state.

Comments? The idea is to use data binding as a metaphor that many programmers are already familiar with. Can I assume people will get what “Model-View-Binding” is, even though I just invented the term?

40 Replies to “Coherent Binding”

    1. Who you callin a programming language theorist? Them’s fightin words.

      Seriously, Model-View-Binding = MVC + data binding. All the cool MVC frameworks now offer some form of data binding that automatically propagates data changes.

  2. I get it. Sounds interesting and I wish I could attend. Will you be posting slides/video or a paper?

    1. Yes, this is a form of reactive programming. My last paper was called “Coherent Reaction”. That is actually a more technically accurate description than the analogy with binding. But I am thinking binding is a more familiar concept.

      1. I’ve been fascinated w/ the idea of reactive for about a year now and I read your coherent reaction paper too. I’ve been fiddling with some ideas in my spare time, but I’m planning on solving the ordering problem in more of a hardware engineering inspired way with virtual latches, so you can only create loops in the circuit if there is a latch in the loop. I suppose it’s a bit more explicit than your solution. For example in a game there would be a latch that latches every frame, and to do a loop there would be a block that churns an external state machine by flipping a latch until a “done” line is raised making the output of the loop valid.

        I love your work on subtext, but I haven’t quite bought the new coherence idea. It seems like it’s a sharp turn towards being relegated to academia, but maybe I just haven’t grasped it completely yet?

        1. Your latches sound like Synchronous Reactive Programming. Check out Esterel and Lustre.

          You may be right about being relegated to academia. But I found that I couldn’t extend Subtext to imperative programing, so I needed to invent a way to express state change declaratively. I also came to the conclusion that merely improving the user interface of programming would not be sufficient to get people to change languages. It needs to be have some hard semantic benefit that can be appreciated even by Emacs lifers.

    1. Thanks Joe. Indeed lots of people have had the same insight that we ought to use some form of dataflow programming. They just have never figured out how to make it as flexible as normal imperative programming, with pointers and dynamically allocated data.

    2. This book seems very interesting. Can I maybe find it somewhere on the ‘net? Except ordering a paper edition for hundreds bucks plus shipping. In google books there are only a few pages available.

          1. Fant is about clockless and concurrent design. There are many ways to do this. I found IPL confusing to read for even some trivial tasks, as compared to UML, which is capable of modeling similar problems graphically.

            I don’t think he is a crackpot, just an idealist. He’s discussing how to model *entirely* flow-based computing at the hardware level. The big thing is he depends on passing Nothing | Something and the alternation of these two in order to coordinate flows. It is exactly what he says: logically determined. In other words, no use of probability is allowed. The only caching operation is indeterminism from running multiple pure calculations at once and saving only the one that “mattered”. Other CPUs have way more interesting probability models, allowing more elimination of branching. I think memory systems, not data paths and control paths, are the only systems that matter these days at the hardware level. So to use IPL as an interface for hardware seems misguided. Something like Ivan Sutherland’s Fleet architecture is probably more promising.

            In UML, we’d just take advantage of extra details and deterministically know that the hardware allows 32 words at a time, so object A communicates with object B using the optimal pub-sub data packet size. There is no strictness analysis; it is pure optimal design. Faaaaaast. But requires code generation and some metasystem for negotiating the data packet size, either at compile-time or run-time. IMHO, in either case, there is only one sensible scheme for persisting that info: fexprs with handles back to the source. But my friends tell me I’m wrong.

          2. Thanks for the book report Z-Bo! Clockless logic has been talked about for quite a while, but it doesn’t seem to have caught on. I am sure I could learn from studying up on it, but there is only so much time…

  6. Hi Jonathan,

    Love your work.

    One of the primary benefits of model-view separation, and indeed of object-oriented programming in general is the encapsulation of behaviour in the data-model as opposed to ad-hoc integration of procedure.

    Even though we’re now (ostensibly) designing with objects, we still tend to describe their behaviours imperatively rather than functionally. Why is it so? The whole point of having a model in the first place is consistency: functional programming does this very well.

    Although imperative programming is regarded as more “flexible”, I have a suspicion that the large majority of imperative effects are unnecessary anyway, so this “power” is more often a burden then a blessing.

    Other than persistence and I/O, is there any reason why one would want to apply imperative effects to deliberately avoid functional consistency? e.g. bidirectional bindings which are not symmetrical?

    BTW, I’ve read your paper on Coherent Reaction, which got me thinking down this path…

    Cheers,
    Lach

    1. Lachlan, thanks for your comments. I think there is widespread agreement that functional API’s with immutable objects are preferable when dealing with “value-like” entities. There is less consensus when considering collection types. And opinion flips the other way on databases. Seems to be a matter of size.

      Other than persistence and I/O, is there any reason why one would want to apply imperative effects to deliberately avoid functional consistency?

      Many applications, like desktop and web apps, are mostly about persistence and I/O. It’s mostly schlepping bits from the database to the user, then reacting to inputs from the user and side-effecting the database.

      1. Many applications, like desktop and web apps, are mostly about persistence and I/O. It’s mostly schlepping bits from the database to the user, then reacting to inputs from the user and side-effecting the database.

        Right, but the interesting problems aren’t in reading and writing from the persistent data-store — it’s how the data is transformed in the meantime. I find it hard to think of examples of when you would want to transform it in a way that can’t be conveniently described with functional semantics. Granted, event-driven GUIs make the separation more problematic.

          1. That’s an imperative effect, of course which will alter the state. But my question is more about what relationships the counter has with other variables. If the consistency of those variables is a constant property of the system—seems to me, that’s usually what you want—why not describe them functionally?

            To ask it a slightly different way: Does coherence guarantee consistency?

          2. I think that by consistency you mean what is called invariant satisfaction. The problem is that invariants are constraints that typically admit many solutions, and don’t tell you how to pick one, only whether your pick was right. The problem of guaranteeing invariant properties is the old program verification problem, which has been a Holy Grail of computer science. A hopeless quest, in my opinion.

  7. Model-View-Binding makes perfect sense to me!

    For a long time I’ve wanted a way in to declare relationships between data that are automatically maintained in similar ways as bindings are defined in GUI libraries like WPF. In fact, I’ve been working on a general binding library for C# that can work on many different types of objects (not just DependencyObjects), where values can easily be bound to arbitrary expressions using expression trees (no more one-off converts!).

    There are others who are working on similar ideas. You might want to take a look at Obtics, if you haven’t already: http://obtics.codeplex.com/.

    I’d be interested in exploring how this idea effects the reusability of code. I could see it becoming much more viable than it is in traditional OO languages, because one has a lot more flexibility in how objects (or tree nodes?) are connected without having to get bogged down in writing lots of glue code.

  8. I like the data binding entry point. That’s always been one of my favorite ways to explain the potential value of reactive programming.

    Another of my favorite pitches is ‘caching without the pain’. The contribution of relational database systems to the world that resonates with me the most was not the relational data model per se. It was the idea of separating essential and incidental state and reaping the benefits this brings with it. (Admittedly, this is still only a partially realized promise in the database world; witness the practical need that still exists for denormalization.)

    A major promise of reactive programming is to transfer these benefits to application programming. One of the big problems with elaborate hand-coded caching schemes is that correct synchronization is hard to implement in the first place and even harder to maintain over time as requirements evolve. Database indexes and many other uses of state in real-world applications simply exist to facilitate access to the essential state. A programming system should help you keep essential and incidental state in step with each other.

    The analogy to data binding should be clear. When you explain reactive programming to workaday programmers, their response is often, as it indeed should be, “That just sounds like events.” And that’s what it is: events without the worries.

  9. Do I have this right: you are trying to make a system with these primitives:

    1) a reference cell (you call it a cursor)
    2) a way to attach a callback to a cursor cell that gets called when the value changes
    3) a transaction-like mechanism that lets you update multiple cursors as if they were updated in the “right” order automatically

    Is this what you have in mind? Can you explain a bit why restricting data to trees avoids the problems of your previous approach?

    1. No, that would be Clojure. Was that a trap? I am working now on a presentation which may answer some of your question. As always, I will be posting it.

      1. I don’t think that Clojure updates the cells in the right order. It does updates atomically, but that doesn’t work here, because then you are left with multiple inconsistent values for the cells if you run the derivations/reactions. I’ll be patient until you post the presentation 🙂

        Another thing: derivation allows you to update 1 cell based on values of n cells. Reaction allows you to update m cells based on the value of 1 cell. Would it make sense to combine this in a n x m operation that updates the value of m cells based on the values of n cells?

        And another thing: derivation updates the value of a cell if *any* of the values it depends on changes. You could manually handle coherence if you were also allowed to specify reactions that run if *all* of the values changed.

        For example:

        if end changed AND length changed: start := end – length

        This would also allow you to handle this case:

        if start changed AND end changed: length := end – start

        I believe this case is not handled by the example in your paper.

        This is of course more cumbersome to use, but it’s more flexible, so this may be a good trade-off because Coherence issues don’t come up extremely often, and when they come up you might need something like this. You would of course be able to use arbitrary boolean expressions to dispatch on (e.g. X changed AND (Y changed OR Z changed)). The problem of how to execute multiple n x m reactions harmoniously remains though.

        1. Oh, and that would also avoid the problem of innocent looking code ending up taking exponential time because of backtracking 😉

        2. Sorry for the flurry of comments. The mechanism I described above seems similar to the join calculus at least on a superficial level. The implementation of join calculus may give some ideas on how to implement it efficiently and how to react to things concurrently.

        3. Yes, I did not address the issue of steering reactions based on patterns of change. I intend to use conditionals just as you propose. That quickly becomes cumbersome beyond 3 values, but I am guessing that you typically don’t want such complex flows anyway.

          1. Great! Yeah, I think that even two values will be much rarer than 1, and even if you only supported 1 value to react to it would still be much more general than FRP, and FRP gets/got a lot of interest.

            This does seem like a natural generalization, so perhaps it will lead to some cool stuff. Good luck with your presentation. I’m looking forward to see how you make multiple reactions play well.

  10. RE: “change triggered actions” – I suggest considering state-triggered reactions, rather than change-triggered. There are all sorts of tricky semantic and implementation issues with observing “changes”, especially in a continuous system. Basing transitions on current state results in a simple semantics (one is always computing ‘in the now’). It has proven to work well in a variety of systems (timed concurrent constraint programming, Dedalus: Datalog in Time and Space, etc.).

    RE: “bidirectional data binding” – Besides the inductive step of maintaining the data-bindings, you must also consider the non-trivial base-case step of setting them up in the first place. If Alice (perhaps a unit of hardware or software) doesn’t already know about Bob, then how can Bob bind Alice to his data? You have been assuming the use of imperative side-effects to achieve this. I posit those effects are much stronger than you need for many uses. An alternative is “declarative side-effects” – a limited class of effects that are idempotent, continuous, and concurrent and thus suited to the abstractions and optimizations of declarative programming. (Confer: imperative expressions implicitly modify time and thus cannot be repeated or rearranged without changing semantics.) Agents in Timed Concurrent Constraint (tcc) programming might be seen as having this sort of side-effect – modifying and maintaining constraints on shared variables over time. However, tcc’s global notions of consistency don’t readily allow for adversarial agents or open systems programming. So I’m pursuing an alternative model I call ‘Reactive Demand Programming‘ (RDP). RDP embraces ‘observer-effect’ and extends it to include arbitrary requests and ‘demands’ in a declarative and reactive manner.

    A feature in common with RDP, tcc, and Dedalus is that you are able to express both declarative (continuous, concurrent, idempotent) and transitory (not quite imperative) ‘effects’. In all three cases, transitions are based on “current state” rather than any “delta”. RDP isolates transitions to the local agent (which serves as a reactive state-machine), whereas tcc and Dedalus express transitions as part of a global store.

    1. Good luck with that. I am always glad to see people trying alternative approaches to long-standing problems. “Continuous and idempotent” doesn’t really work for me though. I don’t see how it handles the keypresses with which I am editing this comment, for example.

      1. Declarative effects are, of course, of limited expressiveness. That said, they’re suitable to replace a large portion of code across a wide variety of domains. Data binding used by coherence can be seen in the same light.

        For completeness – to cover the relatively few effects that are cannot effectively be expressed declaratively – one can use those transitory effects I mentioned in the prior comment in order to modify present and future state. Effects that “cannot effectively be expressed declaratively” seem mostly to be those whose implementation would require a permanent history be maintained ‘outside’ the system if state is not allowed ‘into’ the system – thus introducing time-space leaks and regressing the state-management issues.

        Dedalus would represent keypresses as a logical assertion at a given instant, allowing deductions about the future instant (and, inductively, all future instants until the next such event) be inferred. Timed concurrent constraint programming would represent a keypress as a constraint at a given moment, provided by an agent, thus allowing other agents to react, very similar to Dedalus.

        RDP lacks a clock or a global information space, and instead isolates transitions within agents (which may transition based on observed behaviors). Thus, one could represent key state as observable behavior, allowing agents to transition accordingly. Alternatively, if one wishes to ensure presses are not lost (i.e. across disruptions) one could instead represent key events as a stream with futures (each future represented by an RDP agent); this stream could be consumed by a reactive state-machine agent to, for example, build a block of text.

        Of course, this is all much more fine-grained than necessary for many scenarios. If we were to assume browsers as part of the system, then a text-area could be one big behavior as far as the rest of the system is concerned, with its current contents affecting the system continuously (Google Wave and Wikis and text-editing in Croquet…).

        Anyhow, I did cover much of this in the RDP page. I am not especially encouraged by an insincere “Good luck with that” from someone who can’t be bothered to review the content; might as well say “Go away”. So I’ll say nothing more directly on the subject of RDP.

        Data-binding with imperative side-effects on change, as you are promoting, has been made to work before. I pursued that idea for a couple years, allowing actors to ‘hook’ complex behaviors so they can receive messages whenever the behavior changes. Data-binding makes for nice, distributed ad-hoc queries – something that can be difficult to set up with plain observer-pattern. It can also support live-programming (especially if data-binding can carry functions or procedures). If you control where reactions are introduced then you can support a great deal of automatic caching, multi-cast, and parallelism.

        However, the interface between the data-binding and imperative/message-passing systems is quite awkward. Fundamentally, you have a continuous observation being converted into a discrete operation. This awkwardness manifests itself in terms of concurrency control and synchronization requirements. For example, if an actor behaves on one update before the activity from the prior one is complete, anomalies ensue. My target was open distributed systems (where adversarial code, temporary and permanent disruption, network partitioning, slashdot effect, etc. are facts of life), and so I pursued concurrency control that could be secured across mutually distrustful hosts and not used in denial-of-service attacks – transactions.

        Your own “Coherence” approach acts in a similar role, serving as a form of global concurrency control by producing a schedule based on dependencies. As such, coherence will help interface between the data-binding and imperative code. You restrict references between objects, which will inevitably result in complexity elsewhere, but that simplifies construction of a valid schedule. I doubt coherence would work for open distributed systems, but that’s probably outside your goals.

        Rather than managing this complexity, I think it wiser to eliminate or avoid it where possible.

        Actors model and other imperative models introduce a significant amount of accidental complexity by imposing a logical ordering for effects. When order is imposed upon effects that are concurrent within the problem-domain, then explicit state-management becomes necessary to represent concurrent influence on a shared resource (and to later clean up). State requires serialization, forced serialization imposes need for state, state requires serialization… our systems spiral towards far more explicit mutable state than required by essential complexity of the problem domain.

        Pursuit of alternatives to ‘ordered effects’ – for those many cases where the problem domain does not demand order or long-term memory – is only logical. There is enough history with concurrent constraint programming and logic programming that this isn’t breaking new ground, but is rather combining proven elements of older models. We still need some ordered effects, of course, when serialization is inherently part of the problem-domain. But support for declarative effects ensures we don’t introduce additional need for state while fighting the computation model.

        I believe you, and your work with Coherence, could really gain something from this. Of course, you’d need to think about it a bit longer than the time it takes to pat me on the head and say “Good luck with that, shoo now.”

        1. I don’t think Jonathan meant “Good luck with that” in a bad way. He just meant that you were pursuing a problem that has been pursued by many great computer scientists, and they’ve all only made incremental progress. “Good luck with that” really means, “Well, send me an e-mail when the proof-of-concept is ready”.

        2. I think you are on to something with RDP. I saw a friend write his program like this when he was learning programming:

          if(button.click){ ... }

          This is a very natural way to express things, but we programmers have been taught to think like

          button.onclick.add(fun () => { ... })

Comments are closed.