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!

The Long March on Characterization

My synthetic biology work, like that of many other computer science-ish folks who have entered the field, sometimes feels like it's entirely a matter of recursion and yak-shaving.

Let's review the motivation: I got into synthetic biology from spatial computing, as a potentially really interesting and important application area. Cells, you see, can be viewed as computing devices, and a tissue, colony, or biofilm is a collection of locally interacting cells that clearly may be viewed as a spatial computer.  That's one of the original drivers behind the amorphous computing project, where I did my graduate work, alongside synthetic biology pioneers like Tom Knight and Ron Weiss.  They went down into cells, while I went up into the abstractions.

Spending time around the synthetic biology folks, I naturally got interested, and eventually realized there's a tight match between the computational models in Proto and the semantics of genetic regulatory networks. Wonderful! Now all we need are some well-characterized parts, and we can apply compiler technology and automatically generate designs for multicellular organisms and the whole shebang...

All we need...

All we need is something that the field of synthetic biology has been struggling with since its inception. What exactly does it mean for a part to be well-characterized, and how do you use a well-characterized part to predict the behavior of a composite circuit? Hell, what is this "part" thing of which you speak, young padawan?

When we started the TASBE project in Fall of 2010, working with Ron's lab, we quickly realized that the existing data wasn't up to the standards we needed, and set about improving the methodology. You biologists in the audience should begin to laugh knowingly at this point.

It's been a long, long march, but we're seeing things that (to the best of our knowledge) nobody's ever seen before, and modeling things that nobody's ever needed to model before. We've had preliminary results better than anybody else has ever seen, then been convinced by the higher resolution data that we needed to study things yet more. And maybe, just maybe, we're finally there...

The long march continues, but the destination is in sight. And if we get there, then it will be a big step forward for synthetic biology.

And maybe then we can start thinking about the cells as spatial computers again as well...

The Power of Visualization

One of the really important steps I made recently in the Zome project wasn't really a technical step at all. Or at least, not as I usually think of as being technical. You see, I changed how we graph our simulations.

Big deal, right? Well, Old Me, that's a very math-chauvinist way of thinking. Spending a lot of time with my colleague Aaron Adler at BBN, I've come to appreciate just how important a good user interface is. In fact, I'm coming to think that even just calling it "user interface" is inappropriately dismissive. How we visualize things is how we think about them, and any good AI researcher will tell you that representation is everything.

Enough beating around the bush. When we're visualizing how power is getting managed using the ColorPower algorithm I'm working on with Zome, I now show it like this:

