From mboxrd@z Thu Jan 1 00:00:00 1970 X-Spam-Checker-Version: SpamAssassin 3.4.5-pre1 (2020-06-20) on ip-172-31-74-118.ec2.internal X-Spam-Level: X-Spam-Status: No, score=-1.9 required=3.0 tests=BAYES_00 autolearn=ham autolearn_force=no version=3.4.5-pre1 Path: eternal-september.org!reader02.eternal-september.org!feeder.eternal-september.org!news.cs.hut.fi!goblin2!goblin1!goblin.stu.neva.ru!newsfeed.pionier.net.pl!pwr.wroc.pl!news.wcss.wroc.pl!not-for-mail From: antispam@math.uni.wroc.pl Newsgroups: comp.lang.ada Subject: Re: Multiple dispatch in Julia Date: Fri, 13 Nov 2020 12:55:45 +0000 (UTC) Organization: Politechnika Wroclawska Message-ID: References: <6faed833-462a-4b4b-b555-9a632fd7caddn@googlegroups.com> NNTP-Posting-Host: hera.math.uni.wroc.pl X-Trace: z-news.wcss.wroc.pl 1605272145 19775 156.17.86.1 (13 Nov 2020 12:55:45 GMT) X-Complaints-To: abuse@news.pwr.wroc.pl NNTP-Posting-Date: Fri, 13 Nov 2020 12:55:45 +0000 (UTC) Cancel-Lock: sha1:+sufbWp2qH5CGR8yfrXnOh/hMTY= User-Agent: tin/2.4.3-20181224 ("Glen Mhor") (UNIX) (Linux/4.19.0-10-amd64 (x86_64)) Xref: reader02.eternal-september.org comp.lang.ada:60582 List-Id: Dmitry A. Kazakov wrote: > On 12/11/2020 22:22, antispam@math.uni.wroc.pl wrote: > > Dmitry A. Kazakov wrote: > >> On 12/11/2020 18:56, antispam@math.uni.wroc.pl wrote: > >>> 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? > >>>> > >>>> ----------- > >>>> 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