How to create a best of breed multiple dispatch solution for Erlang?

[peerst]

Because the topic The need for "protocols" in Erlang was closed while I was editing and this is a separate topic anyway: for such a relatively high impact change like adding Clojure/Elixir like „protocols“ to the language:

We should rather leapfrog to the best of breed solution that playing catch up with partial solutions to open problems in this space.

Maybe we can discover a efficient, well integrated into pattern matching and hot code loading i.e. a very Erlangy feeling solution for multiple dispatch or something similar that us at least as good as the best solution today for other languages.

That will be a hard challenge but solving it would be worthwhile!

Lets collect ideas and insights how other languages solve this here.

[rfk23]

The best typeclass/multiple dispatch implementation I’ve seen was in Coq. It’s also (conceptually) the simplest one, which is not surprising, because in a dependently-typed language one can treat instances and types as regular variables. So, in a sense, it unveils a lot of the magic which I spoke against in the previous thread. Roughly speaking, Coq’s approach to the “protocols” boils down to the following mechanisms:

1. implicit arguments (arguments of a function that can be inferred from the context, and therefore can be omitted by the caller)
2. type inference for said arguments
3. implicit generalization mechanism that replaces free variables in a statement with values automatically inferred from the context according to some rules

The problem, of course, is that Erlang doesn’t have user types. But if you look closely, this is very reminiscent of passing a callback module as an argument to an Erlang function. If one substitutes proper types for module atoms, I can speculate that it can be reproduced without affecting the bytecode and/or VM, or maybe even can be slapped together with a parse transform.

So, how can it work? Start from normal Erlang code:

foo(PrettyPrintModule, A) ->
  pretty_printer:pretty_print(PrettyPrintModule, A).

In Coq terms, with a lot of leeway and imagination, PrinterCallbackModule would be an “instance” of “PrettyPrint” “class”.

Step 1: Let’s “improve” this function by emulating an implicit variable. This can be done by defining a new function foo/1 that tries to guess the first argument:

foo(A) ->
  PrettyPrintModule = multiple_dispatch:dependent_module(pretty_printer, A), 
  foo(PrettyPrintModule, A).

Note, that this function can be generated mechanically. I could easily write a parse transform that takes an annotation

-implicit(foo/2, {PrettyPrintModule, pretty_printer}).
foo(PrettyPrintModule, A) ->
  ...

…and transforms it to foo/1.

How does multiple_dispatch:dependent_module work? I guess it can assume that the second argument is a tuple where the first argument uniquely identifies the type. Then it can lookup VMT stored in a persistent term or something.

Step 2: Let’s “improve” the implementation of foo/2 by emulating implicit generalization (again, annotations and parse transforms should do the trick). foo/2 becomes:

-implicit(foo/2, {PrettyPrintModule, pretty_printer}).
foo(PrettyPrintModule, A) ->
  pretty_print(A).

and it can be invoked as

foo(MyDatatype)

Here, the compiler should know that pretty_print is a “method” of pretty_print, but nothing parse transforms can’t handle.
So, that’s how we get the best typeclasses on the market, lifted straight from Coq.

Step 3: Don’t do that.

[mmin]

My 0.02:

I don’t like idea of traversing through a list of modules to get a result. What if the function you’re calling doesn’t exist, none of clauses match, generates an error, etc.? What if no modules generate a result? What if multiple modules generate a result? Can user rearrange the list? I see a lot of edge cases.

As @josevalim mentioned in the prev thread, dispatching a message is done via pid - which maps to exactly one process, dispatching a call is done via module atom - which maps to exactly one module. So why not have exactly one module that handles some protocol/type_class/trait/behavior?

My idea is: some app A exposes behavior and provides a default implementation of it in a separate module. The user can override default implementation by implementing it’s own behavior in a new module. It can, but is not forced to, reuse the default implementation. So, there is exactly one module that is called when protocol must be invoked. That module can be set via e.g. application environment or some other mechanism. Therefore, this is not idea on how to implement a dispatch mechanism, but how to get rid of one.

E.g. stdlib exposes “printable” protocol, and provides a default implementation of it in std_printable module. So, when you want to print something in your own way, you define a new module (e.g. my_printable) in the following maneer:

-module(my_printable).

-behavior(printable).

-export([print/1]).

print({my_struct, Data}) -> do_anything;
print(List) when is_list(List) -> do_something_else;
print(Other) -> std_printable:print(Other).

Notice that:

1. There is new mechanism involved, just a design pattern
2. You’re not limited to tagged structs, you can pattern-match binaries, lists, tuples, anything you want
3. You probably want to have match-all clause, but you’re not forced to, you can just fail if you want
4. Overriding is more flexible/customizable than having a list of modules you traverse in searching for a result

At the end, you’re responsible for the protocol implementation, you always know where calls will end, you’ll get a clean stacktrace.

[michalmuskala]

In my opinion the best solution to this problem requires adding one constraint - the implementation of a protocol/multiple dispatch/dynamic clause lives either in the module with the definition of the protocol or in the module with the definition of the data type. This means “free-standing” definitions in random places aren’t possible. This is a similar constraint that Rust has for its trait mechanism.

This limitations, however, makes the dispatch extremely simple - since you always have at most 2 modules to check. With some very simple name mangling (similar to what comprehensions do), you could just check for the presence of the single necessary function in one of the modules. This doesn’t need any pre-compilation step, doesn’t need any consolidation, etc. The dispatch can likely be only slightly more expensive then a regular dynamic function call.

This, of course, assumes some support from compiler & runtime for such a feature, not just a pure user-level implementation.

[nzok]

Whence came the idea that there are only two modules to consider? Multiple dispatch means dispatching on the dynamic types of multiple parameters. Multiple. Not just one. So the resolution of
foo(X, Y, Z)
depends on X, Y, and Z, which may belong to types defined in three separate modules, with foo/3 itself originating in a fourth. This is the point of the long thread we just had on so-called ‘protocols’.

I still cherish my Brian Marick “An Example Would be Handy About Now” sticker. I’d love to see what all the added complexity in the language or the implementation is FOR.

Let’s get real here. The math: module is still missing hypot(X,Y). What is the point of having arctan2 but not its other half, hypot/2? I could point to gap after gap in stdlib. Is it time to fashion a triple crown when the socks have holes?

Speaking of Brian Marick, I’d like to propose a meta-rule.
From now on, when anyone proposes a change to Erlang (INCLUDING ME), they should discuss its impact on testing.

For example, there’s a paper “Automated Random Testing in Multiple Dispatch Languages”. It’s behind an IEEE paywall, so I can’t read it. But it sounds like the kind of thing that should be part of any serious proposal for multiple dispatch in Erlang.

[michalmuskala]

The initial post specifically asked about Elixir/Clojure-like protocols - in both of those cases protocols are single-dispatch. They can be extensible on the type of only one of the arguments.

Clojure does also include “multimethods” which are a full-blown multiple-dispatch construct, but they are separate to protocols.

I agree multiple-dispatch systems would necessarily be much more complex. I’m not sure we actually need them. Restricted single-dispatch polymorphism, as I presented above, to me offers good trade-off between complexity and expressivity.

[nzok]

Yes, but as discussed at least in that other thread, single dispatch doesn’t even come close to addressing any of the proposed uses for it.

I’m a big fan of Smalltalk. I’ve spent way too much time building a Smalltalk system and using it. Smalltalk is very flexible in allowing you to add new methods to existing classes, and even correct methods in a running system (although my system was written to probe the standard and to set a benchmark for compiler comparisons, so it doesn’t let you change a running system). So I am very much on board with OOP (what’s that humming? It’s Joe Armstrong turning in his grave) and extending existing types for new uses.

BUT.

The proposed uses were ones where the processing DIDN’T belong in the data structure and DIDN’T belong in the ultimate consumer of the data but belonged in a module expressing a (communication) protocol.

