Re: Limited types

Re: Limited types

[Matthew Heaney]

In article <3564E39E.B8D445B0@ececs.uc.edu>, Phani Putrevu
<pputrevu@ececs.uc.edu> wrote:

(start of quote)
How  exactly is limited type defined.. In the glossary of the on-line
RM, limited type is defined as a type for which the assignment operator
is not defined. What about the equality operator?  In the operators
section,  it is told that equality and inequality operators are
predefined for nonlimited types.  Does this follow from the assignment
operator not being allowed.
(end of quote)

Typically, you'd declare an abstract data type as limited, as in:

   type LT is limited private;

or 

   type LT is tagged limited private;

or

   type LT is abstract tagged limited private;

You can also declare a record as limited:

   type RT is 
      limited record
         ...
      end record;

Limited private types are used when you have an item which it doesn't make
sense to duplicate, ie

   type Bank_Account is tagged limited private;
...
   Matts_Money : Bank_Account;

I would love to be able to do this:

   Matts_Money := Matts_Money + Matts_Money;

but of course I don't think the bank would take too kindly to this sort of
thing!  That's why it's illegal (for limited types).

Equality isn't predefined for a limited type, but you can add one if it
makes sense for your abstraction:

   function "=" (L, R : Bank_Account) return Boolean;

Equality is predefined for a non-limited type.  The default definition is a
bit-wise compare, which very often is _not_ what you want, so even for
non-limited types, you typically override it.

Limited types

[Phani Putrevu]

Hi,

very basic question :

How  exactly is limited type defined.. In the glossary of the on-line
RM, limited type is defined as a type for which the assignment operator
is not defined. What about the equality operator?  In the operators
section,  it is told that equality and inequality operators are
predefined for nonlimited types.  Does this follow from the assignment
operator not being allowed.

Thanks a lot,

Phani

limited types (Was: Records that could be arrays)

[Thierry Bernier]

Stephen Leake <stephe_on_the_web@toadmail.com> wrote : 

> If we implemented points as limited private types, we wouldn't be

Please do not.
limited is like the flu : a record containing a limited field must be 
limited itself.
For example, you can not extend a Gtk.Window.Gtk_Window_Type with an 
extension containing a limited type, or else the root of these types must 
be limited (and I don't own it).

limited should be used only when the type is really limited (when using 
accesses, tasks, etc).

Disagrees ?
--
Thierry Bernier

 

Re: limited types (Was: Records that could be arrays)

[Randy Brukardt]

"Thierry Bernier" <email@enon.moc> wrote in message
news:Xns9774B59B784EFemailenonmoc@212.27.42.197...
> Stephen Leake <stephe_on_the_web@toadmail.com> wrote :
>
> > If we implemented points as limited private types, we wouldn't be
>
> Please do not.limited is like the flu : a record containing a limited
field must be
> limited itself.
> For example, you can not extend a Gtk.Window.Gtk_Window_Type with an
> extension containing a limited type, or else the root of these types must
> be limited (and I don't own it).
>
> limited should be used only when the type is really limited (when using
> accesses, tasks, etc).
>
> Disagrees ?

Limited is a flu, as you put it, but it is a pretty mild flu. Indeed, in Ada
200Y, it pretty much means that you can't assign it, and that's it. You can
have aggregates and functions with suitable limitations.

Indeed, many of us think that "limited" should be the default for Ada. (It
certainly ought to be for interfaces and tagged types, because that allows
more uses.) Only if you *need* assignment should something be non-limited.

For example, your window example *should* be limited; it doesn't make sense
to assign windows. (Yes, Claw does this wrong, too, mainly because of the
limitations on the use of limited in Ada 95 that no longer apply.) That's
especially valuable because then the extensions can include any kind of
component.

Of course, you often do need assignment. The containers are non-limited so
that they can be composed. And that's because it doesn't make sense to have
limited elements (as the elements have to be copied into the container).

But in any case this is decision that needs to be made based on the use of
the type, not for philosophical reasons...

                              Randy.

Re: limited types (Was: Records that could be arrays)

[Matthew Heaney]

"Randy Brukardt" <randy@rrsoftware.com> writes:

> Of course, you often do need assignment. The containers are non-limited so
> that they can be composed. And that's because it doesn't make sense to have
> limited elements (as the elements have to be copied into the container).

On that subject, we recently had need of a bounded list (for restricted
runtimes, sans dynamic memory allocation), something like:

generic
  type ET is private;
  with "=" (L, R : ET) return Boolean is <>;

package Ada.Containers.Bounded_Lists is
  type List (Capacity : Count_Type) is tagged limited private;
  ... -- more or less same as Doubly_Linked_Lists
end;

That brings up the composability issue, since you'd like to be able to create a
container whose elements are bounded lists.  I came up with something like:

generic
  type ET is limited private;

package Ada.Containers.Limited_Bounded_Lists is
  type List (Capacity : Count_Type) is tagged limited private;

  function Element
    (Container : not null access List;
     Position  : Cursor)
    return not null access ET;

  function Constant_Element
    (Container : not null access constant List;
     Position  : Cursor)
    return not null access constant ET;

  function First_Element
    (Container : not null access List)
    return not null access ET;

  function Constant_First_Element
    (Container : not null access constant List)
    return not null access constant ET;

...
end;

Query_Element and Update_Element are still there, but it's awfully nice to be
able to rename an element directly.  You can do something like:

procedure Op (L : in out List) is
begin
  L.Append (Initialize'Access);  -- init elem
  -- or: L.Append;               -- no init necessary
  -- or: L.Insert (Before => No_Element, Process => Initialize'Access);
  -- or: L.Insert (Before => No_Element);

  declare
    E : ET renames L.Last_Element;  -- implicit 'Access
  begin
    ... -- use E
  end;
end Op;


The only potential issue is that if you rename an active element, it can
subsequently become inactive (if you Delete it) in the scope of the renaming.
If you were to subsequently manipulate it that would probably be bad, but at
least the object doesn't disappear as it would in the unbounded case, since the
object just moves onto an internal free list owned by the list.

Don't know if that's the right thing to do, though.  I haven't done anything
with it yet so maybe I'll just get rid of those ops.  It's just that in the
case of a limited element, it's OK to declare the element as aliased, since
there's no issue (I think) about constraining an element object whose type is a
discriminated record with default discriminant.

It was nice to be able to bounce ideas off of the ARG subcommittee.  We ought
to set up a mailing list or something to discuss post-Ada 2005 container
issues.  We might be able to reuse the old mailing list at yahoo if it's still
around.

-Matt

Re: limited types (Was: Records that could be arrays)

[Matthew Heaney]

Matthew Heaney <matthewjheaney@earthlink.net> writes:

>   declare
>     E : ET renames L.Last_Element;  -- implicit 'Access
                     ^^^^^^^^^^^^^^

Oops!  Should be:

      E : ET renames L.Last_Element.all;

Re: limited types (Was: Records that could be arrays)

[Dmitry A. Kazakov]

On Fri, 24 Feb 2006 15:57:46 -0600, Randy Brukardt wrote:

> Indeed, many of us think that "limited" should be the default for Ada. (It
> certainly ought to be for interfaces and tagged types, because that allows
> more uses.) Only if you *need* assignment should something be non-limited.

Right
 
> Of course, you often do need assignment. The containers are non-limited so
> that they can be composed. And that's because it doesn't make sense to have
> limited elements (as the elements have to be copied into the container).

I think that there should also be [limited] containers of limited types.
For this we need a construction model, which would allow user-defined
in-place constructors. After all Ada has always had arrays of limited
components. We have to extend this model onto user-defined containers.

I think that this would require separation of assignment from copy
constructor, as C++ does. Though the default must be that assignment is
generated from destructor and copy constructor.

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Re: limited types (Was: Records that could be arrays)

[Matthew Heaney]

"Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> writes:

> I think that there should also be [limited] containers of limited types.
> For this we need a construction model, which would allow user-defined
> in-place constructors. After all Ada has always had arrays of limited
> components. We have to extend this model onto user-defined containers.

But you can pass in an Initialize procedure as a parameter of an insertion
operation, to perform whatever initialization needs to be done.

Also (see below for ex), you already have copy ctors for Ada 2005, even for
limited types.


> I think that this would require separation of assignment from copy
> constructor, as C++ does. Though the default must be that assignment is
> generated from destructor and copy constructor.

You could pass in a copy constructor if this were an unbounded form (I thik),
something like:

  procedure Insert
    (C : in out CT;
     E : in ET;
     Copy : not null access function (E : ET) return ET)
  is
     Node : Node_Access :=
       new Node_Type'(Element => Copy (E), others => <>);
  begin
     ...
  end;

Wouldn't that work?  I don't have a compiler that can do that yet, but I know
this would be legal:

  procedure Op (E : ET) is
    EE : ET := Copy (E);
  begin
    ...
  end;

so I assume initialization of an aggregate is the same.  (But I could be
wrong.)

Re: limited types (Was: Records that could be arrays)

[Randy Brukardt]

"Matthew Heaney" <matthewjheaney@earthlink.net> wrote in message
news:ufym7tr6w.fsf@earthlink.net...
...
> You could pass in a copy constructor if this were an unbounded form (I
thik),
> something like:
>
>   procedure Insert
>     (C : in out CT;
>      E : in ET;
>      Copy : not null access function (E : ET) return ET)
>   is
>      Node : Node_Access :=
>        new Node_Type'(Element => Copy (E), others => <>);
>   begin
>      ...
>   end;
>
> Wouldn't that work?  I don't have a compiler that can do that yet, but I
know
> this would be legal:

Yes, that's legal (a limited function can be an aggregate element, and an
aggregate can be used to initial an object). The compiler is required to
build the object in place for such aggregates and functions; no temporaries
are allowed.

                       Randy.

Re: limited types (Was: Records that could be arrays)

[Dmitry A. Kazakov]

On Sat, 25 Feb 2006 15:05:02 GMT, Matthew Heaney wrote:

> "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> writes:
> 
>> I think that there should also be [limited] containers of limited types.
>> For this we need a construction model, which would allow user-defined
>> in-place constructors. After all Ada has always had arrays of limited
>> components. We have to extend this model onto user-defined containers.
> 
> But you can pass in an Initialize procedure as a parameter of an insertion
> operation, to perform whatever initialization needs to be done.

You mean "return .. do" for limited types. It is in-place, but a
constructing function does not have safety of a constructor. Then you
cannot ask it from the type, so it can't have a default [deduced from the
type.] It is not dispatching in Insert. What about container of
class-wides, i.e. when Node_Type should have ET'Class?

... and of course passing pointers to functions is ugly.

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Re: limited types (Was: Records that could be arrays)

[Matthew Heaney]

"Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> writes:

> On Sat, 25 Feb 2006 15:05:02 GMT, Matthew Heaney wrote:
> 
> > But you can pass in an Initialize procedure as a parameter of an insertion
> > operation, to perform whatever initialization needs to be done.
> 
> You mean "return .. do" for limited types. 

For an unbounded form, you could do it either way, via an Initialize procedure,
or via a Copy function (using the new return do syntax).

For a bounded form, only an Initialize procedure would work, since the actual
initialization of the elements happens only once, when the (bounded) container
object is elaborated.


> It is in-place, but a constructing function does not have safety of a
> constructor. 

Huh?  An Ada 2005 constructor function *is* a constructor.  It's no different
from a copy ctor in C++.


> Then you cannot ask it from the type, so it can't have a default
> [deduced from the type.]. It is not dispatching in Insert. 

Aren't constructors always non-dispatching (unless you're using a Factory
Method pattern)?  But this is no different from the C++ STL.

If you have an container (of indefinite elements) instantiated with (limited)
type T'Class, then I suppose you might want to have a dispatching constructor.
I'd have to think about how to do that[but see below].  (In my earlier example
I was really thinking of bounded forms, which cannot have indefinite elements.)


