Multiple dispatch in Julia

Multiple dispatch in Julia

[Jerry]

I'm curious to know what Ada folks think about this discussion about Julia, especially the extended comment about multiple dispatch.

Jerry

Re: Multiple dispatch in Julia

[Dmitry A. Kazakov]

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

Re: Multiple dispatch in Julia

[Jerry]

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.)

Re: Multiple dispatch in Julia

[Dmitry A. Kazakov]

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

Re: Multiple dispatch in Julia

[antispam]

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

Re: Multiple dispatch in Julia

[Dmitry A. Kazakov]

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

Re: Multiple dispatch in Julia

[antispam]

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

Re: Multiple dispatch in Julia

[Dmitry A. Kazakov]

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

Re: Multiple dispatch in Julia

[antispam]

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

Re: Multiple dispatch in Julia

[Dmitry A. Kazakov]

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

Re: Multiple dispatch in Julia

[antispam]

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

Re: Multiple dispatch in Julia

[Dmitry A. Kazakov]

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

Re: Multiple dispatch in Julia

[antispam]

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

Re: Multiple dispatch in Julia

[Dmitry A. Kazakov]

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