Hi Sage folks! I gave that presentation on multiple dispatch at Strange Loop last year. Since someone pointed this thread out to me and the topic of multiple dispatch and type promotion is near and dear to my heart, I thought I'd chime in. Maybe my comments will be of some use. (Btw, since some people prefer their notebooks with some explanation, if anyone would care to see a video of a similar but not quite identical talk, this one <http://vimeo.com/84661077> from CodeMesh last year is pretty close, although it spends less time on multiple dispatch and type promotion.)
On Thursday, July 17, 2014 10:35:32 PM UTC-7, Robert Bradshaw wrote: > > I'm not sure multimethods alone are enough to solve issues with > Sage's type system (e.g. coercion, where the result of a+b may happen in > a completely new domain) but they could certainly help. I'm not familiar with Sage's issues with coercion (or even what you mean exactly by coercion), so take this with a grain of salt. I'll hazard a guess that you mean the problem of how to let the user specify what to do when it encounters something like a + b where a and b are different types, one or both of which are user defined, and which may or may not know anything about each other. When developing Julia, initially we didn't realize that multiple dispatch could handle this kind of problem so elegantly, but it turns out it can, which I attempted to explain in my talk and which I will say a bit about below. On Thursday, July 17, 2014 11:56:43 PM UTC-7, Nils Bruin wrote: > > In a dynamically typed language, multiple dispatch has a rather high cost. > LISP MOP implementations have a lot of experience. > If Julia has shown anything, it's that you *can* have ubiquitous multiple dispatch in a dynamic language and have it be very fast – it is commonly a zero-cost abstraction in Julia. First let me explain how multiple dispatch allows a promotion system that users can hook into for their own types by explaining how 1 + 2.5 works in Julia. 1 and 2.5 are of type Int and Float64 respectively, both of which are defined in Julia <https://github.com/JuliaLang/julia/blob/876e0d3cc3d0b7198875778a9dde3abb0c5f8444/base/boot.jl#L178-L200> just like any user-defined type would be. When you do 1 + 2.5, there is no specific method for +(::Int, ::Float64), so a very generic fallback method <https://github.com/JuliaLang/julia/blob/00528ae4a9cccbbd908fa2b8180f612d3e87b72e/base/promotion.jl#L158> is called: +(x::Number, y::Number) = +(promote(x,y)...) This tries to add a pair of generic numbers by calling promote(1,2.5) to convert 1 and 2.5 to a common type, and then calling the + function on the resulting like-typed pair. The promote function itself is just a generic function, defined in Julia <https://github.com/JuliaLang/julia/blob/00528ae4a9cccbbd908fa2b8180f612d3e87b72e/base/promotion.jl#L122-L124>, that calls the promote_rule function, another generic function, which acts as a user-extensible lookup table, mapping pairs of argument types the desired promotion type. In this case, there's a promote_rule method <https://github.com/JuliaLang/julia/blob/master/base/float.jl#L18-L31> indicating that promote(1,2.5) should convert its arguments to Float64 (using the convert function – yet another user-extensible generic function). The resulting Float64 pair (1.0,2.5) is added in the usual way. That is nice and all, but how can it possibly be fast? The trick is that Julia's type inference knows about generic functions and multiple dispatch and can actually analyze the promote function's behavior, determine that all it does for (Int,Float64) arguments is convert the Int to Float64, then inline that behavior into code for the expression +(promote(x,y)...). As a result, the LLVM code that does 1 + 2.5 is just this: julia> @code_llvm 1 + 2.5 define double @"julia_+;19364"(i64, double) { top: %2 = sitofp i64 %0 to double, !dbg !1885 %3 = fadd double %2, %1, !dbg !1885 ret double %3, !dbg !1885 } I.e. just a signed int to floating-point conversion of the first argument and a floating-point add of the result of that with the second argument. Or in native x86_64 code: julia> @code_native 1 + 2.5 .section __TEXT,__text,regular,pure_instructions Filename: promotion.jl Source line: 158 push RBP mov RBP, RSP Source line: 158 vcvtsi2sd XMM1, XMM0, RDI vaddsd XMM0, XMM1, XMM0 pop RBP ret Despite the layers of abstraction, the meat of the addition method is just two instructions: vcvtsi2sd and vaddsd (the rest is function prologue and epilogue). One can be forgiven for suspecting that this might only work for simple built-in types like Int and Float64, but that's not the case – it's completely general. Among my favorite examples is the SIUnits package <https://github.com/Keno/SIUnits.jl>. This package defines an SIQuantity wrapper type <https://github.com/Keno/SIUnits.jl/blob/a5826ae4992adffb22f00f96f3d61945da5fa113/src/SIUnits.jl#L3-L5> that tracks SI units <https://en.wikipedia.org/wiki/International_System_of_Units> in the type system. To teach Julia to do 1s + 2.5s (where `s` is a constant exported by SIUnits bound to the SIQuantity representing one SI second), all one needs is to provide a method for generically adding <https://github.com/Keno/SIUnits.jl/blob/a5826ae4992adffb22f00f96f3d61945da5fa113/src/SIUnits.jl#L143-L147> two SIQuantity values with the same units: function +{T,S,m,kg,s,A,K,mol,cd}( x::SIQuantity{T,m,kg,s,A,K,mol,cd},y::SIQuantity{S,m,kg,s,A,K,mol,cd}) val = x.val+y.val SIQuantity{typeof(val),m,kg,s,A,K,mol,cd}(val) end It's a bit verbose, I'll admit, but it buys you an awful lot. For example: julia> using SIUnits, SIUnits.ShortUnits # allow `s` for `seconds` julia> 1s + 2.5s 3.5 s That's kind of cool, but what's really cool is that even with the additional layers of abstraction, this still boils down to just two CPU instructions: julia> @code_native 1s + 2.5s .section __TEXT,__text,regular,pure_instructions Filename: /Users/stefan/.julia/SIUnits/src/SIUnits.jl Source line: 139 push RBP mov RBP, RSP Source line: 139 vcvtsi2sd XMM1, XMM0, RDI vaddsd XMM0, XMM1, XMM0 Source line: 140 pop RBP ret With no further definitions you also get much more complex behavior, like, for example, this: julia> (7//5)m/s + (12873918273918273918273981273981273981273980 + 2im)m/s 64369591369591369591369906369906369906369907//5 + 2//1*im m s⁻¹ julia> typeof(ans) SIQuantity{Complex{Rational{BigInt}},1,0,-1,0,0,0,0} (constructor with 1 method) The SIUnits package doesn't mention Complex, Rational or BigInt, yet this works. On Thursday, July 17, 2014 11:56:43 PM UTC-7, Nils Bruin wrote: > > In the end it's just a little helper tool, though. It doesn't really do > things you can't otherwise do. > Of course, you can do anything in one turing complete language that can be done in any other, but that's clearly not a good argument, since if it was, we'd all be programming in machine code. If multiple dispatch is "just a little helper tool" then so are object orientation and functional programming. In a sense, both are subsumed by multiple dispatch / generic functions – multiple dispatch is the object-oriented side of the coin while generic functions are the functional side of the coin. So is this at all helpful for Sage? I'm not sure. The things that you need to make multiple dispatch really useful for something as basic as integer-float addition are: 1. The + operator as a generic function – otherwise the multiple dispatch can't come into play. 2. Enough type information and inlining to allow + to still be sufficiently fast. I'm not sure if either of these are possible in Sage. The speed requirement can be alleviated by only doing multiple dispatch on user-defined types where + doesn't need to be so fast. Alternatively, you can limit operations that are less performance critical than +, such as the EllipticCurve constructor in Nils' example. However, multiple dispatch should not be dismissed out of hand since it can provide elegant solutions to type promotion and mixed-type operations (and many other issues), and it can be made very fast, although this is admittedly not trivial to do. -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at http://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
