Discoverability, Language Features, and the First Step Toward Composition

We cannot compose our own code with pre-written code (terms, types, classes, mixins/traits, modules, signatures, metalinguistic abstractions, etc.) - or compose two or more already constructed code constructs - if we cannot discover that such appropriate code exists.

What language features might help or hinder "code discovery". My own thoughts are thoroughly scattered. I think about completely diverse things such as 1) the standard "omnibus" Smalltalk package/class browser; 2) Stepanov and Lee's early emphasis re: STL on the more or less precise performance characteristics of different but otherwise functionally equivalent "pluggable" algorithms; 3) the extreme encapsulation, and thus essential invisibility, permitted by languages such as Pascal and Scheme with nested functions, other terms and even nested types (Pascal?); 4) the desirability or lack thereof of ADT's (existential types) as afforded by ML signatures and the very real trade offs between such encapsulation and the pragmatics of reuse; 5) the extremely widely varying "scope" of term composition and thus the size of the unit of computation and hence composition - from the typically terse Forth "word" all the way to giant multipage C functions common in industry, or even the domain specific, typically monolithic commercial libraries or "frameworks" often comprising 100,000's of lines of code or more.

As I said, my thoughts have a few "anchors," but otherwise seem completely scattered. I seek some set of uniform, organizing principles.

Our languages (common production languages plus at least the most popular "academic" languages) seem to be all over the map regard "discover-ability" - an attribute that seems both antecedent to and essential to the "holy grail" (among others) of relatively painless code discovery and consequent code composition.

Any papers, thoughts or general enlightenment greatly appreciated, particularly related to the relationship between individual or types of language features that enhance or hinder discover-ability. Thanks much in advance.


Comment viewing options


A lot of axes for discoverability

In addition to the axes you list, I'd add more prosaic ones like standard and complete documentation formats, cross-platform packaging, clean binary versioning, existence (and quality) of automatic dependency management systems, in-language declarative metadata with package and runtime visibility, and similar pragmatic issues.

We're in the time of Google, and we've learned that search is better than memory, and sometimes better than thought. There's a lot of scope for improving the programmer experience of languages based on that fact.

I'm working on a paper on just this right now

There is almost nothing on discoverability, beyond the code search work done in the ICSE community (you can find a few of those papers at OOPSLA to).

The angle of my paper is to focus on naming in PL. If we can make names descriptive enough, then we can bring search technology to bear in helping us find and rank matches to our queries. If name's include architectural dependencies, then we can automatically apply them to our programs. But I'm still baking this so..., I'll post something later when I have a draft.


Sean, take a look at Jade. It builds on Emerald, a distributed language descendant from the Smalltalk dialect. It is more general than Smalltalk's browser model.

Geoff Wozniak's dynamic abstract data types are another idea...

Vineet Sinha's Relo project is also relevant -- not published in ICSE

Finally, David Binkley has been doing stuff such as Unifying Program Slicing and Concept Assignment for Higher-Level Executable Source Code Extraction.

There are other prior arts I can't think of at the moment.

I'm familiar with Jade, but

I'm familiar with Jade, but they seem to be attacking the problem of composition vs. just finding stuff. More relevant would be Holzle's "Integrating Independently-Developed Components in Object-Oriented Languages" in ECOOP '93 (amazing how good ECOOP used to be, '93 was a golden year for them). But...the finding stuff problem. All the other links still seem to be about mining code from existing code bases, and none of the approaches really "work" yet (i.e., the problem is still open).

The working title of my paper is "What's in a name: the design of a name-oriented programming language". Here is the working abstract:

Natural names as noun or verb phrases are incredibly descriptive in that words can be combined in new and arbitrary ways to communicate existing and novel concepts. In contrast, the names supported by programming languages at best serve only as mnemonics to help programmers read and write code. Meaning is instead wrapped up in definitions, declarations, and documentation, and so the programmer's ability to name code into existence or guess the name of code that could exist is extremely limited. This paper describes how a naturalistic naming system can increase expressiveness in a way that is tractable to the computer. Names in our programming language are list of words with minimal structure to precisely describe objects and their members along with their essential relationships. Because computers excel at heuristically processing list of words, they can match and rank guessed names with the existing names of a large database, allowing programmers to more effectively communicate through the programming language. Among other things, this enhanced communication enables programmers to more easily share code directly in the programming environment.

Otherwise, I'm still baking this. I'll post a draft within a month I think.

sounds compelling

very much looking forward to the draft!

You might want to take a

You might want to take a look at Einar Host's work at last year's ECOOP (unless you are already well aware of it). He trained a system with the method names and method body bytecodes of 100 major open source project, and got a system that is able to find naming bugs! The paper was called debugging method names.

I like your idea of creating a recommendation system for names, and I think it can greatly improve the readability and understandability of code by other programmers. I have been experimenting with that as well using LSI and other techniques in a Squeak Smalltalk image. It has beens shown in UI design that the chance of having two persons picking the same name for an object is 7% to 18%, and I guess a similar finding (even though with slightly higher numbers thanks to design patterns) might be reasonable for software. However, I am not sure if teaching humans to choose better names so computer can better search software is the right way to got. I would rather prefer to teach the computer to cope with synonymy and polysemy, and it seems that techniques like LSI seem able to do so. It's the Yahoo directories vs Google approach, dont fix the web, fix the search engine. Still I see very high value in name-centric programming for human understandability.

You might also be interested in this. I think it was Hummel etal that created a UML drawing plug-in for Eclipse that used code search to suggest missing fields and methods when designing your classes. (I can try to find the original paper if you are interested.)

Ah! That ECOOP paper is a

Ah! That ECOOP paper is a great find, thanks!

My idea is to make naming a more core part of the programming language, and actually turn it into the language's type system (names are types, type relationships are explicitly encoded as name relationships), although this might be a bit too aggressive right now.

You mean something like

You mean something like first-class labels? Or are you going even further?

Different: names have

Different: names have nothing to do with the expression/statement language, and everything to do with the type language. E.g.,

"slider element of a ui panel" is a control that is a sub-type of "element of a ui panel", and we could mix things up so that "slider element of a ui dock panel" is a sub-type of "slider element of a ui panel". The rule being that subtypes are implicitly defined through name subset relationships ("a b c" is a sub-type of "a b" and "b c") rather than through explicit sub-class definitions.