That is, we can solve the problems cleanly using existing language resources. We not only don’t need multiple dispatch, we don’t need Smalltalk-style single dispatch. More than that, reaching for those things as the preferred solution would lead us to deeply flawed architecture.

Single dispatch would ALSO add complexity to Erlang. And this at a time when we don’t even have a reliable way to get cross-module inlining (the preprocessor is a hack to sort of provide this, but it is not really a reliable way). It is complexity that nobody has yet provided any convincing need for.

That’s why we need examples.

By the way, I found out what happened to Safer Erlang. Hardly anybody was interested. Had it been picked up, adapting Erlang to multicore would have been easier. (And E might have been based on Erlang.) (Virtual) subnodes are a proven technology – heck Tcl/Tk had “sandboxes” – that address a number of architectural and security concerns. That is the level at which Erlang shines.

[MononcQc]

It feels to me like all the approaches mentioned here to the dispatching are consistently implemented at the type level, and that this shows a constant friction because by virtue of being a dynamic language, the code—by extension, the module—and the data structures are distinct entities.

The protocol-based approaches or those coming from type-based or even object-oriented approaches seem to all get their effectiveness from tying a code-level abstraction (class, module, interface) to a piece of data (type, typeclass).

In Erlang, records were doing a halfway step by forcing a structure to data types (tagged tuples) and a scope within a module (or via include files) that the compiler just leapt and assume were the proper thing. The tagged tuple or wrapper tuple approach ({TypeAnnotation, OpaqueData}) are contextually limited because they still require the calling code to bridge the gap between the type annotation and the handling.

Parametrized modules used part of it to create a more direct connection between the module, the data type, and state. By carrying the module information (and some state), you could get something similar by just using the data structure and calling a function on it, which would dispatch it, and leverage behaviours further for compiler checks.

The protocol-level stuff suggested here (and even by extension what a Golang-style duck-typed interface would do) still requires creating that connection between the module (or a subset of functions) and a given data structure, and that needs to be carried into the runtime, either through code—via annotations in the data structure—or analyzed solidly enough at build time that there is no ambiguity at runtime—typically done with type analysis.

When neither work, I imagine it ends up being data held somewhere in memory, possibly by tracking lists of potential implementations and having a determined order in which they are tried to see what would work.

But no matter what we’re talking about here, it seems like the crux of the problem is not how to specify the protocols/behaviors/interfaces, but how do we think the information tying a loose data structure into an implementation ought to be carried at runtime (if at all), because that implementation detail will direct most of the high-level design possibilities.

What I’m seeing here though is a lot of high-level-first proposals which end up getting in the weeds of debating the lower-level challenges, and that creates a degree of separation between proposal and solution that’s really hard to make adequate.

[peerst]

@MononcQc

When neither work, I imagine it ends up being data held somewhere in memory, possibly by tracking lists of potential implementations and having a determined order in which they are tried to see what would work.

Thats was what I was imagining when I have been thinking about “how to dispatch” so far. Using static type analysis would feel very weird and it’s probably not really possible in a language like Erlang.

So far I’m always ending up with a multi module function head pattern matching i.e. one specifies some incompletely matching function headers in several modules, possibly associating it with some kind of common structure, lets not call that protocol for disambiguation but something else like for example domain.

Then one would use the domain to mark function calls that should be multi dispatched and they would try all headers until one matches. Main problems that come to my mind:

• How to determine the order of matches?

• How does this interact with module loading? Having only the loaded modules “registered” with the domain would possibly not be the right semantics. That leads to some compiler intervention collecting all matching headers and put them into one module (possibly named like the domain ?)

Another way would be doing something like CLOS is implemented but that is maybe too OOPy for our collective taste here. IIRC (has been a while since I read the Art of the Metaobject Protocol) it would require each datatype having a reference to its implementation, and we would need some extra “boxing” layer for simple types. Altogether probably not the way to go.