Lambda the Ultimate

Sean McDirmid: There seem to be various approaches ranging from formal to less formal, its unclear if the less formal systems (e.g., SuperGlue) can be considered FRP.

First of all, thanks for replying, Sean! Second of all, where can I download SuperGlue? :-) I've been wanting to ever since reading your paper with the embedded movies! Thirdly, I absolutely consider SuperGlue to be an example of FRP, and only didn't link to it because, as far as I can tell, there's no public implementation to link to, which is a shame.

Sean McDirmid: I have a hard time understanding formal FRP because it often seems to just be fighting against the purity straight jacket that Haskell puts you in. And how does purity make programmers more productive?

That's true for Reactive and other Haskell FRP systems, but obviously, FrTime isn't pure, React in OCaml isn't pure, etc. So what you see is indeed an effort to talk about time in referentially transparent terms in Haskell, and it leads to interesting results like Conal's "Simply efficient," in which he claims to have arrived at a garbage-collection friendly system, and Luke Palmer's, in which he concludes that you can't get where he wants to go in Haskell and so begins a new language design.

As for how purity makes programmers more productive, I think that there's an unfortunate initial learning curve, but after that, ensuring that your system is consistently referentially transparent has significant productivity benefits. But this observation is rather obviously anecdotal.

Sean McDirmid: here is still a lot of opportunity for bringing FRP-like constructs to mainstream programmers; e.g., through Bling. But I'm curious to see where the more formal approaches are going.

Agreed on all counts.

At anyrate, I think physics is the next frontier to be explored. We know how to abstract over time or make time a first-class value, but now can abstract over integrated time? In other words, rather than having "t", you have dt, and some fancy integration algorithm like Euler, RK4, or something else inside your interpreter to perform a nice dynamic simulation.

I see by following the link that Conal replied to those very issues in that thread, and that he has tackled the issue of continuous time in Reactive, so I don't know that I have anything to add here. It would also be interesting to hear what Luke Palmer thinks of the issues in the context of Dana.

First of all, thanks for replying, Sean! Second of all, where can I download SuperGlue? :-) I've been wanting to ever since reading your paper with the embedded movies! Thirdly, I absolutely consider SuperGlue to be an example of FRP, and only didn't link to it because, as far as I can tell, there's no public implementation to link to, which is a shame.

I learned from a long time ago (~Jiazzi) that just releasing something doesn't make it useful, and actually, can lead to lots of misunderstandings. SuperGlue is a demo vs. something to release, there are bugs when you hit certain keys, the library support is shallow (to support the examples in the OOPSLA paper), and of course always the performance problems that I talked about in the paper. The source code for SuperGlue was hanging around for a long time on the Lamp SVN server, but its probably been moved somewhere else now. I'll dig it up and publish it if you'd like, but I don't have time to move it forward to a release quality project. Bling is where my future effort is going for now, as it is much more useful in the near term (let's get more of FRP in the mainstream!). I hope I time and need to explore live programming again someday, heartbreaking that there is so much stuff to explore these days and no time to do it!

I'm not sure if SuperGlue can be considered an example of FRP. The dependency propagation algorithms that I use are a bit too pragmatic and I don't worry about glitches. But the biggest reason SuperGlue might not be FRP is that its not functional at all, rather its declarative/connection-based (ya, F often means D but not necessarily) without functions. If anything, SuperGlue was moving closer towards a declarative constraint system. I never could figure out why the FRP people didn't want to cite/compare against constraint language work (or vice versa with newer update propagation work). I think I am just missing some fundamental concept in FRP that makes it totally unrelated with constraints.

I see by following the link that Conal replied to those very issues in that thread, and that he has tackled the issue of continuous time in Reactive, so I don't know that I have anything to add here. It would also be interesting to hear what Luke Palmer thinks of the issues in the context of Dana.

I didn't really understand Conal's reply, but probably he is just way smarter than me :). The problem I see is that all efficient dynamic simulation techniques are based on discrete time steps, and there are a lot of techniques out there (I'm playing with Verlet now). I'm trying to absorb as much of the software physics work as possible, they just have so many clever ideas in that field that absorption will probably take forever! If we can provide language support for physics, it would be a nice cross over between SIGPLAN and SIGGRAPH.

Sean McDirmid: SuperGlue is a demo vs. something to release, there are bugs when you hit certain keys, the library support is shallow (to support the examples in the OOPSLA paper), and of course always the performance problems that I talked about in the paper. The source code for SuperGlue was hanging around for a long time on the Lamp SVN server, but its probably been moved somewhere else now. I'll dig it up and publish it if you'd like, but I don't have time to move it forward to a release quality project.

I thought the point behind releasing was to hope others in the community would help! :-) Also, how can we tell if it's FRP enough or not otherwise? ;-)

Sean McDirmid: But the biggest reason SuperGlue might not be FRP is that its not functional at all, rather its declarative/connection-based (ya, F often means D but not necessarily) without functions. If anything, SuperGlue was moving closer towards a declarative constraint system. I never could figure out why the FRP people didn't want to cite/compare against constraint language work (or vice versa with newer update propagation work). I think I am just missing some fundamental concept in FRP that makes it totally unrelated with constraints.

Peter Van Roy would tell you: it's not unrelated. :-)

Sean McDirmid: I didn't really understand Conal's reply, but probably he is just way smarter than me :)