Sounds cool

I've played around with similar ideas a little bit, but never really got something that didn't seem problematic in one way or another. So I'm looking forward to reading your paper.

Sounds like ontology engineering w/ structured editors

see subject line... not aware of any academic papers to point you to... but i'd be surprised if similar ideas haven't been explored in structured editors

Cobro might also be related

Cobro might also be related to your interests then, Dirk Derrider extended Smalltalk with (metacircular) Ontologies that live in the same namespace as the classes and are edited/deployed/etc with the same tools as code. I don't recall the work in detail though.

Relo and Architexa

The work behind Relo has been been published at VL/HCC - see here for some publications. We have taken the ideas in Relo, added two more tools focusing on different parts of the problem and continue to work on it at Architexa (we are in private beta, but can add any of you if you are interested).




Maybe even use something like PageRank over all source files...

Has been done countless

Has been done countless times already. I guess at time in the past is must have been to most often assigned bachelor project in SE groups (the typical hammer-based "here is an algorithm, apply it" research topic). The problem is what should count as a link between software artifacts, so that it has the same semantics as links in the web ie that of citations. (Typically the most important classes are almost never cited and the utility classes are cited all over the application.) Alas most of these works never went through a user study, so it remains open whether a practical application of pagerank on software was ever found. PS, I would be more than happy to be proven wrong on that last claim though! :)

Steven Reiss' S6

You reminded me of this: Semantics-based code search from Steven Reiss at Brown University.

There's a live site as well.

Scalable Composition

I've been interested in developing since 2002 a language that I intend to be truly composable, up to Internet-scale and across enterprise interests. Indeed, scalable composition is the primary motivation for that language, so I've been thinking about these issues for quite a while. I'll share a few of the observations and principles that have been guiding my design decisions.

Service Composition: service composition - development of new services and integration with existing live services and resources - is far more important than code composition. Service and Code compositions tend to overlap only in languages with considerable ambient authority (where arbitrary external services can be accessed via a library of code), but the whole 'service composition via code composition' is a bad design by most of these principles. Service composition needs all the same properties as code composition (safety, performance, predictability, upgrade, failure handling, etc.) plus quite a few more (serialization, security, persistence and resilience, disruption tolerance and graceful degradation, economics/trade, concurrency and control thereof, etc.). I'll touch on a few of these individual principles below.

Performance: One common motivating factor against code-reuse (and service reuse) is that a system's performance often degrades with each 'layer' of abstraction or communication. Libraries are often compiled separately and designed to be pluggable, which hinders code optimizations (partial-evaluation, etc.) in the small. Context switching and network costs hurt composition in the large, which is in part why 'libraries as pluggable services' is popular. Ideally, we want to support large amounts of partial-evaluation, even to the point of collapsing late-bound object graphs. JIT is more promising than static compilation, as it can optimize in the case of late-binding. Ability to restrict arbitrary mutability is important for performance, but where one cannot restrict mutability it is ideal if the system can intelligently 'cache' resources without input from the developer - and FRP serves well in this role. For high-performance composable services, we also want automated code distribution so that the less security-sensitive aspects of remote services may be automatically inlined and JIT 'compiled' directly into the local code.

Predictability and Safety: composition of code and services must have as many predictable properties as possible under a broad range of uses. Developers cannot reasonably compose systems when they cannot predict how they interact. Predictable performance characteristics, termination characteristics, control over where delay and disruption may be introduced, failure modes, confinement properties, behavior under concurrent or shared access, etc. are all very useful. In a concurrent system, high-priority or real-time operations should be able to nudge aside low-priority operations (no priority inversions).

I would call ADTs a good thing for predictability. So is parametricity, as much static type safety as one can get (especially effect-typing), determinism where it can be acquired, and ability to stabilize which components will automatically upgrade.

Garbage collection can go either way for predictability, which makes it a bit controversial. It is easy to fail to dealloc properly for explicit memory management, especially in a concurrent language. I would say we want a collector that provides time and space guarantees: longest delay waiting on GC (i.e. you'll not be delayed more than 10 ms at a time), total delay per second (i.e. you won't be delayed more than 100 ms per second), usable space and fragmentation promises, etc. I favor copying collectors.

Good support for automated testing is also useful for predictability.

Security and Trust: If people can use code and services developed by groups they do not trust, then a lot of avenues for widespread sharing open up. Discoverability does you very little good if you aren't going to be comfortable using what you discover! One may reduce need for trust by improving predictability, especially predictability regarding confinement, delay*, distribution of authority, distribution of sensitive information, and stability of the system across code or service upgrades. One may also support trust concepts directly via support for auditing, investment, liability, web-of-trust and reputation, etc.

I favor object capability model for this reason, though it is insufficient by itself. It allows developers to predict confinement properties, to control distribution of authority, to know that remote service code automatically distributed to their machines will not gain any authorities that it would not also have obtained if running remotely. To complete object capability model whilst allowing for automated code distribution, one must also support sensitivity annotations and data-flow analysis to prevent accidental distribution of sensitive information (including capabilities) to an untrusted host machine. Sealer/unsealer pairs and DRM-style 'trust' features for capabilities (including data resources) can go a long way.

Usefully, cross-service ADTs can be implemented in a first-class manner via use of sealer/unsealer pairs.

*: Predictable delay is another way of saying 'resistance to denial-of-service attacks'. Predictable delay under various forms of concurrency control is an especially sensitive area. Locks are horrible for this purpose, and promises or logic variables are only slightly better. Serializers are okay but stateful, which hurts a few optimizations plus performance for persistence and redundancy. Transactions have good features for predictable delay without introducing undesirable object-local state for this purpose (better allowing code distribution and inlining). Automated code distribution and task parallelism is also useful for predictable delay, allowing a service to easily request as many resources as it needs among a cloud of host machines even for very large requests.

Namespaces and Sharing: Currently code is buried in pocket-sized repositories, and it is very difficult to share code across these repositories. Even if attempted to share the code, the languages built around pocket-sized repositories often suffer namespace issues and won't make for easy builds. I would propose that most code go into a global, flat namespace - i.e. something like a 'Wiki' of non-viral open source code, such that it becomes easy to discover code even by accident.

