* Multiple dispatch in Julia @ 2020-11-12 7:12 Jerry 2020-11-12 7:48 ` Dmitry A. Kazakov 0 siblings, 1 reply; 14+ messages in thread From: Jerry @ 2020-11-12 7:12 UTC (permalink / raw) I'm curious to know what Ada folks think about this discussion about Julia, especially the extended comment about multiple dispatch. Jerry ^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: Multiple dispatch in Julia 2020-11-12 7:12 Multiple dispatch in Julia Jerry @ 2020-11-12 7:48 ` Dmitry A. Kazakov 2020-11-12 8:55 ` Jerry 2020-11-12 17:56 ` antispam 0 siblings, 2 replies; 14+ messages in thread From: Dmitry A. Kazakov @ 2020-11-12 7:48 UTC (permalink / raw) On 12/11/2020 08:12, Jerry wrote: > I'm curious to know what Ada folks think about this discussion about Julia, especially the extended comment about multiple dispatch. What discussion? ----------- Like other dynamic languages claiming that they have multiple dispatch, Julia deploys run-time type matching for the target method. This is all you need to know. Because the most important requirement of properly designed dispatch (multiple or not) is: dispatch may never fail. It is very difficult to satisfy already with multi-methods. BTW, I am not sure, but it seems that Julia has only multi-methods and no full multiple dispatch. Full multiple-dispatch is even harder to approach. P.S. Multi-method dispatch is something like X + Y. Both arguments and the result are from the same type hierarchy. Full multiple dispatch is like Print (X, Y). Arguments are from different hierarchies. P.P.S. Ada in fact has multi-method dispatch. It is defined so that when tags of controlling arguments are different you get an exception ARM 3.9.2 (16). Which, yes, violates the principle above, but nobody ever pretended that Ada had multiple dispatch in the first place. -- Regards, Dmitry A. Kazakov http://www.dmitry-kazakov.de ^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: Multiple dispatch in Julia 2020-11-12 7:48 ` Dmitry A. Kazakov @ 2020-11-12 8:55 ` Jerry 2020-11-12 10:27 ` Dmitry A. Kazakov 2020-11-12 17:56 ` antispam 1 sibling, 1 reply; 14+ messages in thread From: Jerry @ 2020-11-12 8:55 UTC (permalink / raw) On Thursday, November 12, 2020 at 12:48:55 AM UTC-7, Dmitry A. Kazakov wrote: > On 12/11/2020 08:12, Jerry wrote: > > > I'm curious to know what Ada folks think about this discussion about Julia, especially the extended comment about multiple dispatch. > What discussion? Oops. https://arstechnica.com/science/2020/10/the-unreasonable-effectiveness-of-the-julia-programming-language/ (It's mostly an elementary descriptive analogy involving cooking.) ^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: Multiple dispatch in Julia 2020-11-12 8:55 ` Jerry @ 2020-11-12 10:27 ` Dmitry A. Kazakov 0 siblings, 0 replies; 14+ messages in thread From: Dmitry A. Kazakov @ 2020-11-12 10:27 UTC (permalink / raw) On 12/11/2020 09:55, Jerry wrote: > On Thursday, November 12, 2020 at 12:48:55 AM UTC-7, Dmitry A. Kazakov wrote: >> On 12/11/2020 08:12, Jerry wrote: >> >>> I'm curious to know what Ada folks think about this discussion about Julia, especially the extended comment about multiple dispatch. >> What discussion? > > Oops. > https://arstechnica.com/science/2020/10/the-unreasonable-effectiveness-of-the-julia-programming-language/ > (It's mostly an elementary descriptive analogy involving cooking.) ars technica, huh, are you serious? Reading discussions of pop/ad articles? If you want, you can read/ask about Julia technicalities here: https://discourse.julialang.org https://github.com/JuliaLang/julia/issues Otherwise, as I said. It is a non-starter. -- Regards, Dmitry A. Kazakov http://www.dmitry-kazakov.de ^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: Multiple dispatch in Julia 2020-11-12 7:48 ` Dmitry A. Kazakov 2020-11-12 8:55 ` Jerry @ 2020-11-12 17:56 ` antispam 2020-11-12 18:28 ` Dmitry A. Kazakov 1 sibling, 1 reply; 14+ messages in thread From: antispam @ 2020-11-12 17:56 UTC (permalink / raw) Dmitry A. Kazakov <mailbox@dmitry-kazakov.de> wrote: > On 12/11/2020 08:12, Jerry wrote: > > > I'm curious to know what Ada folks think about this discussion about Julia, especially the extended comment about multiple dispatch. > > What discussion? > > ----------- > Like other dynamic languages claiming that they have multiple dispatch, > Julia deploys run-time type matching for the target method. This is all > you need to know. > > Because the most important requirement of properly designed dispatch > (multiple or not) is: > > dispatch may never fail. Hmm, AFAICS typical implementation of dispatch in dynamic language may raise error "no such method". If error is undesired one can add catch all method or catch errors. Do you think that all such implementations are improperly designed? > It is very difficult to satisfy already with multi-methods. BTW, I am > not sure, but it seems that Julia has only multi-methods and no full > multiple dispatch. > > Full multiple-dispatch is even harder to approach. > > P.S. Multi-method dispatch is something like X + Y. Both arguments and > the result are from the same type hierarchy. Full multiple dispatch is > like Print (X, Y). Arguments are from different hierarchies. I am not sure what you want to say here. '+' is just funny name, why it should be different than 'Print'? Concerning hierarchies, Sevaral languages insit on "top" type, so there is only one hierarchy. Other languages have several different toplevel types, consequently there are different hierarchies originating at different toplevel types. I do not see why single hierarchy versus multiple hierarchies should decide if dispatch is multiple dispatch. In language I use there is type for equations. One can add scalar to equation or add two equations. This language uses overloading, but if another language implemented this via dipatch I would call it multiple dispatch. OTOH this language has single argument 'print'... > P.P.S. Ada in fact has multi-method dispatch. It is defined so that when > tags of controlling arguments are different you get an exception ARM > 3.9.2 (16). Which, yes, violates the principle above, but nobody ever > pretended that Ada had multiple dispatch in the first place. Maybe you talk about multi-method when types of arguments (or rather "dispatching arguments") are all equal? That would be rather unconventional definition of multi-method. -- Waldek Hebisch ^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: Multiple dispatch in Julia 2020-11-12 17:56 ` antispam @ 2020-11-12 18:28 ` Dmitry A. Kazakov 2020-11-12 21:22 ` antispam 0 siblings, 1 reply; 14+ messages in thread From: Dmitry A. Kazakov @ 2020-11-12 18:28 UTC (permalink / raw) On 12/11/2020 18:56, antispam@math.uni.wroc.pl wrote: > Dmitry A. Kazakov <mailbox@dmitry-kazakov.de> wrote: >> On 12/11/2020 08:12, Jerry wrote: >> >>> I'm curious to know what Ada folks think about this discussion about Julia, especially the extended comment about multiple dispatch. >> >> What discussion? >> >> ----------- >> Like other dynamic languages claiming that they have multiple dispatch, >> Julia deploys run-time type matching for the target method. This is all >> you need to know. >> >> Because the most important requirement of properly designed dispatch >> (multiple or not) is: >> >> dispatch may never fail. > > Hmm, AFAICS typical implementation of dispatch in dynamic language > may raise error "no such method". If error is undesired one can > add catch all method or catch errors. Do you think that all > such implementations are improperly designed? Exactly. I do not care much about dynamically typed languages as they are garbage per definition. But in a statically typed language if you declare a primitive operation you must either inherit or else override. Ergo, "method not understood" may never happen. >> It is very difficult to satisfy already with multi-methods. BTW, I am >> not sure, but it seems that Julia has only multi-methods and no full >> multiple dispatch. >> >> Full multiple-dispatch is even harder to approach. >> >> P.S. Multi-method dispatch is something like X + Y. Both arguments and >> the result are from the same type hierarchy. Full multiple dispatch is >> like Print (X, Y). Arguments are from different hierarchies. > > I am not sure what you want to say here. '+' is just funny name, > why it should be different than 'Print'? + is defined on, say, Matrix: + : Matrix x Matrix -> Matrix You could have a hierarchy like: Band_Matrix <: Sparse_Matrix <: Matrix. The dispatching table is 3D with all indices corresponding to the tags from the same hierarchy. Print is defined as Print : Device x Shape Device may have hierarchy: Grayscale_Printer <: Color_Printer <: Device. Shape could be: Circle <: Ellipse <: Shape. The dispatching table is 2D with independent indices. > Concerning hierarchies, > Sevaral languages insit on "top" type, so there is only one > hierarchy. Other languages have several different toplevel > types, consequently there are different hierarchies originating > at different toplevel types. I do not see why single hierarchy > versus multiple hierarchies should decide if dispatch is > multiple dispatch. In a multi-method when you derive a new type you have full information about all instances of +. E.g. when you derive Band_Matrix from Sparse_Matrix, you already know the dispatching table at the point. You need only to expand it in all dimensions. There is a problem is with branching derivations in independent packages, but it could be fixed, I think. With full dispatch, assuming separate compilation and binding, when you derive Circle from Ellipse, you have no idea if you must provide Print for Crayscale_Printer. The compiler simply does not know if it exists. > In language I use there is type for equations. One can add > scalar to equation or add two equations. This language > uses overloading, but if another language implemented this > via dipatch I would call it multiple dispatch. Overloading is ad-hoc static polymorphism Dispatch is dynamic polymorphism. They are way different things. Static polymorphism has implicit classes with no objects of, only instances. Another example of is generics/templates. Dynamic polymorphism has explicit classes with objects of. These in Ada are called class-wide objects. >> P.P.S. Ada in fact has multi-method dispatch. It is defined so that when >> tags of controlling arguments are different you get an exception ARM >> 3.9.2 (16). Which, yes, violates the principle above, but nobody ever >> pretended that Ada had multiple dispatch in the first place. > > Maybe you talk about multi-method when types of arguments (or rather > "dispatching arguments") are all equal? Classes are equal. Types are not. The following is legal in Ada: type T is tagged ...; procedure Foo (X : T; Y : T); -- Primitive operation and multi-method type S is new T with ...; overriding procedure Foo (X : S; Y : S); X : T'Class := T'(...); -- The specific type is T Y : T'Class := S'(...); -- The specific type is S Foo (X, X); -- Calls Foo of T Foo (X, Y); -- Raises Constraint_Error Foo (Y, Y); -- Calls Foo of S -- Regards, Dmitry A. Kazakov http://www.dmitry-kazakov.de ^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: Multiple dispatch in Julia 2020-11-12 18:28 ` Dmitry A. Kazakov @ 2020-11-12 21:22 ` antispam 2020-11-13 7:49 ` Dmitry A. Kazakov 0 siblings, 1 reply; 14+ messages in thread From: antispam @ 2020-11-12 21:22 UTC (permalink / raw) Dmitry A. Kazakov <mailbox@dmitry-kazakov.de> wrote: > On 12/11/2020 18:56, antispam@math.uni.wroc.pl wrote: > > Dmitry A. Kazakov <mailbox@dmitry-kazakov.de> wrote: > >> On 12/11/2020 08:12, Jerry wrote: > >> > >>> I'm curious to know what Ada folks think about this discussion about Julia, especially the extended comment about multiple dispatch. > >> > >> What discussion? > >> > >> ----------- > >> Like other dynamic languages claiming that they have multiple dispatch, > >> Julia deploys run-time type matching for the target method. This is all > >> you need to know. > >> > >> Because the most important requirement of properly designed dispatch > >> (multiple or not) is: > >> > >> dispatch may never fail. > > > > Hmm, AFAICS typical implementation of dispatch in dynamic language > > may raise error "no such method". If error is undesired one can > > add catch all method or catch errors. Do you think that all > > such implementations are improperly designed? > > Exactly. I do not care much about dynamically typed languages as they > are garbage per definition. But in a statically typed language if you > declare a primitive operation you must either inherit or else override. > Ergo, "method not understood" may never happen. That is your point of view, I must disagree. First, even in static language once you have multiple dispatch you can not check for presence of operations at place when you define types. Your "inherit or else override" only makes sense if you mean that one must provide catch all method. But I do not see good reason to insist on that, if there are no logically applicable action than calling catch all method is as wrong as raising error. At the end of the day what matters if the program satifies its spec and there are various specs and various methodologies to satify the spec. > >> It is very difficult to satisfy already with multi-methods. BTW, I am > >> not sure, but it seems that Julia has only multi-methods and no full > >> multiple dispatch. > >> > >> Full multiple-dispatch is even harder to approach. > >> > >> P.S. Multi-method dispatch is something like X + Y. Both arguments and > >> the result are from the same type hierarchy. Full multiple dispatch is > >> like Print (X, Y). Arguments are from different hierarchies. > > > > I am not sure what you want to say here. '+' is just funny name, > > why it should be different than 'Print'? > > + is defined on, say, Matrix: > > + : Matrix x Matrix -> Matrix > > You could have a hierarchy like: Band_Matrix <: Sparse_Matrix <: Matrix. > The dispatching table is 3D with all indices corresponding to the tags > from the same hierarchy. > > Print is defined as > > Print : Device x Shape > > Device may have hierarchy: Grayscale_Printer <: Color_Printer <: Device. > Shape could be: Circle <: Ellipse <: Shape. The dispatching table is 2D > with independent indices. Assume that we have Device <: Type, Shape <: Type and Matrix <: Type. That is we have single hierarchy with Type at top. > > Concerning hierarchies, > > Sevaral languages insit on "top" type, so there is only one > > hierarchy. Other languages have several different toplevel > > types, consequently there are different hierarchies originating > > at different toplevel types. I do not see why single hierarchy > > versus multiple hierarchies should decide if dispatch is > > multiple dispatch. > > In a multi-method when you derive a new type you have full information > about all instances of +. Even for single dispatch this is not true. Inheritace may add new instances. In staticaly typed single dispatch you now set of possible method for type, so you can use one dimensional array to store methods and you can statically compute position in the methods array (table). If you want interesting multi-methods (not the Ada ones), this is no longer possible. > E.g. when you derive Band_Matrix from > Sparse_Matrix, you already know the dispatching table at the point. That is _very_ restrictive definition, I would say that almost none uses it. > You > need only to expand it in all dimensions. There is a problem is with > branching derivations in independent packages, but it could be fixed, I > think. > > With full dispatch, assuming separate compilation and binding, when you > derive Circle from Ellipse, you have no idea if you must provide Print > for Crayscale_Printer. The compiler simply does not know if it exists. AFAIK tables for multiple dispatch are usulally build at runtime. Compiler may be able to derive some information about dispatch tables as an optimization, but general case is delayed to runtime. Typlically, potential dispatch table is quite large while actual one is much smaller. > > In language I use there is type for equations. One can add > > scalar to equation or add two equations. This language > > uses overloading, but if another language implemented this > > via dipatch I would call it multiple dispatch. > > Overloading is ad-hoc static polymorphism > Dispatch is dynamic polymorphism. > > They are way different things. Static polymorphism has implicit classes > with no objects of, only instances. Another example of is > generics/templates. Sure. But one can use multiple dispach instead of overloading. In particular the set of potentialy applicable methods may be the same. My point was that is resonable system you may have + : Matrix x Matrix -> Matrix + : Equation x Equation -> Equation + : Equation x Integer -> Equation + : Integer x Equation -> Equation (and hundreds of other combinations), while '+' for say Matrix x Equation is undefined. -- Waldek Hebisch ^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: Multiple dispatch in Julia 2020-11-12 21:22 ` antispam @ 2020-11-13 7:49 ` Dmitry A. Kazakov 2020-11-13 12:55 ` antispam 0 siblings, 1 reply; 14+ messages in thread From: Dmitry A. Kazakov @ 2020-11-13 7:49 UTC (permalink / raw) On 12/11/2020 22:22, antispam@math.uni.wroc.pl wrote: > Dmitry A. Kazakov <mailbox@dmitry-kazakov.de> wrote: >> On 12/11/2020 18:56, antispam@math.uni.wroc.pl wrote: >>> Dmitry A. Kazakov <mailbox@dmitry-kazakov.de> wrote: >>>> On 12/11/2020 08:12, Jerry wrote: >>>> >>>>> I'm curious to know what Ada folks think about this discussion about Julia, especially the extended comment about multiple dispatch. >>>> >>>> What discussion? >>>> >>>> ----------- >>>> Like other dynamic languages claiming that they have multiple dispatch, >>>> Julia deploys run-time type matching for the target method. This is all >>>> you need to know. >>>> >>>> Because the most important requirement of properly designed dispatch >>>> (multiple or not) is: >>>> >>>> dispatch may never fail. >>> >>> Hmm, AFAICS typical implementation of dispatch in dynamic language >>> may raise error "no such method". If error is undesired one can >>> add catch all method or catch errors. Do you think that all >>> such implementations are improperly designed? >> >> Exactly. I do not care much about dynamically typed languages as they >> are garbage per definition. But in a statically typed language if you >> declare a primitive operation you must either inherit or else override. >> Ergo, "method not understood" may never happen. > > That is your point of view, I must disagree. First, even in > static language once you have multiple dispatch you can not > check for presence of operations at place when you define > types. Either you have static typing or not. But there is no disagreement. You said you do not know how to implement multiple dispatch (while keeping the language statically typed), I said same thing. > Your "inherit or else override" only makes sense > if you mean that one must provide catch all method. One must fulfill the contract of the primitive [multiple] dispatching operation. The language has no say in that. If the contract does not include "method not understood" you have a broken program. If the language does not care about contracts, it is a broken language. > At the end > of the day what matters if the program satifies its > spec and there are various specs and various methodologies > to satify the spec. In short, the program cannot be written in the language this way because, see above. > Assume that we have Device <: Type, Shape <: Type and Matrix <: Type. > That is we have single hierarchy with Type at top. Sure, you can reduce everything to a single God-class. You can even drop all types and go to the machine code. After all it will remain Turing-complete. It is not a question if you could bend program design this or that way. Some Ada programmers hate dynamic polymorphism to the core and avoid it at all costs, the design ones included. >>> Concerning hierarchies, >>> Sevaral languages insit on "top" type, so there is only one >>> hierarchy. Other languages have several different toplevel >>> types, consequently there are different hierarchies originating >>> at different toplevel types. I do not see why single hierarchy >>> versus multiple hierarchies should decide if dispatch is >>> multiple dispatch. >> >> In a multi-method when you derive a new type you have full information >> about all instances of +. > > Even for single dispatch this is not true. Inheritace may > add new instances. It can, but at the point where new instances are added, the information is again complete. The compiler does not need to know future derivations and does not need to know parallel derivations in order to ensure consistency of single disaptch. > In staticaly typed single dispatch > you now set of possible method for type, so you can use > one dimensional array to store methods and you can statically > compute position in the methods array (table). This is not required. Hashing/mapping type tags into indices can be delayed until linkage- and even until run-time. > If you > want interesting multi-methods (not the Ada ones), this > is no longer possible. Switching from 1D to nD table is not a big deal when all indices are same, at first glance admittedly. >> E.g. when you derive Band_Matrix from >> Sparse_Matrix, you already know the dispatching table at the point. > > That is _very_ restrictive definition, I would say that > almost none uses it. See above. >> You >> need only to expand it in all dimensions. There is a problem is with >> branching derivations in independent packages, but it could be fixed, I >> think. >> >> With full dispatch, assuming separate compilation and binding, when you >> derive Circle from Ellipse, you have no idea if you must provide Print >> for Crayscale_Printer. The compiler simply does not know if it exists. > > AFAIK tables for multiple dispatch are usulally build at runtime. > Compiler may be able to derive some information about dispatch > tables as an optimization, but general case is delayed to runtime. > > Typlically, potential dispatch table is quite large while actual > one is much smaller. It is not about the whole table. It is about checking consistency of the operations directly reachable at the derivation point. The challenge is to split the table into statically known parts such that consistency of each of them would imply consistency of the whole table. >>> In language I use there is type for equations. One can add >>> scalar to equation or add two equations. This language >>> uses overloading, but if another language implemented this >>> via dipatch I would call it multiple dispatch. >> >> Overloading is ad-hoc static polymorphism >> Dispatch is dynamic polymorphism. >> >> They are way different things. Static polymorphism has implicit classes >> with no objects of, only instances. Another example of is >> generics/templates. > > Sure. But one can use multiple dispach instead of overloading. Different forms of polymorphism exist, yes. You can use one or another to some extent. > In particular the set of potentialy applicable methods may be > the same. My point was that is resonable system you may have > > + : Matrix x Matrix -> Matrix > + : Equation x Equation -> Equation > + : Equation x Integer -> Equation > + : Integer x Equation -> Equation > > (and hundreds of other combinations), while '+' for say > Matrix x Equation is undefined. And the point is? -- Regards, Dmitry A. Kazakov http://www.dmitry-kazakov.de ^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: Multiple dispatch in Julia 2020-11-13 7:49 ` Dmitry A. Kazakov @ 2020-11-13 12:55 ` antispam 2020-11-13 14:59 ` Dmitry A. Kazakov 0 siblings, 1 reply; 14+ messages in thread From: antispam @ 2020-11-13 12:55 UTC (permalink / raw) Dmitry A. Kazakov <mailbox@dmitry-kazakov.de> wrote: > On 12/11/2020 22:22, antispam@math.uni.wroc.pl wrote: > > Dmitry A. Kazakov <mailbox@dmitry-kazakov.de> wrote: > >> On 12/11/2020 18:56, antispam@math.uni.wroc.pl wrote: > >>> Dmitry A. Kazakov <mailbox@dmitry-kazakov.de> wrote: > >>>> On 12/11/2020 08:12, Jerry wrote: > >>>> > >>>>> I'm curious to know what Ada folks think about this discussion about Julia, especially the extended comment about multiple dispatch. > >>>> > >>>> What discussion? > >>>> > >>>> ----------- > >>>> Like other dynamic languages claiming that they have multiple dispatch, > >>>> Julia deploys run-time type matching for the target method. This is all > >>>> you need to know. > >>>> > >>>> Because the most important requirement of properly designed dispatch > >>>> (multiple or not) is: > >>>> > >>>> dispatch may never fail. > >>> > >>> Hmm, AFAICS typical implementation of dispatch in dynamic language > >>> may raise error "no such method". If error is undesired one can > >>> add catch all method or catch errors. Do you think that all > >>> such implementations are improperly designed? > >> > >> Exactly. I do not care much about dynamically typed languages as they > >> are garbage per definition. But in a statically typed language if you > >> declare a primitive operation you must either inherit or else override. > >> Ergo, "method not understood" may never happen. > > > > That is your point of view, I must disagree. First, even in > > static language once you have multiple dispatch you can not > > check for presence of operations at place when you define > > types. > > Either you have static typing or not. But there is no disagreement. You > said you do not know how to implement multiple dispatch (while keeping > the language statically typed), I said same thing. I do not see why failure (error) during dispatch would conflict with static typing. It is in the same category as out of bound array reference, uninitialized variable or overflow. As long as it is detected at runtime program will produce correct result or signal error. And if you insist on no error for dispatch, "solution" is the same as for uninitialized variables: you need default value (catch all method). I write it in quotes because it really does not solve problem of calling _correct_ method. I see no reason to insist that programmer provides catch all method, which probably will raise error, it is simpler when dispatch machinery raises errors. Concerning dynamically typed languages: I have strong preference to static typing. But static and dynamic typing have complementary advantages: static typing is good for core (system) part, dynamic typing is good for scripting/prototyping. If you insist that everything is staticaly typed, then you confine yourself to a niche (you may be confortable there, but you will not see many real word things). BTW: AFAIK SPARK checker was implemented in dynamically typed language (Prolog). > > Your "inherit or else override" only makes sense > > if you mean that one must provide catch all method. > > One must fulfill the contract of the primitive [multiple] dispatching > operation. The language has no say in that. If the contract does not > include "method not understood" you have a broken program. If the > language does not care about contracts, it is a broken language. My contract include "no applicable method"... > > At the end > > of the day what matters if the program satifies its > > spec and there are various specs and various methodologies > > to satify the spec. > > In short, the program cannot be written in the language this way > because, see above. > > > Assume that we have Device <: Type, Shape <: Type and Matrix <: Type. > > That is we have single hierarchy with Type at top. > > Sure, you can reduce everything to a single God-class. You can even drop > all types and go to the machine code. After all it will remain > Turing-complete. Hmm, your God must be quite weak: such typlevel type usualy have limited number of features and it can not do much. But what it can do is useful enough... > It is not a question if you could bend program design this or that way. > Some Ada programmers hate dynamic polymorphism to the core and avoid it > at all costs, the design ones included. OK, you have no argument beside that you hate dynamic features... > >>> Concerning hierarchies, > >>> Sevaral languages insit on "top" type, so there is only one > >>> hierarchy. Other languages have several different toplevel > >>> types, consequently there are different hierarchies originating > >>> at different toplevel types. I do not see why single hierarchy > >>> versus multiple hierarchies should decide if dispatch is > >>> multiple dispatch. > >> > >> In a multi-method when you derive a new type you have full information > >> about all instances of +. > > > > Even for single dispatch this is not true. Inheritace may > > add new instances. > > It can, but at the point where new instances are added, the information > is again complete. The compiler does not need to know future derivations > and does not need to know parallel derivations in order to ensure > consistency of single disaptch. > > > In staticaly typed single dispatch > > you now set of possible method for type, so you can use > > one dimensional array to store methods and you can statically > > compute position in the methods array (table). > > This is not required. Hashing/mapping type tags into indices can be > delayed until linkage- and even until run-time. > > > If you > > want interesting multi-methods (not the Ada ones), this > > is no longer possible. > > Switching from 1D to nD table is not a big deal when all indices are > same, at first glance admittedly. There are important pragmatic differences: - "full" table may be quite large (number of types to power n), so sparse representation is prefereble - it is no longer natural to isist that all combinations of types are sensible (you seem to insist that they are) - there is no natural order on methods, so later additions may change dispatch for earlier methods/types Put it differently, popular implementation of single dispatch uses per type method table indexed by slot number. At call site compiler knows slot number so can generate quite efficient code. Of course other implementations are possible, but this one gives you static checking, fast runtime and acceptable memory overhead. In particular, once per-type table is generated and checked there is no need to change it. In case of multiple dispatch typical implementation uses per method table. Such tables naturally change when you add types or new method implementations (instances). > >> E.g. when you derive Band_Matrix from > >> Sparse_Matrix, you already know the dispatching table at the point. > > > > That is _very_ restrictive definition, I would say that > > almost none uses it. > > See above. > > >> You > >> need only to expand it in all dimensions. There is a problem is with > >> branching derivations in independent packages, but it could be fixed, I > >> think. > >> > >> With full dispatch, assuming separate compilation and binding, when you > >> derive Circle from Ellipse, you have no idea if you must provide Print > >> for Crayscale_Printer. The compiler simply does not know if it exists. > > > > AFAIK tables for multiple dispatch are usulally build at runtime. > > Compiler may be able to derive some information about dispatch > > tables as an optimization, but general case is delayed to runtime. > > > > Typlically, potential dispatch table is quite large while actual > > one is much smaller. > > It is not about the whole table. It is about checking consistency of the > operations directly reachable at the derivation point. The challenge is > to split the table into statically known parts such that consistency of > each of them would imply consistency of the whole table. Well, consitency means: - given method will get arguments of prescribed types (is applicable) - no more specialized method is applicable You seem to include condition that there is always applicable method. However, in general minimal set of needed methods is not known (even in single dispatch case determining if given exact type appears at call site is uncomputable). In single dispatch case conservative approximation (if method is present in a type, then it must be present in derived types) is quite reasonable. Similar approximation in multiple dispatch case it is much less reasonable (and implementations I know do not make it). > >>> In language I use there is type for equations. One can add > >>> scalar to equation or add two equations. This language > >>> uses overloading, but if another language implemented this > >>> via dipatch I would call it multiple dispatch. > >> > >> Overloading is ad-hoc static polymorphism > >> Dispatch is dynamic polymorphism. > >> > >> They are way different things. Static polymorphism has implicit classes > >> with no objects of, only instances. Another example of is > >> generics/templates. > > > > Sure. But one can use multiple dispach instead of overloading. > > Different forms of polymorphism exist, yes. You can use one or another > to some extent. > > > In particular the set of potentialy applicable methods may be > > the same. My point was that is resonable system you may have > > > > + : Matrix x Matrix -> Matrix > > + : Equation x Equation -> Equation > > + : Equation x Integer -> Equation > > + : Integer x Equation -> Equation > > > > (and hundreds of other combinations), while '+' for say > > Matrix x Equation is undefined. > > And the point is? You claimed that '+' has somewhat special properties that make it into multi-method and not general multiple dispatch. So is the above multi-method in your sense? Or maybe because some combinations of types are illegal, you consider this bad design and reject completely? -- Waldek Hebisch ^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: Multiple dispatch in Julia 2020-11-13 12:55 ` antispam @ 2020-11-13 14:59 ` Dmitry A. Kazakov 2020-11-15 12:43 ` antispam 0 siblings, 1 reply; 14+ messages in thread From: Dmitry A. Kazakov @ 2020-11-13 14:59 UTC (permalink / raw) On 13/11/2020 13:55, antispam@math.uni.wroc.pl wrote: > Dmitry A. Kazakov <mailbox@dmitry-kazakov.de> wrote: >> On 12/11/2020 22:22, antispam@math.uni.wroc.pl wrote: >>> Dmitry A. Kazakov <mailbox@dmitry-kazakov.de> wrote: >>>> On 12/11/2020 18:56, antispam@math.uni.wroc.pl wrote: >>>>> Dmitry A. Kazakov <mailbox@dmitry-kazakov.de> wrote: >>>>>> On 12/11/2020 08:12, Jerry wrote: >>>>>> >>>>>>> I'm curious to know what Ada folks think about this discussion about Julia, especially the extended comment about multiple dispatch. >>>>>> >>>>>> What discussion? >>>>>> >>>>>> ----------- >>>>>> Like other dynamic languages claiming that they have multiple dispatch, >>>>>> Julia deploys run-time type matching for the target method. This is all >>>>>> you need to know. >>>>>> >>>>>> Because the most important requirement of properly designed dispatch >>>>>> (multiple or not) is: >>>>>> >>>>>> dispatch may never fail. >>>>> >>>>> Hmm, AFAICS typical implementation of dispatch in dynamic language >>>>> may raise error "no such method". If error is undesired one can >>>>> add catch all method or catch errors. Do you think that all >>>>> such implementations are improperly designed? >>>> >>>> Exactly. I do not care much about dynamically typed languages as they >>>> are garbage per definition. But in a statically typed language if you >>>> declare a primitive operation you must either inherit or else override. >>>> Ergo, "method not understood" may never happen. >>> >>> That is your point of view, I must disagree. First, even in >>> static language once you have multiple dispatch you can not >>> check for presence of operations at place when you define >>> types. >> >> Either you have static typing or not. But there is no disagreement. You >> said you do not know how to implement multiple dispatch (while keeping >> the language statically typed), I said same thing. > > I do not see why failure (error) during dispatch would > conflict with static typing. Because it violates typing. A multiple dispatch method is declared as acting on the whole Cartesian product of classes of arguments and/or the result. Violating that is type error. In Ada you cannot declare such methods ARM 3.9.2 (12). > It is in the same category > as out of bound array reference, uninitialized variable > or overflow. No, they are not same: 1. Failed call, dispatching or not, is a type error. 2. Bounds errors and overflows are constraint errors. They do not violate typing, they enforce it. They are not errors but legal program states. 3. Unintialized variable access is either type or constraint error depending on the meaning of initialization. If initialization means user-provided assignment of a differently constrained value comparing to the value set by the default initialization, then an access would be a constraint error. Otherwise it is a type violation (the variable does not hold a value of the declared type). > As long as it is detected at runtime > program will produce correct result or signal error. Limited effect of an error does not make it no error. You can implement addition so that it would sporadically return wrong results. If you can detect that the result is incorrect would such detection magically make it right? >> One must fulfill the contract of the primitive [multiple] dispatching >> operation. The language has no say in that. If the contract does not >> include "method not understood" you have a broken program. If the >> language does not care about contracts, it is a broken language. > > My contract include "no applicable method"... My does not. >>> Assume that we have Device <: Type, Shape <: Type and Matrix <: Type. >>> That is we have single hierarchy with Type at top. >> >> Sure, you can reduce everything to a single God-class. You can even drop >> all types and go to the machine code. After all it will remain >> Turing-complete. > > Hmm, your God must be quite weak: such typlevel type usualy > have limited number of features and it can not do much. > But what it can do is useful enough... God-class is a technical term in OOD. It describes a situation when methods migrate down to the root of the type hierarchy forming a class that has all possible methods, a God-class. You can have a common ancestor Type, but if Type has + and Print and everything else, that is a God-class. >> It is not a question if you could bend program design this or that way. >> Some Ada programmers hate dynamic polymorphism to the core and avoid it >> at all costs, the design ones included. > > OK, you have no argument beside that you hate dynamic features... The argument is that I do not want to carry massive burden of fixing the client code in all places where a method is called. > There are important pragmatic differences: > - "full" table may be quite large (number of types to power n), > so sparse representation is prefereble > - it is no longer natural to isist that all combinations of > types are sensible (you seem to insist that they are) > - there is no natural order on methods, so later additions > may change dispatch for earlier methods/types You argue here against multiple dispatch rather than for broken implementations of. > You seem to include condition that there is always applicable > method. Yes, if the method (a primitive operation) is declared so, namely as acting on the class product. Ada explicitly forbids this ARM 3.9.2 (12). Only power class (multi-method) is allowed. > However, in general minimal set of needed methods > is not known (even in single dispatch case determining if > given exact type appears at call site is uncomputable). There is no such thing in a statically typed language. The minimal and maximal sets are same set of declared operations. If you want to reduce the set you must invent some static mechanism excluding operations you do not want. It is a valid but other issue. E.g. the problem parallel type hierarchies. The most common examples of parallel hierarchies are handle and target type, container and element type etc. You derive a new instance of the target type and you want a new handle type derived from the handle corresponding to target parent's handle. Each handle type works only with its own target type. Operations are always defined on such pairs. The dispatching table is diagonal. >>>> They are way different things. Static polymorphism has implicit classes >>>> with no objects of, only instances. Another example of is >>>> generics/templates. >>> >>> Sure. But one can use multiple dispach instead of overloading. >> >> Different forms of polymorphism exist, yes. You can use one or another >> to some extent. >> >>> In particular the set of potentialy applicable methods may be >>> the same. My point was that is resonable system you may have >>> >>> + : Matrix x Matrix -> Matrix >>> + : Equation x Equation -> Equation >>> + : Equation x Integer -> Equation >>> + : Integer x Equation -> Equation >>> >>> (and hundreds of other combinations), while '+' for say >>> Matrix x Equation is undefined. >> >> And the point is? > > You claimed that '+' has somewhat special properties that > make it into multi-method and not general multiple > dispatch. So is the above multi-method in your sense? It is not a method in either of its arguments. Methods are operations defined on the whole class. In Ada terms method is called primitive operation. A primitive operation is defined on the whole class. Each non-abstract instance of the class has a body selected upon dispatch, possibly inherited. All bodies have corresponding free operations which overload each other when visible. Overloaded free operations are not yet methods, when they are defined on specific types. In Ada terms a free operation is a subprogram with no controlling arguments or results. [A subprogram can be method in one argument and free operation in another] -- Regards, Dmitry A. Kazakov http://www.dmitry-kazakov.de ^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: Multiple dispatch in Julia 2020-11-13 14:59 ` Dmitry A. Kazakov @ 2020-11-15 12:43 ` antispam 2020-11-15 13:37 ` Dmitry A. Kazakov 0 siblings, 1 reply; 14+ messages in thread From: antispam @ 2020-11-15 12:43 UTC (permalink / raw) Dmitry A. Kazakov <mailbox@dmitry-kazakov.de> wrote: > On 13/11/2020 13:55, antispam@math.uni.wroc.pl wrote: > > Dmitry A. Kazakov <mailbox@dmitry-kazakov.de> wrote: > >> On 12/11/2020 22:22, antispam@math.uni.wroc.pl wrote: > >>> Dmitry A. Kazakov <mailbox@dmitry-kazakov.de> wrote: > >>>> On 12/11/2020 18:56, antispam@math.uni.wroc.pl wrote: > >>>>> Dmitry A. Kazakov <mailbox@dmitry-kazakov.de> wrote: > >> > >> Either you have static typing or not. But there is no disagreement. You > >> said you do not know how to implement multiple dispatch (while keeping > >> the language statically typed), I said same thing. > > > > I do not see why failure (error) during dispatch would > > conflict with static typing. > > Because it violates typing. A multiple dispatch method is declared as > acting on the whole Cartesian product of classes of arguments and/or the > result. Violating that is type error. In Ada you cannot declare such > methods ARM 3.9.2 (12). OK, Ada defines it own terminology, conflicting with terminology used outside Ada. Since this discussion clearly goes beyond Ada features my assumption was that general terminology applies. Anyway, I think that I know what you are saying. I strongly disagree with several your views, but new arguments are unlikely to appear, so I skip most things. But I can not resit comment about your integer addition example... > > As long as it is detected at runtime > > program will produce correct result or signal error. > > Limited effect of an error does not make it no error. You can implement > addition so that it would sporadically return wrong results. Most languages do so... > If you can > detect that the result is incorrect would such detection magically make > it right? Standard Ada detects overflow instead of returning result. Is Ada wrong? I usualy do integer arithmetic in language where overflow is impossible, but it can run out of memory. It is impossible to do better. Is world fundamentally wrong? -- Waldek Hebisch ^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: Multiple dispatch in Julia 2020-11-15 12:43 ` antispam @ 2020-11-15 13:37 ` Dmitry A. Kazakov 2020-11-15 14:32 ` antispam 0 siblings, 1 reply; 14+ messages in thread From: Dmitry A. Kazakov @ 2020-11-15 13:37 UTC (permalink / raw) On 15/11/2020 13:43, antispam@math.uni.wroc.pl wrote: > Dmitry A. Kazakov <mailbox@dmitry-kazakov.de> wrote: >> On 13/11/2020 13:55, antispam@math.uni.wroc.pl wrote: >>> Dmitry A. Kazakov <mailbox@dmitry-kazakov.de> wrote: >>>> On 12/11/2020 22:22, antispam@math.uni.wroc.pl wrote: >>>>> Dmitry A. Kazakov <mailbox@dmitry-kazakov.de> wrote: >>>>>> On 12/11/2020 18:56, antispam@math.uni.wroc.pl wrote: >>>>>>> Dmitry A. Kazakov <mailbox@dmitry-kazakov.de> wrote: >>>> >>>> Either you have static typing or not. But there is no disagreement. You >>>> said you do not know how to implement multiple dispatch (while keeping >>>> the language statically typed), I said same thing. >>> >>> I do not see why failure (error) during dispatch would >>> conflict with static typing. >> >> Because it violates typing. A multiple dispatch method is declared as >> acting on the whole Cartesian product of classes of arguments and/or the >> result. Violating that is type error. In Ada you cannot declare such >> methods ARM 3.9.2 (12). > > OK, Ada defines it own terminology, conflicting with terminology > used outside Ada. Since this discussion clearly goes beyond > Ada features my assumption was that general terminology applies. No, it is not a terminology issue. When an operation is declared it is on all possible values of the arguments, unless explicitly stated otherwise. So if you declare Print acting on the closure of the class rooted in the type Device and the closure of the class rooted in the type Shape, it *must* work on all instances from there. If you wanted to limit the set of instances, you must have declared that in some form upfront. That is an elementary language design principle, what you see is what you get. The reader must understand the meaning of a declaration. The problem is that this is not possible to do. There is no contract of a multiply-dispatching operation in languages like Julia. Which is why it is a type error or an undefined behavior. >> If you can >> detect that the result is incorrect would such detection magically make >> it right? > > Standard Ada detects overflow instead of returning result. > Is Ada wrong? The result is returned. Here the result is propagation of Constraint_Error. If you contracted the multiple-dispatch operation Print to propagate exception on *certain* combinations of arguments that would not be a fault either. The problem is with [un]certainty. -- Regards, Dmitry A. Kazakov http://www.dmitry-kazakov.de ^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: Multiple dispatch in Julia 2020-11-15 13:37 ` Dmitry A. Kazakov @ 2020-11-15 14:32 ` antispam 2020-11-15 16:28 ` Dmitry A. Kazakov 0 siblings, 1 reply; 14+ messages in thread From: antispam @ 2020-11-15 14:32 UTC (permalink / raw) Dmitry A. Kazakov <mailbox@dmitry-kazakov.de> wrote: > On 15/11/2020 13:43, antispam@math.uni.wroc.pl wrote: > > Dmitry A. Kazakov <mailbox@dmitry-kazakov.de> wrote: > >> On 13/11/2020 13:55, antispam@math.uni.wroc.pl wrote: > >>> Dmitry A. Kazakov <mailbox@dmitry-kazakov.de> wrote: > >>>> On 12/11/2020 22:22, antispam@math.uni.wroc.pl wrote: > >>>>> Dmitry A. Kazakov <mailbox@dmitry-kazakov.de> wrote: > >>>>>> On 12/11/2020 18:56, antispam@math.uni.wroc.pl wrote: > >>>>>>> Dmitry A. Kazakov <mailbox@dmitry-kazakov.de> wrote: > >>>> > >>>> Either you have static typing or not. But there is no disagreement. You > >>>> said you do not know how to implement multiple dispatch (while keeping > >>>> the language statically typed), I said same thing. > >>> > >>> I do not see why failure (error) during dispatch would > >>> conflict with static typing. > >> > >> Because it violates typing. A multiple dispatch method is declared as > >> acting on the whole Cartesian product of classes of arguments and/or the > >> result. Violating that is type error. In Ada you cannot declare such > >> methods ARM 3.9.2 (12). > > > > OK, Ada defines it own terminology, conflicting with terminology > > used outside Ada. Since this discussion clearly goes beyond > > Ada features my assumption was that general terminology applies. > > No, it is not a terminology issue. When an operation is declared it is > on all possible values of the arguments, unless explicitly stated otherwise. Well, in typical multiple dispatch laggage method (operation) declaration is split into several part. First part just introduces name. Without extra info such method applies to no arguments. Then there are definitions of specializations, each specialization has corresponding tuple of types and is potentially applicable to any combination of derived types. Language rules explicitely say that operation is applicable if and only if there is applicable specialization. Unapplicable argument combination propagates exception. Dispatch rules says which specialization will be run if there are multiple potentially applicable specializations. Once you have all specializations there are no doubt which combinantion of argument types are valid. > So if you declare Print acting on the closure of the class rooted in the > type Device and the closure of the class rooted in the type Shape, it > *must* work on all instances from there. > > If you wanted to limit the set of instances, you must have declared that > in some form upfront. That is an elementary language design principle, > what you see is what you get. The reader must understand the meaning of > a declaration. > > The problem is that this is not possible to do. There is no contract of > a multiply-dispatching operation in languages like Julia. Which is why > it is a type error or an undefined behavior. I did not look at Julia rules. But languages which I know give tight contract on multiple dispatch. > >> If you can > >> detect that the result is incorrect would such detection magically make > >> it right? > > > > Standard Ada detects overflow instead of returning result. > > Is Ada wrong? > > The result is returned. Here the result is propagation of Constraint_Error. > > If you contracted the multiple-dispatch operation Print to propagate > exception on *certain* combinations of arguments that would not be a > fault either. The problem is with [un]certainty. There is no uncertainty: language rules and program text exactly specify which argument combinations propagate exception and which go to specific implementation. -- Waldek Hebisch ^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: Multiple dispatch in Julia 2020-11-15 14:32 ` antispam @ 2020-11-15 16:28 ` Dmitry A. Kazakov 0 siblings, 0 replies; 14+ messages in thread From: Dmitry A. Kazakov @ 2020-11-15 16:28 UTC (permalink / raw) On 15/11/2020 15:32, antispam@math.uni.wroc.pl wrote: > Dmitry A. Kazakov <mailbox@dmitry-kazakov.de> wrote: >> On 15/11/2020 13:43, antispam@math.uni.wroc.pl wrote: >>> Dmitry A. Kazakov <mailbox@dmitry-kazakov.de> wrote: >>>> On 13/11/2020 13:55, antispam@math.uni.wroc.pl wrote: >>>>> Dmitry A. Kazakov <mailbox@dmitry-kazakov.de> wrote: >>>>>> On 12/11/2020 22:22, antispam@math.uni.wroc.pl wrote: >>>>>>> Dmitry A. Kazakov <mailbox@dmitry-kazakov.de> wrote: >>>>>>>> On 12/11/2020 18:56, antispam@math.uni.wroc.pl wrote: >>>>>>>>> Dmitry A. Kazakov <mailbox@dmitry-kazakov.de> wrote: >>>>>> >>>>>> Either you have static typing or not. But there is no disagreement. You >>>>>> said you do not know how to implement multiple dispatch (while keeping >>>>>> the language statically typed), I said same thing. >>>>> >>>>> I do not see why failure (error) during dispatch would >>>>> conflict with static typing. >>>> >>>> Because it violates typing. A multiple dispatch method is declared as >>>> acting on the whole Cartesian product of classes of arguments and/or the >>>> result. Violating that is type error. In Ada you cannot declare such >>>> methods ARM 3.9.2 (12). >>> >>> OK, Ada defines it own terminology, conflicting with terminology >>> used outside Ada. Since this discussion clearly goes beyond >>> Ada features my assumption was that general terminology applies. >> >> No, it is not a terminology issue. When an operation is declared it is >> on all possible values of the arguments, unless explicitly stated otherwise. > > Well, in typical multiple dispatch laggage method (operation) > declaration is split into several part. First part just introduces > name. [...] Right. You can proclaim it all untyped and so avoid type errors. No types, no type errors. >> The problem is that this is not possible to do. There is no contract of >> a multiply-dispatching operation in languages like Julia. Which is why >> it is a type error or an undefined behavior. > > I did not look at Julia rules. But languages which I know give > tight contract on multiple dispatch. How is it tight if it does not guarantee execution of the operation? >> If you contracted the multiple-dispatch operation Print to propagate >> exception on *certain* combinations of arguments that would not be a >> fault either. The problem is with [un]certainty. > > There is no uncertainty: language rules and program text exactly > specify which argument combinations propagate exception and > which go to specific implementation. That would not qualify even if it were true. It must be the specification of the module where the type declaration appears, nothing else. Contract /= implementation of. But of course Julia does not check the whole source code for consistency of dispatching calls. It is just typical "use it at your own peril" stuff. -- Regards, Dmitry A. Kazakov http://www.dmitry-kazakov.de ^ permalink raw reply [flat|nested] 14+ messages in thread
end of thread, other threads:[~2020-11-15 16:28 UTC | newest] Thread overview: 14+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2020-11-12 7:12 Multiple dispatch in Julia Jerry 2020-11-12 7:48 ` Dmitry A. Kazakov 2020-11-12 8:55 ` Jerry 2020-11-12 10:27 ` Dmitry A. Kazakov 2020-11-12 17:56 ` antispam 2020-11-12 18:28 ` Dmitry A. Kazakov 2020-11-12 21:22 ` antispam 2020-11-13 7:49 ` Dmitry A. Kazakov 2020-11-13 12:55 ` antispam 2020-11-13 14:59 ` Dmitry A. Kazakov 2020-11-15 12:43 ` antispam 2020-11-15 13:37 ` Dmitry A. Kazakov 2020-11-15 14:32 ` antispam 2020-11-15 16:28 ` Dmitry A. Kazakov
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox