Lambda the Ultimate

inactiveTopic David Mertz: Multimethods
started 5/31/2003; 3:39:24 AM - last post 6/11/2003; 12:42:37 AM
Ehud Lamm - David Mertz: Multimethods  blueArrow
5/31/2003; 3:39:24 AM (reads: 2604, responses: 11)
David Mertz: Multimethods
(via Daily Python-URL)

This article continues a review of advanced object-oriented programming concepts. In this installment I examine multiple dispatch, which is also called multimethods. Most object oriented languages--including Python, Perl, Ruby, C++, and Java--are intellectually descended from Smalltalk's idea of message passing, albeit with syntax and semantics only loosely related to this source. Another option, however, is to implement polymorphism in terms of generic functions; this has the advantage of enabling code dispatch based on the types of multiple objects. In contrast, the native method calling style of common OOP languages only uses a single object for dispatch switching.

A very readable and simple explanation of what multimethods are. Far too basic to interest the experts, but a good introduction if you always found the term mysterious.

Once more we see that if Scheme is not an option, Python can serve as a nice tool to explore language design ideas.


Posted to Python by Ehud Lamm on 5/31/03; 3:44:05 AM

Adewale Oshineye - Re: David Mertz: Multimethods  blueArrow
5/31/2003; 9:46:14 AM (reads: 1084, responses: 1)
Speaking of using Python to explore language design ideas: I noticed the announcement of Contacts for Python which enables one to experiment with DBC using Python. I do wonder if any language really needs assertions, DBC, unit testing and static typing. There seems to be so much overlap between these ideas that some subset ought to suffice.

Ehud Lamm - Re: David Mertz: Multimethods  blueArrow
5/31/2003; 9:53:30 AM (reads: 1120, responses: 0)
In theory. The current state of the art, such as it is, requires you to use all of these (and more) to achieve acceptable reliability.

Dominic Fox - Re: David Mertz: Multimethods  blueArrow
6/1/2003; 11:54:48 AM (reads: 982, responses: 1)
I'm puzzled: how is dispatching on the type of the argument(s) different from what C++/Java do with multiple method signatures? Or isn't it? Obviously C++/Java decide which way to branch at compile-time...

It also seems to me that the Python techniques Mertz outlines (which look like they're based, like many other clever things in Python, on intercepting method calls using __getattr__ and __setattr__) remain less sophisticated than what you can do in Haskell with pattern matching - e.g. dispatch not only on type but also on value. This isn't an inherent limitation of Python, however.

To the extent that multimethods are useful, I guess they argue for the usefulness of static typing. In Python you can never know for sure if an object having class Foo will really be the Foo-instance you expect: it might have been created using a metaclass that alters its behaviour, or it might have had methods added and removed dynamically at run-time.

Zope interfaces may be a better way of documenting the expectations it's reasonable to have of an object. You can actually implement a full blown run-time interface-checking system fairly easily in Python, by adding a list to each class that states what interfaces objects passed to each of its methods must implement and checking them in __getattr__ and __setattr__ before passing them along to the methods themselves; it's also possible to create "interface safe" collections the same way, by subclassing Dictionary and overriding its methods...

Dan Shappir - Re: David Mertz: Multimethods  blueArrow
6/1/2003; 1:41:44 PM (reads: 971, responses: 0)
I'm a bit disappointed by this article. While it's obvious that David Mertz understands multimethods, he neglected to emphasize a critical point. This point is actually critical for standard OOP as well. David Mertz contrasts a hardcoded dispatching code (what he calls "old-fashioned procedural") with OOP dynamic dispatch, saying "OOP merely adds some elegance".

I don't know about elegance, but to me the main difference is that the hardcoded dispatching needs to be explicitly aware of all possible types at compile-time. Dynamic dispatch, as its name implies, does not require this static encoding. The whole "old code calling new code" thing that is the OOP mantra. The same is even more true for multimethods.

David Mertz also comments on the ability to add/remove dispatching rules at runtime saying "...makes multiple dispatch using multimethods a bit more dynamic than in a static class hierarchy". IMO this is a significant understatement. This sort of dynamism makes it possible to create all sort of evolving rule-based systems that are hard to do in standard OOP (well, Python's dynamic nature does make it easier than other, more static, OOPLs).

I started to implement something similar in JavaScript, over BeyondJS, a while back but got sidetracked. I intended to support dispatching rules not only limited to object type but also to object value.

Aaron Ucko - Re: David Mertz: Multimethods  blueArrow
6/1/2003; 6:53:24 PM (reads: 981, responses: 0)
Multimethods generally resolve at runtime, based on dynamic types; this approach is much more powerful than C++-style static resolution, which does not in general have access to all the information you'd like to use.

Yes, patterns give you the same functionality, but you have to make sure that you list more specific patterns before less specific ones; multimethods allow bodies to appear in any order, which is particularly useful if they might not all come from the same source file. (Granted, splitting bodies up may make manual tracing harder, but it also makes it possible to extend multimethods defined elsewhere without having to duplicate any of the original cases.)

Also, predicate types (perhaps implicitly defined in a signature) give multimethods pattern-level granularity, at the cost of making certain relative specificity judgments undecidable. :-/

David Mertz - Re: David Mertz: Multimethods  blueArrow
6/9/2003; 10:35:13 PM (reads: 732, responses: 0)
Couple comments since I wrote the mentioned article.

Dominic Fox wrote: |look like they're based, like many other clever things in Python, on |intercepting method calls using __getattr__ and __setattr__) remain |less sophisticated than what you can do in Haskell with pattern |matching - e.g. dispatch not only on type but also on value.

I like Haskell, and recognize that it does what it does better than Python-imitating-Haskell can. But I don't know about Haskell pattern matching on values, only on types. Of course, -guards- can match value, but that's the same thing as a conditional in most any programming language. Can you give me a 3-line example of what you mean? (btw. multimethods.py does not use __getattr__ anywhere; not that there's anything wrong with that magic, but I think my style is more elegant).

Dan Shappir wrote: |I don't know about elegance, but to me the main difference is that |the hardcoded dispatching needs to be explicitly aware of all |possible types at compile-time.

I cannot at all see why procedural code needs to be aware of all possible types. Maybe Shappir is more focused on a dynamic versus static typing issue. Here's some procedural code (in Python):

  if type(x) is IntType:
     do_an_int_thing(x)
  elif type(x) is StringType:
     do_a_string_thing(x)
  else:
     do_a_generic_thing(x)

No OOP to be seen anywhere.

Dan Shappir - Re: David Mertz: Multimethods  blueArrow
6/10/2003; 6:45:53 AM (reads: 728, responses: 0)
I cannot at all see why procedural code needs to be aware of all possible types. Maybe Shappir is more focused on a dynamic versus static typing issue.

Probably the most common OOP example is the shape drawing example (in the C++ style (sorry, I'm not a Python expert):

void doDraw(Shape* shape)
{
  if ( shape ) shape->draw();
}

where Shape is an abstract base class (or interface) from which a family of shapes are derived. Now if you added a new shape to the system doDraw() doesn't change. You don't even need to recompile it. That's what I ment by "old code calling new code".

With procedural coding:

void doDraw(Shape* shape)
{
  if ( !shape ) return;
  Circle* circle = dynamic_cast<Circle*>(shape);
  if ( circle ) { drawCircle(circle); return; }
  Square* square = dynamic_cast<Square*>(shape);
  if ( square ) { drawSquare(square); return; }
...

Each time you add a new shape this version of doDraw must be updated. In your sample you have a do_a_generic_thing fallback. But how can you implement a generic, yet type dependant, function without dynamic dispatch of some sort?

BTW, my general attitude with this whole thing is "use static dispatch when I can, use dynamic dispatch when I must"

David Mertz - Re: David Mertz: Multimethods  blueArrow
6/10/2003; 10:39:53 AM (reads: 718, responses: 3)
Dan Shappir: "But how can you implement a generic, yet type dependant, function without dynamic dispatch of some sort?"

I agree with Shappir that you need some form of dynamic dispatch to implement generic calls. I just don't see that as implying OOP, per se. But in part, this is a semantic quibble--you could say that anything that implements dynamic dispatch is thereby a kind of OOP, whatever the particular syntax. After all, Python, Ruby, and other OOP languages are themselves written in C... so obviously there is SOME way to implement OOP in procedural code.

Btw. How do I get my posts to have properly indents and line-breaks on this website? My Python sample above turned into a mess (as did my attempts to quote other posters, but that is easier to read past).

Ehud Lamm - Re: David Mertz: Multimethods  blueArrow
6/10/2003; 10:44:15 AM (reads: 748, responses: 0)
You can use most HTML tags. I usually use pre when I post code. Another option is to use a fixed font.

Ehud Lamm - Re: David Mertz: Multimethods  blueArrow
6/10/2003; 10:54:12 AM (reads: 744, responses: 0)
People often disagree on what OOP really means. I think this question is worth investigating, even if at times it does look like splitting hairs.

For some OOP is about message passing, for others it is mainly about extending and reusing ADTs. Others insist on polymorphism, state or whatever.

I think it is helpful to see how all these semantic features are derived from the more low level smantics of inheritance (i.e, dispatching etc.) Interestingly enough many find the way inheritance works to be problematic (hence the need for length discussions on things like the LSP, "everything is an object", co/contra-variance etc.) Yet it is very hard to dissect inheritacne into a set of more fine grained features, even if theoretically each such feature would be useful for different things.

It's more of a "take it, or leave it" situation.

Flame away...

Dan Shappir - Re: David Mertz: Multimethods  blueArrow
6/11/2003; 12:42:37 AM (reads: 738, responses: 0)
I agree with Shappir that you need some form of dynamic dispatch to implement generic calls. I just don't see that as implying OOP.

I never claimed that dynamic dispatch is unique to OOP, indeed several non-OO PLs implement dynamic dispatch (for example, using multimethods ;-).

OTOH procedural PLs often do not intrinsically provide this facility. C is a good case-in-point. In order to achieve dynamic dispatch in C you must manually construct the facility (probably using function pointers). I guess that most C programmers just do without (you don't need dynamic dispatch to be Turing complete).

Oh, and please call me Dan, not Shappir.