Given that my only other post so far steps on the toes of a major company, I thought it might be appropriate to make my second post a bit less contentious. Well, that was until Arthur Whitney (creator of the K programming language, among others) came to talk about language design to our research group over at the Stanford Graphics Lab.
I found the talk and ensuing discussion very interesting, in large part because Whitney’s taste in language design is so far from my own. Of course, its hard to argue with results, and so I’ve decided to spend some time trying to understand my own biases about programming langauges.
Static and Dynamic Typing
Most programming-language geeks seem to fall strictly on one side of the static/dynamic divide or the other (those who talk about “optional typing” as a middle road are almost always closet dynamic-typers). Despite the long-standing flame-war passionate debate between the opposing camps, there is one important position that I haven’t seen explained.
Looking at Method Dispatch
Here is a simple question that can be asked for most langauges: given a method call:
obj.m( a )
what factors contribute to the decision of what code gets run?
Note that I’m using the
obj.m( a ) syntax purely as a representative. There might be languages where the same thing is expressed as “
obj m a“, “
m(obj, a)” or any number of other variations. The syntactic details, and the object-oriented styling just make it easier to contrast some of the typical punching bags in the static/dynamic debate.
My own survey of languages leads to the following list of factors that might affect dispatch:
- The method name:
- The dynamic run-time value of the object
- The statically computed type of
- The dynamic run-time value of the argument:
- The statically computed type of
- The lexical context of the entire expression
Comparing Some Languages
A typical dynamic class-based language like Smalltalk or Python will use only (1) and (2) above to control dispatch. For the purposes of dispatch the object (or its class) is treated like a dictionary mapping keys to values. In this case the key is the method name, typically encoded as a string “
Dynamic languages with multimethod dispatch also take (4) into account. This is built-in functionality in languages like the Common Lisp Object System (CLOS) and Dylan, and Guido himself demonstrated a way of adding them to Python as a decorator.
Many functional programming languages would use only (1) and (6) to resolve a call. In many of these languages functions like
m are just ordinary values, and thus function names get looked up in the current lexical environment like any other name. Since a name typically only binds to a single value, there is no need to consult any other information to resolve a call. If the programmer wants to execute different paths depending on dynamic information (2, 4) then they will use pattern matching – an orthogonal mechanism to ordinary dispatch.
Haskell’s type classes allow dispatch in that language to take (3) and (5) into account. A function name in Haskell might belong to a type class, and thus the compiler must search a suitable type-class instance which provides the concrete functions for particular types of operands. The search for type class instances is driven by the lexical environment (6).
A typical static class-based language like C++, Java, C# or Scala will use (1), (2), (3), (5) and (6). Our mainstream static object-oriented languages don’t currently support multimethods, often for historical reasons (c.f. Martin Odersky’s comments (bottom of the page) on why Scala eschews multimethod dispatch). A static object-oriented language with multimethods could take all of the available information (1-6) into account. If you can’t already guess, that is exactly the kind of language I would advocate building.
It is completely reasonable to ask why any of this matters. Widely-used languages have covered very different parts of this space, with the only constant being that dispatch depends in some way on the name of the operation being invoked (which it would seem pretty difficult to ignore).
Where your choices about how to handle dispatch really start to matter is when you have multiple entities with the same name. I intentionally used the word “entities” to be all-encompassing, but I’ll give a quick example.
Suppose you have a base class
Base and a derived class
Derived. What happens if both
Derived try to declare a method
m, for different purposes? What if
Derived were developed by different people, or different organizations? What if
Derived was originally coded using version 1.0 of
Base which didn’t have an
m method, and then the programmer tries to upgraded to version 1.1 which adds the new method to
As another example, what if you have two protocols or interfaces
IBar and some objects need to support both protocols? Are the two protocols allowed to have operations with the same name
m, but different semantics?
In a functional-programming setting the question becomes: what if two separately-developed modules or typeclasses try to define operations with the same name – can user code import both?
Let’s look at how we can cope with these situations, depending on what kinds of dispatch our language supports:
Strategy: Statically-Typed Object-Oriented Languages
If our dispatch logic takes the static types of the operands into account, then there isn’t really a problem. In the expression
obj.m(a) we can look at the static type of
obj. If it is
IFoo, then we can call
IFoo::m; and if it is
IBar, we can call
IBar::m. If there is not enough information in the current lexical context to know which operation the user meant, then an error can be signaled because of the ambiguity.
This is important – the compiler can use all the information at its disposal in trying to resolve a potential ambiguity. In particular, this means they can use all the information that is manifest in the code the user is writing – including the types of the user’s variables. Only when there is no information available that unambiguously indicates the programmer’s intent will the compiler throw up its hands and request that the user be explicit. All of these languages give the programmer some way to explicitly signal their intent.
In contrast, if our language cannot take any of this contextual information (static types, lexical context) into account, then there is no way that can ever determine the programmer’s intent. All such references would be ambiguous, and we need to figure out some way to circumnavigate the problem.
Strategy: “That just doesn’t happen in practice!”
The easiest solution here is to just bury your head in the sand. This might involve making your language resolve all these name clashes by fiat – every class is just a key-to-value mapping, and there can only be one value with a particular key. Alternatively, you might try to protect the user from creating name clashes in the first place – don’t allow a class to inherit multiple methods with the same name, or to re-declare an inherited methods.
In all honesty, these are reasonable approaches for any “little language.” Coming up with a robust solution to name clashes can compromise the simplicity of a language. The user needs to learn the specialized rules that control dispatch, and since every method call is subject to these rules this can make understanding code difficult until fluency is achieved. C++ developers who fully understand “argument-dependent lookup” are few and far between.
But if your “little language” has grown up to the point where it is being used to ship serious software (hello, Python!), then you will definitely face these problems. If the language does not directly address them, then you will end up using convention to avoid the issues.
Strategy: Name Decoration
A simple approach is to decorate the method name
m to avoid clashes in the first place. That is, rather than
IBar both having a method
m, we instead have methods
IBar_m. Of course, since the pain is felt by downstream developers, both
IBar would need to have preemptively decorated their method names to avoid future clashes.
Python actually has a limited form of support for this approach built-in (mentioned briefly in the Python style guide). Field names that begin with a single underscore are automatically prefixed with the name of the enclosing class. Note that this is a very specific case of taking the lexical context into account (number 6 in my earlier list).
I hope it hasn’t escaped your attention that by amending the method name with the name of the enclosing type we have basically replicated the ability of a static language to dispatch based on the static type of the object. This came at the cost of more verbose method names everywhere – not just at the call sites that needed it.
Strategy: Module-Scoped Methods
The approach taken by CLOS and Dylan is to put the methods associated with a class into module scope, rather than nesting them inside the class. This means that even if an
obj.m( a ) syntax is supported, it is just sugar for
m( obj, a ), and the name
m is always resolved by looking it up in the lexical environment.
The benefit of this approach is that the meaning of
m can now be tailored to each call site – depending on which definition of
m is in scope. The downside, of course, is that if more than one definition is in scope the reference once again becomes ambiguous.
Disambiguating these methods either requires explicitly qualifying the method with the name of a module:
FooModule.m( obj, a ), or importing the method into the current scope with a decorated name:
Foo_m( obj, a ). Thus we still end up having to explicitly decorate our references with information that the statically-typed language was able to glean from the current context.
Strategy: Avoid Inheritance
One each way to avoid ever making the
obj.m( a ) operation ambiguous is to disallow certain forms of inheritance – either in the language, or institutionally. This might involve a blanket ban on implementation inheritance and multiple inheritance, or some more subtle middle ground.
If an object wants to support two different protocols like
IBar, it could do this by using the Adapter pattern. Two auxiliary objects would be created (one to implement
IFoo, the other to implement
IBar) and any place where we want to use our object through one of these interfaces, we pass the auxiliary object instead. Thus our original method call might be disambiguated as either
obj.asIFoo.m( a ) or
obj.asIBar.m( a ).
This form of disambiguation is not unlike inserting a cast to either
IBar in a statically-typed language (which is a common way of disambiguating a call). Compared to decorating method names it has the nice benefit that we can “cast” an object once, store the adapter object in a variable, and re-use the adapter for multiple calls (without decoration). Of course, this idiom then looks suspiciously like declaring a statically-typed variable.
When we are “programming in the large” and aggregating separately-developed code from multiple suppliers, names clashes seem inevitable. For most mainstream programming languages, it is possible to plan ahead and build libraries that are robust against these issues. Which language you are using, though, determines which strategies you can employ to achieve that robustness.
In many static languages, name-clash problems are anticipated by the language design, and there are explicit features (including method dispatch strategies) that make it relatively painless to cope with. In particular, users typically only have to amend their code in cases where their intent isn’t already clear from context. The price for this is a more complex set of rules in the language (for resolving potential ambiguities).
In all of the mainstream dynamic languages I am aware of, name clashes must instead be handled by diligent and defensive programming practices. In the best case, the idioms that work to avoid name clashes lead to slightly more verbose code. In the worst case, though, they amount to using ad-hoc mechanisms to express precisely the same information that the static types in other languages provide “for free.” The benefit is that for programs or libraries that don’t need this level of defensiveness, programmers benefit from intuitive language semantics.
For my part, I’d rather build (and use) languages that have a robust solution to problems like this built in. Dynamic typing advocates often complain about having to write extra annotations to “appease the compiler,” but that particular saw cuts both ways. If the context of my code makes my intention clear, I want my compiler to use that context to resolve potential ambiguities, rather than making me always add extra annotations to “appease the runtime.”