There's three classes of power there: green is really flexible, yellow is less flexible, and red is not very flexible at all. We always want to turn off green appliances before yellow appliances and yellow before red. I'm stacking the power on top of each other, so you can see how much is being used by area. Solid colors are currently enabled, pale colors are currently being restricted by the algorithm, in order to meet the goals showed by the black dashed line. The blue line under it (hard to see it's so close!) is how our algorithm is actually performing in simulation. The cross-hatched areas are devices that recently switched on or off and so can't be changed again for a while.

This simulation is a "hot summer day" scenario, when we're being asked to curtail power. The thing to notice here: we're doing damned well!

Now, here's the old visualization:

Horrible, ain't it? Even I have a hard time telling what's going on, and I wrote the thing!  I rest my case, and thanks to Aaron for his suggestions and also to Kyle Usbeck for being my independent test subject.

Tech Report on Biological Part Characterization

Last year in synthetic biology, my TASBE project spent a lot of time sprinting hard in the lab and producing new results.  This year, we should finally finish writing up a lot of this material and hope to end up with some nice articles reporting it all and laying down the foundations for a new and more integrated approach to predictive design of DNA circuits for controlling cell behavior.

Perhaps the biggest effort over the past year has been improving the characterization of DNA parts: in order to design cellular controls effectively, we need to be able to quantify fairly precisely how gene expression (the output of our computing devices) is regulated by the concentration of transcription factors or other such input signals.  We started out without this as a goal, as there have been excellent claims with nice looking curves for years, but we quickly found out that the prior methods just weren't up to our requirements.  (You see, suitability for computer automated design is actually a much stricter test than ability to pass even the most stringent peer review, since the computer doesn't know a damned thing about the field and can't fill in any gaps from experience).  And thus began a long and magical journey that I'll probably say more about in a future post...

Bottom line: we've got a new and better methodology, which combines a little more experimental work with a lot better analytic methods, and it's giving us the data we need.  And now, in this Characterization Tech Report, we're sharing that method with the rest of the world, since we want other people to produce usable data as well...

Soon, we should have a web service up that lets people use our whole suite of software tools as well... stay tuned...

Spatial Computing Workshop 2012: June 5th at AAMAS in Spain!

This year is the fifth anniversary of the Spatial Computing Workshop, and it's first year at AAMAS---the big multi-agent systems conference.  Previously, the workshop was always at IEEE SASO, the self-adaptive and self-organizing system conference, and it was a good home, but a relatively small conference.  We're hoping that AAMAS's order-of-magnitude larger attendance will attract a larger group of attendees and be a good next step toward eventually setting up an independent Spatial Computing conference.  The preliminary list of talks has just been announced, and I'm excited to hear the stuff that my colleagues have submitted.  I think it's going to be a damned good program... come to Spain and join us at SCW'12 on June 5th!

Zome!

One of the threads of research that's really got me excited these days it my Zome work. That's Zome as in Zome Energy Networks, a company that I helped get started, based on the distributed energy management work I did at MIT during my postdoc.

The thing that really sets Zome apart from the rest of my work is that it's about this far from actually changing the goddamned world. The other things I'm working on I think are really cool and important, but the path to getting out into the field is much longer. With Zome on the other hand, we're talking about possible pilot projects in the next year or two. And "pilot" seems to mean a huge lot more houses to the energy industry than I would have thought when I was but a poor postdoc proposing to wire a couple dozen appliances to radio-controlled switches.

So, in a nutshell, the big idea of the Zome work is this: we put a vast number of energy-consuming appliances under distributed control, using an algorithm and architecture that I developed. The elegant thing is that, because of how the algorithm operates, even though the electrical utility gets a knob to adjust up and down the amount of power that's being consumed, individual consumers like you and me never have to feel like Big Brother is breathing down our necks. You see, the appliances never give up power unless we're willing, we always get an override, and all the most sensitive information stays inside the house. The aggregate information that goes upstream has all sorts of appliances from lots of different houses combined together---because otherwise it's just too hard to ship bits fast enough---and that gives security by obscurity. It's an idea that I learned to appreciate from my friend Rachel Greenstadt's thesis, where she showed that distributed constraint optimization could be made more secure through aggregation of information. What we're doing is similar thematically, though it's different in pretty much every way technically.

In any case, Zome's been really cooking along recently, and we've had some big results that I'm writing up now---hopefully for publication in the not too distant future. And that's why it's one of the things that's got me really excited... expect to hear more about it soon.

Housecleaning and Reboot

My dear neglected readers (who mostly don't exist), it's high time for some housecleaning. My poor webpage had gone entirely without updates for the better part of a year, and that has now been remedied: there are more than a dozen new publications since I last posted on this poor blog, plus various new talks, changes in projects, etc. I've also gone through, updated the text, and reorganized things a bit, reflecting changes like the fact that I now mostly work on spatial computing and engineered self-organization and don't do much human-level AI work any more.

It's also time to change this embarassingly dry and sporadic blog to something a bit more meaningful. Now, this has been a bit of a stumbling block for me, since I'm posting under my real name and in my professional capacity. On the one hand, dear reader, I hope you'll understand that, cathartic though it might be, I feel it would be a poor idea to bare my every angst, fury, and imposter-syndrome moment to every colleague, competitor, and funding agency. On the other hand, I need to speak with my own voice here, or else this is just a piece of soulless drabble torn from my fingers out of a vague sense of duty to the God of Social Media. And that's no fun for me or anybody else.

So here's the plan: I'm going to make this an exercise in the positive. You, dear reader, should know that you're getting the real me, straight and unfiltered (else why would I write such godforsakenly circuitious sentences like in the last paragraph), but circumscribed. I've got enough good and interesting things going on in my research life that I'm going to focus on those and leave the tragedy and angst implicit. For those familiar with the scientific world, please take those details as read: for every paper accepted and every proposal funded, invisible siblings have failed to much wailing and gnashing of teeth, and so too with anything else I discuss.

Last note, before I vanish for now: I plan to stick to a set schedule as well, posting once a week. To make sure that I actually do this, I'm not going to post this until there's a queue of posts to come at least two months long. In the interests of full transparency, please feel free to compare the date of this post with the "last updated" mark on my web page and that will tell you how long that took.

And now, in the interests of health, wealth, and SCIENCE, I am cranking up the VNV Nation in my headphones and forging ahead in this godforsaken airport. See you next week...