Posted on by Jonathan Edwards

NEPLS slides up

Here are the slides from my NEPLS talk. People seemed to enjoy it, and I got a bunch of laughs. Positive comments afterwards. Mitch Wand couldn’t stay for my talk, but I got a few minutes to talk with him, and he gave me a promising suggestion for the completeness theorem. Overall a good experience, though as usual I am relieved now that it is over.

8 Replies to “NEPLS slides up”

  1. Looks like a great talk. “Non-true”…hah. I also enjoyed the closing slide.

    The conclusions are interesting. To make sense of persistent data structures in a declarative setting you really need pointers, so it’s nice to think there may be a way to have that without the pursuant nastiness of imperative languages.

    Couple of questions:

    * Assuming you can obtain a satisfactory completeness result, have you any initial thoughts on the overhead of the backtracking? (E.g. pathological cases when it might be exponential in the size of the coaction, or similar…)

    * What areas of existing research might be relevant? It feels like
    there should be lots of relevant work, but perhaps not from the standard PL literature. Maybe there are analogous problems that have been studied in the algorithms community.

    1. Thanks Roly.

      The worst-case performance is really bad: factorial in the number of statements. But these days we solve NP-complete problems for breakfast! I think standard analysis techniques can be used to propose an approximate execution plan. It should only be a linear cost to check such a plan at run-time, and then fall back to the inefficient search when the plan fails.

      I agree that it seems there ought to be a lot of relevant research, but I am not finding a lot of it.

  2. I just wanted to say again that your talk and your idea are both very nice.

    One clarification question: what’s the difference between this programming model and a reactive programming system that also supports bidirectional binding? Is the key benefit an efficiency one, since in a reactive system each bound expression is re-evaluated on each change to a dependency (whereas here, the dependency graph is effectively topologically sorted before executing it)?

    1. Thanks, Yang. Do you mean the data binding frameworks in common GUI and web frameworks? I am replacing data binding with a more general language feature. The benefit is primarily simplicity and flexibility.

      Data binding frameworks work mostly on the special case of a single layer of links between special View and Model classes, and have special purpose hooks for doing transformation and validation. GUI frameworks generally have no ability to synchronize multiple changes together, whereas web frameworks do so with special purpose phases. I want to allow you to build change propagation graphs of any shape over any objects involving any computation, and without worrying about synchronization. Hope that answers your question.

  3. Great slides, easy to understand and to follow.

    I also have some questions:

    – What is the reason for having the following statement?
    length` = end` - start`;

    I understand the apostrophe is for post-state, but is it also possible to have several post-states, i.e. length``?

    – If so, could the length` = end` - start`; be rewritten as length`` = end` - start`; to express it more clearly, or would that break functionality? (If so: why? Since the post-post-state would have a pre-state of the previous post-state.)

    If this is true: can this rewrite made implicit? I.e.
    length = end - start; would be rewritten as length`` = end` - start`;, by using dependency trees?

    – Did you consider dependency trees? A dependency tree for
    start = 4;
    end = start + 5;
    length = end - start;
    would be:
    start
    end - start
    length - (start, end)
    such that one only has to sort the tree to determine execution order. This can be done at compile-time, and thus reducing the search-problem at run-time. (Dependency can be determined by lexical analysis and the tree can be build using

    * For all statements, add the statement, at the root of the tree, iff it has no dependencies, and remove it from the statement list.
    * For all statement in the statement list and for all dependencies: is the dependency already somewhere in the tree? If this holds for all dependencies, remove the statement from the statement list and add the statement to the tree (connect it to it’s dependencies) at the current depth and flag. After all statements and when flagged, increase the current depth.
    *If delta depth is zero the tree cannot be build.

    )
    Dependency trees can be used to detect undetermination, since determination is based on resolving the variable references in time.

    If you considered these trees, is there a reason why you did not use them?

  4. Hans,

    Yes, the example can be resolved by static analysis – I simplified it for the presentation. The problem comes in when you add another variable that is aliased on the same object, breaking all hope of static analysis of the dependencies.

    I do plan to allow multi-step computations – what I call progressions – but that reintroduces sequential programming, and I want to first show how to avoid that in common situations.

    1. Got it: pointers breaks the static analysis, which is your point in Coherence. Then, wouldn’t it be more useful for a viewer to use an example with these pointers (or aliases), to show Coherence works there, especially, too?

Comments are closed.