Is it possible to make a possibly self-referential type using containers?

Is it possible to make a possibly self-referential type using containers?

[Shark8]

Consider something like Forth, IDL, and ASN.1 where there recursion plays a big part in the underlying ideas: the former in its definition of "Word"*, and in the latter two in the defining of types**.

So, given that the most straightforward way to implement these would be in a self-referencing type it would be nice to be able to use containers for this, perhaps like:

Type Executable_Code(<>) is private; -- The type in which we store executable code.
Type Word(<>);

Package Word_List is new Ada.Containers.Indefinite_Vectors
  (Element_Type => Word, Index_Type => Positive);

Type Word( Is_List ) is record
  case Is_List is
    when True  => List : Word_List.Vector;
    when False => Item : Executable_Code;
end record;

The above would be nicely elegant insofar as maintenance goes as it's simple and straightforward. However, we cannot use that because Element_Type cannot be a incomplete-type, but it needs to be because the full type declaration requires the instantiation of the container. -- It also seems that Limited/private with clauses cannot help. 

* Word: a chunk of code to execute or a list of words [to execute].
** Something like SEQUENCE OF INTEGER is fundamental in IDL and ASN.1.

Re: Is it possible to make a possibly self-referential type using containers?

[Randy Brukardt]

You could, of course, create a container using a formal incomplete type 
(which does match incomplete types). The issue(*) is that you'd need to pass 
in a constructor function and a destructor procedure (since you can't 
allocate an object of an incomplete type). That would look something like:

    generic
         type Index_Type is range <>;
         type Element_Type;
         with function "=" (Left, Right : Element_Type)  return Boolean is 
<>;
         with function Copy_Constructor (Obj : Element_Type) return access 
Element_Type;
         with procedure Destructor (Value : access Element_Type);
    package Incomplete_Vectors is
      ....

Then the operations that add elements to the container would use 
Copy_Constructor to allocate a copy, and the clean-up code would use 
Destructor. (It might be better to use a named access for this purpose, the 
problem with that is that you'd have to declare it visible before the 
instance, while that type is really an implementation artifact best kept 
private to this usage.)

                 Randy Brukardt.

(*) It's *almost* possible to create a container of pre-existing objects 
using a formal incomplete type. The problem is that you're not allowed to 
take 'Access of a parameter of such a type (that violates 3.10.1(10/3) - 
even though there's no real problem with that particular operation). I've 
suggested "fixing" this issue in the Ada Standard, but that hasn't gotten 
any traction as most see it as a curiosity rather than the realistic 
technique. If you'd like to see this work, send something to Ada-Comment!


"Shark8" <onewingedshark@gmail.com> wrote in message 
news:18dfc647-ef22-4052-b6ad-ce3516124085@googlegroups.com...
Consider something like Forth, IDL, and ASN.1 where there recursion plays a 
big part in the underlying ideas: the former in its definition of "Word"*, 
and in the latter two in the defining of types**.

So, given that the most straightforward way to implement these would be in a 
self-referencing type it would be nice to be able to use containers for 
this, perhaps like:

Type Executable_Code(<>) is private; -- The type in which we store 
executable code.
Type Word(<>);

Package Word_List is new Ada.Containers.Indefinite_Vectors
  (Element_Type => Word, Index_Type => Positive);

Type Word( Is_List ) is record
  case Is_List is
    when True  => List : Word_List.Vector;
    when False => Item : Executable_Code;
end record;

The above would be nicely elegant insofar as maintenance goes as it's simple 
and straightforward. However, we cannot use that because Element_Type cannot 
be a incomplete-type, but it needs to be because the full type declaration 
requires the instantiation of the container. -- It also seems that 
Limited/private with clauses cannot help.

* Word: a chunk of code to execute or a list of words [to execute].
** Something like SEQUENCE OF INTEGER is fundamental in IDL and ASN.1. 

Re: Is it possible to make a possibly self-referential type using containers?

[Jeffrey R. Carter]

On 07/30/2016 05:31 PM, Shark8 wrote:
> Consider something like Forth, IDL, and ASN.1 where there recursion plays a big part in the underlying ideas: the former in its definition of "Word"*, and in the latter two in the defining of types**.
> 
> So, given that the most straightforward way to implement these would be in a self-referencing type it would be nice to be able to use containers for this, perhaps like:

There was a discussion of this on here about a year ago in the context of having
a private type that is self-referential using a container. See

https://groups.google.com/d/msg/comp.lang.ada/SO9olMGfF4o/aGrCFMsVCwAJ

The advantage of using a container is that one doesn't have to deal with the
error-prone aspects of using access types and doing memory management.

I presented a solution there that used a tagged type, an indefinite container of
the 'Class of that type, and a type extension to achieve this:

with Ada.Containers.Indefinite_Vectors;

package P is
   type T (<>) is private;
private
   type Root is tagged null record;

   package Lists is new Ada.Containers.Vectors
      (Index_Type => Positive, Element_Type => Root'Class);

   type T is new Root with record
      List : Lists.Vector;
   end T;
end P;

The intention here is that only values of type T will be stored in such a
vector, so Root and the type extension for T are noise. You also have to
explicitly convert anything retrieved from the list to type T, which is more
noise. But it beats messing with access values.

-- 
Jeff Carter
"I was either in love, or I had smallpox."
Take the Money and Run
137

Re: Is it possible to make a possibly self-referential type using containers?

[Dmitry A. Kazakov]

On 2016-07-31 02:31, Shark8 wrote:

> Type Executable_Code(<>) is private; -- The type in which we store executable code.
> Type Word(<>);
>
> Package Word_List is new Ada.Containers.Indefinite_Vectors
>   (Element_Type => Word, Index_Type => Positive);
>
> Type Word( Is_List ) is record
>   case Is_List is
>     when True  => List : Word_List.Vector;
>     when False => Item : Executable_Code;
> end record;
>
> The above would be nicely elegant insofar as maintenance goes as
> it's  simple and straightforward.

Nothing elegant in this, but anyway...

> * Word: a chunk of code to execute or a list of words [to execute].
> ** Something like SEQUENCE OF INTEGER is fundamental in IDL and ASN.1.

    type Word is interface;
    type Executable_Code (<>) is new Word with private;
    package Lists is
       new Ada.Containers.Indefinite_Vectors
           (  Index_Type   => Positive,
              Element_Type => Word'Class
           );
    type List is new Lists.Vector and Word with null record;

P.S. Type recursion is inconsistent if not resolved, as in the example 
which splits self-referential Word into Word interface and Word'Class.

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