Re: Multiple dispatch in Julia

["Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de>]

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