Re: "Must instantiate controlled types at library level." Why?

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

On Mon, 24 May 2004 14:40:33 +0000 (UTC), Georg Bauhaus
<sb463ba@l1-hrz.uni-duisburg.de> wrote:

>Dmitry A. Kazakov <mailbox@dmitry-kazakov.de> wrote:
>: On Mon, 24 May 2004 11:38:38 +0000 (UTC), Georg Bauhaus
>: <sb463ba@l1-hrz.uni-duisburg.de> wrote:
>: 
>:>Dmitry A. Kazakov <mailbox@dmitry-kazakov.de> wrote:
>:>: Georg Bauhaus wrote:
>:> 
>:>: That's no problem. The type tag could be an index in a multidimensional
>:>: dispatch table.
>:> 
>:>With fallback entries, so you don't have to provide entries for
>:>all m x n x k for a function of (Tm, Tn) -> Tk, I guess, where
>:>m, n, and k the number of types in the respective type trees?
>: 
>: No, there is only one more level of indirection needed as compared to
>: single dispatch.
>
>OK but to what do the pointers refer? Say I write
>a two argument procedure expecing it to be dispatching in both.
>
>  proc drive (v: in out Vehicle; d: Steering_Device);
>
>I get
>  drive.Impl (v'tag) -> i
>  drive.Impl (d'tag) -> j

>OK. Now what if later during development some programmer
>adds a module that calls
>
>  drive(vv, ddd);
>
>The program then would have to have entries in the dense
>dispatching maps for i', j', wouldn't it?

Yes. If there are I types rooted in Vehicle and J types rooted in
Steering_Device, then the size of the dispatching table is I x J.

>So in general you will need n x m implementations, unique or
>not. And prior to whole program analysis you will need fallback
>mechanisms.

No, it does not differ from SI case. When a new type is derived from
some base(s), all primitive operations of that type are inherited.
Technically it means that dispatching tables of all subroutines having
the type as an [dispatching] argument receive a column(s).

>: So to disptach to Foo the compiler should resolve:
>: 
>: Foo.Impl (Foo.A (First'Tag), Foo.B (Second'Tag), Foo.A (Third'Tag))
>: 
>: All arrays here are dense.
>
>Still before complete analysis of the linked program you might
>have to provide for the possibility of an argument that is not
>yet in A's or B's map.

Same with SD.

>How does this remove the conceptual need for an m x n x k dispatch
>matrix, independent of how you implement it, along with the need to
>actually think of m x n x k cases? Is it worth the trouble?

If you have MD you have to think about all possible combinations of
the parameter types. It does not depend on how MD is implemented. It
is what MD is.

Note that when you are trying to implement MD using SD, these problems
do not disappear. There are still m x n x k cases to think of. The
only "advantage" is that you have no language support.

And finally, Ada already has MD, though limited:

1. All arguments types are descendants of same base
2. Only diagonal elements of the dispatching table can be overridden
3. Non-diagonal elements raise Constraint_Error

>:>: How it differs from what we have now: [...]
>:>: You have to implement ">" before you instantiate.
>:>
>:>You won't have to add a type with an implementation of a
>:>comparison interface. All that is needed is a comparison function,
>:>inheritance/implementation is not involved.
> 
>: When you write in a generic interface something like "type X is <>",
>: you in fact specify an interface to be implemented. During
>: instantiation the actual type is checked against the interface. If
>: check is OK the implementation is accepted. One can do same for
>: non-generic interfaces. 
>
>Yes certainly, but why?

To have class-wide instances. This is what generics cannot provide.

>: I see no technical reason why generic instantiations should be more
>: flexible in that respect. AFAIK ARG is going to relax some
>: restrictions anyway.
>
>Consider a simple untagged user defined type that by itself is not
>ordered.  For some reasons you want to store objects of the type in sorted
>containers (yes, there may be reasons to do so.)  So you have to provide
>"<", consistent with "=".  But "<" does not belong to the simple user
>defined type because that by itself is not ordered.
>
>Solution 1: Add it to the type no matter what and explain that
>  "<" is there because some remote part of the program has good
>  reasons to store objects in a sorted container.

In many cases you cannot do that. Consider predefined types, like the
type Tag. It would be nice to have "<" with the semantics of "<:" (a
descendant of), but you can nothing to do about it.

>Solution 2: Turn the simple user defined type into a tagged type
>  and derive a new one from it adding "<" to the derived type
>  (possibly implementing a Less_Than interface in Ada 200Y).

>Solution 3: Add "<" locally in the remote part of the program,
>  implement it using operations of the simple user defined type.

In this case "<" will not be a primitive operation of the type. So it
might get lost. Even worse are many concurrent implementations of "<"
puzzling you which one will be selected by the compiler.

>Solution 3 leaves the simple unordered user defined type completely
>as is, untagged.  At the same time it hides "<" locally, as does
>solution 2. But 2 achieves this effect only at the cost of making
>the simple UDT tagged, and adding the possibility of dispaching,
>prior to a full investigation by the compiler/linker.

All specific types have to be tagged in the sense of existence
T'Class. This costs nothing as long as no objects of T'Class exist. So
you need not care about dispatch.

>:>Is it impossible to have a generic function that operates on
>:>reals as well as on complex numbers?
>: 
>: for I in A'Range loop
>:   A (I) := 0;
>
>  A(I) := neutral_element_of_addition;  -- of course
>
>: end loop;
> 
>: Is it impossible to write
>: 
>: A(A'First) := 0;
>: A(A'First + 1) := 0;
>: A(A'First + 2) := 0;
>: A(A'First + 3) := 0;
>: ...
>: ?
>
>I don't understand. It is possible...

I shows that there is no need to have loop statements in the language,
because everything one might wish to do with a finite set of elements
can be done using a plain sequence of statements. So when you ask why
one needs class-wide programs instead of generic ones, then answer is
- no more than loop statements instead of code above.

>:>What's wrong with generic units that work like this, with either formal
>:>tagged types or explicit requirements listing with defaults?  ;)
>: 
>: I do not see how they could help. Consider a program (say parser) that
>: should work with both String and Unbounded_String. When the type is a
>: generic parameter, then the whole compiler will be generic too.
>
>I have a generic in a program for turning Wide_String values into
>external representations. This requires either String or Wide_STring,
>so I'm using either String or Wide_String in the respective
>instantiations...
>If I had a need to inject string polymorphism in all parts of the
>program I'd do the usual thing: create a user defined type, as
>for every other predefined type that isn't polymorphic.

It is nothing else than I propose - an ability to *easily* create a
user-defined type serving as a supertype for String, Unbounded_String,
Wide_String, Wide_Wide_String, Wide_Wide_Unbounded_String etc.
Presently, you have to do it manually and then explicitly convert
values and literal. It is a mess.

>:>(In Ada200Y you can even have multiple interfaces, IIRC.)
>:>
>:>Maybe you want take Eiffel into account, as it has a lot of what you
>:>seem to want, including full multiple inheritance?
>: 
>: C++ has MI.
>
>I did say Eiffel not because it has MI. It is no alone there.
>But a lot of what you have said has reminded me not only of
>C++ templates and compiling/linking, but also of problems that
>Eiffel has solved. It might be interesting to look at the solution
>and the consequences it has.
>Eiffel libraries use MI a lot to express a component's dependence
>on the presence of methods specified in interfaces like COMPARABLE,
>HASHABLE, etc.

That we will have in Ada200Y with multiple interface inheritance.

But that is far not enough to make array types second-class
(user-defined). In fact even more interesting would be second-class
access types (for smart pointers, garbage collection, etc)

--
Regards,
Dmitry Kazakov
www.dmitry-kazakov.de