> What about container of class-wides, i.e. when Node_Type should have
> ET'Class?

Only applies to unbounded containers whose elements are indefinite.  GCC
allocates each indefinite element (so Node_Type has a pointer to ET).  

In general there's never any direct dispatching inside a generic, since the
generic formal region doesn't pass in any operations, the formal type isn't
tagged, and formal operations must be statically bound to the element type.

If you wanted a contructor to dispatch, you'd have to say (assuming my
knowledge of Ada 2005 is correct):

  type ET is tagged limited private;
  function Copy (E : ET) return ET;  -- primitive op

  function Copy_Classwide (E : ET'Class) return ET'Class is
  begin
    return Copy (E);  -- legal Ada 2005?
  end;
  
Then you pass this in as per the example of my earlier post:

  package List_Types is
    new Limited_Indefinite_Lists (ET'Class);
  ...

  procedure Op (L : in out List) is
  begin
    ...
    L.Insert (...New_Item => E, Copy => Copy_Classwide...);
    ...
  end;

Then the primitive Copy operation will dispatch according to the tag of actual
parameter E.  This is always what you do inside a generic to enable dispatching
(when the generic formal type is non-tagged and indefinite).


> ... and of course passing pointers to functions is ugly.

This is not an argument.  The existing API already has function pointers
everywhere, so you might as well get used to it.

Re: limited types (Was: Records that could be arrays)

[Dmitry A. Kazakov]

On Sun, 26 Feb 2006 18:20:39 GMT, Matthew Heaney wrote:

> "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> writes:
> 
>> It is in-place, but a constructing function does not have safety of a
>> constructor. 
> 
> Huh?  An Ada 2005 constructor function *is* a constructor.  It's no different
> from a copy ctor in C++.

No. The constructor is wrapped by the function. Differently to a true
constructor, you cannot ensure the wrapper to be always called for some
specified signature.

> If you have an container (of indefinite elements) instantiated with (limited)
> type T'Class, then I suppose you might want to have a dispatching constructor.
> I'd have to think about how to do that[but see below].  (In my earlier example
> I was really thinking of bounded forms, which cannot have indefinite elements.)

Consider the following use cases:

1. Containers of class-wide types (this will be possible.)

2. Subtypes of (1) constrained to a definite type from the class.

3. Containers of specific types building a parallel types hierarchy. I.e.
if S is a subtype of T, then a container type with the elements of S is a
subtype of a container type with the elements of T.

>> What about container of class-wides, i.e. when Node_Type should have
>> ET'Class?
> 
> Only applies to unbounded containers whose elements are indefinite.  GCC
> allocates each indefinite element (so Node_Type has a pointer to ET).  
> 
> In general there's never any direct dispatching inside a generic, since the
> generic formal region doesn't pass in any operations, the formal type isn't
> tagged, and formal operations must be statically bound to the element type.
> 
> If you wanted a contructor to dispatch, you'd have to say (assuming my
> knowledge of Ada 2005 is correct):
> 
>   type ET is tagged limited private;
>   function Copy (E : ET) return ET;  -- primitive op