For services, namespaces also matter: if access service A depends upon where service B is hosted, that may prove very problematic for composing service A with service B even if you have the necessary authority (a capability). A global, flat namespace for object capabilities is a very good thing.

Persistence, Resilience, and Upgrade: I say above that service composition is more important than code composition. An extension of this rule is that support for persistence is very important. Services must live long enough for their discovery to be useful, for their compositions to be meaningful and stable. They must survive independently of the power-cycle of any given host machine. Ideally, services must also survive independently of the life span of any given host machine - which implies support for automated redundancy (which is, naturally, yet another motivation for automated code distribution). Databases, web services, DNS, etc.: all achieve stability, all are stable enough that one may develop 'against' them. Making persistence 'transparent' or orthogonal is a huge aide for security.

But, while persistence provides a sort of resilience against power failures and node failures, it does not provide resilience against corruption, upgrade, and partial-failures. I.e. if a service is going to live a long time, you are almost guaranteed to eventually want the ability to upgrade it.

Developers of E call this the 'upgrade problem'. To them, it is a big deal, and they chose to resolve it by disfavoring transparent persistence. It is my belief that the developers of E are simply going about the upgrade problem the wrong way, starting with bad assumptions like "upgrade is local to a Vat" or "upgrade involves 'directly' changing the code used by existing objects" or "upgrade involves a transform of a Vat image", all of which assume a need for infrastructure outside E itself. It is much easier to see issues surrounding upgrade if you start by assuming decentralized distributed systems and automated code distribution. Because there is no single persistent image to focus one's attention, the mind is free'd to seek other solutions.

Upgrade becomes an issue of architecture and capability, to be achieved fully within the language... just like security patterns. Known upgrade patterns are pluggable architectures, publish/subscribe systems, service registries and service-factory patterns, advisors and expert systems, and functional-reactive components carry procedural information (allowing a tweak to a database or code in a debug-mode IDE to cascade out to observers).

Support for explicit and cascading destruction are useful features for architecture-layer upgrades, even if you don't need them for garbage collection. Explicit destruction allows you to replace pluggable components. Cascading destruction makes partial-failure modes more predictable and detectable (allowing one to use fall-backs). Of course, for security the authority to kill should be separate from the objects. My current language design uses 'kcell' (killer cell) objects and 'dependencies' between objects to support cascading destruction.

Good language-layer support for persistent services and integration with upgradeable architectures are critical steps towards highly scalable service composition (which is more important than code composition). In the absence of persistence or tight integration with an external persistent services, most languages are useless for more than toy academic projects. I would suggest that 'persistence' be the default, and that volatility be carefully introduced and otherwise inferred for performance.

Disruption tolerance and Graceful degradation: these are specific instances of predictable 'failure modes', but they are very important for service composition. A language design can aim to support these features in the common features and architectures. I.e. FRP can support 'fallback' resources (slowing down updates or switching to lower-quality feeds), or switch to lower-quality feeds. Some architectures, like publish/subscribe and blackboard metaphor, tend to handle disruption and degraded access quite well, so I suspect this will be more architectural than language-layer.

Automated code distribution can help with disruption tolerance, since code on or near your host is less likely to be disrupted than is code further away. Even if it isn't distributed to your host directly (due to sensitive information), it could be distributed to a nearby host in a trusted cloud. Integration with services and hardware outside the language takes a little extra work, something like a common 'unum' pattern - i.e. the ability to access HTTP is fairly widespread, so one might allow a 'capability' to access a certain HTTP domain be received from an external system and implemented via a plugin on the host. This is still capability-secure if that remote code can gain no more capabilities than it had before being hosted on your machine, but you do need to be careful about local domain name resolutions (localhost, 192.168.*.*) and about reverse DNS lookups (e.g. as performed by ACM paywall), and so on.

Market, Economics, Trade: Code and Services are both subject to trade agreements, contracts, etc. I would like to see these supported much more widely at both the language and IDE layers, to support freelance developers (also of media resources - art, sound, animation - not just code). I would like to see a competitive market of services, and even of host-machine resources (i.e. competitive clouds).

An 'integrated' development environment should be integrated with a market. Imagine opening up your IDE, writing up a few requirements for a prototype, and letting some third-party review your request and make a proposal which you may accept or reject based on their reputation, liability, bid, etc. Or perhaps you develop a new service, and you want to allow others to pay for itself, so you allow others to pay for service which will then pay for its space on the cloud in addition to extra change for later upgrades and maintenance. Or perhaps you develop a neat bit of game music, and you choose to hold one of many forms of 'open-source' auctions (i.e. where each person bids and you choose a price, and everyone at or above that price pays the price you chose and gets a copyright on the resource).

Certainly, integration with an open market offers a powerful enhancement to 'security' of a language. It allows systems and services to be self-regulating. A denial-of-service attack is unlikely if it costs money. Spam becomes a market opportunity, rather than a burden. Today, negotiations end up being performed at a higher layer or through humans, which makes them slow, relatively insecure, and inefficient enough that they often aren't used at all. This, in turn, favors reinvention over sharing and composition of most market services among enterprises.

More architectural developments along the lines of smart contracts, Waterken IOU, and market-based composition (i.e. market-enhanced publish/subscribe and plugin-architectures). Plenty of free services will still be available, of course, but the integration with the market is a positive influence for both users and developers.

Concurrency and Concurrency Control: One of the big problems we have for scalable composition today is that most languages are awful at handling concurrency. This often forces us to implement services on a once-per-user basis rather than sharing services between users. Unfortunately, most non-toy services cannot be implemented once-per-user... i.e. you can't just create a new database for each user, since the very value of a database comes from it being shared. Thus, developers of new services must deal with concurrent access to the service. For composition of services, they must also accept that the services they depend upon are also accessed concurrently. Even for GUI applications, sharing is often desirable, i.e. so that multiple operators can collaborate.

These facts of life mean that scalable composition requires both concurrency in the language, and some ability to control concurrency across services (i.e. to prevent malign race-conditions when integrating or negotiating between two independently developed external services during the creation of a third).

