lambda cube... 3D

LambdaCube 3D is a domain specific language and library that makes it possible to program GPUs in a purely functional style.

Like, the game demo requires Haskell. More prose and code examples on the project blog.

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

I'd really like to see

I'd really like to see something of this sort:

  • efficiently integrated with a reactive paradigm, especially with respect to buffer, texture, and mesh acquisition and resource handling at the GPU (i.e. as opposed to downloading a texture to the GPU every frame)
  • supporting WebGL canvases

watch Elm

the Elm community has some folks who want similar things, it look like. (since that's where i heard about this in the first place :-)

These are quite old goals

These are quite old goals though. It is already easy to treat global parameters as signals, Bling was able to route textures to the GPU via signals also. The bigger problem, and the reason I gave up, was that the pipeline stages were becoming less functional (geometry shaders...) and I had no real hope of tackling general GPU computations.

Glitch should be able to handle this better, maybe I'll try again.

art is about constraints

i have never done direct gpu programming (more is the pity for me). i'm the kind of person who doesn't mind having some basic stuff that works for basic things, and then working within those constraints. so (as long as it is performant, e.g. 30+fps) then i don't mind not having full general GPU computation. i just want my retro-vector-graphics-style video game progject to run fast.

I imagine it would be more

I imagine it would be more profitable to focus on specific use-cases for GPU computing - graphics, machine learning, computer vision, physics, etc.. each with its own DSL, perhaps refactoring out useful aspects as you learn more.

Anyhow, while the goals are old and solutions exist, the solutions are not yet readily accessible by anyone who wants to use them. I guess I'd like to see the reactive version of Unity.

This is quite true, but I

This is quite true, but I would argue that the solutions being presented are not new, and will fail for reasons similar to why previous solutions failed. I'm not expecting to see anything interesting come out of Elm, they have already been pretty oblivious to previous work and making the same mistakes we made 10 years ago.

GPUs are quite a hard environment to work in; you can't really do much efficiently beyond pure functional computations. So you can't trace dependencies, record differences at a fine granularity, and so on. If you want to just do this work on the CPU, you have to transfer memory to the CPU, which can be super slow. Using the CPU is probably unavoidable at this point, so you have to be careful about how much and how often you need to transfer.

I agree. GPUs are very hard

I agree. GPUs are very hard to work with. They can't even express the wider varieties of pure functional computations efficiently - e.g. first-class functions, latent procedural generation, deep tree structures. (We could potentially do much with pure time and level-of-detail driven procedurally-generated scene-graphs on the GPU, but it isn't happening soon.) Since we can't flexibly generate or acquire more information, we're forced to make more "up front" decisions, and perform certain kinds of operations on the CPU.

That said, GPUs can do a lot of specific things relatively easily. They are very easily applied to neural networks, difference analyses, collision detection, 2D+depth/transparency composition, sound or music generation, visual object detection, etc. (supposing you express these as matrix or vector operations). We can also do quite a few animations on the GPU.

I would argue that the solutions being presented are not new, and will fail for reasons similar to why previous solutions failed

My hypothesis: a significant factor in the "failure" of old solutions has been the lack of perserverence. Taking the solutions that last mile, and addressing various transition challenges, never happened. We don't necessarily need a new solution. We need someone to take existing solutions all the way without getting bored or depressed halfway through.

That aside, there are some important technical differences compared to other solutions, e.g. regarding how 'explicit' is the communication between CPU and GPU, or even along stages in the GPU pipeline. The solutions I gravitate towards seem to use the type system to enforce that all such communication is explicit, at least for an intermediate target.

You don't need anything fancy for FRP

GPUs are quite a hard environment to work in; you can't really do much efficiently beyond pure functional computations. So you can't trace dependencies, record differences at a fine granularity, and so on.

IMO, we needed the heavy dependency-tracking machinery mainly to correctly implement a bunch of corner cases that no one really wanted in the first place. So by using a little bit of type theory to statically rule out those corner cases, almost all the implementation complexity simply evaporates.

I have a new paper, Higher-Order Reactive Programming without Spacetime Leaks, which shows how to implement higher-type FRP using nothing but plain old call-by-value, with a light dusting of call-by-need --- and you could even drop the call-by-need if you had to.

