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.

This entry was posted in General. Bookmark the permalink. Both comments and trackbacks are currently closed.

12 Comments

  1. Posted October 1, 2009 at 10:16 am | Permalink

    Are you aware of Warth and Kay’s paper “Worlds: Controlling the Scope of Side Effects”? Your idea of object spaces sounds very similar.

    • Posted October 1, 2009 at 3:05 pm | Permalink

      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

      • Posted October 2, 2009 at 11:01 am | Permalink

        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. Posted October 3, 2009 at 2:45 pm | Permalink

    Hello Jonathan,
    I would like to share with you my recent work also on reactive languages.
    LuaGrvity is implemented as runtime extensions to the Lua language and tries to reconcile Esterel reactive style with FRP.
    Check my website if you are interested.
    (http://thesynchronousblog.wordpress.com/)
    Kind Regards,
    Francisco

    • Posted October 3, 2009 at 7:29 pm | Permalink

      Francisco,

      Thanks for letting me know about your work. It looks interesting and I will definitely read the paper.
      — Jonathan

    • Posted October 5, 2009 at 9:59 am | Permalink

      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

      • Posted October 7, 2009 at 7:52 am | Permalink

        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. Posted October 4, 2009 at 12:16 am | Permalink

    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

    • Posted October 4, 2009 at 9:29 am | Permalink

      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.

      • Clark Brown
        Posted December 4, 2009 at 4:40 pm | Permalink

        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. Posted October 7, 2009 at 7:30 am | Permalink

    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. Raoul Duke
    Posted December 8, 2009 at 1:47 pm | Permalink

    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.

  • Subscribe to Blog via Email

    Enter your email address to subscribe to this blog and receive notifications of new posts by email.