Time is of the Essence

The following is an abstract of a position statement for the Live programming workshop at ICSE.

Time is of the Essence

Today we only know how to do live programming in special cases, such as pure functions on primitive values as in spreadsheets, or at the top level of domain-specific programs like games and graphics. To fully realize live programming we must solve an essential problem to do with time. This problem is bridging the gap between the programmer’s experience of time while programming and the program’s internal semantics of time. Indeed the current examples of live programming are all cases with a narrow time gap: either the program is timeless as in pure functions, or it has a macro-level user-comprehensible notion of time as in games. To achieve comprehensive live programming, programming that is live all the way down, we must confront the fact that mainstream imperative languages embrace the CPU’s perception of time, which is quite foreign from that of the programmer. To envision a path forward we draw a lesson from the history of programming languages. To rationalize the insanity of programs that could read and write arbitrary data to any memory address, languages evolved the now ubiquitous notion of automatic memory management. We suggest that to rationalize the insanity of programs that can read and write globally at any time that languages should impose automatic time management. Managed time would offer live programming a representation of program execution at a higher level than program counter traces. We survey current research on managed time, including functional reactive programming (FRP), synchronous reactive programming (SRP),  effect systems, and transactions. Perhaps surprisingly, we conclude that although transactions are the most popular form of time management they are not actually very helpful for live programming. Without progress towards managing time we expect that live programming will succeed mainly where a domain-specific notion of time can be exploited.


I have decided not to submit this. It puts me in the position of an old guy telling a bunch of enthusiastic kids that what they want to do is naive and impossible. When I was a kid I just ignored those old guys and went ahead and did the impossible.

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