As a result, I don't think there's anything intrinsically harder about supporting GPUs with FRP, than with ordinary functional programming. (Which is to say, it's still hard, but as far as I can tell FRP doesn't add any new sources of hardness.)

Are you referring to pure

Are you referring to pure synchronous FRP or impure asynchronous FRP (e.g. FlapJax, FrTime)? For pure FRP, I think the abstraction is that you recompute on every time step, while asynchronous FRP depends on dependency tracing to re-compute on demand. The problem and solution spaces of both kinds of FRP are very different, and I've only ever really looked at the latter since my domains of interest (UI/game programming) are pretty messy. I see you address this in your related work section.

But maybe pure FRP is a better fit for GPU programming. A colleague who is active in GPU HPC work (deep neural network training) told me that the appeal of GPU programming is its completely synchronous nature: all your threads run in lockstep with each other, running the same code, almost always taking the same branches; memory is loaded in chunks and consumed by all threads at the same time. GPUs are quite the antithesis of CPUs in this regard. But given that dynamic allocations are not very reasonable, and more importantly, coherence in how each thread executes is very important, it might be a better fit for simpler synchronous data-flow programming than even pure FRP.

Yes, this paper is about

Yes, this paper is about synchronous FRP. I've also got a paper in the works about asynchronous FRP, too, but the basic message doesn't change. The high-order bit is that you still don't need a sophisticated change-propagation infrastructure: callbacks a la subject-observer are enough.

How is subject/observer not

How is subject/observer not a change propagation infrastructure? Is there a more formal definition for change propagation that I'm not getting?

No, not more formal...

I just want to say that systems like Flapjax, Scala.react, and adaptive functional programming (e.g., Froc) are qualitatively more advanced than a plain subject-observer infrastructure, since they have a global dependency management system in which nodes maintain both the set of things they read and the things which observe them, and use global topological properties to figure out the best order to re-execute nodes.

In contrast, a naive sub/obs system just fires its callbacks blindly, without dynamically considering what else needs to be run.

I think I got it. In my own

I think I got it. In my own work, Glitch avoids a global dependency graph also and goes with per-state dependency queues, which each node knows what they depend on. However, change is computed on a per-node basis, so even if sA -> nB -> sC -> nD, we don't invalidate nD because sA is invalidated, instead, nB has to drive a real change into sC on its re-execution to cause nnD to be invalidated. No global dependency graph means no topological sort, and the order that we re-execute nodes can be "wrong" (no effort is made to find a "best" order), leading to further invalidations and re-executions that could have been avoided had a "right" order been chosen (hence the name Glitch).

So Glitch lies somewhere in the middle, or would its dependency management be considered more like subject/observer?

Glitch is closer to

Glitch is closer to a naively implemented observer pattern with respect to dependency management - i.e. doesn't do it, thinks testing for change is sufficient, and for many use-cases it will be.

A linear graph, of course, won't reveal the issue here. The topological sort is important when you have diamond-patterns in the dependency graphs, or large fan-ins of nodes that will modify states.

What are examples of use

What are examples of use case where it would fall down? Everything I've thrown at it, that I would use Bling or SuperGlue for, seems to work just fine. Maybe a robot where eventual consistency is not acceptable and real-time guarantees are needed?

Use Cases for Proper Sorts

Organically grown applications - i.e. the kind that grow up over years with ad-hoc 'feature' extensions, in desperate need of an architectural overhaul, nobody remembers the complicated dependencies. These can rapidly go from 10x wastage to 100x or more because they tend to have unusually high fan-outs and ad-hoc updates.

Also, highly performance-competitive systems, i.e. where performing the same big-matrix operation four times with stale data is intolerable because you don't have CPU and memory to spare. Video processing, video games. Though, these might be mitigated by separating the critical loops.

(Robotics can actually deal with inconsistency fairly well. They need to, due to all the noise in their sensors. Further, physics itself helps dampen most issues.)

The first one, organic

The first one, organic applications, seems to just mean "legacy" systems. I think run-time profiling would go a long way to helping us maintain large evolving application over time. That dependencies are traced at all is useful in implementing profilers.

Video processing and video games are ideal Glitch applications. Their is waste, but not that much waste. If a node really takes a long time to execute, it should be broken up if possible. If a node involves loading a matrix onto a GPU, doing a large computation, and then moving it back to the CPU, then you have to be careful...

Actually, one of the applications I was looking at that I didn't find suitable for Glitch was machine learning via gradient descent. The problem here is that the model changes a little bit on each step; none of the bits stay the same! As a result, I couldn't figure out how to incrementalize it even with an ideal system. But then, how would any other incremental model deal with these problems?

In robotics, you wouldn't want to throw in inconsistency of the programming model on top of sensor inconsistency. The other problem is just the unbounded nature of eventual consistency if no guarantees are made on when the system is consistent for some time t.

When the problem is

When the problem is unnecessary callbacks with stale data with large fan-out, runtime profiling often does a poor job of isolating the root cause, and does nothing to fix the problem.

Glitch won't be suitable for video games until it handles time. :)

After that, it might be useful for game object management, and possibly for scene-graphs. But executing even ONE extra time per frame would be intolerable for some computations.

Gradient descent is already incremental; just model it as running over 'time' and you're set. :)

In robotics, you wouldn't want to throw in inconsistency of the programming model on top of sensor inconsistency.

Well, I wouldn't want to. But the rest of the robotics community doesn't seem to have a problem with it. ROS, DDS, some truly awful protocols... (Dealing with this is my day job.)

My task for the next year is

My task for the next year is to augment Glitch with Fujimoto-style space-time memory (as they call it...STM), so time is coming soon. The goal is to be able to handle N minutes of Kinect-based computer vision processing code, where N is hopefully greater than 1 :) You can run with space-time memory in real time: we can garbage collect all info related time t when no nodes in the inconsistent queue depend on it.

If it was just ONE extra time per frame, our overhead is fairly constant and we can just say we are 2X as slow as C, or 5X or 10X, which are completely acceptable for Python or Haskell, and games are written in Python! If we offer enough candy, developers will accept a reasonable multiple of performance decrease. The question is: is Glitch's cost constant? I'm not sure.

Gradient descent is incremental, ya, but not in a way that Glitch can deal with, even if it supported time. The problem is that nothing stays the same between each time step, so everything depends on everything in the past. They get around this in ML with mini-batches, but that is not something that we can apply transparently.

dependency management can be a nonissue

If there is real consistency, then the order in which dependencies are resolved is immaterial. One can handle the issue depth-first. All that is really needed is a way to know, when you are loading something, whether it has already been loaded, and a way to link to already-loaded modules rather than requiring linkage to "the" one that is specifically loaded at your request.

Blowing it on diamond patterns or circular dependencies is just an unnecessary failure IMO. It's easy to avoid.

Module loading? You seem to

Module loading? You seem to have missed the context. We were discussing dependencies in a dataflow update graph (e.g. like a spreadsheet, or an observer-pattern).


You're right that I was drifting offtopic, but the point is still valid. The 'resolution' is well known in module loading, in that if you have real consistency (ie, modules never do something different when loaded another time or in another context) you never need to load a module twice.

But one can apply the same technique (given real consistency) in dataflow update graphs. All you need to do, in this analogy, is to be able to tell when you're deriving something that has already been derived, and cause derivations that would otherwise create references to new but identical derived terms to create references instead to the existing terms.

If there is real consistency, then the order in which dependencies are resolved is immaterial. The worst that can happen is that you discover the same things in a different order or in a less efficient way.

Real Consistency?

I'm not sure what you mean by that phrase, but it sounds like you're using it as a substitute for 'idempotent'.

Please consider the following simple example:

a = 4
b = (a + 3)
c = (a + 4)
d = b * c

Initially, we can evaluate these: b = 7, c = 8, d = 56.

Now assume we change a to 3. A consistent result would be: b = 6, c = 7, d = 42. This can be achieved if our update order is [abcd] or [acbd].

However, in dataflow implementations that do not track dependencies, we might have an update order like: [abdcd]. Or [acdbd]. In these cases, d will temporarily possess an inconsistent value (respectively 48 or 49). Such designs are described by the phrase "eventually consistent" (EC).

For some observations in an EC design, there may be some 'real inconsistency'. For many problems, this temporary inconsistency is acceptable. For many problems, it is not. Sean's system, Glitch, is designed for the problems where it is acceptable. (Though, I think Sean and I have different opinions on 'where it is acceptable'.)

Beyond that, the update stream in the EC design is less efficient. In this particular simple case, the inefficiency is small and would not be noticed.

But now let's consider a more complex dependency graph, with dependencies encoded left-to-right (such that 'f' depends on e,c,i).

    / \ / \ / \
    \ / \ / \ /

In this case, if 'a' updates then an optimal update order is pretty easy to find: [abhecifdjgklm]. But what is the worst case order? Spend a little time coming up with horrible update orderings, such as one starting with: [aef gklm j gklm d gklm cf gklm d gklm j gklm ij gklm f gklm j gklm...].

In general, the worst case update ordering is exponential in the number of dependencies while (assuming no cycles) the best case is linear in the number of dependencies. Personally, I feel uncomfortable just waving such a significant performance gap off as inconsequential.

And keep in mind that every time we repeat a letter, we've seen some real inconsistency. Also, if we waste too much time, 'a' might change on us again. Poorly designed EC systems subject to periodic updates might NEVER exhibit 'real' consistency. Well designed EC systems might provide a (perhaps probabilistic) bound on how long it takes to account for an update.

Of course, tracking dependencies can be difficult. In an open or modular system, we might lack the global information to find an optimal ordering. In a dynamic system, the graph might be a little different every time we compute it. Systems also may have cyclic relationships. Many interesting system are open, modular, dynamic, and cyclic all at once. (My model, RDP, is designed for such systems.)

What can we do in those cases, to achieve consistency and avoid expensive wastes of CPU? Well, there are a number of designs that can address this - e.g. we can track or learn dynamic dependencies, we can lower the update priority of nodes that get updated often (like 'k', above), we can send an advance signal that basically says, "hey, an update is coming; prepare!"

In Sirea, I used a pair of techniques: an advance signal within a thread, and a staged batching technique such that all updates from other threads are processed together in each 'round' of updates (i.e. all incoming updates send their 'update is coming' signal before any of them are processed in a round). Sirea's design allows a guarantee of "snapshot" consistency (i.e. atomic snapshot-view of computations in other threads) which is very nice for reasoning about glitches in-the-small; it also tends to avoid worst-case orderings because batches from threads tend accumulate and be processed together.

Anyhow, a 'good' dataflow system should address both the consistency and performance issues somehow. I think pointing to resolution in a module system misrepresents the severity of these issues.

Just to note, there are

Just to note, there are problems where inconsistency is unavoidable: take any iterative algorithm that only converges "eventually," like a data flow analysis in a compiler for a language with loops (aka cycles). In fact, whenever you have cycles, you will have temporary inconsistencies no matter what. There is plenty of work in that community in coming up with "optimal" orderings given global information, but in practice, the results are the same as processing in random orders!

Adaptive orderings are probably one easy way forward: given that A and B are in the queue, and B historically has been influenced by A, process A first. But now you've made your worklist processing slower with additional book keeping, and it will take a while for that to pay off over random, if it ever does! On the other hand, your worst cases tend to be less bad when and if they do come up.

It is much better to take the static structure of your code and come up with perfect, or at least optimal, orderings, but if your language has indirection, aliases, or whatever...well, the problem becomes very hard and might not be worth it. And if you allow for code to change while the program is running, you'll have to re-run that static analysis often.

Cycles and Bookkeeping

In RDP, I deal with iterative cycles by formally modeling them as taking time - i.e. so each update is to a 'future' state. Inconsistencies don't need to be observable in this case (unless we try to read the future).

Regarding book keeping: in my experience, the book keeping is cheap and the payoff is relatively large. Even if we're leagues from the "worst" case, we are often a large factor (+20-100%, easily, even for small graphs) from the "best" case. And often a 20% savings more than outweighs the bookkeeping costs (which can easily be less than 5%).

Glitch traces dependencies.

Glitch traces dependencies. It doesn't go for a global view because just because A led to B being invalidated, that doesn't mean C will be invalidated; we must reexecute nodes before knowing whether they cause downline changes. The only decision we have is if N nodes are invalidated by changes that happen at the same time: is there an optimal order for re executing those nodes? Should we bother trying to find that order? Does static anylisis help?