I certainly have that problem!

Sean McDirmid: I'm trying to absorb as much of the software physics work as possible, they just have so many clever ideas in that field that absorption will probably take forever!

Quite right. I didn't mean to imply that there's nothing more to learn and that Reactive answers all the questions. Only that it might serve as a more effective launching-off point than we currently realize. And that, in a nutshell, is what I appreciate about FRP in a pure context. I myself am not a Haskell programmer, but I like that the Haskell community is out there, keeping us honest in terms of our semantics, while the OCamlRTs, Reacts, FrTimes, Flapjax, SuperGlues, etc. get to be pragmatic.

Need to find time to update the SuperGlue prototype to the current versions of Scala and Eclipse, then I'll put it out. I've been playing a lot with the DLR lately, this is really cool: you can easily generate code to be JIT'ed that is lightweight; e.g., the function pointers will get garbage collected when no longer in use. This means I can do Live Programming the right way...The next version of SuperGlue (or whatever replaces it) is definitely going to be much much better/faster/real. Now I just need the time.

Thanks for react! I look forward to taking it for a spin. I'm especially interested in the relationship to real time as, again, I'm primarily interested in exploring Nick Szabo's insight that his contract language is essentially a real-time-based reactive one.

Wow, I'm glad OCamlRT was useful for someone. I gave up working on it about a year ago at the behest of my advisor ("who uses OCaml?"). FWIW I've moved the sources (along with myself) to http://cs.brown.edu/~squirrel/temp/ocamlrt2.tgz, since at least a few people seem to miss it.

React looks pretty solid, I hope sometime I get a chance to play with it.

Re compute-expensive "dirty bits"... you want an async_map function (over events). Unlike map, its input and output events are not causally related... the output event occurs in its own distinct time step whenever the computation completes. Works well for I/O too.

The dirty bits I mention are not related to computational intensiveness, they are dirty w.r.t. to time itself. When you do continuous collision detection in frp, the problem is that when you realize that your object's position went too far you already computed it and made it visible to the outside world, to prevent that you have to dismiss this position, but then you get further problems with collision response.

I didn't research that extensively (and already forgot the details of my unsucessfull findings) but it seems hard to get an elegant and efficient solution. Reading about physics engine implementations made me feel that it doesn't fit well in the frp framework because during a "dt" it needs to play with time (and hence positions) internally and then in the end communicate the resulting position for this "dt". Thus the suggestion that an frp interface may be more suited than an implementation in frp itself. But I'd love the be proven wrong.

Best,

P.S. Don't forget that an advisor is just that...

Perhaps Conal's new paper on automatic differentiation is related to the physics problem. I can see it being useful in expressing physical constraints, even if these constraints are then solved via discrete integration.

1. The implementation of the physics engine and how to expose it are different. FRP is a clean interface to it, giving a lot of wiggle room in the implementation. E.g., you can play with parallel streams, fusion (dipping/lowering work, or lucid/synchrone tricks), precomputation (schedule your animation) and QoS (drop frames), specialization, etc. To my knowledge, except for FrTime, FRP engines haven't really been optimized (likely because our collective interest in getting the abstractions right first), but that's one of their big appeals.

2. I'm not sure I understand the dirty bit problem. The implementation (w or w/out signals) can likely have dirty bits encoded inside, and only clean values are exposed. If you coded the engine with signals itself, that might even be as simple as a case of merge/filter/hold -- this is a common pattern, such as for lifting object oriented code (MrEd, the DOM, etc.).

3. There's a cost to dirty bits in a parallel system; perhaps you can refine what you intend them for, algorithmically?

2. I'm not sure I understand the dirty bit problem. The implementation (w or w/out signals) can likely have dirty bits encoded inside, and only clean values are exposed. If you coded the engine with signals itself, that might even be as simple as a case of merge/filter/hold -- this is a common pattern, such as for lifting object oriented code (MrEd, the DOM, etc.).

I think the problem that dbuenzli is referring to is specific to physics: because your time step is discrete, you have the problem where one object can pass through another if it moves completely through it in one time step. In this case, collection detection occurs by assuming the object takes the shape of its entire movement for that time step. Actually, real physics engines are all about apply and re-applying constraints on every time step until the system stabilizes.

I really admire people like Erin Catto who really have a handle on these problem; I get lost beyond Gauss-Seidel stabilization, this is really hardcore math and its still all real (e.g., implemented and fast)! Can we PL'ers learn from these systems? Yes! What can we PL'ers bring to the table? Abstraction, of course. An FRP candy shell can make it much easier to use could make this stuff more accessible; i.e., we could apply more physics to UI programming (writing a paper on that topic right now).

Ah, that makes more sense. One cool direction is stuff like continuous time languages ( http://ptolemy.eecs.berkeley.edu/ptolemyII/ptIIlatest/ptII/ptolemy/domains/ct/doc/body.htm ), though I haven't had a chance to look at them yet.

One nice feature of Ptolemy is that it has pluggable levels of models; you might be able to use CT to write your physics engine, and then export the values into a SDF framework (e.g., most FRP systems).

we could apply more physics to UI programming (writing a paper on that topic right now).

Definitely, I'm working on a draft to submit to UIST 09 (deadline March 30th), I'll try to have an early draft ready for early review in a couple of weeks. I've never tried writing an HCI paper before, so this is an interesting learning experience.