The Artima Developer Community
Sponsored Link

Weblogs Forum
Dynamic Function Overloading

12 replies on 1 page. Most recent reply: Apr 10, 2006 4:44 PM by Tim Hochberg

Welcome Guest
  Sign In

Go back to the topic listing  Back to Topic List Click to reply to this topic  Reply to this Topic Click to search messages in this forum  Search Forum Click for a threaded view of the topic  Threaded View   
Previous Topic   Next Topic
Flat View: This topic has 12 replies on 1 page
Guido van van Rossum

Posts: 359
Nickname: guido
Registered: Apr, 2003

Dynamic Function Overloading (View in Weblogs)
Posted: Apr 7, 2006 7:30 PM
Reply to this message Reply
Summary
I've checked an implementation of dynamic function overloading into Python's subversion sandbox.
Advertisement

I'm going to stick to the term "(dynamically, or run-time) overloaded functions" for now, despite criticism of this term; the alternatives "generic functions", "multi-methods" and "dispatch" have been (rightly) criticized as well.

A slightly optimized implementation is here: http://svn.python.org/view/sandbox/trunk/overload/

Phillip Eby has suggested that my implementation is too slow; but I recommend that you run test_overloading.py and see for yourself. (This requires the Python 2.5a1 release that was just released from python.org.)

Phillip also suggested that I use issubclass() instead of relying on the MRO (method resolution order); he believes the MRO approach can cause false precision. I'm not sure I believe that, since for single dispatch my approach actually matches the class method lookup approach exactly.

There are tons of additional features or potential requirements. For example, should there be a mechanism to invoke the "next" applicable method? But the algorithm doesn't clearly produce a next method. Also, in the case of ambiguity, should an exception be raised or the default method be invoked? (Or perhaps the "next" method, if we can agree on what it is?)

In terms of optimization, I believe that a little bit of code generation could make overloaded functions nearly as fast as hand-coded functions; see 'accelerated' in test_overloading.py.

And no, this isn't for Python 2.5; it's a highly contagious but also highly controversial thing that should be tried out in Python 3000 (or perhaps as a 3rd party add-on for 2.5) first.

I totally forgot that I blogged about this earlier, over a year ago. My implementation then was pathetic compared to today's! Phillip's ideas have helped a lot.

My hope is to eventually drive PyProtocols out of the market. Phillip should be so proud of me. :-)


Rene Dudfield

Posts: 2
Nickname: illume
Registered: Mar, 2006

Re: Dynamic Function Overloading Posted: Apr 7, 2006 10:16 PM
Reply to this message Reply
Here's some silly ideas about using if/else and lists for it instead.

Advantages:
- familiar look. if/else and lists are understood already.
- Can iterate over large tests making them non blocking.


List style interface

eg.

# the default resolution of tests.
tests()

# loop over the tests, with some extra logic in there.
for x in tests:
if x:
some_other_statement()
if some_other_expression:
break
x()
break

# testing one part.
if tests[3]:
tests[3]()

# testing one part passing in variables for the expression.
# always using .expression() and .statement() calls.
if tests[3].expression(a=3, b=4):
tests[3].statement(44)


# remove one test.
del tests[1]

# add another test later.
tests += elif expression:
statement



Using if/else/elif for construction


Below is something which looks nice to me. Not sure if it can be manipulated into python easily.

eg.


tests = if(x == 4):
print "1 blabla :%s:" % x
tests += elif x == 55:
print "2 asdf :%s:" % x
tests += else:
print "3 qwer :%s:" % x

tests(x=44)



I think if/else are fine for most situations. Faster, and easier to read. Generic/multi/dispatching/dynamic overloading functions are good if you have hundreds of tests in 40 different files that you can't clean up to put into one file. Or if you need to modify the tests/rules at runtime.

Guido van van Rossum

Posts: 359
Nickname: guido
Registered: Apr, 2003

Re: Dynamic Function Overloading Posted: Apr 8, 2006 12:09 AM
Reply to this message Reply
I had my first hard-to-find bug with this feature.

I had written something like this:

from overloading import overloaded

@overloaded
def foo(x):
print x

@foo.register(int)
def foo(x):
print hex(x)

print foo("abc")


and got this traceback:

Traceback (most recent call last):
File "x.py", line 11, in <module>
print foo("abc")
File "x.py", line 9, in foo
print hex(x)
TypeError: hex() argument can't be converted to hex


Spoiler

It took me a while to realize that the second 'def foo' was overriding the first. The fix was to use 'def foo_hex' for the second one. I wonder if we should build in a check for this to prevent it from happening to every newbie...

Nick Coghlan

Posts: 13
Nickname: ncoghlan
Registered: Dec, 2004

Re: Dynamic Function Overloading Posted: Apr 8, 2006 12:29 AM
Reply to this message Reply
> Spoiler
>
> It took me a while to realize that the second 'def foo'
> was overriding the first. The fix was to use 'def
> foo_hex' for the second one. I wonder if we should build
> in a check for this to prevent it from happening to every
> newbie...

We could change the behaviour of register to do something like:
def register(self, signature):
def helper(f):
self.registry[signature] = f
if f.__name__ = self.__name__:
return self
return name
Reusing the same name as the function you're extending seems like a fair indication that you don't care about accessing your extension function directly.

Nick Coghlan

Posts: 13
Nickname: ncoghlan
Registered: Dec, 2004

Re: Dynamic Function Overloading Posted: Apr 8, 2006 12:31 AM
Reply to this message Reply
D'oh. Try that again, this time with the missing line included:
def register(self, signature):
def helper(f):
self.registry[signature] = f
if f.__name__ = self.__name__:
return self
return name
return helper

Phillip J. Eby

Posts: 28
Nickname: pje
Registered: Dec, 2004

Re: Dynamic Function Overloading Posted: Apr 8, 2006 3:23 AM
Reply to this message Reply
> It took me a while to realize that the second 'def foo'
> was overriding the first. The fix was to use 'def
> foo_hex' for the second one. I wonder if we should build
> in a check for this to prevent it from happening to every
> newbie...

What RuleDispatch does to deal with this, is that if the name of the decorated function is already bound to the generic function, the decorator returns the generic function instead of the registered function, so that it doesn't get overwritten.

Nick Coghlan

Posts: 13
Nickname: ncoghlan
Registered: Dec, 2004

Re: Dynamic Function Overloading Posted: Apr 8, 2006 6:02 AM
Reply to this message Reply
Third time lucky?
def register(self, signature):
def helper(f):
self._do_registration(signature, f) # Store in mapping, or maybe some other mechanism
if f.__name__ == self.__name__:
return self
return f
return helper

Eli Courtwright

Posts: 14
Nickname: eliandrewc
Registered: Jan, 2006

Re: Dynamic Function Overloading Posted: Apr 9, 2006 8:54 PM
Reply to this message Reply
So how will this interact with pydoc? If I have:

@overloaded
def foo(x):
"prints x"
print x

@foo.register(int)
def foo(x):
"prints the hex representation of x
print hex(x)

then if I look at the pydoc for the foo function, what will I see?

Tim Hochberg

Posts: 3
Nickname: timh
Registered: Apr, 2006

Re: Dynamic Function Overloading Posted: Apr 9, 2006 11:31 PM
Reply to this message Reply
Assuming overload or pydoc is smart about it, I imagine it would look something vaugely like:

>>> help(foo)
Help on function foo in module __main__:

foo(x)
print x

<int>:
prints the hex representation of x

<float>:
prints some other special representaion.

...

Mr Plonk

Posts: 2
Nickname: plonk
Registered: Mar, 2006

Re: Dynamic Function Overloading Posted: Apr 10, 2006 11:02 AM
Reply to this message Reply
> And no, this isn't for Python 2.5; it's a highly
> contagious but also highly controversial thing that should
> be tried out in Python 3000 (or perhaps as a 3rd party
> add-on for 2.5) first.

Don't understand why you'd want to "try out" new features in python 3000. If you can make backwards-incompatable changes to python in Py3k, wouldn't you want to benefit from field-testing new features in 2.X so you can possibly implement them again correctly in 3k? ;-).

I guess there must be a paragraph in one of those python 3000 meta-peps you mentioned previously that explains why my understanding of 3k isn't correct ...

Tim Hochberg

Posts: 3
Nickname: timh
Registered: Apr, 2006

Re: Dynamic Function Overloading Posted: Apr 10, 2006 3:40 PM
Reply to this message Reply
> <p>There are tons of additional features or potential
> requirements. For example, should there be a mechanism to
> invoke the "next" applicable method? But the
> algorithm doesn't clearly produce a next method. </p>

Let me float a procedure for determining the "next" method. Simply rerun the procedure for finding the main method, but with the main method excluded. To find the third method, rerun with the first two methods excluded, etc. This procedure may in fact be very slow, but the result seems sensible and perhaps a faster means can be achieved for reaching the same thing.

Guido van van Rossum

Posts: 359
Nickname: guido
Registered: Apr, 2003

Re: Dynamic Function Overloading Posted: Apr 10, 2006 3:46 PM
Reply to this message Reply
> Let me float a procedure for determining the "next"
> method. Simply rerun the procedure for finding the main
> method, but with the main method excluded. To find the
> third method, rerun with the first two methods excluded,
> etc. This procedure may in fact be very slow, but the
> result seems sensible and perhaps a faster means can be
> achieved for reaching the same thing.

But if the current method was registered in order to resolev an ambiguity, there is no "next" method -- if you re-run the algorithm with the current method's registration removed you'll get an exception.

Tim Hochberg

Posts: 3
Nickname: timh
Registered: Apr, 2006

Re: Dynamic Function Overloading Posted: Apr 10, 2006 4:44 PM
Reply to this message Reply
> > Let me float a procedure for determining the "next"
> > method. Simply rerun the procedure for finding the main
> > method, but with the main method excluded. To find the
> > third method, rerun with the first two methods
> excluded,
> > etc. This procedure may in fact be very slow, but the
> > result seems sensible and perhaps a faster means can be
> > achieved for reaching the same thing.
>
> But if the current method was registered in order to
> resolev an ambiguity, there is no "next" method -- if you
> re-run the algorithm with the current method's
> registration removed you'll get an exception.

Exactly. I don't see the concept of next-method as useful for fixing ambiguities. Instead I see it as a way for either the main method to punt on it's responsibilities, or for the caller to get a second opinion.

Perhaps I'm missing something butI just can't see what next method would mean in the ambiguous case. Perhaps if you could pass a set of functions or maybe signatures to exclude from consideration it would be useful for breaking ties:

overloaded.find_func(args, excludes=somefunctios)

You could implement next method as I proposed it on top of this trivially, so maybe this is the more fundamental construct. You could get the next method using:

overloaded.find_func(args, excludes=[first_func])

You still need to manually break up ambiguous cases by telling overloaded what functions to ignore, but I suppose this gives you a method of doing so. It does seem a little clunky though.

FWIW, when I was rewriting pprint, I kept thinking I needed a next_adapter method, but I kept being wrong. I wouldn't draw any conclusions from that, but it's one data point.

Flat View: This topic has 12 replies on 1 page
Topic: Software Architecture is Leadership Previous Topic   Next Topic Topic: Beta of Thinking in C


Sponsored Links



Google
  Web Artima.com   

Copyright © 1996-2014 Artima, Inc. All Rights Reserved. - Privacy Policy - Terms of Use - Advertise with Us