Of course, if on a change you can know all that will change as a result, your language must be very inexpressive. I suspect we have similar systems but you somehow know more about the graph given that your language is declarative?

There is no global analysis

There is no global analysis in Sirea. RDP is declarative, but also open, and supports runtime behaviors, potentially distributed. Since Sirea was a proof of concept implementation, I avoided anything I can't obtain in a limited trust distributed system.

We don't need an optimal ordering to benefit. If you can ensure progress, fairness, stable performance - that's good. If you can remember a few relationships and make smarter decisions, it will often pay for itself.

Perhaps you're too optimistic that "random" works well? Dataflows often have fan-in followed by large tails (like the gklm above). Even if you can avoid some tail reps or "convoying" update patterns, that can be a big improvement.

Glitch is procedural, any

Glitch is procedural, any non-local (non-parent/child) data-flow relationships arise from reading/writing shared state. For a compiler, the main non-local interactions between the nodes is through the type system (the typeless one), so the disturbances are on average actually quite small; the ripples in the pond fade quickly. Now, you could change some core type (like java.lang.Object) used by everyone, and that would effect everyone, we are screwed in any case if that happens, no matter how smart we are. The same happens if we change some core syntax used everywhere in the test program being compiled.

It is possible that some procedural programs have large tails, but I would prefer to talk about real programs rather than theoretical worst cases. My hunch is that the realistic bad cases have many bad things going for them anyways, while the average cases behave well whether we do something very smart or very simple.

Behaving Well

It sounds like your main test case is very well behaved. Those conditions where state stabilizes quickly are very nice, and I try to achieve them by design where I can. You might be getting a biased view of the "average case".

My own experiences use time, of course, which will certainly affect my own impressions on the typical use case. With time, more than one thing changes (at a time). With loops or fan-in, convoying patterns down a tail are really common unless I design against them - kind of like a heartbeat (in 'gklm' the 'm' might be processing the last heartbeat while 'k' is starting to process the current one).

I'm positive my test case is

I'm positive my test case is "biased." What I'd like to get is some concrete examples of applications that are (a) not well behaved incrementally (changes tend to cause cascading re-computations) and (b) that they misbehave in such a way where being "really careful" with node processing would actually cause them to behave well (i.e. a majority of the re-computations are redundant and can be eliminated if we are really careful). It is a quite simple example to ask for, I don't want to be fighting theoretical bogey men as I don't have time for that, and I think our focus on these bogey men is extremely misguided.

My hunch is that real applications that are in (a) are just not in (b). Even when you involve "time", say in a simulation or a distributed system, if you have either have a nice system where changes are fairly isolated and just ripple in the pond, or you have a hurricane where anything that you do isn't going to avoid re-computation.

You misunderstand the

You misunderstand the purpose of the bookkeeping. The purpose is NOT to magically transform volatile systems into stable ones. The purpose is to avoid wasted computations, such as those using values that have a high probability of being altered by an already pendng upstream computation. We also want to promise that no node or component falls too far behind - i.e. a sort of temporal window that represents 'fairness'.

Even systems that are "well behaved incrementally" can benefit. Well-behaved doesn't mean near-optimal. E.g. if you have two sequential updates to the same state within milliseconds. If you process them one at a time through the graph, you'll have paid twice as much, unless the second computation somehow "catches up" to the first one. When there are many asynchronous, periodic update sources - e.g. a dozen robots each sending location, status, and a few other messages ten times each second - the amount of waste can build up very quickly, even if each update independently is incremental.

I have a feeling we won't be

I have a feeling we won't be able to argue much better on this until I have a comparable system, as I'm looking at incremental computation in the absence of time (progression) right now.

That being said...

When there are many asynchronous, periodic update sources - e.g. a dozen robots each sending location, status, and a few other messages ten times each second - the amount of waste can build up very quickly, even if each update independently is incremental.

Has anyone done any experiments to see what the real impact is? Or is it what they mean by "time leaks" in Haskell?

Time leaks in Haskell are a

Time leaks in Haskell are a completely different problem.

I am not aware of any experiments that study this in a controlled manner.

Time leaks arise from laziness

Suppose you have a recursively-defined stream of values, like

   ints : int -> stream int 
   ints n = n :: ints (n+1)

Now, in a lazy language, when you unfold the definition, the term will look like:

  ints 0 = 0 :: (0+1) :: ((0+1)+1) :: (((0+1)+1)+1) :: ...

A lazy language will not force any element of the list, unless it is actually requested. So if you have a client of ints 0 that only looks at (say) every 10,000th element, then a huge 10,000-element thunk will build up until it is eventually forced. In a strict language, every element is always forced, so you would never need more than one word to store the int.

On a completely unrelated note, if you want to find bad cases for incremental computation, you might try looking in Umut Acar's PhD thesis. IIRC, he has a formalism called "trace stability", which you can use to figure out when (his kind of) incremental programs will be efficient or not.

Thanks! I'm still going

Thanks! I'm still going through Acar's work, but its slow going. Any tips on what to focus on are appreciated.

I seem to have know this about time leaks before, but keep letting that slip out of my mind.

You're right that I was

You're right that I was drifting offtopic, but the point is still valid.

It beats the other active clusterf**k topics that don't seem to end.

All you need to do, in this analogy, is to be able to tell when you're deriving something that has already been derived, and cause derivations that would otherwise create references to new but identical derived terms to create references instead to the existing terms.

This is what we do, except that it is kind of a heuristic unless some sort of rigid structured editor is used.

please blog

i know it isn't your responsibility to educate the kids on the lawn, etc., but it might be a great service to plt humanity to concisely note what Elm (and others e.g. maybe knockoutjs, etc.) is doing that is already known to be doomed. :-)

Our argument on reddit

Our argument on reddit should be public :p. I'm negative on FRP in general these days, but Elm doesn't even learn the lessons of FrTime or FlapJax.

I'm not at liberty to comment on knockout.js, they didn't publish a PLDI paper :) As far as I can tell, all the data-binding frameworks are more similar to WPF with nice Bling syntax than FRP.

somebody summarize?

i haven't found it yet, maybe it does/not exist? reading the reddit thread, there are several issues in the frp world that seem to be unclear to most people, even people who are doing frp. :-) i wish there were a wiki page / table that tried to break down the issues. arrowized vs. something else; how the graph is updated (flapjax vs. elm vs. glitch vs. ...); signals vs. events; when things can/not be leaked; what can/not be composed. having a giant table of these things would be wonderful for expanding the audience i feel. i'm not clueful enough to do it, only to want it!

Functional Reactive Physics and Objects

A few good quotes from the thread:

Pure FRP and time-stepped physical simulation are generally not very compatible. [..] As far as I know, no one in the FRP community has been able to come up with a decent physics engine so far; to do so is probably worth a PhD thesis itself! -- Sean McDirmid

never seen FRP do a serious physics engine in a compositional way [..] The promise of FRP is to do things compositionally. And it works for trivial examples like pong: you define the position of the ball as the integral over its velocity, you define the velocity in terms of the position, etc. The trouble is that this doesn't work for a serious physics engine. You quickly end up with a world step function -- Jules Jacobs

I believe that a compositional 'FRP physics or game engine' would consist of adding lots of small FRP objects (or software agents) to the larger engine.

