Lambda the Ultimate

I'm not a big fan of messaging passing in this case, as it basically gives up on composition at the level of values. You could create nodes that then compose the values via message passing, but we are back to square one!

I'm not sure if this was clear, but there is also a matter of time as well other constraints; "thunking" a future means halting until the future's CPU value is computed, thunking a signal gives me the current value of an FRP expression without the benefit of update (thunk with observe could do that). There is also something about space that goes beyond memory; say I express logic to compute the color of a pixel, but what pixels are actually computed depends on rasterization; they aren't discretely addressable. We might also have values from a secure world where thunking is impossible and we can only manipulate them using certain APIs (to prevent private user info from leaking from the program).

I consider Batches to be a technology for bridging computational worlds. The idea is to partition code that refers to and uses results from an "alien API" into two parts: the local code and the alien code. The system then optimizes the communication to transfer data in bulk, and sends the alien actions as a script that is executed in the alien context. You can think of the partitioning as being based on "binding place analysis" much like "binding time analysis" for partial evaluation. The place analysis allows staging by place, rather than staging in time. Oracle has encouraged me to release batches as a proposed future feature of Java, and you can try it out in my fork of OpenJDK "javac".

I can't believed I missed this paper! Bling does something very similar ("binding place" analysis) but in a value-oriented rather than control-oriented, decent fro the problems I was trying to solve (reactive and GPU programming, consider that the expression that is assigned to the color property becomes "transported").

"batch" seems to be a control-flow oriented world change: the data world under the batch is native while the CPU world is alien, but you can still refer to it (e.g., System.out.Println), where the operations are then stored up and executed in a single transition at the end of the batch. But I'm thinking that the batch calls shouldn't necessarily exists. Instead, "music" would have APIs callable from the native world, where the results (as 2nd class values) and effects of these APIs are not directly observable from that world. Of course, this would require an explicit flush somewhere, and depending on the data topology it might not bring over data as efficiently.

I agree that automatic coercion between worlds isn't ideal; it should be more like an explicit coercion that gives us awareness over the costs of the conversion (e.g., a shader register for CPU -> GPU coercions). On the other hand, if the cost is effectively free and the conversion is semantically lossless, then an implicit coercion would probably be acceptable.

I guess I'm really looking for a low overhead solution here, I mean, a language that is a smaller delta from what programmers use today that adds 1st class support for 2nd class (alien) values that don't scare away most programmers. I know this is commonly done in Haskell, but the support (a) still seems to be somewhat of a pattern and (b) requires some amount of unconventional thinking associated with programming in Haskell at all.