So far, I'm placing my bets on distributed ACID transactions. I'm not entirely happy with them, but I haven't found anything better. BASE (basic availability, soft-state, eventual-consistency) transactions are very nice for an important subset of domains, but their design is domain-specific (per def of 'consistency' and a given manipulation API) and their implementation usually requires multiple, smaller, distributed ACID transactions.

You should turn this post

You should turn this post into an onward paper :)

Namespaces and Sharing:


As it appears you are emptying out your design diary, I will shadow it with something from my own design diary:

Indexing, not Wiki-like namespaces, is the way to go. It has not been done yet; Steve Reiss is heading in this direction, but appears to be using the wrong base model (just an opinion). Probably because most PLT'ers would shrivel at the thought of learning a large discipline like information retrieval. However, with Mahout (built on top of Hadoop) and Lucene, this becomes a glueable solution; the PLT'ers need only understand basics to take something off-the-shelf and make it reality.



Indexing of public resources is useful for various service composition patterns (service registries, publish/subscribe and multi-caster systems, factories, other pluggable architectures). In a sense, you could consider a wiki to be a service - even an easily composable one (DVCS style).

But it is unclear to me what it would mean for a developer to reference code via an index, and I suspect the 'open' nature of an index would prove of less utility if you abandon ambient authority (such that all new builds start confined until hooked into external services via IDE).

[Edited heavily]


the awful 'libraries introduce services' design for service-composition-is-code-composition

You should know by now that I am an MDA weenie and that all Model-Driven Engineers think that there were no winners nor losers in the initial rush to design systems for the Web; most of us thought "the war was over" in 2001, and then SOAP came around... and people apparently learned nothing.

Let me put this another way: Had Roy Fielding put in the effort to describe how to properly design media types in his seminal thesis on the Web, it would've eclipsed Claude Shannon's seminal Master's Thesis A Symbolic Analysis of Relay and Switching Circuits in terms of number of readers and proper application of the theory.

Your other points are interesting and valid, but do not influence my opinion on how to aggregate piles of code.


I've never gotten past the impression that MDA is a bunch of buzzword-laden hype. Every website I have ever perused on the subject does much to reinforce that impression.

I've been assuming that businesses should be responsible for integrating or representing their specific services within an infrastructure that recognizes only common requirements and interfaces (aka middleware, such as HTTP and HTML and DDS and RDBMS and OpenGL and DNS). Only services and requirements recognized as common among enterprises get elevated in this manner.

This turns what is oft explained to be MDA's priority (business-specific functionality) upon its head, in favor of prioritizing secure and high-performance middle-ware and integration with it. If MDA really is about representing and exporting interfaces to business-specific functionality, then that means new services aren't already integrated when first developed, plus rejects automated integration (because automated integration requires conforming to a common interface, protocol, and (ideally) semantics). Of course, I may be misunderstanding the role of MDA; I've had a lot of difficulty cutting through all those buzzwords in the past (and again in the present)...

The OP is about composition in an environment where developers wish to take advantage of code and services developed by others. The principles I described earlier are to support such composition... i.e. the distinction between code and services is useful for security, testing, and predictability, which are allow developers to make easy use of what they discover. Perhaps you should speak of how MDA supports the purpose of discoverability and composition, and of how indexing is relevant to this purpose.

There are numerous

There are numerous approaches to MDA, and some try to be too powerful, much like the downfall of some 3rdGenPLs.

UML 2.0 is confusing to most, precisely because it allows you to model things sane model-driven architecture weenies would not. By augmenting 2.0 with the right profile, you can limit UML to a standard set of modeling idioms very similar to what you can do in a model checking / specification language system like Alloy.

Finally, beyond UML, there are some excellent texts on modeling (IMHO), such as The Austin Protocol Compiler, Compiling Esterel (synchronous reactive modeling for reactive systems), and Roel Wieringa's overview text Design Methods for Reactive Systems. -- These do not conform to the OMG "MDA" vision, but are instructive in thinking about what constitutes a minimal model of a system.

As for search: the vision of MDA has always been that product prototypes, intended to be merged into final designs for software product lines in software factories, allow for hundres or thousands of model prototypes to be generated, separated, combined, and searched. To do this, there have been many modeling systems in the past aimed at allowing components built in disparate languages, for disparate systems, deployed in disparate environments, such as Ptolemy. Also, for UML, the notion sof Platform Independent Model(PIM) and Platform-specific Model (PSM) allow you to limit searching to appropriate levels of granularity.

Edit: I would also think that for security, code and services may best have two different security models. First, claims-based authorization for services (SAML, CardSpace). Second, the implementation of code conforming to capability security o-caps model.

Edit #2: Despite working at a small ISV, we're pretty close to attaining this vision of computing. We probably won't, because it would require full culture buy-in plus more dedicated resources, but even getting close is a huge impact on quality. Our entire architecture is hypermedia-driven; the number of 'components' we use across all products in our software factory probably numbers over 100,000.

Dual Security Models?


