8 ms·

Five-minute Multimethods in Python

113 points by llambda 15y ago

SammyRulez 15y ago
The power of a static typing in a dynamic typed language.. that's great.. and elegant too! GO BDFL !
- tikhonj 15y ago
  Except that you have to statically specify the types using decorators. So it's more like a subset of static typing in a dynamically typed language.
  - skimbrel 15y ago
    It's not a subset of static typing at all. If multimethods were a subset of static typing, then regular methods would be too. Methods are dynamic by definition: the type of the method's target is inspected at runtime and used to dispatch to the correct function entry. In Python, it's explicitly stated because the first argument of all object methods is "self". Multimethods extend this to do dynamic dispatch on all argument types, not just the target object. Most Python object methods are declared at compile time; this doesn't make method declaration a "subset of static typing". You can add new methods to classes and objects at runtime using Python's reflection and introspection; you can just as easily add new multimethods at runtime using this framework. Finally, the @decorator(...) syntax at compile time is just syntactic sugar for something like the following: def _foo(self, arg): ... foo = decorator()(_foo) So you can use decorators at runtime whenever you want too.
- radarsat1 15y ago
  Actually it's just checking the types at runtime, nothing much 'static' about it. This is pretty much the antithesis of duck typing, in fact. I could see it being useful, but I could also see it leading to confusion for people who expect Python's usual duck-typing behaviour when they pass their own types into a function. Whoops you subclassed from a type for which this function has a multimethod defined? Gonna do something different. On the other hand, in non-trivial programs there _are_ certainly occasions when you need to check the type, so using an elegant method like this isn't a bad compromise.
tikhonj 15y ago
The definition of multimethods presented here sounds suspiciously like ad-hoc polymorphism (or just overloading functions). It seems like the real difficulty is not in the concept but in the fact that I've now seen under three different names: multiple-dispatch, ad-hoc polymorphism and overloading. All but the last name seem complex; since I initially encountered the concept in Java as overloading, I never thought much about it. Polymorphism based on types like this is something that statically typed languages are naturally good at. Looking at his example code, the trick to having this sort of code in dynamically typed Python is to introduce type annotations via decorators. You're doing the work of static typing for a fraction of the benefits. Additionally, a statically typed language can take this concept even further. Haskell, for example, supports polymorphic functions like this very well using type classes. It even allows functions polymorphic on their return types--you can have a function `read` which takes a String and returns whatever. This means you can actually even have polymorphic constants--maxBound, for example, is the maximum value of whatever numerical representation it happens to be. Overall, I think features like this make more sense in a statically typed language. They fit in--you're already specifying types everywhere--and can do more. However, it is interesting to see how you could accomplish something like this in a dynamically typed language.
- swannodette 15y ago
  I think you're getting distracted by the simplistic implementation presented here. multimethods are plenty powerful outside of static types - see CLOS, Clojure. That said multimethods are a halfway step to predicate dispatch (this is mentioned in the article comments). With predicate dispatch you can get efficient dispatch on any interesting predicate - not just types - for example even?, odd?, structural matching, etc. I think dynamic languages could benefit a lot from predicate dispatch.
- jules 15y ago
  Multimethods and overloading are completely different beasts, despite the syntactic similarity. Overloading is resolved at compile time by looking at the compile time types. Multimethods are dispatched at run time, by looking at the run time values. This makes overloading much less powerful. Multimethods are in fact problematic in statically typed languages; they are difficult (but not impossible) to type check.
mhb 15y ago
Not the main point but if the if-else pattern gets tedious why is there no switch in Python?
- adobriyan 15y ago
  COND, man, COND.
- tikhonj 15y ago
  In this case, a switch statement wouldn't help because you're dealing with a bunch of boolean functions rather than a single value. If you were using something like typeof and switched on the type, a switch statement would make more sense. However, even that would be pretty tedious for code like this, I think. In general though, I have no idea why Python doesn't have a switch or case statement of some sort.
  - yummyfajitas 15y ago
    Now it's a single value: case [typeof(X) for x in X] of: [int, int]: ... [int, float]: ...
    - icebraining 15y ago
      { (int, int): methodWithTwoInts, (int, float): methodsWithIntAndFloat, ... }[ tuple([typeof(x) for x in X]) ]()
      - adobriyan 15y ago
        Actually this is better that switch (or whatever). Some advanced dispatch code can notice that some tuples are dispatched more often that the rest and can check for them first. Ditto for dict lookup. But this would unexpected for switch code.
  - candeira 15y ago
    Python doesn't need a switch or case statement because you can write a suite of ad-hoc functions, stick them in a dictionary with your values as keys, and dispatch on the values: >>> def first(): ... print "a" ... >>> def second(): ... print "beta" ... >>> caseof = {1: first, 2: second} >>> caseof[1]() a >>> caseof[2]() beta >>>