From the physics/game engine, each object would receive continuous information about all the forces and signals it can observe. (I'll assume some forms of optimization is available for ignored signals.) Each object would output continuous signals describing its own actions in terms the physics model or game engine can observe and understand. Internally, each functional reactive object may be composed of more objects that do the same thing, but perhaps operate on higher level signals (e.g. after semantic processing of low-level physics signals).

The engine would be a 'higher order' reactive system, processing a large collection of independently reactive objects. It would track some information about each object, such as position and orientation, and would be responsible for computing which signals are observable by each object within the system. A major challenge would be optimize this: e.g. objects that see don't necessarily need to 'see' in every direction at once, nor do they need to see through opaque objects, and even some level-of-detail processing might be reasonable.

Fortunately, we could draw on a large amount of expert knowledge from developing scene-graphs and physics engines.

For a gaming system, we would want to augment the incoming "physics" signals with external control signals, and also support some output signals from objects that describe what is sent back to the players.

Overall, I don't see why an FRP physics engine shouldn't operate a great deal like existing physics engines.

We would need some support for collections processing ('foreach'), and corresponding support for dynamic behaviors (adding behaviors to a collection, and perhaps self-removal or removal by name). We don't need heterogeneous collections or signals, but they would probably be convenient.

The idea of taking OOP and replacing procedural methods with continuous signals is, I think, a pretty good and simple idea. It would also be a good fit for FRP, which naturally encapsulate state. The engine itself would still essentially be a global step function, but would be 'extensible' in the sense that we can always add more objects to the system. The engine as a whole could also be compositional, if output the state of one physics engine as the observable signal to another.

One could always hide the

One could always hide the physics engine underneath the FRP engine: inputs are geometries and collections of forces, outputs are read-only simulation values. Collision detection/reaction just happens under the covers based on constraints configured from the outside. This is quite easy, but it doesn't allow for very much flexibility (it would be impossible to come up with a completely flexible simulation engine underneath, it could work for one game engine with rigid body physics), and I don't think this is really FRP, at least not pure FRP.

Not "hiding" a physics engine

Every 'object' is a first-class FRP behavior whose geometry and color is an output signal, an internally computed consequence of the signals it has experienced. The physics engine (itself implemented in FRP) handles orientation, location, velocity, and determines what signals each object experiences (light, sound, collision, scent, etc.). Many of these objects might be rigid geometries that basically ignore most or all of their input signals. That's certainly an optimization to consider. However, many of these objects could be reactive, e.g. changing shape and color based on collisions, or changing direction based on light or sound. Further, the reactive objects would internally be constructed of more such reactive behaviors.

Control signals can be modeled as part of the physics environment, e.g. as a special frequency of 'light' that only objects attuned to it can 'see' (one could use sparse capabilities to identify such frequencies). Output signals can be handled similarly. We don't need to extract our FRP-objects from the physics engine to interact with them. They can live and die, and perhaps even spawn, by their own will.

This is true FRP. It is true FRP in the sense that having a bunch of independent, FRP-robots and FRP-objects in an FRP-universe is lots of FRP and nothing but FRP. It is true FRP in the sense of involving a great deal of deterministic, synchronous concurrency based on time-varying signals and (potentially) events. I do assume dynamic, higher order FRP, with support for processing collections of signal-functions or 'behaviors'. Not every FRP implementation has this feature, but many do.

It's also very flexible. Flexibility is determined primarily by what sort of signals the engine provides and expects. Some physics engines won't be able to model objects breaking into pieces, spawning children, or being absorbed. Others will.

I am curious how you interpreted what I described above as: "hiding a physics engine" good only for "rigid body physics". I was describing something much more expressive (and probably much less efficient) than that.

I was just being pragmatic,

I was just being pragmatic, I didn't interpret what you were saying as "hiding a physics engine".

I kind of get what you are saying, but it goes against my natural intuition about the problem. In the natural universe, physics is sort of hidden under the covers, it is actually the computer that is running us in a very non-functional way. So I think any system that attempts to simulate physical behaviors should be expressed the same way: physics is just one opaque layer below some other sub-system where we can actually exert control. FRP seems to muddle that relationship by throwing everything together. I don't get a sense of encapsulation or modularity at all.


I have a different intuition. Physics is "all around me", like I'm swimming in a lake of physics. It makes sense to me to model physics as an outer shell, a time-varying environment into which I inject objects, perhaps even some reactive fish.

You seem interested in modeling physics without an explicit engine, without even an explicit physics context. Is this right? I agree that FRP doesn't make this approach very feasible.

Turtles all the way down

I see physics as something to modeled as an interpreter that then executes a program that "exists" within it, just like we are forced to deal with physics in real life and can hardly modify it, because it is running us, not the other way around.

Then why do you have an

Then why do you have an issue with modeling physics as an 'interpreter' (environment) that 'runs' a bunch of FRP objects that 'exist' within it?

IIRC, I've seen you provide 'springiness' examples where each object is 'running' its own approximation of Hook's law as a set of iterative constraints. Isn't that exactly the opposite of what you're saying now?

If we explicitly include those position constraints or spring equations in our code (except as part of a separate interpreter) then are we properly programming with physics?