Re: Var-free programming (slightly off-topic)

[Dan Moniz <address@hidden>]

On 12/3/01 3:33 PM, "shivers@cc.gatech.edu" <shivers@cc.gatech.edu> wrote:

[snip]

> This is very handy, of course. Note that Alan Bawden wrote a not-widely-known
> gem of a dissertation at MIT in which he says that the *problem* with names
> is the thing that's good about them -- this multiple-reference property. For
> contexts where the cost of reference is very high, names are painful to
> manage. There is such a real-world case: distributed network services. If
> I have can bind to a name a resource that lives somewhere else on the net,
> then, in order to know when that resource is no longer needed, I have to
> do distributed garbage collection, a very painful and complicated and
> inefficient thing to do. So Alan proposes one of these pointy-headed-theorists
> kind of language formalisms, "linear type systems," that gives you a handle
> on references by nameing. His thesis, then, is that linear type systems are
> not just for effete, weedy type theorists -- they are for network-protocol
> designers. It's just that the NPD's don't know it.
> 
> So Alan builds distributed systems using a language that back-ends out to
> a "linear language" back end. That's his diss (or most of it), from 50,000
> feet. The subtitle of his diss is "Confronting the cost of naming."
> 
> An interesting read. If you are interested, look here:
>   ftp://ftp.ai.mit.edu/people/alan/

This sounds like some other things I'm familiar with. Excuse me while I
cross-pollinate lists here. There was a recent discussion on e-lang (a
mailing list for developers of the E language, see <http://www.erights.org/>
for more information) regarding the upgrading of old objects (as well as
related issues like naming, etc.) and I thought this might be germane. I
apologize up-front for the off-topic and potentially noisy nature of this
mail, what Mark is talking about are objects and Olin is talking about named
variables, but I think there are parallels to be drawn, especially as Olin
noted, in distributed systems.

On 11/29/01, 3:02 PM, "Mark S. Miller" <markm@caplet.com> wrote:

(For some background, there were three cases identified when objects needed
to be upgraded, very briefly identified here by another snipped from Mark's
mail:)

[snip]

>> 1) "upgrade for release" -- I release a new version of some body of code,
>> and my customers upgrade their old instances to be instances of the new code.
>> 
>> 2) "comm coexistence" [...]
>> 
>> 3) [upgrade for prototyping] -- for development and debugging work.
> 
> [#3 was called "live upgrade", but in the present context they're all live,
> so I renamed it above.]

(and here was a possible solution as expounded on by Arturo Bejar, whose
work in distributed garbage collection immediately came to mind when Olin
talked about Bawden's work, above:)

> Arturo Bejar (of secure distributed cyclic gc fame) realized the key
> difference needed to support upgrade-for-release, and engineered Original-E's
> second persistence/revival/upgrade mechanism based on this insight.  This
> system, State Bundles, is explained at
> http://www.erights.org/e/StateSerialization.html , but unfortunately in
> terms specific to the original Unum model and the particulars of our app --
> EC Habitats.  Here, I'll try to explain the central insight in more general
> terms.
> 
> Arturo wrote:
>> "Do you, Programmer, take this Object to be part of the persistent state of
>> your application, to have and to hold, through maintenance and iterations,
>> for past and future versions, as long as the application shall live?"
>> 
>>                                 - Erm, can I get back to you on that?
> 
> A live program consists of a tremendous amount of state.  If we had to
> figure out how to live with or upgrade most of that state in engineering a
> new release, we'd rarely succeed at making new releases, or our releases
> would be limited to only trivial changes.  Anything more ambitious would
> simply be too hard.
> 
> The most important step we can take is to simply reduce the size of the
> problem, typically tremendously, by manually choosing which state is
> precious and which isn't.  On upgrade-for-release, only precious state is
> upgraded, and all other state is recreated from this precious state.
> 
> In Java terms, to be part of precious state, an object must be somehow
> declared precious (in Arturo's State Bundles work, the class must implement
> Serializable), and it must be reachable from the precious-state root, which
> I'll now call the "lifeline", by traversal of non-transient fields.
> 
> In E terms, I plan to add the lifeline as a magic power to the privileged
> scope.  The lifeline will have a message for adding precious roots, and
> possibly for removing them.  An object expression declares that its
> instances are precious using the "::Persistent" auditor.  (Perhaps this
> should be renamed "::Precious"?)  If precious-traversal finds an instance of
> a non-precious object expression, a keeper is invoked, for which the default
> behavior is to trace a problem and substitute a broken reference.
> 
> When engineering a new release that must reliably upgrade customer's old
> instances in the field, one need only consider non-transient state in object
> expressions declared ::Persistent.  Further, one may be able to reason about
> precious-reachability in order to narrow cases still further.
> 
> We can forever elaborate the support provided for format conversion of this
> precious state.  Java again provides a decent example of where to start.
> But we need to appreciate that the work done in narrowing cases was much
> more important than the work that remains figuring out what to do with the
> cases we have left.
> 
> The above upgrade process can be seen as like a stop-and-copy garbage
> collector.  Call it stop-and-upgrade.  It doesn't necessarily involve
> persistence or even serialization.  But since we have to use serialization
> for persistence on some platforms, and since upgrade-for-release requires a
> full traversal of all the state we're keeping, we may as well use
> serialization for upgrade-for-release, even when we're not doing so for
> persistence purposes.
> 
> Another insight from Arturo: On those platforms where we are using
> serialization for persistence, we may as well always serialize only the
> precious state.  First, this allows up to serialize much less.  Second, it
> treats every revival as a zero-delta upgrade, giving us somewhat greater
> confidence that our upgrade mechanisms may work even when there's an actual
> delta.
> 
> 
> By contrast, we shouldn't use stop-and-upgrade of precious state for
> upgrade-for-prototyping, because it would throw away much of the
> non-precious state we may be trying to debug.
> 
> I'll respond to the rest of your message later.

For those that are interested, the mail archives of the e-lang list are
linked off of the E site, URL shown above.


-- 
Dan Moniz <dnm@pobox.com> [http://www.pobox.com/~dnm/]