Re: Multiple dispatch in Julia

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

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