Posted on by Jonathan Edwards

Lost in the forest

I am lost. The essential idea of coherence is a year old, and I still haven’t implemented it. I blame the trees. I have been struggling to integrate coherence with the tree-based model of computation in Subtext. It just isn’t working. In fact it hasn’t been working for years – I have struggled with the subtleties of trees in my last 4 papers. And the reviewers seemed to have struggled as well. My conclusion is that these trees are standing in the way of progress, and they have to come down.

I have been hugging trees because they seemed essential to my long-term agenda. But I realize now that if I defer the more ambitious aspects, I can still achieve some major goals with a more normal language, one that uses syntax for code and objects for data. Such a language is not only a lot simpler to invent, but also a lot more approachable to everyone else. Three realizations make this simplification now seem viable.

Firstly, I have remembered that I can make a syntactic language still appear to be live and example-centric in the IDE. That is what I did back in my original Example Centric Programming paper. That work was limited to a purely functional subset of Java. But now with coherence I can equally well visualize the execution of imperative code in the IDE.

Secondly, I can construct updatable views out of objects. My last paper talked about virtual trees, which are computed on demand, but can be read and written like normal trees. I can do the same thing with objects by automatically generating getter and setter methods, and by carefully limiting their visibility. Collections have to change substantially. This will not be a plain vanilla object model.

Thirdly, I can do hypothetical imperative computations (progressions in the paper) using object spaces. A space appears to be a copy of the entire heap, except with some specific changes. Spaces nest, which may offer some of the hierarchical goodness of trees, like deep copying.

The road forward looks like this: right now I am working on my talk at OOPSLA this month. I only have a 20 minute slot, so it will not be very deep. As usual I’ll post a video after the talk. Concurrently, I am working on an informal description of the syntax and semantics of the language to cover roughly the same capabilities as in the paper. I will try to present that in more detail later this fall at NEPLS. Then I need to do a prototype implementation, probably as a REPL without an IDE.

This is a complete 180 from my last move. Oh well. Research is confusing and unpredictable, and I’m not very good at it. I hope I eventually find my way out of the forest.

12 Replies to “Lost in the forest”

    1. Thanks Justin. Warth’s thesis has a more recent presentation. Yes, it is a similar idea. The major apparent difference is that spaces can nest, whereas worlds seem to be separate. Also, I am taking the idea further, for example forcing loops to create a new world at each iteration.
      — Jonathan

      1. Worlds actually support fine-grained to coarse-grained controlling of side-effects. In fine-grained ways, it is about:
        * more composable ways to “try” an operation that may result in critical failure
        * backtracking
        * futures
        * continuations in general

        (As an aside, I dislike the fact Kay and Warth don’t use run-to-completon semantics as a way of defining whether an operation leaves a program in a consistent state – moving the program counter is in fact a side effect).

        To me, the difference between worlds and coherent reactions is that worlds are designed top-down, whereas coherent reactions are designed bottom-up. This is therefore two different ways of modeling object interaction. The way coherent reaction works, it also hides Warth & Kay’s sprout/commit semantics by instead requiring run-to-completion for each nested level. In addition, it seems like Warth’s approach leaves you with flattened subtrees. Thus, all you are doing is defining a “computation space”. The trees are never flattened in the Coherence paper, which is probably the “subtleties of trees” Jonathan is having problems implementing.

        Both approaches use prototype-based object models, and basically add transactional semantics to classical Jackson Inversion. There was actually a commercial software package by mainframe manufacturer ICL in the ’80s that did the latter, but it was ahead of its time. See: “Database Processing in RADS – Rapid Application Development System”, which later became ICL QuickBuild. Also, I don’t believe RADS/QuickBuild was Turing-complete.

        Also:

        > Research is confusing and unpredictable, and I’m not very good at it.

        In the recent book Coders at Work, Simon Peyton Jones reflects back on how when he was first starting out he would just sit in his office waiting for great ideas to just come to him.

    2. Francisco,

      Very nice work, with a good balance of power and usability (like much of Lua). Have you looked at Sean McDirmid’s SuperGlue? It has declarative linking like you do.

      To me the nicest (and as far as I know novel) idea in the paper is the way single-threaded access to variables is guaranteed by the scheduler.

      The thing that bothers me the most is the split between LINK and SPAWN. You don’t say it, but presumably LINKs must be set up statically during some initialization. The nice properties of links do not apply to dynamic spawns, particularly glitch avoidance and single-threaded variables.

      You stress “implicit invocation” as the key feature, but I find that a little confusing, as LINKs are quite explicit, it is just that they are declarative rather than imperative. I might call this “declarative invocation”.

      Again, nice work, and thanks for letting me know about it. Feel free to let me know about further developments.

      Best,
      Jonathan

      1. Hi Jonathan,

        Yes, I know about SuperGlue and read most (all?) papers about it.
        Seems to me that the declarative part of most reactive languages is following the FRP style with dependency between data (variables).

        In LuaGravity, LINKS are as dynamic as SPAWN calls, you can create and destroy them at anytime.
        Also, all SPAWN calls run on the same thread—the whole LuaGravity is single-threaded.
        The fact that SPAWN calls are subject to glitches is due to the lack of a compiling phase in LuaGravity. We cannot predict SPAWN calls until they happen.

        LINK(x,y) is actually equivalent to the following code:

        SPAWN(function()
        while true do
        AWAIT(x)
        SPAWN(y)
        end
        end)

  3. Hi Jonathan,

    What does this mean for your subtext project? I think your graph based programming model, and in particular, schematic tables are truly excellent ideas. Will you continue to develop this project or are you primarily interested in pursuing coherent reaction independently? I’m not sure I understand how you can dispense with trees entirely. Isn’t syntax just another kind of view on top of tree semantics?

    Best,
    Lach

    1. Lachlan,

      Good questions. I am deferring work on the UI of programming while I try to fix the semantics of imperative programming. I am finding that doing it all at once is just too hard. I shall return.

      ASTs are much simpler than Subtext’s trees, which are really misnamed: they are spanned graphs with internal copying and computation constraints. AST’s are simple passive tree structures that only need to manifest in the compiler and the IDE.

      1. I think the schematic tables in the UI are a great idea and hope to see more of that when you return to it. Swinging the mouse around seems cumbersome compared to VIM though, keyboard navigation could be a really nice addition.

  4. Its easy to get stuck down a rat hole, this is standard process for PL researchers (epiphany => obsession => rejection => reboot). This is something like my process with SuperGlue, where I’m taking concepts from there and putting them into a more pragmatic Bling C# library. I still like to play around with new syntax, but its more of a way of developing concepts without contamination that later can be backported to more conventional systems. Still haven’t figured out a nice way to do live programming in C# though.

    BTW, I would suggest you look into .NET/DLR for language exploration work. They have very nice and powerful support for code generation, which allows you to explore a lot of concepts even without creating new syntax. I’ve recently added a feature to Bling where you can provide the type of an annotated interface, and the system will automatically compute/cache an implementation for that interface.

  5. i kinda wish all the FRP-related folks could be under one roof for more than a few hours a year. so i could stand a higher chance of getting to use it; of getting free of the usual crappy approaches to interactivity and state and graphics.

Comments are closed.