Apropos of my discussion of distributed first-class functions last week, I'm going to be giving a talk on them this Friday, at the NEPLS - the New England Programming Languages and Systems Symposium Series.
As I've been working on my slides and thinking about the problem, it's becoming more and more clear to me that the basic problem here is a breakdown in the mapping between aggregate and local views of a program. You see, the really key thing about Proto (or any aggregate programming language) is that when you write a program for a group of devices, there's a well-defined mapping that transforms that aggregate-level program into a program that can be run on individual devices.
Consider distributed distance calculation---one of the all-time favorite canonical examples. If I want to run a program that computes the distance to a set of source devices, then I describe that as setting source devices to be distance zero, and all other devices apply the triangle inequality on estimated distance through their neighbors. There we go, nice simple aggregate model.
That then gets transformed into the programs to run on the individual devices, which include details on how a device should format messages to its neighbors about distances, how it should interpret messages from its neighbors, how often to send the messages, how to walk through the neighbor information when it's computing the triangle inequality, etc.
None of this is terrible complicated, but that's because we're going from aggregate to local. The other direction, often termed "the local to global problem" in the complex systems community, is proving quite intractable. In fact, that's why we create aggregate programming models in the first place---it's just too damned hard to figure out what's going to happen with the aggregate if you're trying to write programs for individual devices!
So how does this impact the problem of first-class distributed functions?
In Proto, when we make a distributed function call, we're currently depending strongly on an assumption. That assumption is that the space where a function is called is the same as the space where the function call is executed. All of our aggregate-to-local transformations depend on that assumption right now, because they use those spaces to determine what goes into the messages that devices send to one another. If we have first-class functions, though, and determine what function to run at a device based on the value of a field it's computed, then this assumption no longer holds: the same function call can result in different functions being executed at different parts of space! In order to understand what happens, we have to go back to the local-to-global problem, and everybody knows that's no damned good...
What exactly to do about this is not yet clear, but the better that we understand the problem, the more likely we'll be able to find a way to wriggle around it. And so that's why I'm going to NEPLS: to bounce the problems, in detail, off of a bunch of sharp programming language folks and see if something useful gets sparked.
Next week: the Spatial Computing Workshop at the multi-agent systems conference!
No comments:
Post a Comment