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

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

Georg Bauhaus wrote:

> Dmitry A. Kazakov <mailbox@dmitry-kazakov.de> wrote:
>  
> : (*) Surely one could further pursue the present Ada approach to arrays,
> : which is kind of hard-wired "template", because "type X is array (Y) of
> : Z", is much close to a generic instantiation. The problem with that is,
> : that anything that should work with different array types automatically
> : becomes generic as well, which ends in STL for Ada. If we could lift
> : this limitation, things might become much easier.
> 
> Easier in which way? It is very easy to write a multimethod in CLOS.
> I think it is also very easy to forget a whole bunch of cases,
> each part of the parameter profile multiplying the number of cases.

Are you talking about MD? If Ada should support it, then there RM should
require that when one signature of a primitive operation gets overridden
all other signatures of the operation should be explicitly overridden as
well. To reduce the number of cases one should also provide language
support for commutative operations and ones in parallel type hierarchies.

> It also incurs some mechanism that dedices what to call based on
> arguments, right?

That's no problem. The type tag could be an index in a multidimensional
dispatch table.

> Likewise, how does it become easier to write all the implementations?

Discrete types are predefined. Implementations will be needed in non-trivial
cases only. For example, if you want an array indexed by String.

> If everything that some construct like abstract array indexing needs
> has to be provided by the implmenting types, this might easily lead
> to type inflation.

How it differs from what we have now:

generic
   type Index is private;
   with function ">" (Left, Right : Index) return Boolean;
   with function First return Index;
   ...

You have to implement ">" before you instantiate.

> I'm not sure whether or not this is better than to
> define operations based on what the type already has, and near where
> they are needed.

You will have this for free with multiple inheritance. Consider a possible
scenario of making Integer an array index. It is made by deriving a new
type from Integer (by implementation inheritance) and abstract index type
(by interface inheritance). The inherited Integer implementation will
implement the index interface. This is what will happen behind the scene
when you write "array (Integer range <>) of".

> :> Is this efficient? How many checks are needed at run time (in the
> :> presence of separate compilation)?
> : 
> : Implementations can be declared inline.
> 
> But won't implementations have to have some overhead, inlined or not?
>
> Say you make Number a base class for all sorts of numbers.

That will be an abstract type with no implementation, just an interface. As
such it is just a label you can attach to any type by providing
implementations.

> How do you manage to write code so the compiler will know
> it deals with numbers of the kind required in some algorithm
> involving Array or MultiArray without whole program analysis?

You cannot have objects of an abstract type (interface). So what you would
do to write a program dealing with all kind of numbers? Presently it is
impossible, so there is nothing to compare with.

I have an idea of ad-hoc supertypes. Instead of making all numbers derived
from Number, sharing its implementation, which will be either impossible or
inefficient, we could create such supertypes as necessary *afterwards*. So
if you want to bring Integer and Float under one roof, you create a common
non-abstract supertype MyNumber. This would require an implementation for
MyNumber, which can be made more efficient, because you know all the
players. Observe that now you have a choice:

1. either you write your numeric library in terms of MyNumber, which would
make it possible to have efficient shared bodies.

2. or you write it in terms of Number'Class, which will be less efficient if
bodies are not inlined (the compiler does not know ultimate type
representation).

> : It does not differ from templates.
> 
> If you pass pairs of pointers around, and have separate compilation,
> and specs and bodies, and access types with values pointing to some
> derivation, I imagine a multimethod like
> 
>    function "()"(mine: Basket; i: JumpyIndex) return Goods;
> 
> will still not be that quick, unless everything about it can be
> found out at compile time. Is this correct?

With multimethod (=MD), "()" will dispatch. That's the only overhead I see,
and only if the destination is not statically known. Parameter passing
mechanism can be any.

> : Then I'd like to have a mechanism to fore compile-time evaluation of
> : pure functions, when arguments are static. This would solve all problems
> : with efficiency.
> 
> All problems?

Many. You will have unbounded strings, statically checkable dimensioned
values, all user-defined! to begin with...

> How much is static in an average program?

This varies depending on the application field. In an embedded system it
could be 100%.

The goal is to go static as much as possible, but also to have an ability to
switch to dynamic (=less efficient) approach when you cannot otherwise.

> How long does program analysis take for the compiler to find out?
> Or is it the linker?

I do not expect any new problems here. I presume that generics/templates
impose the most difficult problems for compilers (and programmers too).
Dymanic management of dispatching tables could become a problem if we relax 
restrictions of the contexts where the new types can be derived.

> : More difficult problems are:
> : 
> : 1. setters
> : 2. anonymous array subtypes and anonymous subarray types needed to all
> : sorts of aggregates and slices
> : 3. user-defined aggregates, of course
> : 4. same with index types, to have ranges
> : 
> :> How do you get hold of plain basic types?
> : 
> : I see no problem with them. For example, discrete types could be
> : considered derived from some abstract index type.
> 
> Hmmnn, if the compiler knows about some very special derivations
> it might know how to use processor registerers for indexing.
> Otherwise....
> 
> : type I is range 1..40;
> : 
> : be treated as an abbreviation of something like:
> : 
> : type I is new Ordered_Index with range 1..40;
> : -- function ">" (Left, Right : I) return Boolean implements
> : -- function ">" (Left, Right : Ordered_Index) return Boolean is
> : abstract;
> 
> This looks somewhat like Haskell, doesn't it?

I cannot judge.

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