Hacker News new | comments | show | ask | jobs | submit login
Programming with Managed Time [pdf] (microsoft.com)
64 points by seanmcdirmid on May 6, 2014 | hide | past | web | favorite | 10 comments



This was brought up recently in the comments for "Mostly functional" programming does not work where there's also a thread on Glitch: https://news.ycombinator.com/item?id=7654686


Reminds me a little of Alan Kay's VPRI paper on 'Worlds: Controlling the Scope of Side Effects'.

http://www.vpri.org/pdf/rn2008001_worlds.pdf


If you read to the end of the paper, we talk a very little bit about branching time as future work so one could explore multiple "possible" worlds simultaneously (technically easy, the problem is UX). Also see Alexander Repinning's "conversational programming" paper [1] from last year's Onward.

[1] http://www.cs.colorado.edu/~ralex/papers/PDF/Conversational-...

But now that you mention it, I should definitely refer to this work also!


As noted in section 5 of the paper, managing time is also the point of functional reactive programming (FRP). The idea there is instead of working with time implicitly through mutable state, time is an explicit part of the programming model.

With FRP, you program directly with "time-varying values". So where you used to have a normal pair of ints (Int, Int), you would have a "stream" or "signal" of (Int, Int). This could, for example, represent the position of a mouse. This allows you to really elegantly combine different reactive values in high-level ways; for example, you might want to filter events when a game is paused. The code would just look roughly like this:

    when (not <$> paused) (step game)
Personally, I find this style far more direct than actually using mutable state and coupling the evaluation/execution of your code with the time-varying behavior of your domain. This is the difference with FRP: since you never access the value of a variable "right now", the time in your domain and the time implicit in your code's evaluation and execution are separated.

This is what makes FRP more declarative than many of the alternatives, but also what (according to the linked paper) makes it harder to debug. Personally, I think the FRP approach with a nice abstraction is preferable to a more imperative approach even if it is easier to debug, especially if the FRP system manages to preserve nice semantics[1] that let you worry far less about the operational details of the library.

The operational view of FRP is roughly what the paper alludes to, thinking about FRP programs as dataflow networks with explicit propagation and so on. While you can think of FRP like this, I personally find this neither natural nor helpful—it also doesn't really get into the "functional" spirit of FRP, which originally came out of the Haskell community.

Instead, I prefer thinking about FRP as just programming with time-varying values largely as normal values, and keeping the actual implementation details under the ambient level of abstraction as much as possible. This is where the nice semantics I alluded to earlier really help by really clearly demarcating the line of abstraction between your FRP code and what actually happens at runtime. This approach has some difficulties on the edges, like when interfacing with non-FRP components, and is difficult to implement, but I think it's the ideal to strive for.

If you want to play around with FRP, you could take a look at Elm[2] which is a relatively new language that compiles to JavaScript with FRP at its core. There was a recent article about Elm's "Time Travelling Debugger"[3] which is particularly relevant compared to something like Glitch. It doesn't quite capture the abstraction and semantics I was talking about, but it's a very good introduction to the subject and really gets a lot of the "incidental" details right, like being really easy to install and deploy.

[1]: It's possible to come up with very elegant semantics for FRP systems that let you not worry about the particular details of how time is implemented or how time changes. It makes your code "resolution independent" over time—it's like using vector graphics instead of raster graphics.

Unfortunately, these very nice semantics are a bit difficult to implement. I think Conal Elliott's "Push-Pull Functional Reactive Programming"[4] paper is the best example to date, and definitely worth a look.

[2]: http://elm-lang.org/

[3]: http://debug.elm-lang.org/

[4]: http://conal.net/papers/push-pull-frp/


Your comparison of FRP is fairly accurate, but let me reply to a couple of points:

> for example, you might want to filter events when a game is paused. The code would just look roughly like this:

In Glitch/YinYang this is:

  on Tick:
    if !Paused: fire game.Step
Basically, the entire program is lifted over time, whereas in FRP, only values are. But the effect is very similar.

> thinking about FRP programs as dataflow networks with explicit propagation and so on. While you can think of FRP like this, I personally find this neither natural nor helpful—it also doesn't really get into the "functional" spirit of FRP, which originally came out of the Haskell community.

Propagation is implicit, not explicit, I think. Conal's original Fran work has a very data flowy feel to it, as "composed" functional code does in general. The only place where the syntax becomes more procedural again is in the less pure push-based FRP systems (like FrTime, Flapjax).

> Instead, I prefer thinking about FRP as just programming with time-varying values largely as normal values, and keeping the actual implementation details under the ambient level of abstraction as much as possible.

I had this goal with my own FRP work also, but to get there I came up with something very different. Basically, think of Glitch as being something like "time-varying code" vs. FRP's time-varying values.

> [1]: It's possible to come up with very elegant semantics for FRP systems that let you not worry about the particular details of how time is implemented or how time changes. It makes your code "resolution independent" over time—it's like using vector graphics instead of raster graphics.

Even vector graphics must be rasterized at some point. For most programming tasks, a notion of event-time (with everything staying the same in between as in Glitch) is quite useful. There aren't that many tasks that require continuous time abstractions (e.g. animations can be chopped up into 15 millisecond chunks).


Neel Krishnaswami has a paper[0] on implementing FRP with a type system which can statically disallow all the problematic constructs which typically result in time or space leaks. There is a caveat in that he hasn't proven the soundness of the implementation of the linear type system (which is used as a basis).

[0] https://www.mpi-sws.org/~neelk/simple-frp.pdf


This is a really interesting approach. Do you think it will be possible in future to get it performance approaching something like ruby (or even javascript)? It seems like it would be impossible because of the extra work the system has to do. Then again it might not matter in the same way that the usability of Ruby outweighed its performance issues. The usability of Glitch for concurrent applications could easily outweigh it also.


I think we might eventually be able to go beyond dynamic language performance in two ways:

1. memoization can save doing a lot of work when a change is processed.

2. We can optimize task replay as long as it's basic form stays the same, even if the values that run through the task over time change.

We'll see how this works out.


This paper is essentially about how Excel works.


I can't say much about about how Excel works, but there are many different ways to realize recalc :)




Applications are open for YC Winter 2019

Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | Legal | Apply to YC | Contact

Search: