Multiple dispatch #2364
Comments
|
I agree! We have very efficient single dispatch, as well as a not-as-efficient multiple dispatch implementation in the I'd love to merge them by either making the single-dispatch version of multi-dispatch just as fast as it is now, or improving the multi-dispatch to be as fast as single-dispatch is. |
|
One thing julia has is abstract types, which I don't think factor has a great alternative to. There's singleton classes, but those are instances of themselves, which isn't the most desirable behavior (the class of numbers is not a number). I also don't think you can inherit from a singleton type, which kinda defeats the purpose. |
|
abstract classes: USING: kernel classes classes.private words parser math sequences combinators classes.tuple lexer vocabs.parser ;
IN: classes.abstract
PREDICATE: abstract-class < class abstract-class word-prop ;
: abstract-class-instance? ( abs-class class -- ? )
[ 2dup =
[ 2drop t ]
[ superclass-of abstract-class-instance? ] if
] [ drop f ] if* ; ! this if* uses the fact that f is used as the top class
M: abstract-class instance? swap class-of superclass-of abstract-class-instance? ;
: define-abstract-class ( word superclass -- )
[ { } clone dup clone abstract-class define-class ]
[ "superclass" set-word-prop ]
[ drop
[ t abstract-class set-word-prop ]
[ set-last-word ] bi
] 2tri ;
: parse-abstract-class-definition ( -- word superclass )
scan-token current-vocab create-word \ ; parse-until
{ { [ dup length 0 = ] [ drop f ] } ! no superclass specified
{ [ dup [ first \ < = ] [ length 2 = ] bi and ] [ second ] }
[ "syntax error" throw ] } cond ;
SYNTAX: ABSTRACT: parse-abstract-class-definition define-abstract-class ;
! allows tuples to inherit from abstract classes (kinda important)
M: abstract-class final-class? drop f ; |
|
Multiple dispatch would be really nice! |
|
True, multiple dispatch would certainly serve a purpose, seeing how successful Julia is using it for code reuse. What about the current "experimental" multiple dispatch code by Slava (vocabulary multi-methods)? |
|
Just going through one of Slava's (@slavapestov) old posts on the optimizing compiler, in which he writes: |
|
It seems Slava (@slavapestov) did indeed progress beyond this point in his post on polymorphic inline caching. Not sure if more recent progress was made on speeding up polymorphic dispatch. Nor how that would look like for multiple dispatch. |
|
Yup, found another, but older post on multi-methods, which gave some more details : "The powerful thing about this new implementation of hooks is that not only can you dispatch on multiple variables, but you can add methods to any old generic which dispatches on a variable and the original designer of the generic does not have to explicitly take this into account." "The other nice thing about this is that the multi-method GENERIC: word unifies and generalizes four words in the core, GENERIC:, GENERIC# for dispatching on a value further down on the stack, HOOK: for dispatching on a variable, and MATH: which performs double dispatch on numbers only." "All that remains to be done is to merge the multi-methods code. The code is still not quite ready to go in the core, though. The only feature that single dispatch has and multiple-dispatch lacks is call-next-method, which is easy to implement. A bigger hurdle to clear is performance; right now multi-methods are implemented in a naive way, where the dispatch time is O(mn) with m methods and n stack positions and variables to dispatch on. This can be improved significantly and I will find time reading the literature on optimizing method dispatch over the next few weeks." Note, this is from a 2008 post, 4 years before the launch of the Julia language. (B.t.w. Jeff Bezanson's thesis has details on how Julia implements its type system and multi-methods) |
|
How about a syntax like this for multimethods?
Open problems/questions:
GENERIC: length ( *obj* -- len )
M: length ( array -- n ) length>> ;
! : length ( array -- n ) length>> ; would be an error if GENERIC: length is in scope, needs M:
GENERIC: shift ( *x* n -- y ) foldable
M: shift ( bignum n -- y ) integer>fixnum bignum-shift ; inline
M: shift ( fixnum n -- y ) integer>fixnum fixnum-shift ; inline
! multiple dispatch off a and b
GENERIC: rock-paper-scissors ( *a* *b* -- a-wins? )
M: rock-paper-scissors ( scissors paper -- ? ) 2drop t ;
M: rock-paper-scissors ( rock scissors -- ? ) 2drop t ;
M: rock-paper-scissors ( paper rock -- ? ) 2drop t ;
M: rock-paper-scissors ( thing thing -- ? ) 2drop f ;
! dispatch off os dynamic variable (like HOOK:)
GENERIC: resolve-symlinks ( os | path -- path' )
M: resolve-symlinks ( windows | path -- path' ) normalize-path ;
M: resolve-symlinks ( unix | path -- path' )
path-components "/"
[ append-path dup exists? [ follow-links ] when ] reduce ;
! dispatch off two dynamic variables
GENERIC: get-editor ( os editor-class | -- path )
M: get-editor ( windows visual-studio-code | -- path ) "code.cmd" find-in-applications ;
M: get-editor ( windows visual-studio-code-insiders | -- path ) "code-insiders.cmd" find-in-applications ;
M: get-editor ( unix visual-studio-code | -- path ) "code" which ;
M: get-editor ( unix visual-studio-code-insiders | -- path ) "code-insiders" which ;With @kusumotonorio's suggestion of putting dynvars last: GENERIC: length ( *obj* -- len )
M: length ( array -- n ) length>> ;
! : length ( array -- n ) length>> ; would be an error if GENERIC: length is in scope, needs M:
GENERIC: shift ( *x* n -- y ) foldable
M: shift ( bignum n -- y ) integer>fixnum bignum-shift ; inline
M: shift ( fixnum n -- y ) integer>fixnum fixnum-shift ; inline
! multiple dispatch off a and b
GENERIC: rock-paper-scissors ( *a* *b* -- a-wins? )
M: rock-paper-scissors ( scissors paper -- ? ) 2drop t ;
M: rock-paper-scissors ( rock scissors -- ? ) 2drop t ;
M: rock-paper-scissors ( paper rock -- ? ) 2drop t ;
M: rock-paper-scissors ( thing thing -- ? ) 2drop f ;
! dispatch off os dynamic variable (like HOOK:)
GENERIC: resolve-symlinks ( path | os -- path' )
M: resolve-symlinks ( path | windows -- path' ) normalize-path ;
M: resolve-symlinks ( path | unix -- path' )
path-components "/"
[ append-path dup exists? [ follow-links ] when ] reduce ;
! dispatch off two dynamic variables
GENERIC: get-editor ( os editor-class | -- path )
M: get-editor ( | windows visual-studio-code -- path ) "code.cmd" find-in-applications ;
M: get-editor ( | windows visual-studio-code-insiders -- path ) "code-insiders.cmd" find-in-applications ;
M: get-editor ( | unix visual-studio-code -- path ) "code" which ;
M: get-editor ( | unix visual-studio-code-insiders -- path ) "code-insiders" which ; |
|
I think your suggestion of having the sequence of the dynamic variable before the output sequence is better than what I've presented before.
This is because dynamic variables that do not exist in the regular word definition are not always present in the method definition. If a generic word definition contains the names of the input (e.g. |
|
All posts I could find by Slava on multiple dispatch / multi-methods: https://factor-language.blogspot.com/2008/04/multi-methods-and-hooks.html https://factor-language.blogspot.com/2008/08/factor-is-now-five-years-old.html Interestingly enough, Slava mentioned multiple dispatch to be top priority back in 2008 "very soon I will start moving forward with the language again, with multiple dispatch at the top of the list." and he saw multiple dispatch to be a complete replacement for current single disptach, if it could be made fast enough "Let's put this another way. The following parsing words will be eliminated: "I will tackle multi-methods; what this really means is efficient implementation of multi-methods, given that an inefficient implementation already exists in extra/. This presents its own set of unique challenges but I look forward to solving that problem. [..] Once Factor has multi-methods, our object system will be comparable in power to CLOS, however I believe it will offer genuine improvements and innovations in several respects. Furthermore, the implementation will be a lot simpler than PCL." I could not find any info beyond that, especially not on how the performance improvement should be realized (other than referring to studying literature on the subject). |
It would be interesting to compare this to Slava's post on a proposed new syntax |
|
B.t.w. googling "optimizing multi-method dispatch" will give a whole array of papers and proposals for speeding up multi-methods. The catch is in the different type systems, and on implementation details/design choices of specific languages, compared to Factor's details, and how that will translate to a solution capable of replacing all single dispatches with same or better performance, as well as improving on the current O(mn) implementation in 'extras'. |
|
I want to mention that CommonLisp, especially SBCL, has very fast multi-methods for a long time. And with their Meta Object Protocol, define an interesting concept of having a default implementation of dispatch but leaving it open to the implementor to choose a different one for specific purposes. This becomes important when thinking about removing |
|
The "syntax" post by Slave seems to go into the direction of typed stack declarations, where if you omit the type, it defaults to 'object' (i.e. "determine at runtime"), otherwise it means "a type or its subtype". Pretty comparable to a lot of (even statically) typed OO languages, except for the contraints he puts that methods/words with the same name should have the same stack effect w.r.t. the number of items on the stack. Are we moving towards making everything |
|
Regarding dispatch: Methods are always |
|
It seems to me that Slava was intended to achieve something similar to the generic functions realized in other languages. However, I think it would be nice if the stack language Factor had a unique multi-dispatch function that was different from those. |
|
@erg: I like the idea of adding stack effects to all Are you proposing two alternative syntax options there? Do you propose to support both? @spacefrogg: "Methods are always |
|
Pop quiz: which is more abstract - |
|
@alexiljin the |
|
What about somethings that looks more like the existing I'm not sure I like the dynvars in the stack effect, is it more comprehensible to keep things separate? Is it really worth it to have this information stuffed in the stack effect as symbols, vs using something like I don't know, "quot: " is nice in the stack effect, so maybe the dispatch information can go there too. |
|
My suggestion of extending |
|
I'm worried about fast code being deoptimized because generic or multimethod dispatch is silently introduced, especially if it's in another file somehow. That's why the |
|
No takers on the pop quiz? |
|
Someone might reach out to Slava for some ideas or pointers... surely he is allowed to discuss it. :/ |
I don't see an immediate issue, here. Careful implementation should be able to yield a fast "normal" word lookup in case there is only one method specializing on |
That was not what I was referring to, but I was imprecise. What I meant was, everything is implicitly typed in factor. That means when you don't make type assumptions, you implicitly assume |
|
By the way, actually, The current resource:core/math/integers/integers.factor
resource:core/syntax/syntax.factor
3: USING: accessors arrays byte-arrays byte-vectors classes
4: classes.algebra.private classes.builtin classes.error
^
resource:core/classes/error/error.factor
3: USING: accessors classes.private classes.tuple
4: classes.tuple.private combinators kernel parser sequences words ;
^
resource:core/parser/parser.factor
3: USING: accessors arrays classes combinators compiler.units
^
resource:core/compiler/units/units.factor
7: QUALIFIED-WITH: multi-generic mg
^
Vocabulary does not exist
name "multi-generic" |
|
I can help get bootstrap working, is that all that’s left?
… On Feb 12, 2021, at 6:21 AM, kusumotonorio ***@***.***> wrote:
By the way, actually, "benchmark" run fails at the benchmark of boot in the middle. Also, make-my-image gives me an error.
I have built multi-generic step by step, and it works fine for me, but I don't think I can get other people to try it. That makes no sense. I would like to improve this situation somehow, but it seems to be very difficult...
The current multi-generic' requires a lot of file changes, and those files are USING:ing each other." The chain of "USING:" fails. For example, if you do make-my-image` now, you will get the following.
resource:core/math/integers/integers.factor
resource:core/syntax/syntax.factor
3: USING: accessors arrays byte-arrays byte-vectors classes
4: classes.algebra.private classes.builtin classes.error
^
resource:core/classes/error/error.factor
3: USING: accessors classes.private classes.tuple
4: classes.tuple.private combinators kernel parser sequences words ;
^
resource:core/parser/parser.factor
3: USING: accessors arrays classes combinators compiler.units
^
resource:core/compiler/units/units.factor
7: QUALIFIED-WITH: multi-generic mg
^
Vocabulary does not exist
name "multi-generic"
—
You are receiving this because you were mentioned.
Reply to this email directly, view it on GitHub, or unsubscribe.
|
|
This is probably the only thing I've changed/made: |
|
I have been working on integrating multiple dispatch with the existing inline cache mechanism, and took another look at your benchmarking code. I think it basically took caching completely out of the picture even with tuple classes, because in the : wrapped-md-beats? ( obj1 obj2 -- ? )
md-beats? ;
: wrapped-sd-beats? ( obj1 obj2 -- ? )
sd-beats? ;and in gc
[
TIMES [
paper paper wrapped-sd-beats? drop
paper scissors wrapped-sd-beats? drop
paper rock wrapped-sd-beats? drop
scissors paper wrapped-sd-beats? drop
scissors scissors wrapped-sd-beats? drop
scissors rock wrapped-sd-beats? drop
rock paper wrapped-sd-beats? drop
rock scissors wrapped-sd-beats? drop
rock rock wrapped-sd-beats? drop
] times
] benchmark
[ 1.0e9 / ] [ no-dispatch-time get / ] bi
"non-inlined sd: %.6f seconds (%.2f times slower)\n" printf
! ...
gc
[
TIMES [
paper paper wrapped-md-beats? drop
paper scissors wrapped-md-beats? drop
paper rock wrapped-md-beats? drop
scissors paper wrapped-md-beats? drop
scissors scissors wrapped-md-beats? drop
scissors rock wrapped-md-beats? drop
rock paper wrapped-md-beats? drop
rock scissors wrapped-md-beats? drop
rock rock wrapped-md-beats? drop
] times
] benchmark
[ 1.0e9 / ] [ no-dispatch-time get / ] bi
"non-inlined md: %.6f seconds (%.2f times slower)\n" printfNote that Factor has support for benchmarking dispatch with |
|
I added these to the list. ! wrapped
: wrapped-md-beats? ( obj1 obj2 -- ? )
md-beats? ;
: wrapped-sd-beats? ( obj1 obj2 -- ? )
sd-beats? ;
: wrapped-smd-beats? ( obj1 obj2 -- ? )
smd-beats? ;Wow! How effective is the inline cache you made? |
I haven't done enough testing yet to give an informed answer to that. I tested it with this some tests from this benchmark (adapted the syntax), and it has not improved anything. That was to be expected though, since the inline cache does almost nothing to accelerate runtime dispatch of predicate classes. |
|
I added a test for tuples and ran |
|
I changed my own bm to make it easier to compare. Caching during multi-dispatch is good. It is not a big difference in this example, but the difference is likely to widen when there are more methods or more parameters to specify. |
|
I have changed https://github.com/kusumotonorio/factor/tree/multi-generic I hope this will allow other people to try |
|
@kusumotonorio Why not create a pull request? That way, it is easy for others to keep up-to-date with your branch. |
|
@timor That's because I don't think it's the right time to merge it as it is. |
|
You can always mark them as draft to mark them as work in progress. I'd like to try attaching my backend implementation code to your modified syntax frontend. |
|
Apparently, I succeeded in incorporating @timor 's algorithm into my Before incorporating @timor 's code, it looked like this: |
|
Nice! That was pretty much exactly the case that I wrote that code for. I suspect that will be one of the most common ones in practice. |
|
The code I wrote in |
|
What started as an attempt of "just" using as much of In any case, feel free to pick whatever you find useful. I think supporting and extending |
Do you have a branch of that somewhere on github? |
|
It's just in my hand and I haven't uploaded it to github yet. In order to take advantage of the nice effects of your code, I have to make sure that there are no conflicts with the dispatch algorithm derived from |
|
Yes it also starts with the top of the stack. However, I implemented a check that ensures that if you have something like |
|
@timor Thanks for the useful info! I hadn't ported the code for that check. That was just a coincidence and not something I did to work around the problem. Also, what do you think I should consider in order to use If I have your permission, I'd like to incorporate it into the main branch of |
|
Feel free to use the code any way you want. Don't bother with the copyright. |
|
Thank you for your generous consideration. I transcribe the description of the commit:
e.g. MGENERIC: cached-md-beats? ( obj1 obj2 -- ? ) cached-multi
MM: cached-md-beats? ( :paper :scissors -- ? ) 2drop t ;
MM: cached-md-beats? ( :scissors :rock -- ? ) 2drop t ;
MM: cached-md-beats? ( :rock :paper -- ? ) 2drop t ;
MM: cached-md-beats? ( :thing :thing -- ? ) 2drop f ; |
|
I modified my benchmark for method dispatch which slow down when a multi-generic has many methods, to see how the speed changes with the cache-enabled dispatch algorithm using covarinat-tuple. (It is Based on the results of the previous rock-paper-scissors benchmark and @timor's previous comments, I expected that the new algorithm would be very effective for tuple dispatching, but not for singleton dispatching. However, the results were not what I expected. Its new algorithmic dispatching has a great effect on dispatching by singleton as well as tuple dispatching. That's nice to see, but it begs the question, why didn't the Rock-Paper-Scissors benchmark show such results? @timor, isn't this a strange result according to your perception? |
|
@kusumotonorio |
|
Perhaps it's time for "generic.multi: Some convience syntax for dispatch tuples d72f938". |
I've been working with Julia a lot lately and think multiple dispatch would fit Factor quite well. It would solve the problems with math functions not being extendable.
The text was updated successfully, but these errors were encountered: