This Friday: First Class Functions @ NEPLS

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!

First Class Space-Time Functions

Let's take a trip into the esoteric for a few minutes.  Here's a corner of my spatial computing work that I've been nibbling away at for a while, which I think may be one of the most important theoretical questions I'm engaged with: how can we define first-class functions over space-time?


Let me unpack that wedge of words a bit:

• Function: by this, I mean a function in the programming language sense: a chunk of code that we can run in order to do something or other.
• First-Class: this means that we can treat the function as a piece of data, passing it around in other pieces of code, constructing it on the fly, changing bits of it, and so on.
• Over Space-Time: here I throw in the nasty bit: I want this function to be something that, on the one hand, I can think about as an operation over a manifold, and on the other hand I can implement as a distributed computation on a whole lot of scattered devices.

First-class functions, just as themselves, have been around for a long time in computer science.  Distributed algorithms have been around for a long time too.  There's even been some nice work on programming models for code that moves around from device to device like data (Marco Mamei's TOTA system, for example, or the code in Bill Butera's paintable computing system).


None of that, though, lets you step back and get a clean global view of what's going on with your program, and that's what I want.  I want (in the way I usually do with Proto), to be able to write code for the aggregate, and compile it to execute on individual devices.


My first stab at this was in 2009, in this paper for the Spatial Computing Workshop.  That came at the problem from the bottom up, worrying about how you can tell whether two executing processes that started at different points where the "same" or not.  I proposed some mechanisms that were way ahead of what the Proto compiler could support at the time, and we're *still* catching up to be able to try them out.  But in the end, what this paper basically said was: this is a serious problem, and none of the straightforward mechanisms work, so let's give it to the programmer to deal with.  Have fun!  Good step forward, but not enough.


The next stab was from the top down, as part of the 2010 Spatial Computing Workshop paper where I proposed a basis set of space-time operators.  This was really asking how we could define space-time computations without reference to a particular programming language, and part of that was coming up with a (very abstract) definition of a space-time computation.  So you could certainly fit first-class functions over space-time into the model created by this paper, but it didn't give any recipe for how to do so.


Most recently, Kyle Usbeck and I put together a precise model of Proto function calls (for SCW'11, where else?), and used it to get some of the things you want out of first-class functions.  But once again, we had to stop short of the full goal---and in fact, ran into a clear problem caused by closures (the use of variables in the definition of a function).


So: what exactly is the problem?  Why are first-class functions so hard?


Here's my current understanding of the problem:

• When a first-class function is evaluated over space-time, the data values it manipulates are fields over manifolds.  No device knows all these data values, because they're stored locally at the devices representing particular locations in the manifold.
• When a first-class function acts like data, it can be stored as a value at a particular location in the manifold, and moved to another location.

So that means any data fields used as part of the function definition can't all be stored when the function acts like data, and the function can move around to places where its data fields aren't even defined.  This rules out really standard first-class function tricks like partial evaluation: if we take function f(X,Y) and make a new function using field Z for X, g(Y) := f(Z,Y), then we have no way to assure that Z gets carried around with the function in a meaningful way!


I am undaunted, though.  I think the solution is going to require us to take a much more nuanced view of what "defining a function" and "evaluating a function" actually mean, but I think that solution is out there, and that when it is found it will be extremely important for the future of all of our networked systems.


Perhaps you, dear reader, have a brilliant insight that will resolve this dilemma?  If so, I'd love to argue it with you...

As Below, So Above.

In research, you know you're onto something good when extending an idea into new and more complex domains turns out to be elegant and simple. I had that experience recently with my Zome work when we took a serious look a extending into dispatchable demand and distributed generation.

One thing that never ceases to amuse me about the world of the power grid is how all of these closely related ideas get their own individual and unique names. Maybe that's just my perspective as an outsider entering the field, or maybe it's a result of the type of technological approach we're using, that lets it all be much more unified, but several times now an initially really opaque and thorny looking problem has turned out to be something that looks just like what we're able to do already, only painted a slightly different color.

So, from atop my mighty 30,000 foot view:

• Demand response = stuff that you turn off in order to save power 
• Dispatchable demand = stuff that you turn on in order to burn power 
• Distributed generation = stuff that you turn on in order to make power 

OK, so that's oversimplifying it a bit too much, but from the perspective of the ColorPower algorithm, the categories collapse nearly that simply. Clarify some definitions, follow the consequences out as they ripple through the specification, and bam! Two new thorny power industry problems turn out to be able to be handled with the technology I've already developed... I tell you, that's the best damned feeling you ever get as a researcher.

Dealing with potential phase shifting on the other hand... that's still a daunting idea for me, and one that I'm glad we don't have to deal with quite yet, though I've got a few ideas now...

Noted Scientist Gives Interview

Dear reader, today I have the distinct (if somewhat unnerving) pleasure of announcing my online video debut.  BBN has decided to promote itself by making some "Meet the Scientist" videos, and seems to have decided that my work will be interesting to the masses---which delights me no end, since I think it's pretty cool stuff as well.  In any case, today the one featuring me has gone up online:



It was a lot of fun making it (especially having Kerry, the videographer sitting in on the morning tea that Aaron & Fusun & I have, and listening to us argue about biology concepts), and I think it came out pretty well.  Enjoy!