/ elib / equality / grant-matcher

History of the Grant Matcher

Ages ago, motivated by implementation issues, Lisp introduced one of the most puzzling constructs in all of computer science, the EQ operation. Implementationally, it simply meant Are these two values the same pointer (or memory address)? Seemingly innocent at the time, when computer scientists later wished to give languages semantics--to say what the constructs meant independent of implementation--this construct proved surprisingly elusive. For Lisp, an adequate meaning was eventually pinned down, but then along came dynamic object systems. The first object system was Simula-67, but for us the story begins in 1972 with independent inventions of three dynamic object systems--Smalltalk, Actors, and KeyKOS. The latter two being foundational models of both object computation and capability computation.

Actor semantics, from Carl Hewitt and his group at MIT, is a foundational theory of computation (in the sense that Turing or Von Neumann Machines are). It is a pure theory of object computation and a pure theory of capability computation. In Actor semantics, a reference to an actor enables one to send messages to the actor, and the meaning of the reference is only the behavior one can cause in response to messages. If two references are behaviorally identical, they are indistinguishable. Since behavior is only solicited in response to messages, a reference to a transparent forwarder should seem identical to a direct reference. A transparent forwarder is simply an object that forwards all messages it receives to another object.

As a result of this transparency, many concurrent programming abstractions were first invented in Actor languages. In less pure form, many have made it into more familiar languages. Futures and Lazy Evaluation work perfectly in this context, in which the intermediate object embodying the computation could seem identical to the non-yet computed result. The intermediate object simply forwards all messages whether accumulated in while the computation is in progress or arriving afterwards. Extreme in this regard is the Joule Channel. Combining the power of Actors with support for the patterns explored by Concurrent Logic Languages, and Concurrent Constraint Languages, Joule Channels require that transparent forwarders be fully transparent.

Whereas Actors came out of a symbolic-computation A.I. tradition, with its emphasis on extreme flexibility, KeyKOS is an operating system, most infuenced by Hydra and Algol '68, whose emphasis was extreme flexibility within the constraints of extreme security. (Not coincidentally, both were heavily influenced by the Lambda Calculus, but that's another story.) The Joule design effort sought to reconcile these traditions and build a single system with the best of both worlds.

The primary designers of Joule are E-Dean Tribble, Norm Hardy, and myself (with significant contributions by Pavel Curtis and Chip Morningstar). Dean and I came from the Actor / Concurrent Logic Programming tradition, and were among the founders of the Vulcan Project at Xerox PARC. Norm Hardy was the chief architect of KeyKOS. Despite the difference in goals and starting points, the philosophy of computation arrived at by the two groups was amazingly similar. Indeed, Norm, Dean, and I saw eye to eye on almost everything. Many of the lessons we learned from Norm seemed to not only help us "think KeyKOS" better, but also to "think Actors" better than any lessons available from that tradition.

The one persistent source of disagreement was the question of EQ. Actors didn't have EQ, and Joule's ambitions of flexibility demanded that Joule not have it either. KeyKOS does have EQ (called DISCRIM), and is implicitly or explicitly the basis for several of its impressive security patterns, such as the Factory. Early on, Dean showed how the Factory could be done without EQ. Several years of argument ensued, were Norm would propose problems he thought required an EQ primitive, and Dean would then show how to solve the problem in Joule without any such primitive. I participated on both sides, with a preference for no EQ if it wasn't crucial.

Then, while writing the Escrow Exchange Agent as part of the WebMart system of capability-secure distributed electronic commerce (a collaboration between Agorics and Sun Labs), I ran into a problem that seemed to be insoluble without an EQ primitive. Fortunately for the project, the distributed capability system we had built (orginally known as Corbamite, later attached to Tcl and renamed Tclio), did provide for distributed EQ. However, the problem became another challenge in the controversy. Norm boiled the logic of the problem down to the Grant Matcher Puzzle.

Surprisingly, once we understood one clear example of the problem, we realized that instances of this problem were common. Deciding how to deal with this issue has repeatedly had a big effect on the system we built at Communities.com. E has two EQ constructs: the synchronous "==" and the asynchronous "join". The latter sacrifices full transparency. Instead, we are left with cooperatively-transparent forwardability, which preserves most of the practical benefits of transparent forwardability.

The controversy remains, but the cost of foregoing EQ is finally understood, and seen to be a fundamental cost. The controversy over the cost of having EQ vs the cost of not having EQ remains. For this cake, having and eating are now known to be mutually exclusive.

It's not so simple

The thread rooted here tells of Dean demonstrating that the Grant Matcher puzzle can be solved with Sealer/Unsealer pairs without EQ. Indeed, an EQ adequate to do grant matching can be built purely out of Sealer/Unsealer pairs (and plausibly out of other rights amplification primitives, like sibling communication). In Logical Secrets, we had shown that Sealer/Unsealer pairs could be built (awkwardly) out of EQ. So a capability system enhanced with either of these primitives is adequate to build the other. My remaining hypothesis is that in a pure capability system without either, one cannot build either. Dean (and everyone else of course) is hereby challenged to demonstrate otherwise.