This you have to override in each of non-abstract derived type. If the
compiler knew that Copy is a constructor it could safely compose it out of
constructors of the bases and the components (in most of cases.)

>   function Copy_Classwide (E : ET'Class) return ET'Class is
>   begin
>     return Copy (E);  -- legal Ada 2005?
>   end;

I don't see why it should be illegal. But I wish the compiler to do this
automatically.
  
>> ... and of course passing pointers to functions is ugly.
> 
> This is not an argument.  The existing API already has function pointers
> everywhere, so you might as well get used to it.

And this is an argument? (:-))

Even if the functions were passed without pointers (as they should be in a
language like Ada), even then it would be ugly, because the compiler and
the reader of the code already have full information about what's going on.
The type itself tells everything unambiguously.

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Re: limited types (Was: Records that could be arrays)

[Matthew Heaney]

"Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> writes:

> On Sun, 26 Feb 2006 18:20:39 GMT, Matthew Heaney wrote:
> > Huh?  An Ada 2005 constructor function *is* a constructor.  It's no
> > different from a copy ctor in C++.
> 
> No. The constructor is wrapped by the function. Differently to a true
> constructor, you cannot ensure the wrapper will always be called for some
> specified signature.

This is a specious argument.  If you says the "real" constructor is wrapped by
a function then you're guilty of moving the goal-posts.

We're talking about requiring that a constructor be called. The syntax doesn't
matter.  That fact that Ada 2005 spells it f-u-n-c-t-i-o-n is irrelevent.

If you want to force a constructor to be used, then you can make the partial
view of the type indefinite.


> Consider the following use cases:
> 
> 1. Containers of class-wide types (this will be possible.)

Yes, you already have this.


> 3. Containers of specific types building a parallel types hierarchy. I.e.
> if S is a subtype of T, then a container type with the elements of S is a
> subtype of a container type with the elements of T.

You have totally misunderstood the design of the Ada 2005 container library.

When you use cursors, then this abstracts-away the container itself, leaving
you with a sequence of elements.  This model works for all the containers
already (and for arrays too, in fact).

Write your algorithms in terms of sequences of elements instead of containers,
and you can forget about containers.


> >   type ET is tagged limited private;
> >   function Copy (E : ET) return ET;  -- primitive op
> 
> This you have to override in each of non-abstract derived type. 

Not quite.  You have to override only if this is a non-null extension.  But
again that's no different from C++.  Derived classes need to implement their
own ctor, if only to call the ctor of the base class.

(In the typical case, the base class is abstract, and its ctor is declared as
protected.  The ctor available to users is the ctor of the derived class.)


> If the compiler knew that Copy is a constructor it could safely compose it
> out of constructors of the bases and the components (in most of cases.)

In practice concrete derived classes must implement their own ctors, that call
the ctor of the base class.


> >   function Copy_Classwide (E : ET'Class) return ET'Class is
> >   begin
> >     return Copy (E);  -- legal Ada 2005?
> >   end;
> 
> I don't see why it should be illegal. But I wish the compiler to do this
> automatically.

But I did this to show you how call a dispatching operation inside a generic,
with a non-tagged indefinite formal type.  

It's completely consistent with the existing generic model.  When are
operations for generic formal private types ever just synthesized?  

In the case at hand, you need an operation that takes type ET'Class, which is
the type used to instantiate the generic, so you have to write it yourself, the
same as for any other operation.


> And this is an argument? (:-))