Even between lightweight threads, I would find it difficult to agree that conversion is "effectively free". (It might not require routing or copying, but there is still a scheduler delay, a potential move to another CPU's cache, possible synchronization.) But I agree that "scaring away most programmers" is something to avoid.

A point to consider is that something like `cross` becomes part of a communication model, serves a similar role to channels or pipes. It isn't so difficult to support partition types if developers only need to be vaguely aware of them at certain communication boundaries (except, of course, when they are writing the communication abstractions). I think that, even applied heavily, partition types are not likely to disrupt most programmer experiences.

In any case, all you need for alien types are: abstract data types and operator overloading. (Haskell uses typeclasses for the latter.) The primary technique is to abstract the constructors for a value, i.e. so that we aren't modeling this as creating CPU integers then converting them, and we are instead capturing code that creates the integer.

In Haskell, most of the control-flow abstractions (Applicative, Arrows, Monads) each allow embedding of arbitrary Haskell values (pure, arr, return). This has proven a weakness for generalizing these "patterns" in Haskell. We really need to say that only some values can be converted, and even then only at certain times and places. There has been some work at generalizing the control flow models so they do not assume a language that is a superset of Haskell (cf. the Categories package and Adam Megacz's Generalized Arrows). Using these more generalized control abstractions, we can apply type-level transformers to lift from software design pattern into proper abstraction.

I believe one could leverage Cook's Object Grammars to a similar purpose. I am planning to pursue Object Grammars further, as they are much closer in nature to the partitioned model already (unlike typeclasses, which push overloaded behaviors to a global space).

Even between lightweight threads, I would find it difficult to agree that conversion is "effectively free".

I prefer to optimize the programmer's time where feasible. I like the idea of a compiler err-warn that allows the compiler to "figure it out" while prototyping, then allow the programmer to debug and optimize the cost of what they've done rather easily. Ya, thunking this future 'here' is expensive, but if you must...

In any case, all you need for alien types are: abstract data types and operator overloading. (Haskell uses typeclasses for the latter.) The primary technique is to abstract the constructors for a value, i.e. so that we aren't modeling this as creating CPU integers then converting them, and we are instead capturing code that creates the integer.

This is what I did in Bling, but I found it to be completely unscalable (for C#), where some sort of auto-lifting of safe functions would be nicer.

I really need to spend time on grocking the object grammar work; incidentally, this idea first came up when I was talking to a colleague about his recent ecoop paper.

I agree with optimizing the programmer's time. I touched on this when I mentioned `auto-wiring` earlier, but it would be easy to miss in a wallotext.

You and I have, several times in the past, discussed the possibility of soft constraint-logic systems or similar to "fill the gaps" in a partial specification, allowing programmers to work at something closer to a sketch or pseudocode level (and gradually improve the constraints on a system). That sort of feature remains a significant part of my vision for unifying UX and PX. I imagine such systems working at both development time and at runtime (depending on where the programmer wants to use them).

I feel that programmers should be explicit when they want the auto-wiring; explicit doesn't mean verbose, but it is different from automatic coercion. To the extent developers abstract strategies for a constraint-logic system, they will need to be explicit about which coercions are available. The underlying logic needs to be very formal and precise and under developer control, even if the decision heuristics for strategies and preferences are fuzzy.

Automatic coercions imply a built-in heuristic that is difficult for developers to control. Similarly, you're suggesting built-in "err-warns" (nice noun-verbing there :) where I would wish for developers to build warnings into their own heuristics (e.g. via annotation of low-preference or high-cost strategies, or reflective observers on them).

Efficiency is another problem with being too explicit. Often in a GPU computation, the best partitioning for the computation depends on what the encapsulated functions called do. For example, setting up a global parameter (CPU -> GPU) explicitly means you must decide before you call the functions that mix the CPU value with the GPU values, but its very possible that the run-time encode this transition much more efficiently as a larger sub-expression according to what the function does.

I even play a trick in Bling where the vertex/pixel shader computation are considered together, and we only force some computations down into the pixel shader (where they are necessarily less efficient) by stating that some expression is computed at a pixel granularity (e.ToPixel); the run-time then figures out the largest sub-expression that can be computed solely by the vertex shader (not contaminated by a toPixel value), which is then passed as a parameter to the pixel shader.

The only alternative that I can see recodign all the logic explicitly, so if your triangle hypotenuse computation mixes CPU, vertex, and pixel values, you'll have to recode it and divide the computations accordingly to get the best efficiency.

You mention granularity problems, e.g. lots of small `CPU->GPU` operations instead of one bigger one. That seems more an artifact of control-flow languages. The declarative nature of data-flow makes a lot more techniques available to optimize granularity of communication. For RDP, I batch updates between partitions. The batching supports multiple objectives: snapshot-consistency, efficiency, minimizing physical synchronization. Within Sirea, I also use a bounded-buffer abstraction - i.e. a bounded number of batches in-flight - to ensure fairness and soft real-time processing. I expect you could use similar mechanisms in Bling, with a clever application of buffers, so long as you make any feedback asynchronous.

Some of the optimizations you mention (the toPixel tricks to push more code to the vertex shader in Bling) are quite specific to the problem domain. I doubt you could achieve them readily in a generic way, i.e. without knowing a lot about the targets. If you were to develop a more generic or general-purpose model of Alien types, how well would this work for you? I think not so much.

I have been developing a relatively generic strategy to improve efficiency and robustness in a system without changing the logic: implicit code distribution or replication. Code distribution can drift in either direction. I.e. if you invoke a remote service, some service capabilities might expose part of their code to you (so you can make service-decisions locally and reduce overheads). Conversely, you might expose some capability code to the service (e.g. so the service can access your policies and preferences without a round-trip). This code may be shared further, e.g. if a service invokes another service to support your request. Automated code distribution is constrained orthogonally to the object capability model - discretionary security, based on certifications of trust and equivalence, and discretionary acceptance to host the foreign code rather than invoking remote caps.

Logically, such code distribution never happens; the round-trip still occurs (and is, thus, still reflected in latency). But the physical cost is much lower. And efficiency is much higher. (There is, of course, a more explicit form of code-distribution available - by sharing a representation of code that hides nothing, aka a "value" instead of a capability).

In addition to that, of course, one can meta-program, e.g. leverage a weighted constraint-logic to build a low-cost program. This avoids the over-specification that sometimes leads to inefficient programs.

When going from a world of lower frequency (fewer updates) to a world of higher frequency (more updates), it makes sense to partition computations as coarsely as possible. We might be able to generalize that into a principle that as much work should be done in the native world before the value is transported into an alien one. However, there is a cost as transporting more coarse grained values might be more expensive than transporting fewer fine grained values to be composed in the alien world; e.g., consuming global parameter registers for a CPU to GPU transition. The GPU infrastructure might be able to optimize in that case, being able to identify redundant computations that depend on static global parameters (they can't change during shader invocation), and reason about whether resources are available to cache their results in extra registers. But GPU programmers really don't trust/rely on the infrastructure to be that smart!

I'm not exactly sure if we are talking about the same thing. I'm just interested in mixing 1st and 2nd class values from a more traditional model of computation (at least, it should look like POC - plain-old code - as much as possible), while you seem to be tackling a much more comprehensive problem. That's quite all right, but I would really benefit from seeing a more focused discussion of your ideas/work...like in the form of a technical paper :)

Initially, I didn't follow your first sentence. Then I realized you interpreted the fine-grained transfers as being on the temporal dimension. I was thinking about the spatial dimension - i.e. rather than updating one integer three times, update three different integers in one batch. This is useful regardless of frequencies.

That said, I do support the temporal dimension. Sirea partitions will process all the batches received at the start of each round. In some cases, that might mean combining up to six batches from another partition. (Six is the default bounded buffer size for batches in flight in each direction between each pair of partitions.) This helps a slow consumer keep up with a fast producer, allowing frequency disparities of up to factor six. The performance properties are quite different compared to systems that use bounded buffers but only process one input at a time.

This is made possible in RDP due to its temporal semantics. I.e. a batch can tell me about future values (value @ time) without overwriting information about past values.

For a GPU, I don't have as much freedom to represent the temporal semantics. Well, it is possible to model some shader variables as temporal splines (they cannot change during shader invocation, but they can model change - e.g. for motion blur, temporal anti-aliasing, and efficient simple animation over multiple frames - tweening, rotating, swaying), and even to model some temporal attributes with vertex attributes. But the translation effort to the GPU is high enough that I feel it's wiser to consider these almost orthogonally to the communication and update model. Though, I would certainly leverage recorded history or anticipated future when computing animations, shaders, or shader variables.

You seem interested in combining a mess of code from both the CPU and GPU then teasing it apart, disentangling it, with a sufficiently smart compiler. You'd face problems such as "what is the largest sub-expression that can be shifted to the GPU?". I can see the motivation for such things, but I'd prefer it be left to staged programming (even if we make it look like plain old code via syntax or similar), with the more formal and generic partitions model underneath it. (For my approach, I imagine some sort of specializer or JIT would be desirable to optimize stable code that is glued together from lots of small first-class functions.)

In some sense you're discussing partitioning: how to managed values from multiple partitions within a program in a straightforward manner.

A somewhat orthogonal (I guess that's like being a little bit pregnant) view on this partitioning problem, specifically in graphics, is this excellent paper on Halide, a system which separates graphics algorithms from the schedules used to execute those algorithms (where "schedule" is a spacetime schedule, e.g., describing both spatial and temporal partitioning).

The main valuable insight here, as in many other domains, is that scheduling details are critical for performance but irrelevant for correctness, so separating them linguistically simplifies both the algorithm description and the schedule description.

Looks like a nice paper. Thanks for the link.

If valid, I would expect such abstraction to be supported. But how could that go into today's languages?

Inferring code contracts from check constraints in a tool like Linq2Sql's sqlmetal seems feasible.

Very nice. I might need to look into that sort of modal logic for some of my own work.