Lambda the Ultimate

I'd like to explore the topic of argument-dependent lookup (a.k.a. Koenig lookup), and in particular I'd be interested to find out what people think is the "state of the art" when it comes to resolving unqualified identifiers.

It's my opinion that one of the primary motivations for ADL is to support operator overloading. The function of ADL is to resolve unqualified names, and operators are essentially functions with unusual unqualified names. For functions that have regular names and which are not operators, it's often not a huge burden to explicitly qualify the name, or to manually import it into the current scope. But for operators this destroys their brevity and convenience.

There are many supporters and detractors of ADL and I won't try and repeat all the arguments here. The common theme is that ADL leads to surprise. However, one limitation that interests me is that the methods which operate on the arguments must live in the same namespace with the definitions of those types. This is not such a hardship in languages like C++ where there's no enforced relationship between the namespace hierarchy and the organization of modules and source files, where any header file can append to any namespace. But for many modern languages that's not the case, the package hierarchy is much more rigid (often with good reason.)

I can imagine scenarios where the co-location of operations and types within the same module would be overly restrictive - you might want to extend the set of operations for some set of types (think of a vector math library) without re-defining those types.

So what are the alternatives? I can think of several. The simplest one is to require that unqualified name definitions be explicitly imported into the module's namespace. This has the benefit of being easy to understand, but I'm not sure how well this scales to large programs - you risk polluting your namespace with a lot of symbols.

Another solution is to allow a more limited kind of namespace extension. Some languages have syntax that allows adding methods and definitions to classes only (not namespaces or packages), usually with keywords like "extends" or "extension". This requires that the unqualified names be defined within the class, rather than outside it, which usually implies that the enclosing class "owns" the definitions or at least has special status. In a single-dispatch world, of course, these definitions are methods, which means you run into the "binary operator" problem - who owns the definitions of A+B, is it A or B?

A third approach is to completely give up on static scoping and use dynamic dispatch - i.e. if there's a definition of A+B anywhere in the program, it will be used, even if it's not visible at the call site. However, while dynamic multi-argument dispatch is a valuable technique, it is not without it's set of costs. One that I'm particularly interested in is the "plugin problem", which is that if you are Adobe Photoshop and you load some filter plugin that happens to contain a new definition of the plus operator, does it suddenly change the behavior of your whole program? Or on the opposite extreme, does the plugin contain its own sandboxed versions of all the operators and type definitions? Neither seems desirable to me - the plugin needs at minimum to implement some interface defined outside of the plugin, but its effects need to be limited and predictable.

The benefit of static scoping is that the conceptual search space for unqualified name lookups is smaller and more predictable, and thus easier to reason about - a programmer need only look at the set of imported symbols and their transitive dependencies, instead of having to search a universe of code.

Anyway, I'm interested to know if there's anything out there that's clearly better than the techniques that I've described.

The third annual ACM conference on High Integrity Language Technology (HILT 2014) call-for-papers is available, with a deadline of June 7th for regular papers, experience reports, and extended abstracts. For more info, see:
  HILT2014-CFP.pdf
The conference website is:
  HILT 2014 Website
We hope readers of LtU will consider submitting a paper, and will encourage your colleagues to do the same. Accepted papers will be published in the conference proceedings, and appear in the ACM Digital Library for wide visibility. We are pleased to be co-located with SPLASH/OOPSLA this year in Portland, OR, with technical sessions being on Monday, Tuesday, and part of Wednesday morning, Oct 20-22.

Since the CfP was produced, we can announce that Peter Feiler of SEI/CMU has agreed to be our invited speaker to introduce the sessions on Model-Based Engineering. In addition, we are putting together a panel on new safe parallel programming languages, tentatively entitled: "Finding Safety in Numbers -- New Languages for Safe Multicore Systems Programming," with three panelists already lined up. We are also coordinating our program further with SPLASH/OOPSLA, so HILT attendees can attend the Wednesday SPLASH keynote, and SPLASH attendees can attend the Tuesday HILT keynote (Tom Ball of Microsoft Research). We are also considering making the above mentioned panel a joint HILT/OOPSLA activity.