This ignores the history of Ada language evolution:

Ada83: no function pointers; royal pain
Ada95: function pointers at library-level only: GUI callbacks, etc
Ada05: function pointers in nested scopes too

No one seems to agree with you, Dmitry!  The trend has been to allow the
declaration of "ugly" function pointers in more places, not fewer.

Re: limited types (Was: Records that could be arrays)

[Dmitry A. Kazakov]

On Sun, 26 Feb 2006 22:07:00 GMT, Matthew Heaney wrote:

> "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> writes:
> 
>> On Sun, 26 Feb 2006 18:20:39 GMT, Matthew Heaney wrote:
>>> Huh?  An Ada 2005 constructor function *is* a constructor.  It's no
>>> different from a copy ctor in C++.
>> 
>> No. The constructor is wrapped by the function. Differently to a true
>> constructor, you cannot ensure the wrapper will always be called for some
>> specified signature.
> 
> This is a specious argument.  If you says the "real" constructor is wrapped by
> a function then you're guilty of moving the goal-posts.
> 
> We're talking about requiring that a constructor be called. The syntax doesn't
> matter.  That fact that Ada 2005 spells it f-u-n-c-t-i-o-n is irrelevent.

There is a fundamental difference between a subprogram and a constructor. A
subprogram can implement a part of a constructor (like Initialize), it can
call to a constructor (like Copy), but it cannot *be* a constructor.
Constructors are not decomposable into subprograms. Copy is a subprogram as
any other. That means, other subprograms can do exactly the same, i.e. you
have a backdoor wide open.

> If you want to force a constructor to be used, then you can make the partial
> view of the type indefinite.

It is not a programmer's choice and not a question of view. There should be
absolutely no way to pass construction by.

>> 3. Containers of specific types building a parallel types hierarchy. I.e.
>> if S is a subtype of T, then a container type with the elements of S is a
>> subtype of a container type with the elements of T.
> 
> You have totally misunderstood the design of the Ada 2005 container library.
> 
> When you use cursors, then this abstracts-away the container itself, leaving
> you with a sequence of elements.  This model works for all the containers
> already (and for arrays too, in fact).
> 
> Write your algorithms in terms of sequences of elements instead of containers,
> and you can forget about containers.

No, thanks. If I wished that sort of untyped design, there would be C++ and
dynamically typed languages at my disposal. I don't want untyped
containers. I would keep boxes for apples and barrels for herrings in
separate rooms.

>> If the compiler knew that Copy is a constructor it could safely compose it
>> out of constructors of the bases and the components (in most of cases.)
> 
> In practice concrete derived classes must implement their own ctors, that call
> the ctor of the base class.

It must be called automatically, like in C++. It is already so in Ada for
the parts generated by the compiler. You cannot override construction of
the components. There is no reason to treat user-defined parts otherwise.
You can skip Initialize, when you inherit and cannot when you aggregating.
Nonsense.

> In the case at hand, you need an operation that takes type ET'Class, which is
> the type used to instantiate the generic, so you have to write it yourself, the
> same as for any other operation.

This is an untyped model. As I said, I prefer a contract-based model. If
copyable type is the contract, that should require a copy constructor.

>> And this is an argument? (:-))
> 
> This ignores the history of Ada language evolution:
> 
> Ada83: no function pointers; royal pain
> Ada95: function pointers at library-level only: GUI callbacks, etc
> Ada05: function pointers in nested scopes too
> 
> No one seems to agree with you, Dmitry!  The trend has been to allow the
> declaration of "ugly" function pointers in more places, not fewer.

When Ada 95 added function pointers, it just admitted that functions are
regular objects. When Ada 05 allows anonymous access types for functions it
only pursues this idea of regularity further. I see no reason how this can
contradict to functions as values? Why a function cannot be passed as a
normal "in" parameter of limited type? Give me a reason. Why don't we
write: "not null access Integer" to pass Integer?

Further, considering distributed systems, how to marshal a function to
remote node, if functions does not have values?

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Re: limited types (Was: Records that could be arrays)

[Georg Bauhaus]

Dmitry A. Kazakov wrote:
> On Sun, 26 Feb 2006 22:07:00 GMT, Matthew Heaney wrote:


>> Write your algorithms in terms of sequences of elements instead of containers,
>> and you can forget about containers.
> 
> No, thanks. If I wished that sort of untyped design, there would be C++ and
> dynamically typed languages at my disposal. I don't want untyped
> containers. I would keep boxes for apples and barrels for herrings in
> separate rooms.

