6 ms·
Ovld – Efficient and featureful multiple dispatch for Python
- linschn 1y agoOne the one hand, this is pretty cool, the API is pythonic and makes quite a lot of sense. On the other hand, I can't stop myself from thinking about "Greenspun's tenth rule": > Any sufficiently complicated C or Fortran program contains an ad hoc, informally-specified, bug-ridden, slow implementation of half of Common Lisp. This doesn't apply directly here, as the features are intentional and it seems they are not bug ridden at all. But I get a nagging feeling of wanting to shout 'just use lisp!' when reading this. https://wiki.c2.com/?MultiMethods https://wiki.c2.com/?MultiMethods
- deleted 1y ago[deleted]
- hasley 1y agoI am thinking more about Julia here - which I would use if Python was not that common in several communities.
- pansa2 1y agoIs it common in Julia to use multiple-dispatch on 3 or more arguments, or just double-dispatch? Julia definitely made the right choice to implement operators in terms of double-dispatch - it’s straightforward to know what happens when you write `a + b`. Whereas in Python, the addition is turned into a complex set of rules to determine whether to call `a.__add__(b)` or `b.__radd__(a)` - and it can still get it wrong in some fairly simple cases, e.g. when `type(a)` and `type(b)` are sibling classes. I wonder whether Python would have been better off implementing double-dispatch natively (especially for operators) - could it get most of the elegance of Julia without the complexity of full multiple-dispatch?
- ChrisRackauckas 1y agoIt's not uncommon to dispatch on 3 or more arguments. Linear algebra specializations are one case where I tend to do this a lot, for example specializing on structured matrix types (block banded matrices) against non-standard vectors (GPU arrays), you then need to specialize on the output vector to make it non-ambiguous in many cases.
- StefanKarpinski 1y agoThe paper "Julia: Dynamism and Performance Reconciled by Design" [1] (work largely by Jan Vitek's group at North Eastern, with collaboration from Julia co-creators, myself included), has a really interesting section on multiple dispatch, comparing how different languages with support for it make use of it in practice. The takeaway is that Julia has a much higher "dispatch ratio" and "degree of dispatch" than other systems—it really does lean into multiple dispatch harder than any other language. As to why this is the case: in Julia, multiple dispatch is not opt-in, it's always-on, and it has no runtime cost, so there's no reason not to use it. Anecdotally, once you get used to using multiple dispatch everywhere, when you go back to a language without it, it feels like programming in a straight jacket. Double dispatch feels like kind of a hack, tbh, but it is easier to implement and would certainly be an improvement over Python's awkward `__add__` and `__radd__` methods. [1] https://janvitek.org/pubs/oopsla18b.pdf https://janvitek.org/pubs/oopsla18b.pdf
- ethagnawl 1y agoI will forever think of this talk by Peter Siebel (author of Practical Common Lisp) whenever I hear about multiple dispatch: https://youtu.be/VeAdryYZ7ak?si=wY3RmcRnW96jxQQm https://youtu.be/VeAdryYZ7ak?si=wY3RmcRnW96jxQQm
- cdrini 1y agoThat's a very long video you've linked to :P could you talk about why multiple dispatch reminds you of that talk?
- ethagnawl 1y agoSeibel spends a fair amount of time talking about how powerful and flexible CL's dynamic dispatch mechanism is and how/why it was still a novel feature at the time (~15 years ago).
- upghost 1y agoIt's actually more like "just use Haskell". Having written one of these[1] a decade ago and inflicting it (with the best of intentions) upon production code in anger, I can tell you this often leads to completely unmaintainable code. It is impossible to predict the effect of changing a method, tracing a method, debugging a method (where do I put the breakpoint??). The code reads beautifully though. Pray you never have to change it. The reason I say "just use haskell" instead of lisp is bc lisp generics suffer from this same problem. Btw if anyone has a solution to this "generic/multidispatch maintainability in a dynamically typed language" problem I would love to hear it. [1]: https://github.com/jjtolton/naga/blob/master/naga/tools.py https://github.com/jjtolton/naga/blob/master/naga/tools.py
- Fr0styMatt88 1y agoI’ve been doing the once-every-few-years deep dive into Smalltalk that I tend to do out of curiosity and this kind of question is one that always comes up for me. The answer there seems to be “the whole environment and philosophy is geared to work that way”; a dynamic language needs a lot of tooling support and interactivity.
- igouy 1y ago> this kind of question Which kind-of question? "where do I put the breakpoint??"
- Fr0styMatt88 1y agoNo specifically the question of how do you write maintainable code with generic multi-dispatch and highly dynamic languages. I like Python, but I like static typing too because there’s just less to think about and when I have to learn a new codebase there’s a lot of assumptions I can lean on about how things work; this saves time. I like the idea of Smalltalk and when you watch Alan Kay or Dan Ingalls talk about it, they make total sense and you have Pharo and Squeak to back it up as in “yes, you can build large systems with this idea”. But I don’t think you could program Smalltalk and have it be maintainable without everything else the environment brings. Being inside the environment with your objects. The total different approach of sending a message an object doesn’t understand, then having the debugger pop up and then you just implementing that message right there. That’s just an utterly different workflow. I like the idea in ‘late binding of all things’ and I think the approach of writing a DSL for your problem and then having to write far less code to solve your problem is great. But the objection is then always “okay but what about when someone else has to work with that code”. I guess what I’m trying to say is, the more dynamic your language is, the more support you need from your tooling to ease the cognitive load while you program, simply because the state-space of things you can do is bigger and not being restricted by types, etc.
- ziihrs 1y agoI'm curious about what makes this implementation faster than the alternatives. Also, if you care about function call performance, I guess you'd use PyPy. Have you tried to run the benchmarks (with appropriate warmup) on PyPy to see if the results carry over?
- breuleux 1y agoMainly codegen. Most other libraries do something like `return dispatch_dictionary[tuple(map(type, args))](*args)`. Whereas ovld generates a specialized function to the set of actual signatures of the overloads (still with a dictionary, but you remove a surprising amount of overhead just from removing varargs). The code is registered in the linecache, so you can step into it with pdb if you want to look at it. After that I became a bit obsessive about pushing it further and further (because it's fun). So... when dependent types are involved, it will actually generate custom dispatch code, e.g. if you define an @ovld with x:Literal[0], for example, it will generate an `if x == 0` in the int dispatch path (and you can define custom codegens for new types like Regexp). Regarding PyPy, I did run some benchmarks recently (I use pytest-benchmark). The advantage over other libraries remains and the magnitude is similar, but when I compare with custom if/isinstance code, that code is optimized a lot more aggressively and it gains a significant edge (let's say ~5x). Now, since I'm into codegen, part of me feels like meeting the challenge and figuring out a way to generate optimal code from a set of signatures, but I think I've spent enough time as it is haha.
- ziihrs 1y agoVery interesting, thanks for the explanation!
- blu3h4t 1y agoWhy is it made look like it’s called by the nickname of a prominent Perl hacker? :D
- shawn_w 1y agoNot just a prominent perl hacker, but one who's been working on a major new OO system for the language.
- blu3h4t 1y agoYea, I know right, Before I had a joke about Perl like this: Perl is like nineties music, it’s simply the best of all times. :) But a few days ago I made a new one up: Perl is a shrodingers programming language. :D
- shawn_w 1y ago>Perl is like nineties music, it’s simply the best of all times. You called that a joke, but I think it's just the truth.
- perlgeek 1y agoIt also looks familiar to multi dispatch in Raku, formerly Perl 6. See for example https://docs.raku.org/language/functions#Multi-dispatch https://docs.raku.org/language/functions#Multi-dispatch
- rahulprasath 1y agoWhy don’t mainstream languages like Python just support multimethods directly?
- RadiozRadioz 1y agoMany of them do, e.g. Java. Why don't _some_ mainstream languages like Python not support it? Entirely design preference, usually because they want to have less emphasis on the type system.
- pdhborges 1y agoJava supports it? Are you conflating method overload (which is statically determined) with multimethods?
- perlgeek 1y agoProbably because typing in Python is optional and kinda bolted-on after the fact, and you really need a good type system to get the most out of multimethods. In particular, type declarations, as they were first introduced in python, did not have a run-time effect, and they very much have a run-time effect with multi methods. (Dataclasses are kind of an exception to this rule, but one that feels far less fundamental than multi dispatch would).
- photios 1y agoLord, have mercy on the souls of those developers that inherit such overload-infested codebases.
- Iwan-Zotow 1y agoAI has no soul
- paddy_m 1y agoThis looks really cool. I get multiple dispatch, multi methods, and CLOS method specialization confused in my head. I can understand what this does... But when do you use it. Can people list some times when they actually used multimethods to solve a real problem? How did it work out? Would you do it again?
- nbadg 1y agoAlso, dependent types, IE value-based dispatch. Which can be incredibly useful when dealing with enums. That alone is enough to make me curious to try it!
- paddy_m 1y agoValue based dispatch is a much better name for it then Dependent Types. I have seen the term dependent types and just glossed over it because I thought it was a more complex topic.
- breuleux 1y agoYeah, I suppose. I wrote "dependent" because I think that's the term of art of it, but you're making me think I should probably change the header to something more intuitive to people unfamiliar with type theory.
- paddy_m 1y agoI was just commenting that I had glossed over that in multiple readings about different typing systems. The parent of my original comment explained it nicely. I know that dependent type is the term of art, and you should probably keep it. You could say something along the lines of "ovld supports dependent types (an additionally specific name for a type that is based on its value, ie > 0)" the first time you use the term dependent types."
- SatvikBeri 1y agoMy company has used Julia for about 5 years now. 90% of the time in application code you only need single dispatch, same as OOP. One case where I actually rely on multiple dispatch is conversion to more or less structured data. Inspired by Clojure, I have a function `conform(OutputDataType, input_data::SomeType)` and specific implementations depend on both types involved. Multiple dispatch is also really helpful when two libraries don't quite do the same thing. In python pandas, numpy, and pytorch all have slightly different implementations of x.std() (standard deviation) with slightly different APIs. This means you can't write code that's generic across a numpy array or a pytorch tensor. In Python this could only easily be fixed if library authors coordinate, but with multiple dispatch you can just fix this in your own code.
- olejorgenb 1y agoI assume this does not play ball with typehints? I don't think a decorator can "output" an @overload?
- olejorgenb 1y agoOr maybe it does: https://github.com/breuleux/ovld/blob/f254dcc6215d50d5f9c3d1c033bfc80b6968b413/src/ovld/__init__.py#L59 https://github.com/breuleux/ovld/blob/f254dcc6215d50d5f9c3d1...
- mpeg 1y agoThat's both genius and a massive hack, love it. For those who are wondering: they alias @typing.overload as @ovld only for type checkers. Normally, @typing.overload is a way to define multiple function signatures with empty bodies so your type checker can work nicely with functions that for example only return a certain type when called with a certain signature, but the function implementation is left to you and usually involves a bunch of runtime type checks to branch your logic the right way
- paddy_m 1y agoWhat is the return type of an overloaded function? I don't see that in any of the examples. I think it would make sense to have each function return either the exact same type, or a generic. @ovld(int) #all of these overloads should return an int len(a:list) -> int len(a:str) -> int #the effective type of len is len(a:Union[int, str]) -> int and then a generic example T = TypeVar('T') @ovld(T) add(a:np.int8, b:np.int8) -> np.int8 @ovld(T) add(a:np.int16, b:np.int16) -> np.int16 In the second example, I don't know how you would connect the input params to the generic T. If you put concrete types in, I see how ovld works. Am I missing something?
- breuleux 1y agoIt works, ish. Type checkers have a rule that you must have a non-stub, non-decorated overload, so if using ty for example, you need to --ignore invalid-overload. mypy doesn't seem to recognize the hack, although I could've sworn it did? Anyway, it'd be nice if we could mark a decorator as functioning like @overload but without the need for stubs.
- est 1y agohow about dispatch for both sync and async? I did this: https://news.ycombinator.com/item?id=43982570 https://news.ycombinator.com/item?id=43982570
- dfissadifdoi 1y ago[dead]