agentultra 15y ago
http://en.wikipedia.org/wiki/Multiple_dispatch#Common_Lisp http://en.wikipedia.org/wiki/Multiple_dispatch#Common_Lisp I tend to prefer the (defmethod) form in CL. You get generic functions which can retrieve the function object specialized for the parameters with (find-method). You also get the auxiliary method goodness... But the great thing with Python that the article shows is that there's probably a way you can get those things in Python too if you needed them. So does Python have multiple dispatch or can you just implement it?
- swannodette 15y ago
  The challenge with expressive features like multimethods - does your language give you the tools not only to implement it, but to make it fast? This is yet another benefit of macros - the ability to add features like this and get good, perhaps even great, performance.
andrewcooke 15y ago
pytyp will also do this, if anyone is interested - http://acooke.org/pytyp/pytyp.spec.dispatch.html http://acooke.org/pytyp/pytyp.spec.dispatch.html (in addition, it can be used to add type checking, and type-guided translation between json and python objects. it will also dispatch on "compound" types, like a list of integers).
antihero 15y ago
"a function that has multiple versions, distinguished by the type of the arguments" Ooh, C# style overloading.
- Anchor 15y ago
  Yes, but not quite. Consider the following example: static void Main() { Bar( 12, 15 ); } static void Bar( object o1, object o2 ) { Foo( o1, o2 ); // error } static void Foo( int x, double y ) { Console.WriteLine( "int double" ); } static void Foo( double x, int y ) { Console.WriteLine( "double int" ); } static void Foo( double x, double y ) { Console.WriteLine( "double double" ); } static void Foo( int x, int y ) { Console.WriteLine( "int int" ); } This does not compile as the compiler does not know which of the four versions it should call. As jules said overloading is resolved at compile time by looking at the compile time types. Multimethods are dispatched at run time, by looking at the run time values. In this case that would be the "int int" version.
  - burgerbrain 15y ago
    I'm not really up on this stuff, but that strikes me as an implementation detail. Does it really need a new name?
  - robododo 15y ago
    Thanks for the explanation. That's cool and all, but why wouldn't I just define an interface with method foo(), then override foo on my classes? This feels like class-based OO turned inside out.
    - drblast 15y ago
      "At run time" is the key. Consider Java. If Dog and Cat are subclasses of Animal (or implement an Animal interface), for example, I might want to use a "breed" method to attempt to breed a hybrid animal with the loyalty of a cat and the stealth of a dog. public Animal breed(Animal a, Animal b) { // return generic Animal } public Animal breed(Dog a, Cat b) { //return Cog } But at compile time, if all I know is that I have two animals to breed, Java will ALWAYS pick the breed() method with the Animal arguments, even if the run-time types will be Dog and Cat. To solve this problem in Java you have to delve into the hideous Java reflection object and litter your code with junk that you'd wish the language would figure out for you. When you've used a language that is aware of types at run time and supports multi-method dispatch, anything else seems like it's half-baked OO.
datashaman 15y ago
This obfuscates code, and I remove it wherever I see it. Sometimes people are too clever for their own good. Use an object. Override a method, FFS.
- barrkel 15y ago
  Any trivial example demonstrating how something like this works will seem obfuscatory, because examples are usually trivially solved with other approaches. But see the Expression Problem[1] for the deep problem. Whether it's an appropriate solution depends on whether introducing new operations or new data types is more common; and where the modularity boundaries are. For example, what if the base class in the hierarchy doesn't have a method for the task you want to perform, and you can't add one because it belongs to third party code, and nor can you implement it appropriately for every descendant? [1] http://en.wikipedia.org/wiki/Expression_problem http://en.wikipedia.org/wiki/Expression_problem
chadrs 15y ago
I did something similar and tried to implement functional language style pattern matching in python: https://gist.github.com/1320421 https://gist.github.com/1320421 Not to actually use, of course.
deleted 15y ago
[deleted]
- judofyr 15y ago
  The difference between multimethods and pattern matching is that pattern matching is usually "closed" (you can't add new clauses somewhere else), while multimethods allow you to extend the method with additional functionality.
daenz 15y ago
This is kind of crazy. I had written pypolymorph independently a few months ago that does this same thing: https://github.com/amoffat/pypolymorph https://github.com/amoffat/pypolymorph
ianb 15y ago
Since people are throwing out similar kinds of implementations, here's my pattern matching library (which is kind of the same thing as multimethods, but allowing more arbitrary matching than just based on type): http://svn.colorstudy.com/home/ianb/recipes/patmatch.py http://svn.colorstudy.com/home/ianb/recipes/patmatch.py

113 points by llambda 15y ago

SammyRulez 15y ago

The power of a static typing in a dynamic typed language.. that's great.. and elegant too! GO BDFL !

tikhonj 15y ago
Except that you have to statically specify the types using decorators. So it's more like a subset of static typing in a dynamically typed language.
- skimbrel 15y ago
  It's not a subset of static typing at all. If multimethods were a subset of static typing, then regular methods would be too. Methods are dynamic by definition: the type of the method's target is inspected at runtime and used to dispatch to the correct function entry. In Python, it's explicitly stated because the first argument of all object methods is "self". Multimethods extend this to do dynamic dispatch on all argument types, not just the target object. Most Python object methods are declared at compile time; this doesn't make method declaration a "subset of static typing". You can add new methods to classes and objects at runtime using Python's reflection and introspection; you can just as easily add new multimethods at runtime using this framework. Finally, the @decorator(...) syntax at compile time is just syntactic sugar for something like the following: def _foo(self, arg): ... foo = decorator()(_foo) So you can use decorators at runtime whenever you want too.
radarsat1 15y ago
Actually it's just checking the types at runtime, nothing much 'static' about it. This is pretty much the antithesis of duck typing, in fact. I could see it being useful, but I could also see it leading to confusion for people who expect Python's usual duck-typing behaviour when they pass their own types into a function. Whoops you subclassed from a type for which this function has a multimethod defined? Gonna do something different. On the other hand, in non-trivial programs there _are_ certainly occasions when you need to check the type, so using an elegant method like this isn't a bad compromise.

tikhonj 15y ago

The definition of multimethods presented here sounds suspiciously like ad-hoc polymorphism (or just overloading functions). It seems like the real difficulty is not in the concept but in the fact that I've now seen under three different names: multiple-dispatch, ad-hoc polymorphism and overloading. All but the last name seem complex; since I initially encountered the concept in Java as overloading, I never thought much about it. Polymorphism based on types like this is something that statically typed languages are naturally good at. Looking at his example code, the trick to having this sort of code in dynamically typed Python is to introduce type annotations via decorators. You're doing the work of static typing for a fraction of the benefits. Additionally, a statically typed language can take this concept even further. Haskell, for example, supports polymorphic functions like this very well using type classes. It even allows functions polymorphic on their return types--you can have a function `read` which takes a String and returns whatever. This means you can actually even have polymorphic constants--maxBound, for example, is the maximum value of whatever numerical representation it happens to be. Overall, I think features like this make more sense in a statically typed language. They fit in--you're already specifying types everywhere--and can do more. However, it is interesting to see how you could accomplish something like this in a dynamically typed language.

swannodette 15y ago
I think you're getting distracted by the simplistic implementation presented here. multimethods are plenty powerful outside of static types - see CLOS, Clojure. That said multimethods are a halfway step to predicate dispatch (this is mentioned in the article comments). With predicate dispatch you can get efficient dispatch on any interesting predicate - not just types - for example even?, odd?, structural matching, etc. I think dynamic languages could benefit a lot from predicate dispatch.
jules 15y ago
Multimethods and overloading are completely different beasts, despite the syntactic similarity. Overloading is resolved at compile time by looking at the compile time types. Multimethods are dispatched at run time, by looking at the run time values. This makes overloading much less powerful. Multimethods are in fact problematic in statically typed languages; they are difficult (but not impossible) to type check.

mhb 15y ago

Not the main point but if the if-else pattern gets tedious why is there no switch in Python?

adobriyan 15y ago
COND, man, COND.
tikhonj 15y ago
In this case, a switch statement wouldn't help because you're dealing with a bunch of boolean functions rather than a single value. If you were using something like typeof and switched on the type, a switch statement would make more sense. However, even that would be pretty tedious for code like this, I think. In general though, I have no idea why Python doesn't have a switch or case statement of some sort.
- yummyfajitas 15y ago
  Now it's a single value: case [typeof(X) for x in X] of: [int, int]: ... [int, float]: ...
  - icebraining 15y ago
    { (int, int): methodWithTwoInts, (int, float): methodsWithIntAndFloat, ... }[ tuple([typeof(x) for x in X]) ]()
    - adobriyan 15y ago
      Actually this is better that switch (or whatever). Some advanced dispatch code can notice that some tuples are dispatched more often that the rest and can check for them first. Ditto for dict lookup. But this would unexpected for switch code.
- candeira 15y ago
  Python doesn't need a switch or case statement because you can write a suite of ad-hoc functions, stick them in a dictionary with your values as keys, and dispatch on the values: >>> def first(): ... print "a" ... >>> def second(): ... print "beta" ... >>> caseof = {1: first, 2: second} >>> caseof[1]() a >>> caseof[2]() beta >>>

agentultra 15y ago

http://en.wikipedia.org/wiki/Multiple_dispatch#Common_Lisp http://en.wikipedia.org/wiki/Multiple_dispatch#Common_Lisp I tend to prefer the (defmethod) form in CL. You get generic functions which can retrieve the function object specialized for the parameters with (find-method). You also get the auxiliary method goodness... But the great thing with Python that the article shows is that there's probably a way you can get those things in Python too if you needed them. So does Python have multiple dispatch or can you just implement it?

swannodette 15y ago
The challenge with expressive features like multimethods - does your language give you the tools not only to implement it, but to make it fast? This is yet another benefit of macros - the ability to add features like this and get good, perhaps even great, performance.

andrewcooke 15y ago

pytyp will also do this, if anyone is interested - http://acooke.org/pytyp/pytyp.spec.dispatch.html http://acooke.org/pytyp/pytyp.spec.dispatch.html (in addition, it can be used to add type checking, and type-guided translation between json and python objects. it will also dispatch on "compound" types, like a list of integers).

antihero 15y ago

"a function that has multiple versions, distinguished by the type of the arguments" Ooh, C# style overloading.

Anchor 15y ago
Yes, but not quite. Consider the following example: static void Main() { Bar( 12, 15 ); } static void Bar( object o1, object o2 ) { Foo( o1, o2 ); // error } static void Foo( int x, double y ) { Console.WriteLine( "int double" ); } static void Foo( double x, int y ) { Console.WriteLine( "double int" ); } static void Foo( double x, double y ) { Console.WriteLine( "double double" ); } static void Foo( int x, int y ) { Console.WriteLine( "int int" ); } This does not compile as the compiler does not know which of the four versions it should call. As jules said overloading is resolved at compile time by looking at the compile time types. Multimethods are dispatched at run time, by looking at the run time values. In this case that would be the "int int" version.
- burgerbrain 15y ago
  I'm not really up on this stuff, but that strikes me as an implementation detail. Does it really need a new name?
- robododo 15y ago
  Thanks for the explanation. That's cool and all, but why wouldn't I just define an interface with method foo(), then override foo on my classes? This feels like class-based OO turned inside out.
  - drblast 15y ago
    "At run time" is the key. Consider Java. If Dog and Cat are subclasses of Animal (or implement an Animal interface), for example, I might want to use a "breed" method to attempt to breed a hybrid animal with the loyalty of a cat and the stealth of a dog. public Animal breed(Animal a, Animal b) { // return generic Animal } public Animal breed(Dog a, Cat b) { //return Cog } But at compile time, if all I know is that I have two animals to breed, Java will ALWAYS pick the breed() method with the Animal arguments, even if the run-time types will be Dog and Cat. To solve this problem in Java you have to delve into the hideous Java reflection object and litter your code with junk that you'd wish the language would figure out for you. When you've used a language that is aware of types at run time and supports multi-method dispatch, anything else seems like it's half-baked OO.

datashaman 15y ago

This obfuscates code, and I remove it wherever I see it. Sometimes people are too clever for their own good. Use an object. Override a method, FFS.

barrkel 15y ago
Any trivial example demonstrating how something like this works will seem obfuscatory, because examples are usually trivially solved with other approaches. But see the Expression Problem[1] for the deep problem. Whether it's an appropriate solution depends on whether introducing new operations or new data types is more common; and where the modularity boundaries are. For example, what if the base class in the hierarchy doesn't have a method for the task you want to perform, and you can't add one because it belongs to third party code, and nor can you implement it appropriately for every descendant? [1] http://en.wikipedia.org/wiki/Expression_problem http://en.wikipedia.org/wiki/Expression_problem

chadrs 15y ago

I did something similar and tried to implement functional language style pattern matching in python: https://gist.github.com/1320421 https://gist.github.com/1320421 Not to actually use, of course.

deleted 15y ago

[deleted]

judofyr 15y ago
The difference between multimethods and pattern matching is that pattern matching is usually "closed" (you can't add new clauses somewhere else), while multimethods allow you to extend the method with additional functionality.

daenz 15y ago

This is kind of crazy. I had written pypolymorph independently a few months ago that does this same thing: https://github.com/amoffat/pypolymorph https://github.com/amoffat/pypolymorph

ianb 15y ago

Since people are throwing out similar kinds of implementations, here's my pattern matching library (which is kind of the same thing as multimethods, but allowing more arbitrary matching than just based on type): http://svn.colorstudy.com/home/ianb/recipes/patmatch.py http://svn.colorstudy.com/home/ianb/recipes/patmatch.py