What kind of operations on containers do you have in mind,
as opposed to operations focussing on their elements?


-- Georg

Re: limited types (Was: Records that could be arrays)

[Dmitry A. Kazakov]

On Mon, 27 Feb 2006 15:34:58 +0100, Georg Bauhaus wrote:

> Dmitry A. Kazakov wrote:
>> On Sun, 26 Feb 2006 22:07:00 GMT, Matthew Heaney wrote:
> 
>>> Write your algorithms in terms of sequences of elements instead of containers,
>>> and you can forget about containers.
>> 
>> No, thanks. If I wished that sort of untyped design, there would be C++ and
>> dynamically typed languages at my disposal. I don't want untyped
>> containers. I would keep boxes for apples and barrels for herrings in
>> separate rooms.
> 
> What kind of operations on containers do you have in mind,
> as opposed to operations focussing on their elements?

1. Passing as a parameter
2. Copying
3. Merging
4. Slicing
5. Closures and simultaneous traversal of two or more containers
6. Relational operations on sets of containers
...

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Re: limited types (Was: Records that could be arrays)

[Matthew Heaney]

Dmitry A. Kazakov wrote:
>
> 1. Passing as a parameter

Just pass a cursor:

procedure Op (C : in out Container_Type) is
begin
   Do_Something (C.First);
   ...
end;

You know you've run out of elements when Has_Element returns False.


> 2. Copying