O-caps, in combination with a rights amplification mechanism (like E's sealer/unsealers) and ample patterns (such as Waterken IOU), can support all the security models you'll need in-language. This includes claims-based approaches and exclusive trade of fungible resource tokens (like trading e-money for time on a grid).

Access to code - be it a tiny snippet or a massive database (or filesystem, or wiki) - is just another service. Treating it as anything else is a hindrance to scalable composition.

Since I plan to aggressively 'distribute' service components to their users (and vice versa), this may carry o-caps or information. To prevent accidental distribution of sensitive o-caps and sensitive information, I do support some extra claims-based security at the host layer. This is useful for distribution that involves cloud computing somewhere in the middle (i.e. Google could plant certificates on the hosts it trusts, and I might trust Google or Amazon with my sensitive information and computations, but not trust Microsoft or the DoD or your personal machine). If a machine is compromised, I could later revoke trust from it to prevent further compromise; doing so would inherently revoke all sensitive capabilities it carries (i.e. because I'm always free to audit for proof that you have a right to hold it). This qualifies as an extra security layer (protecting against accidental leaks and many developer bugs) but isn't really a security model, and allows flexible delegation. It integrates well with a distributed market.

Attempting to incorporate SAML or CardSpace and other identity-based security mechanisms is just going to be a source for headaches - both short term and long term. The benefit you'd gain is mostly political, rather than technical, since it'd better adhere to existing systems and the strong business agenda to centralize authority through a 'trusted' intermediary (who may charge you for it). Identity-based security supports the cathedral, rather than the bazaar.


I don't understand you.

How does single sign on and single sign off, for dynamically distributed and dynamically federated systems, have anything to do with ocaps.

Edit: Most large enterprises for confirming identity on geographically disperse ERP systems resort to federated probabilistic identity matching.

Edit #2: Perhaps the difference is best described as the difference between "system of systems" and "large-scale systems". I would not make the assumption that a service corresponds to anything more than a single system.

SSO vs. O-Caps


Do you mean other than the fact that they are competition and serve primarily as a hindrance to delegation, development of value-added service composition, open markets (i.e. supporting resale), automation, autonomy, anonymity, etc? Hmmm... I'm coming up blank.

The very idea of "single sign on, sign off" [SSO] is about providing authority through proof of identity rather than designation. We don't benefit from SSO in an o-cap system. While SSO offers an improvement to services common today, it is just as easy at this point to improve them by switching to o-caps (which provide authority to secure sharable tokens, not identity). Thus, the two are in competition.

Now, an o-cap system can benefit from a 'dynamically distributed, dynamically federated' sign-on mechanism, where a user can utilize some proof-of-identity (fingerprint, password, smart-card) in order to obtain a service that maintains an organized collection of o-caps (such as a bookmark file). This is perfectly reasonable. But all authority is coming from those o-caps, not from the identity. This means users could share these o-caps and services without sharing the proof-of-identity. This ability to use the o-caps independently of identity is critical to integration of services and open development of value-added services and automated user-agents (which may then be shared or marketed). This is the basis for composition under principle of least authority.

The implementation of the above 'o-cap' federated and distributed identity service is quite easy: instead of having a CardSpace or SAML authorization, simply put o-caps directly on the smart card or upon a similar portable hard device (such as a trusted laptop, or perhaps an Iron Key). Even a networked identity service that trades a username and password or challenge for a collection of o-caps is possible, but there is no need for common trusted CA and providers like Verisign. There is no communications relationship between the identity service and the o-caps obtained upon proof of identity, therefore there is no trust or security or business requirement between them.

The distributed o-cap mechanisms are better than SSO in every way that matters unless you're the one of the few selling the SSO service. SSO can be sold twice: once to end-users (or advertisers), and once to clients (developers of SSO-enabled services). As a platform technology, the value of SSO service - and, therefore, the business leverage of the SSO service provider - grows with the number of end-users and clients buying into it. The providers of SSO also have strong incentives to develop exclusive deals to better compete with 'alternative' SSO giants (e.g. Microsoft vs. Google), and will tend to use their leverage to make these deals. This makes "single sign-on" a very easily corrupted ideal, because it would no longer be SSO: you would need more than one SSO identity to interact with different exclusives.

SSO is perfect for monopoly giants, big brother, and religious cathedrals, but not so good for open competition, autonomy, anonymity, automation, and keeping prices down. SSO does offer advantages over what we use today, plus offers significant business advantages for the giants that first implement it, so there is a lot of pressure to make it happen. But SSO has little value added functionality for end-users relative to o-cap designs, and has significant long-term costs for end-user rights. (What little added value it does have comes from better ability for an SSO provider to vet and regulate services for quality.)

SSO vs. o-caps is ultimately a cathedral vs. bazaar competition in the computer security and electronic markets.

There are a few legitimate reasons for using identity. Most of these reasons have to do with fiscal or legal reputation or responsibility, rather than with authority. An o-cap system - with sealer/unsealer for rights amplification - can implement identity easily enough where it is needed (merely supporting o-caps does not imply the model is capability based; one must also clean up the common libraries and protocols to isolate authority in a secure manner). An identity corresponds roughly to an unsealer, in this case, and need not be associated with a human. Read about Horton's "Who's Done It" for more on the subject.


I seem to be missing a reference here. To which "difference" do you refer?

A service can be as large as DNS or as small as a single object that drops inputs to a single log somewhere. Services compose in a number of ways, and most services either compose other services or are intended for composition into other services.

You can examine scale of composition at least two ways: the 'depth' to which you can compose systems before further composition becomes untenable (including indirections, as through publish-subscribe or a service registry), and the 'width' - the number of simultaneous users sharing connections to a given system (including across enterprise and security-domain boundaries). Scaling on either of these dimensions can fail for a number of reasons (performance, predictability, security, safety, concurrency, integration with a market, legal issues, etc.).

Are you intending to associate wide composition with "large scale systems" and deep composition with "system of systems"? If so, what does this association gain you?

Here's the key point

Services should be composed from the standpoint of non-delegatable authorities. This has been discussed before on Cap-Talk, and covered at length by Toby Murray. See: [cap-talk] the value of non-delegatable authority (was: In defense of Object Capabilities, against non-delegatable *authority*) and Jed Donnelley's reply:

The essence of this, I think, is probably best demonstrated by SQLServer's security model, which is rooted in non-delegatable authorities and allows authority to be delegated via context chains. SQLServer security expert Laurentiu Cristofor has a fascinating example on his blog about how this breaks down when they try to correctly support Windows NT identities. Laurentiu now works primarily on Bing.

I think that services should be identified based on non-delegatable authorities. You should think in terms of what one user can currently do, and what you would like that user to also be able to do. Thus, I tilt Jed's ideas a bit and say that the reason why people are drawn to non-delegatable authority is that it provides a model for pointwise reasoning about information secrecy and object security at the same time. Obviously, coupling these two concerns together at the code level is a bad idea. But when you are searching for a service to compose and have a user role {{not a security role!!}} you are thinking of {{e.g., Hospital Accounts Receivable Staff}}, then you probably want to view things in terms of what you are already allowing them to express, if they could directly interface with the objects.

An identity metasystem like Cardspace is just that - a way to keep track of identities. Identities can be useful for rengineering business processes. The major potential problem with service composition is that it is getting at data in ways that refactoring of the dynamically federated system might be better solution to.

Sorry for the long wait on the reply. You just revised your point so many times that I was waiting for your argument to stabilize... I'm not complaining about this, as I think most here appreciate your edits to improve the clarity of your points. You certainly know that I prefer the big picture to niggling over details, but that does not mean I underestimate the importance of your ferociously acute antennae for detail.

I think that services should


I'm not following the implication you outlined here. Why would the incremental addition of an authority imply the need for non-delegatable authorities?

I agree with the need for incremental authority extension, and object capabilities usually address this using facets and composite patterns. This pattern becomes significantly easier to use safely with advanced language features. In this case, define an incremental extension to a base type class to expose the operations for the new authority, in a similar way that one might extend a modular interpreter in Haskell.

Let me try to refine this one last time...

IMHO, well-designed system's model context, rather than encoding it into out-of-band communication between two objects; I think the phrase 'objects unencapsualted' here is a bit of a misnomer, since the real problem is that objects rely on guards to interpret messages and these guards necessarily limit your ability to 'connect the dots' in a workflow; just because you have a type system that proves you've filled in all the appropriate bubbles with the appropriate dots, doesn't mean you've built a good system.

In a dynamically distributed, dynamically federated system, you'll eventually reach the point where you won't know how services are actually being composed. Terms like "eventual consistency" are only true if you can actually prove you have a system that is capable of being eventually consistent. [Edit: A proof can be done using work based on Dijkstra's self-stabilizing systems, such as using superstabilization to prove that a system will eventually converge on a valid system state.]

What I think you want for services composition is rather than figure out how to refactor messes, first be able to query for potential messes. Perhaps you can get service providers to cooperate and redesign their services.

Anyway, this is my current thinking on this situation. Obviously, more real world experience is needed to hash this out. However, I would not be the first person to propose an odd idea for distributed systems design (e.g. Erik Meijer and Phil Wadler proposed code annotations for (supposedly) automatically splitting code across tiers; as you can probably infer from the recent GWT 2 code splitting discussion on LtU, I have very strong opinions on how this stuff actually works out to be practically feasible, and do not like the approaches of Volta, Links, Jif or GWT.) [Edit: I think Benjamin Pierce's Boomerang language contains hints that Pierce might come up with a better solution than Wadler or Meijer.]

I deal with fairly small systems, but I notice that many of the ideas discussed in supposedly large scale distributed programming applies very much to the pain points I experience on a daily basis.



To be direct, it doesn't. I just think it is a convenient model for searching code bases. Could you explain to me how you think a pure object capability approach is well-suited to search-based software engineering? I've not seen this discussed on Cap-Talk before. I still think object capabilities are the best way to write the code to support the search for the right code, I just think when thinking in terms of system boundaries it is best to think in terms of a user role and a boundary for the end of where composition is. In UML, we call this a Package Diagram...

Could you explain to me how


Do you mean something like Hoogle? There's nothing intrinsic to capabilities that would prevent this sort of search.


Hoogle does not seam to allow you to collect capabilities using pointwise reasoning.

I do like David Barbour's suggestion, though, that instead of speaking directly in terms of CardSpace or SAML's model, we look at the discrete needs of such a model and model it in terms of fine-grained capabilities. In hindsight, my comments are stupid and ugly.

Now the only thing left to help make searching easier would be to come up with an identity metasystem for object capabilities so that everyone uses basically the same model.

Am I wrong?

The downside is I suspect this approach won't see wide adoption, and so things like CardSpace and SAML will still be required due to how people describe incremental authority.

Now the only thing left to


I caution: every time I have ever in the past thought something along the lines of "the only thing left is ...", I've been subsequently proven wrong.

Developing 'standard' meta-data for capabilities isn't a problem to which I've dedicated much thought. I'm not sure why 'identity' would be a big part of such a design.

I suspect any attempt at 'catch-all' standards will fail. We'll want different standards for different domains... e.g. meta-data for capabilities associated with live geographic or temporal information may be largely distinct from meta-data for capabilities about forums or shared documents, which may again be distinct from meta-data for multi-media caps (audio and video). Such things as Multicaster publish/subscribe pattern with its domain based 'Address' class help demonstrate advantage of remaining domain focused. But, in the absence of we can still standardize on a per-domain basis.

In the general, ultra-long-term sense, I'd like to see capabilities associated with well defined contracts: preconditions, provisionals, postconditions, contingencies, invariants, costs... everything one needs to 'compile' capabilities into a program to meet goals (goal-based programming). But that isn't going to happen any time soon.


Even then, separating identity from the capability is an enabling technique. You can use CardSpace or SAML as an adaption layer to access a user's pool of capabilities.

Hoogle does not seam to


What's pointwise reasoning? All meanings that I can infer don't seem to inhibit searching or aggregating capabilities.


If I understand what you're after correctly, it's already done (LtU link). The Horton protocol basically builds "islands" of identity.


Murray's NDA paper doesn't describe a means to really prevent delegation. It instead carefully narrows the definition of 'delegation' so that it excludes proxy:

(NDA Paper section 1.1): An NDA provides a means of distributing authority to uncon fined subjects while ensuring that the only way it can be shared is analogous to proxying.

I provide a similar similar mechanism in my language design that forces explicit proxies in certain circumstances. I do so for purpose of controlling automatic distribution (which is otherwise quite aggressive), preventing accidental leaks of authority, and ability to revoke authority from compromised hosts. (For example, if a weapons platform has been captured by enemy forces, you'll want to revoke the certificates it possesses that validate its capabilities for Forcenet.) I don't consider my caps non-delegable, though. I only call them 'sensitive' and thus subject to 'controlled distribution'. Static analysis can capture most potential errors related to the use of sensitive caps.

In no way do I believe that NDAs are a reasonable way to define or identify 'services', nor do I think they are particularly relevant to composing them. Modulo performance, a proxy is just as good as the original capability, at least until it's revoked.

But I am fairly certain that your apparent goal - allowing developers to think in terms of 'user roles' and incremental tweaks to them - doesn't require NDAs.

I would probably approach the problem by reifying a 'user role' in terms of a record of fine-grained capabilities - what that role can see (FRP capabilities mostly, but potentially a cap to a whole pubsub registry), what that role can do (object capabilities). A default UI would be available to help make use of the caps in this role. Because I want to upgrade roles later, I'd likely express the set of caps within an FRP behavior. If you wished, you could make the caps into NDAs, which offers you the comfort of ensuring any delegation by the user is subject to later revocation, but otherwise ain't particularly relevant.

This would allow the developer of a service to think in terms of user roles.

I suppose that, philosophically, I define 'services' in a similar manner except that a service has many roles. User and provider. Rights holders, trusted intermediary, and transaction. Judge, jury, executioner, prosecutor, defense attourney, evidence, and witnesses. The roles themselves are tied together by protocols and contracts (which really ought to be provable... or at least auditable). Each of these roles may involve many fine-grained capabilities. Attempting to eliminate 'delegation' from these roles seems to be counter-productive, as delegation and composition of services is the basis for fulfilling the contracts associated with a role.

But in practice a service seems to refer more broadly to anything that will hang around for a while and will behave predictably. I.e. I could provide a 'service' that turns an LED on or off, another one that tells me whether the LED is on or off, one that answers every query with the current time, one that emits random quotes from a fortune file, one that provides the Nth fibonacci number on demand. Not all of these even require capabilities - computing fibonacci numbers is usually an ambient authority, along with most pure functions (barring concerns for space and CPU).

The potential of indexing

I live in Washington, DC and a lot of interesting software is developed at NIH. I know some folks who for many years now have designed and built and refined highly custom search algorithms and task specific user interfaces to allow researchers to mine the oodles of truly giant databases of semi-structured medical data.

If even a fraction of this type of effort were applied to the organization, classification, search algorithms and highly ergonomic custom search UI's to allow developers to mine the oodles of truly giant libraries of SOFTWARE, I can easily imagine that this would go far toward solving the discovery and reuse dilemma.


Great Comments, but Maybe Horses Before Carts?

I appreciate the thought you've devoted to the issue and your writing some of these thoughts down in such an extensive manner.

I'm particularly intrigued by the "flat namespace" concept, as I believe this might be a matter of debate vs. other language design priorities. I'm very interested in how exactly a flat namespace impact the myriad scoping mechanisms at pretty much every level of granularity devised over many decades.

My general concern is granting the complex, if very interesting, issues of service discovery and service (re)use some kind of higher priority over the relative prosaic, but important and ubiquitous, goal of code/library discovery and (especially) reuse - a problem we still more or less have not solved in a satisfactory manner (in part if not in total) via our design of programming languages, module systems, standard annotations, compilation units, linking technology (e.g., I haven't heard of tree pruning in many, many years) and so on.


scoping with flat namespaces


So long as developers can control which resources they reference and which resources they export, scoping follows naturally. This is true regardless of the 'component' layer, whether it be a record or module, an object configuration, or a page of code.

For my own language, at the code development layer I've been favoring 'feature@page' (i.e. 'append@list' or 'sum@nat') for references. I decided against use of top-level 'import nat' and the like to reference exported features: that is a role of syntax manipulations (which I plan to integrate later), and syntax manipulations will be a lot more hygienic and modular if they cannot expand to reference page-local imports, and are more subject to refactoring if they are orthogonal to the set of exports by any given page.

Languages such as C/C++ created a lot of extra problems for themselves by use of '#include' directives and inclusion semantics, which in general reference a region of the file-system named by command-line options outside the code itself, and further prevented developers from controlling the local namespace (i.e. controlling what it is they reference, controlling what it is they export). Even languages that corrected the gross flaws of #include still tend to follow the example of using a filesystem as the implicit namespace.

The local namespace niched into a hidden corner of someone's file system encourages independent development of independent projects, which is troublesome: all useful projects and services are integrated with other projects and services, not independent of them, and they further tend to be developed collaboratively, not independently. A great deal of resources have been spent fighting these languages and their development environments, or building tools (SVN, Git, ClearCase) to aide us in that battle.

My two web-developer's cents

I think that a large part of service composition will be done via realtime feeds, i.e. collections of objects with some kind of change notification mechanism.

These enable time-wise and location-wise decoupling of services (because a service can "catch up" after a downtime). When a service creates "result entries" for the entries in a feed it subscribes to, and publishes them in its own feed (correlated via unique IDs), we have some kind of worldwide dataflow programming, that is purely functional (for an outside observer).

Realtime Feeds

That's certainly a large part of the design I've been developing. I just use a different word for it. You write 'realtime feeds' whereas I write 'functional reactive programming' or 'publish/subscribe architecture'.

FRP and these 'realtime-feeds' are quite tolerant to disruption and often allow for graceful degradation and a good bit of temporal decoupling.

It sounds like you're focused a bit more on event processing (i.e. filtering, transforming, distributing discrete events, as opposed to continuous state). Event processing doesn't cover nearly as much interesting ground as FRP, in part because interesting events in real life are almost never 'discrete'. And they are also less resilient and tolerant to disruption - 'catch up' is a difficult problem because it is unclear for how long you should keep a history of events or whether a new subscriber should see historical events. However, simple event processing and distribution does serve well as a basis for first-class multi-cast, publish/subscribe, and 'smart plumbing' between services. See related comment here (section on Complex Event Processing).

Event processing doesn't


Aren't virtual events discrete?... but reacting to them doesn't necessarily require a clock vector such as that used by a synchronous executive. The problem is identification of virtual events is potentially lossy or limited (such as being limited to a Stable Bloom Filter model).

I am assuming simple event processing rejects Luckham's event hierarchies.

Aren't virtual events


The simple ones are, such as messages and variable assignments. Complex events might be described and staged by many simple events over time.

I am assuming simple event processing rejects Luckham's event hierarchies.

SEP has no internal state or time (time = partial ordering on events), and as such cannot relate separate messages into 'higher level' events. SEP cannot recognize Luckham's event hierarchies. I'm not sure that 'rejects' is the right word, though, since it's more a matter of not-quite-enabling. One could certainly use SEP as a smart network when building a CEP system.

The simple ones are, such as


Ah, but a synchronous executive only knows about simple event histories bounded within a clock vector; it only checks for events at the end of a clock vector. The discrete event simulation is not one where events are timestamped as they arrive and processed by timestamp ordering. This would open the door to allowing synchronous executives to coalesce the event queue and more generally aggregate events into event hierarchies??

Synchronous Executive

If some centralized component maintains a little state and obtains access to a wide range of event resources, certainly it would be free to organize said events into arbitrary hierarchies. Programmers are free to develop such event processing systems, though they cannot do so in an SEP layer.

It is unclear to me what your interest is in the synchronous executive implementation, that you've brought it up a few times already.

My own interest in distributed, survivable, and parallel computations has me leaving an implementation of small, local queues up to services that feel the benefit from doing so is greater than the cost. Queues are fragile in a distributed program (they require you choose between resilience and performance), and are a little awkward to use in a distributed context. I handle concurrency control via distributed transactions, rather than serialization by queue. (For 'local' computations, as per realtime systems, I could see such a queue being favored.)

I believe it unwise to combine responsibilities, such that what is essentially a scheduler also becomes responsible for classifying events. Instead, produce dedicated CEP services, and register them with any appropriate-topic-oriented publish-subscribe capabilities you might possess.

It is unclear to me what


You've asked questions like this to me before, whether you've phrased it as a question is a different matter.

My big thing is being able to think about design as fast as possible. e.g. when we discused "complex domain object code" and I said the object-oriented solution would be poorly performant, you said considering it was a pure waste of time. I do not think such exercises are a waste of time. The whole point of problem solving is to hear a problem and analyze it as fast as possible, using as many tools as possible, and show the most elegant solution as possible. The alternatives serve to leave little doubt others can do better, so that when you are gone, some idiot doesn't implement the inferior way of doing things and sell it as the correct way.


considering it was a pure waste of time

I would not say that "considering it" was a pure waste of time. I might have said something along the lines of "I considered it, and I consider it a pure waste of time." A lot of effort has been wasted in the past attempting to use wrong tools for a job, eventually forcing rework.

Anyhow, I was just honestly interested in why you bring up synchronous executive. It isn't of interest to me for the reasons I mentioned earlier, but not everybody is aiming to support Internet-scale open distributed programming.

the most elegant solution as possible

I've yet to see a satisfactory explanation of what 'elegance' is.

the most elegant solution as

the most elegant solution as possible


Doesn't mean we should stop trying...

I've read some interesting historical accounts of elegance. From Discipline of Programming by Dijkstra to Science of Programming by David Gries (which basically is a continuation of Dijkstra's mission). Unfortunately, Dijkstra's approach has basically been proven not to work... I wish I still had the paper/slides of the person who analyzed the book to see how it might work in practice on large-scale software systems.

As for synchronous executives: they are generally not used very much in discrete event simulation, but some alternate designs somewhat mimick synchronous executive behavior. For example, Jeff Berry's causality domains. I am not sure myself the extent to which they are useful, just sort of discussing semantics. At this point, I would suppose this is no more fruitful than discussing syntax of a programming language.

Roll forward

This sounds quite a bit like the roll forward capabilities of RDBMS's.

I can imagine cobbling together a simple prototype of such a system just using XML-RPC. XML based messages are easily serialized into a roll-forward log. Then configure some set of services accessible via this XML-RPC server simply augmented with roll-forward logging and an associated roll-forward capability upon service re-availability after failure.

I'm sure one might add myriad nuanced possibilities and refinements to this basic prototype framework.


A reason I'm in the group I

A reason I'm in the group I am now is that a previous member, Dave Mandelin, did absolutely inspirational work with Prospector (and other projects) for query-driven mining of software. E.g., given a String type, how does typical Java code go to a File to a bit stream?

So, types.

Another dimension is the decoupling/integration process the invariably happens during reuse (it takes generations for an API to be generally reusuable, which I'm guessing is likely not the typical case for code we find :) ). Adobe's Durango takes a bit of an ad-hoc approach to it -- I can imagine stuff like PBD and back slicing to improving it.

Since the rise of

Since the rise of internet-scale search engines, searching for reusable source code has quickly become a fundamental activity for developers. Search engines help developers to find and reuse software. This has led to a practice that we might refer to as "search-driven development". The promise of search-driven development is that developers will save time and resources by reusing foreign code in their local projects. It is thus the same promise as framework reuse or components or et cetera you name it before.

However, search-driven development has a particular twist: it emphasizes ad-hoc reuse. Ad-hoc reuse (aka pragmatic reuse) is about reusing software that was not necessarily written with reuse in mind. Tool support (like the slicing, automated renaming & refactoring etc) is supposed to make the software reusable in the target system. What I personally like about this approach is that it does not attempt to change the problem of reuse up-front. Gosh, it's already hard enough to figure out the current requirements so how can we expect engineerings to plan ahead for future reuse? Rather, the attempt to is to achieve code reuse by a program transformation/adapation once the need for reuse arises. Code is not static, so why rely in composition of static components when all you need is automated suitability, ie components that are automatically transformed to work together? Private method, no problem, clone and refactor that class. (A system with instantiatable modules, such the nested classes of Gilad Bracha's Newspeak might help with that too).

Another aspect is trustability, before even attempting to reuse software a developer will ask "can I trust it", how many fellow users does that software have, are they happy with it, how talented (or rather, well known, which is the best approximation of talent that is typically available to you) are its developers, is it still maintained, how reactive is the mailing list, how many tutorial can I find online etc. At least years SUITE workshop we identified these two issues (ie suitability and trustability) as main challenges for search-driven software development.

Some promising prototypes (ie Steven Reiss's S6 and Dave Mandelin's Prospector) have already been mentioned. Another promising approach is concerned with the way we search for code. So instead of using textual queries or formal specification to search for code, unit tests are used to search for code. That is, you write a failing unit test and then run a search engine that goes in the internet and tries to find passing classes and methods! Prototypes of this approach are CodeGenie by Sushil Bajracharya et al and CodeConjurer by Colin Atkinson et al but also, as far I know, S6 by Steven Reiss has some limited unit test support. The nice property of tests over formal query languages is that: no need to learn another language, tests are inherently as expressive as your language, and tests are something programmers can understand. However all this approaches are very fragile to naming, that is why I am currently working Sushil to improve their results with LSI, lexical similarity and other text information retrieval techniques. Before I worked on using source code vocabulary in reverse engineering.

Other interesting work is eg Assieme by Raphael Hoffmann et al that collects documentation and runnable examples from websites. They just start to parse website line by line with the eclipse compile to find pieces of valid source code, and then use a kind of type & JAR inference to add missing import statement. (Examples on the web typically dont have import statement, even when they are otherwise fully valid code).