30 Comments

  1. Posted February 3, 2013 at 5:47 pm | Permalink

    Do you have specific ideas about how automatic time management should work?

  2. Posted February 3, 2013 at 5:47 pm | Permalink

    (oops, forgot to check the ‘notify’ button.)

  3. Nat
    Posted February 3, 2013 at 5:54 pm | Permalink

    That’s a shame. I think that’s purely a matter of phrasing. You could be more positive about your findings. Instead of concluding that “without progress towards managing time we expect that live programming will succeed mainly where a domain-specific notion of time can be exploited” you could say that novel techniques for managing time are key for live programming to expand beyond domain-specific notions of time and currently an unsolved research area.

  4. Posted February 3, 2013 at 6:55 pm | Permalink

    I would suggest any survey of managed time also include Time Warp protocols (first published in 1985, and improved ~2009 as Lightweight Time Warp), and Cellular Automata.

    I am developing Reactive Demand Programming (RDP) which is another model with time management, differing from FRP and SRP in regards to modeling of effects and state. RDP is designed to support live programming ‘all the way down’. I consider alternative models for state – in particular disfavoring ‘local’ state (‘new’, private attributes, etc.) – to be at least as essential for live programming as managed time.

    • Posted February 4, 2013 at 12:43 am | Permalink

      Indeed state and time are inseparable, as neither makes sense without the other. I’ve heard you talking about RDP in various places, and it sounds very suggestive to me, and certainly an example of what I am proposing we call managed time. I encourage you to keep working on it, and particularly to work on communicating your ideas with worked out example applications. Perhaps you should submit a paper to Onward, which is one of the most welcoming places for this kind of research.

      • Posted April 23, 2013 at 2:52 pm | Permalink

        I suggest Relational Reactive Programming rather than Functional Reactive Programming for the obvious reason that functions are degenerate relations.

        Moreover, by adopting the relational paradigm you not only get to address the “impedance mismatch” with relational databases, you also get to the root of time itself as a calculus of relational links described in the paper “Process, System and Causality”:

        http://arxiv.org/pdf/quant-ph/9808011v1.pdf

        • Posted April 23, 2013 at 2:59 pm | Permalink

          I forgot to mention that this link-theoretic approach naturally gives rise to programming quantum computers. Another benefit that falls out is bringing Bertrand Russell’s “relation arithmetic”to computers in such a way as to naturally include concepts like physical dimensions in the concept of number. See “Relation Arithmetic Revived” for some work I supported toward this goal:

          http://www.boundaryinstitute.org/bi/articles/Relation-arithmetic_Revived_v3.pdf

    • Posted February 4, 2013 at 5:27 am | Permalink

      I second Jonathan’s opinion. I really think the paper writing process helps us focus our work as well as communicate it.

      The Time Warp work looks very interesting.

  5. Posted February 3, 2013 at 8:10 pm | Permalink

    Please reconsider. Besides the young kids, there is also at least one old fossil on the PC (me). I’d like to hear what on earth you actually mean …

    • Posted February 4, 2013 at 12:24 am | Permalink

      Well Gilad, if you don’t already see what I am getting at then maybe I don’t actually know! I wanted to avoid pushing my own solution and instead describe a general direction where I think the field should be heading. Hard to do that without a concrete example though. And the best way to do that is to shut up and build a demo.

  6. Posted February 3, 2013 at 11:19 pm | Permalink

    As a young kid considering attending this workshop, this is exactly the type of submission I’d love to see.

  7. Posted February 4, 2013 at 5:44 am | Permalink

    I would love to read this even though I don’t think I’ll be able to go to the workshop. I’m not sure if I agree with your conclusion, actually, I have found very haphazard ways of dealing with time and ordering to be quite effective. But I agree some sort of special handling of time needs to be baked directly into the language.

  8. Dercsár Péter
    Posted February 4, 2013 at 9:11 am | Permalink

    So you returned to the start position (remember Coherence?).

    • Posted February 4, 2013 at 9:45 am | Permalink

      Never stopped working on it, just changed names. I went back to calling it Subtext since that seems to be my “brand”. But now I find it confusing that each version of Subtext is so different.

  9. Dercsár Péter
    Posted February 4, 2013 at 9:13 am | Permalink

    OFF
    How does this post machine know who I am? It uses my avatar from StackOverflow. Matrix know me or what?!
    /OFF

    • Daniel
      Posted February 4, 2013 at 1:10 pm | Permalink

      StackOverflow and this blog both uses Gravatar. The way it works is that your email is hashed and used as a link to display a picture fetched from Gravatar. Gravatar doesn’t necessarily know your email but it has a picture associated to it anyways, sort of. I don’t know for sure but it looks like setting your avatar on StackOverflow changes your Gravatar. Check out: Wikipedias article on Gravatar and Gravatars web site. Gravatars web site has a StackOverflow logo on it. =)

  10. Posted February 4, 2013 at 3:39 pm | Permalink

    Most programmers don’t need to deal directly with time at this level. But get into real-time or high-frequency trade clearing systems, and you’ll start to see time solidify in system design.
    It is not surprising out of that ecosystem that temporal query and event query languages were invented.

    Programming language, tool builders, researchers must always tackle the challenges that regular developers don’t. But there must be a start.

    • Posted February 4, 2013 at 4:43 pm | Permalink

      Managed time is useful in a lot of domains – music and multimedia, control systems, video games, etc.. I think most programmers and most problem domains would benefit from managed time. Even the exceptions benefit indirectly with respect to process control and other peripheral issues. There was an excellent article on the subject in 2009: Computing Needs Time.

      Most programmers don’t understand why they should deal directly with time at this level. Most programmers aren’t competent enough to even recognize, much less comprehend, what they did wrong with regards to their last concurrency project.

  11. Posted February 4, 2013 at 3:56 pm | Permalink

    I hope you will still publish your thought even if you don’t submit a talk. I find the topic of time in a programmatic sense to be fascinating. I agree that we don’t have a good handle on it yet, at least in mainstream tools.

    Thanks,
    Josh

  12. Posted February 4, 2013 at 8:25 pm | Permalink

    Your right not to discourage people, but perhaps if you wrote it in a different way with different attitude.

    The problem is that when people are constrained by what they know, they cannot consider the things that they don’t know. When people consider the impossible, they sometimes find a way to solve the impossible problem.

    For example, maybe people shouldn’t be building these programs up from nothing and function calls to api’s but they could building functions by genetic splicing of two functions together into a second function. We kind of do this in functional programming by passing functions around, but what if we didn’t, what if we just joined two blocks of code together at splice points to create a third block of code? Consider something crazy and wild and you might find a new approach.

    • Posted February 5, 2013 at 7:57 pm | Permalink

      GMO code! Frankencode! It will be banned in Europe and CA.

      • Posted February 7, 2013 at 12:05 am | Permalink

        Yes, here’s another crazy idea, extend types by binding the type to words in the wordnet database (or opencyc), then if you have a Animal class, if someone attempts to create a Cat class we can infer the inheritance automatically by looking up in the wordnet database and finding that a Cat is a sub-type of Animal. Therefore Cat should automatically inherit from Animal.

        Then extend that to sentences, so a function is composed of many words which make up a sentence, try to infer relationships automatically.

        For example if we have a function:
        find the factorial of

        People could call this function type typing just
        factorial of

        A suitably smart english language understanding system could infer that these two sentences have the same meaning and therefore the call of the sentence binds to the definition.

        • Posted February 7, 2013 at 12:06 am | Permalink

          find the factorial of (n)
          factorial of (n)

          It didn’t like my syntax above

        • Posted February 7, 2013 at 12:10 am | Permalink

          I’ve tried this before and found WordNet to not be very useful for inferring subtype relationships. Frame.Net and Verb.Net are a bit better but they obviously don’t focus on nouns very well. Hugo Liu’s work using montylingua is probably the closest anyone has come, but his examples are also super abstract.

          • Posted February 8, 2013 at 9:43 am | Permalink

            This is going to get narrow -Hi Sean, its nice to know someone else had the idea! I’d also like sentence binding so if someone defines a function as a sentence:

            the factorial of (n: Int) is (k: Int)

            Then if someone types

            find the factorial of (5)

            The computer should work out the meaning of sentences and bind this called sentence with the defined sentence with the most likely common meaning.

            Then I can write in English some sentences with parameters such as the following without even having to look up for the function, the computer just finds the function based upon english language understanding:

            find the circumference of a circle of radius 125 as (result)

            So then you can write your program in English.

            Parameters could be IN or OUT or any direction, if any direction you could get more complex and define unknowns and solve for unknowns. Functions could be reversible such as:

            find the circumference of a circle of radius (r) as (400)

            …. onto another crazy idea, I had this idea where what if the entire universe was just one single program which could solve any problem and the universe could be made into instances of the universe within this universe. I mean, if I could hold onto an instance of the universe in my hand and ask it to solve a problem and it does. I’m not writing this right… change…

            Consider a program which can solve every problem, then what if this program was made up of instances of itself which all talk inside of this program with each other, like instances of the class of the universe. Its like saying me as a person is composed of 1000 mini-me’s inside my brain, and they are talking and working. Actually, its all just one program, and the program is getting better all the time as the mini-me’s inside my brain chat with each other to solve a problem they change the structure of the program of me and there-by change their own structure. Because the structure of their program is the structure of the me program and they are inside me.

            If this was a diagram its the universe inside itself, each atom inside our universe is an instance of the whole universe, recursively forever, they have instances inside themselves, the point is to assume there is a program which can solve any problem and then to compose it recursively like this.

          • Posted February 8, 2013 at 7:39 pm | Permalink

            We probably shouldn’t have this discussion here, but feel free to post on lambda the ultimate or contact me by email (smcdirm@microsoft.com).

            I just had an intern wrap up a project that makes some progress in this area, but we are approaching it right now from the other side (how can we use PL to make encoding dialogue systems easier). I hope to have something written up soon on what we did.

  13. Posted February 5, 2013 at 11:12 am | Permalink

    I hope you go ahead and publish. Now is the time for this (if I understand where you are coming from).

    1) Textual programming based on imperative control flow cannot, IMHO, be the right answer if we are ever to truly put computing power into the hands of normal people. (i.e. non-specialist IT people).

    2) A conceptual model of time and cause-effect is, in my opinion, innate in the human mind and is crying out to be leveraged in computing paradigms, if we can just find a way.

    3) We need to stop thinking that mainstream folk need to learn to program. Rather, programming needs to learn to be like normal folk :-)

    Sean

    • Posted February 5, 2013 at 12:30 pm | Permalink

      Agreed Sean. The problem is that much of the current excitement about live programming is based on the hope that it can be slapped on top of our existing languages and no one has to give up anything or change anything. No one will consider new languages until the painless option fails. I worry that when that inevitably happens the whole idea of live programming will be discredited and no one will want to talk about it anymore.

  14. Lach
    Posted February 9, 2013 at 9:30 am | Permalink

    Is there more to this notion of time than the ordering of things? Is “managed time” the new syntax for “coherence”?

    • Posted February 11, 2013 at 9:45 am | Permalink

      Coherence was a (failed) experiment in managed time. I have a new scheme which is still unpublished. In general managing time means the language gives you a notion of time at a higher level than machine language. In particular time should be partially ordered, meaning some things happen at the same time.