while (Has_Element (C) loop
  Put_Element_Somewhere (Element (C);
end loop;

> 3. Merging

You'll need to define a relational operator over your element type, but
then you can say:

Merge (C1.First, C2.First);


> 4. Slicing

Just use a cursor pair:

Do_Something (C1, C2);  -- half-open range


> 5. Closures and simultaneous traversal of two or more containers

Do_Something (C1, C2);


> 6. Relational operations on sets of containers

Compare (C1, C2);


If you don't understand this, go to

http://charles.tigris.org

and browse the Charles.Algorithms subsystem.  (Things are a little
different for the Ada 2005 container library, but it should give you
the general idea.)

Re: limited types (Was: Records that could be arrays)

[Dmitry A. Kazakov]

On 27 Feb 2006 08:52:23 -0800, Matthew Heaney wrote:

> Dmitry A. Kazakov wrote:
>>
>> 1. Passing as a parameter
> 
> Just pass a cursor:

I don't see how a constraint imposed on elements can propagate to the
cursor.

The question Georg asked was: where typed containers of elements of related
types might themselves appear related. The number of cases is huge.
Generics fundamentally cannot help here, they aren't dynamically
polymorphic. Whatever you do, the polymorphism can come only from outside,
like in the case of a tagged formal parameter, or as a type inheritance in
the declarative part of a generic package. So generics are completely
irrelevant to the discussion about the design of constructors and the types
system.

>> 2. Copying
> 
> while (Has_Element (C) loop
>   Put_Element_Somewhere (Element (C);
> end loop;

It is dynamic typing. The constraint check would happen at run-time. Too
late. You just have tossed a stinking herring in a jug apple cider...

>> 3. Merging
> 
> You'll need to define a relational operator over your element type, but
> then you can say:
> 
> Merge (C1.First, C2.First);

Same as above. I don't mix herrings and apples, because barrels and boxes
never meet in the production line. But they can on a container ship. And
their elements do in someone's stomach.

>> 4. Slicing
> 
> Just use a cursor pair:
> 
> Do_Something (C1, C2);  -- half-open range

Huh, what about a submatrix? The main diagonal of? And, BTW, I don't do
anything I want to get a new container.

[...]
> Do_Something (C1, C2);
> Compare (C1, C2);

Same as above.

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Re: limited types (Was: Records that could be arrays)

[Georg Bauhaus]

Dmitry A. Kazakov wrote:

> The question Georg asked was: where typed containers of elements of related
> types might themselves appear related. The number of cases is huge.
> Generics fundamentally cannot help here, they aren't dynamically
> polymorphic.

But then wouldn't you again be mixing apples and herrings?

  type APPLE_CONTAINER is new CONTAINER with null record;
    -- specializes in apples, only

  type HERRING_CONTAINER is new CONTAINER with null record;
    -- specializes in herrings, only

  x: access CONTAINER'class := ...;

  x.insert(an_apple); -- right or wrong? compile time?


> It is dynamic typing. The constraint check would happen at run-time. Too
> late. You just have tossed a stinking herring in a jug apple cider...
> 
> 
>>>3. Merging
>>
>>You'll need to define a relational operator over your element type, but
>>then you can say:
>>
>>Merge (C1.First, C2.First);
> 
> 
> Same as above. I don't mix herrings and apples,

In fact, herrings with little pieces of apple aren't
that unusual, add onions and mayonnaise and you are
almost set - not everyone's taste, maybe. :-) Seriously,
wouldn't type-forcing containers be in the way of
composition?

How do you make a vector of doughnuts with different
toppings? Something like

 zip(doughnuts.first, toppings.first);

seems reasonable to me.

Re: limited types (Was: Records that could be arrays)

[Matthew Heaney]

Dmitry A. Kazakov wrote:
>
> I don't see how a constraint imposed on elements can propagate to the
> cursor.

generic
  type ET is private;
  type Cursor is private;

  with function E (C : Cursor) return ET is <>;
  ...
procedure Generic_Algorithm (C1, C2 : CT);

Re: limited types (Was: Records that could be arrays)

[Dmitry A. Kazakov]

On Mon, 27 Feb 2006 22:40:18 +0100, Georg Bauhaus wrote:

> Dmitry A. Kazakov wrote:
> 
>> The question Georg asked was: where typed containers of elements of related
>> types might themselves appear related. The number of cases is huge.
>> Generics fundamentally cannot help here, they aren't dynamically
>> polymorphic.
> 
> But then wouldn't you again be mixing apples and herrings?
> 
>   type APPLE_CONTAINER is new CONTAINER with null record;
>     -- specializes in apples, only
> 
>   type HERRING_CONTAINER is new CONTAINER with null record;
>     -- specializes in herrings, only
> 
>   x: access CONTAINER'class := ...;
> 
>   x.insert(an_apple); -- right or wrong? compile time?

You cannot tell without the contract of Container. The above could be
compile error, run-time error or correct.

There are three [all useful] variants:

1. Containers of related types are unrelated
2. Containers of related types are same
3. Containers of subtypes are subtypes (polymorphic containers)

[there is also an axis for the container index/cursor types]

The variants 1 and 2 are relatively easy to get. The variant 3 is much more
challenging.

Consider [imaginary syntax]:

type Food is ...
type Food_Container is ..; -- of Food'Class
type Apple is new Food with ...;
type Herring is new Food with ...;

type Apple_Box is new Food_Container (Element'Tag => Apple'Class);
type Herring_Barrel is new Food_Container (Element'Tag => Herring'Class);

X : Food_Container'Class := Some_Herring_Barrel;
Y : Herring_Barrel := Some_Herring_Barrel;

X.Insert (An_Apple); -- Constraint_Error at run-time
Y.Insert (An_Apple); -- Constraint_Error at run-time + compiler warning

With full ADT one could also do this

   type Apple_Only_Box is new Food_Container some syntax sugar;
private
   type Apple_Only_Box is array (...) of Apple;
      -- The implementation of the container is completely overridden
      -- and replaced by a more efficient

> In fact, herrings with little pieces of apple aren't
> that unusual, add onions and mayonnaise and you are
> almost set -

rather pickled red beets and cucumbers ...

> not everyone's taste, maybe. :-)

Not in a class of apple juice! (:-))

> Seriously,
> wouldn't type-forcing containers be in the way of
> composition?

It will, when that is what's needed. It should be programmer's choice. And
it is much more flexible that the choices we have now: either same type or
different types. Ada was always better than that. Consider Integer and
Positive as an example.

Now what about an array of Integers vs. an array of Positives. Then a slice
of an array of Positives. Presently, constraints cannot propagate between
types. This is a weakness of the type system. You cannot get an array
subtype by constraining its elements. You cannot get an access subtype by
constraining the target type. This is more general and important question
than just container types.

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Re: limited types (Was: Records that could be arrays)

[Dmitry A. Kazakov]

On 27 Feb 2006 15:00:29 -0800, Matthew Heaney wrote:

> Dmitry A. Kazakov wrote:
>>
>> I don't see how a constraint imposed on elements can propagate to the
>> cursor.
> 
> generic
>   type ET is private;
>   type Cursor is private;
> 
>   with function E (C : Cursor) return ET is <>;
>   ...
> procedure Generic_Algorithm (C1, C2 : CT);

Instantiate Generic_Algorithm with some T and CT. Then put a constraint on
T, that will be a subtype S or a derived type. Now how to get CS from CT?

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Re: limited types (Was: Records that could be arrays)

[Matthew Heaney]

Dmitry A. Kazakov wrote:
>
> Instantiate Generic_Algorithm with some T and CT. Then put a constraint on
> T, that will be a subtype S or a derived type. Now how to get CS from CT?

Easy: instantiate Generic_Algorithm again, on type S.

Re: limited types (Was: Records that could be arrays)

[Dmitry A. Kazakov]

On 28 Feb 2006 09:24:35 -0800, Matthew Heaney wrote:

> Dmitry A. Kazakov wrote:
>>
>> Instantiate Generic_Algorithm with some T and CT. Then put a constraint on
>> T, that will be a subtype S or a derived type. Now how to get CS from CT?
> 
> Easy: instantiate Generic_Algorithm again, on type S.

I still don't see CS.

BTW, if I had CS, would need not to instantiate Generic_Algorithm once
more.

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Re: limited types (Was: Records that could be arrays)

[Matthew Heaney]

Dmitry A. Kazakov wrote:
> On 28 Feb 2006 09:24:35 -0800, Matthew Heaney wrote:
>
> I still don't see CS.

I wrote the declaration wrong; it should have been:

generic
  type ET is private;  --or: type ET (<>) is limited private;
  type CT is private;  --cursor type
  with function E (C : CT) return ET is <>;
procedure Generic_Algorithm (C1, C2 : CT);

The cursor pair [C1, C2) describes a range of elements.  It might be
the entire range of elements in the container, or just a subrange.  The
algorithm doesn't care.


> BTW, if I had CS, would need not to instantiate Generic_Algorithm once
> more.

(I assume "CS" means "container of element type S, and S derives from
type T.")

As far as generic algorithms are concerned, it doesn't matter that type
S derives from type T.  That's what "generic algorithm" means.

And yes, you have to instantiate the algorithm twice, since the cursor
types come from different instantiations of some generic container
package.

Of course, if you instantiate the indefinite container package on
generic actual type T'Class, then you'd only have to instantate generic
algorithm once (assuming generic formal type ET is declared
appropriately, as I show above in the comment).

Re: limited types (Was: Records that could be arrays)

[Dmitry A. Kazakov]

On 28 Feb 2006 11:58:11 -0800, Matthew Heaney wrote:

> Dmitry A. Kazakov wrote:
>> On 28 Feb 2006 09:24:35 -0800, Matthew Heaney wrote:
>>
>> I still don't see CS.
> 
> I wrote the declaration wrong; it should have been:
> 
> generic
>   type ET is private;  --or: type ET (<>) is limited private;
>   type CT is private;  --cursor type
>   with function E (C : CT) return ET is <>;
> procedure Generic_Algorithm (C1, C2 : CT);
> 
> The cursor pair [C1, C2) describes a range of elements.  It might be
> the entire range of elements in the container, or just a subrange.  The
> algorithm doesn't care.

But still S <: T does not imply CS <: CT. 

>> BTW, if I had CS, would need not to instantiate Generic_Algorithm once
>> more.
> 
> (I assume "CS" means "container of element type S, and S derives from
> type T.")

Yes and CS should be a subtype of CT, so that CS could be passed as an "in"
where CT is expected. It also could be as an "out", but then with a chance
of Constraint_Error at run-time.

> As far as generic algorithms are concerned, it doesn't matter that type
> S derives from type T.  That's what "generic algorithm" means.

It means "works on a set of types." Generics are only one [weakest] form of
polymorphism.

> And yes, you have to instantiate the algorithm twice, since the cursor
> types come from different instantiations of some generic container
> package.

That is the whole point. BTW, you will need to instantiate it more than
twice for cross combinations, like when C1 is CS and C2 is CT. It
geometrically explodes.

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Re: limited types

[Simon Wright]

"Matthew Heaney" <mheaney@on2.com> writes:

> generic
>   type ET is private;  --or: type ET (<>) is limited private;
>   type CT is private;  --cursor type
>   with function E (C : CT) return ET is <>;
> procedure Generic_Algorithm (C1, C2 : CT);
>
> The cursor pair [C1, C2) describes a range of elements.  It might be
> the entire range of elements in the container, or just a subrange.
> The algorithm doesn't care.

I would have expected some operation like Succ on CT? (and equality?
would predefined equality on cursors be OK?)

Re: limited types

[Matthew Heaney]

Simon Wright <simon@pushface.org> writes:

> I would have expected some operation like Succ on CT? 

Yeah, you're right; I forgot to write an ellipsis.  Each algorithm would have
to pass in the requisite element/cursor operations as generic formals.

For a similar idea, see Ada.Containers.Generic_Anonymous_Array_Sort in the GNAT
distribution.


> (and equality?  would predefined equality on cursors be OK?)

The standard container library guarantees that cursor equality composes, so
predefined equality would work fine.  It wouldn't hurt to pass in a default
equality operator, though.