Composing sequences (interesting to solve)

Composing sequences (interesting to solve)

[Victor Porton]

See an interesting and yet unsolved by me practical task to solve:

I have "elements" of various kinds (Base_Element'Class):

type Base_Element is null record;

There are many various types of element derived from
Base_Element. Some of these contain accesses to other
elements (which I allocate by "new"), so that this forms
trees.

To eliminate access types conversions I decided to limit
myself to use only Base_Element_Access (not accesses to
derived types) (BTW, Is it right design decision?):

type Base_Element_Access is access Base_Element'Class;

One of the types of elements is "sequence" (it is an ordered
container of elements):

type Sequence is new Base_Element with private;

I wish to produce sequences (allocated dynamically) by such
the syntax using overloaded function "&":

E1 & E2 & E3

The question is how to define function "&" so that it would
give the right result (access to one dynamically allocated
sequence) independingly on the number of elements?

Re: Composing sequences (interesting to solve)

[Dmitry A. Kazakov]

Victor Porton wrote:

> See an interesting and yet unsolved by me practical task to solve:
> 
> I have "elements" of various kinds (Base_Element'Class):
> 
> type Base_Element is null record;
> 
> There are many various types of element derived from
> Base_Element. Some of these contain accesses to other
> elements (which I allocate by "new"), so that this forms
> trees.
> 
> To eliminate access types conversions I decided to limit
> myself to use only Base_Element_Access (not accesses to
> derived types) (BTW, Is it right design decision?):
> 
> type Base_Element_Access is access Base_Element'Class;
> 
> One of the types of elements is "sequence" (it is an ordered
> container of elements):
> 
> type Sequence is new Base_Element with private;
> 
> I wish to produce sequences (allocated dynamically) by such
> the syntax using overloaded function "&":
> 
> E1 & E2 & E3
> 
> The question is how to define function "&" so that it would
> give the right result (access to one dynamically allocated
> sequence) independingly on the number of elements?

I think you should clarify whether A & B creates a new object or just binds 
A and B. Why an access type have to be returned? It is a bad style and 
error prone. If you really want heap allocated objects [with reference 
counting and garbage collection], use handles instead of raw pointers. & 
have to be defined on both handles and privately, on the objects. It is a 
bit nasty especially if you want to add some operations to derived 
elements. If so you have two [bad] alternatives:

1. Compile-time checkable. Derive new handle types and define new operations 
on them.

2. Run-time checkable. Define new operations on the handle type and leave 
checks to casting.

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

Re: Composing sequences (interesting to solve)

[Victor Porton]

In article <b06t4c$m4h27$3@id-77047.news.dfncis.de>,
	"Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> writes:
> Victor Porton wrote:
> 
>> See an interesting and yet unsolved by me practical task to solve:
>> 
>> I have "elements" of various kinds (Base_Element'Class):
>> 
>> type Base_Element is null record;
>> 
>> There are many various types of element derived from
>> Base_Element. Some of these contain accesses to other
>> elements (which I allocate by "new"), so that this forms
>> trees.
>> 
>> To eliminate access types conversions I decided to limit
>> myself to use only Base_Element_Access (not accesses to
>> derived types) (BTW, Is it right design decision?):
>> 
>> type Base_Element_Access is access Base_Element'Class;
>> 
>> One of the types of elements is "sequence" (it is an ordered
>> container of elements):
>> 
>> type Sequence is new Base_Element with private;
>> 
>> I wish to produce sequences (allocated dynamically) by such
>> the syntax using overloaded function "&":
>> 
>> E1 & E2 & E3
>> 
>> The question is how to define function "&" so that it would
>> give the right result (access to one dynamically allocated
>> sequence) independingly on the number of elements?
> 
> I think you should clarify whether A & B creates a new object or just binds 
> A and B. Why an access type have to be returned? It is a bad style and 
> error prone. If you really want heap allocated objects [with reference 
> counting and garbage collection], use handles instead of raw pointers. & 
> have to be defined on both handles and privately, on the objects. It is a 
> bit nasty especially if you want to add some operations to derived 
> elements. If so you have two [bad] alternatives:

I don't understand your question, A & B should create (on heap) object of
type Sequence which contains accesses to A.all and B.all . A & B & C 
should create Sequence of three elements etc.

Consider:

type Pair is new Base_Element with
   record
      First, Second: Base_Element_Access;
   end record;
   
The constructor would be just:

function Make_Pair(First, Second: Base_Element_Access)
                  return Base_Element_Access is
begin
   return new Pair'(Base_Element with First=>First, Second=>Second);
end;

But if I use types themselves, I need:

function Make_Pair(First, Second: Base_Element'Class)
                  return Base_Element_Access is
begin
   return new Pair'(Base_Element with
                    First =>new Base_Element'Class'(First),
                    Second=>new Base_Element'Class'(Second));
end;
-- Requires two copying of probably big objects First and Second

In fact I allocate these elements once at program's (or a
subrountine's) lifetime (as these are in fact a part of algorithm,
being something like a programming language interpretor, not just
a typical data) and then are going to deallocate all of them at
once by using scopes, not explicit deallocation. You see that I
don't need reference counting and garbage collection. So I see no
need for handles.

Do you now consider it a good style or have an idea how to make it 
better? Do you still think that introducing handles would be useful?
At least I think that reference counting is a bloating for me.

> 1. Compile-time checkable. Derive new handle types and define new operations 
> on them.
> 
> 2. Run-time checkable. Define new operations on the handle type and leave 
> checks to casting.

The interest case is to make it compile time checkable. (Creating 
runtime check of 'Tag attrs is trivial.)

You haven't given me a solution. (I suspect that it is even impossible 
in Ada9X.)

Re: Composing sequences (interesting to solve)

[Fraser Wilson]

porton@ex-code.com (Victor Porton) writes:

> In article <b06t4c$m4h27$3@id-77047.news.dfncis.de>,> You haven't given me a solution. (I suspect that it is even impossible 
> in Ada9X.)

Presented with

   S & T

where S is a sequence, and T is something else, how can you know
whether the desired result is a new sequence of S and T, or the
sequence S with T tacked onto the end (i.e. an intermediate result
from "P & Q & T")?  Unless you add an extra rule which says that all
sequences get merged (i.e. always choose the second option in this
case), I don't think this is possible.

It's not an Ada thing as such; more of an ambiguity in the problem
definition.

Fraser.

Re: Composing sequences (interesting to solve)

[Dmitry A. Kazakov]

Victor Porton wrote:

> In article <b06t4c$m4h27$3@id-77047.news.dfncis.de>,
> "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> writes:
>> Victor Porton wrote:
>> 
>>> See an interesting and yet unsolved by me practical task to solve:
>>> 
>>> I have "elements" of various kinds (Base_Element'Class):
>>> 
>>> type Base_Element is null record;
>>> 
>>> There are many various types of element derived from
>>> Base_Element. Some of these contain accesses to other
>>> elements (which I allocate by "new"), so that this forms
>>> trees.
>>> 
>>> To eliminate access types conversions I decided to limit
>>> myself to use only Base_Element_Access (not accesses to
>>> derived types) (BTW, Is it right design decision?):
>>> 
>>> type Base_Element_Access is access Base_Element'Class;
>>> 
>>> One of the types of elements is "sequence" (it is an ordered
>>> container of elements):
>>> 
>>> type Sequence is new Base_Element with private;
>>> 
>>> I wish to produce sequences (allocated dynamically) by such
>>> the syntax using overloaded function "&":
>>> 
>>> E1 & E2 & E3
>>> 
>>> The question is how to define function "&" so that it would
>>> give the right result (access to one dynamically allocated
>>> sequence) independingly on the number of elements?
>> 
>> I think you should clarify whether A & B creates a new object or just
>> binds A and B. Why an access type have to be returned? It is a bad style
>> and error prone. If you really want heap allocated objects [with
>> reference counting and garbage collection], use handles instead of raw
>> pointers. & have to be defined on both handles and privately, on the
>> objects. It is a bit nasty especially if you want to add some operations
>> to derived elements. If so you have two [bad] alternatives:
> 
> I don't understand your question, A & B should create (on heap) object of
> type Sequence which contains accesses to A.all and B.all . A & B & C
> should create Sequence of three elements etc.
> 
> Consider:
> 
> type Pair is new Base_Element with
>    record
>       First, Second: Base_Element_Access;
>    end record;
>    
> The constructor would be just:
> 
> function Make_Pair(First, Second: Base_Element_Access)
>                   return Base_Element_Access is
> begin
>    return new Pair'(Base_Element with First=>First, Second=>Second);
> end;
> 
> But if I use types themselves, I need:
> 
> function Make_Pair(First, Second: Base_Element'Class)
>                   return Base_Element_Access is
> begin
>    return new Pair'(Base_Element with
>                     First =>new Base_Element'Class'(First),
>                     Second=>new Base_Element'Class'(Second));
> end;
> -- Requires two copying of probably big objects First and Second

From this code I see that you want to copy objects (i.e. create new ones).
A & B creates a copy of A, a copy of B and an object that points to both. It 
is a questionable design. What if A is A1 & A2? Would you make a deep copy 
of it then?

> In fact I allocate these elements once at program's (or a
> subrountine's) lifetime (as these are in fact a part of algorithm,
> being something like a programming language interpretor, not just
> a typical data) and then are going to deallocate all of them at
> once by using scopes, not explicit deallocation. You see that I
> don't need reference counting and garbage collection. So I see no
> need for handles.

And so you probably need no heap allocation, which is used when automatic 
deallocation is undesirable or when the number and types of the objects are 
unknown. There is an obvious rule about pointers: avoid copying objects if 
you use pointers to them.

> Do you now consider it a good style or have an idea how to make it
> better? Do you still think that introducing handles would be useful?
> At least I think that reference counting is a bloating for me.

I am still unsure what you need. Why Pair has to be in Base_Element'Class? 
It looks like a container. Or is Pair something like a tree node? Why do 
not you declare it as:

type Pair
     (  First  : access Base_Element'Class;
        Second : access Base_Element'Class
     )  is new Base_Element with null record;

I suppose Base_Element is limited. (?)

>> 1. Compile-time checkable. Derive new handle types and define new
>> operations on them.
>> 
>> 2. Run-time checkable. Define new operations on the handle type and leave
>> checks to casting.
> 
> The interest case is to make it compile time checkable. (Creating
> runtime check of 'Tag attrs is trivial.)
> 
> You haven't given me a solution. (I suspect that it is even impossible
> in Ada9X.)

I almost sure that you rather have a case of some well-known problem, which 
definitely can be solved in Ada.

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

Re: Composing sequences (interesting to solve)

[Victor Porton]

In article <u1y3cyyd6.fsf@fwilson.i-did-not-set--mail-host-address--so-shoot-me>,
	Fraser Wilson <newsfraser@blancolioni.org> writes:
> porton@ex-code.com (Victor Porton) writes:
> 
>> In article <b06t4c$m4h27$3@id-77047.news.dfncis.de>,> You haven't given me a solution. (I suspect that it is even impossible 
>> in Ada9X.)
> 
> Presented with
> 
>    S & T
> 
> where S is a sequence, and T is something else, how can you know
> whether the desired result is a new sequence of S and T, or the
> sequence S with T tacked onto the end (i.e. an intermediate result
> from "P & Q & T")?  Unless you add an extra rule which says that all
> sequences get merged (i.e. always choose the second option in this
> case), I don't think this is possible.

I mean to merge all sequences at compile time, but probably not at run 
time. Well, now I'm almost sure that it is impossible in Ada (however 
possible in C++). I'm switching to an another syntax.

Re: Composing sequences (interesting to solve)

[Victor Porton]

In article <b09atk$n7ro0$1@id-77047.news.dfncis.de>,
	"Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> writes:
> Victor Porton wrote:
> 
>> In article <b06t4c$m4h27$3@id-77047.news.dfncis.de>,
>> "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> writes:
>>> Victor Porton wrote:
>>> 
>>>> I have "elements" of various kinds (Base_Element'Class):
>>>> 
>>>> type Base_Element is null record;
>>>> 
>>>> There are many various types of element derived from
>>>> Base_Element. Some of these contain accesses to other
>>>> elements (which I allocate by "new"), so that this forms
>>>> trees.
>>>> 
>>>> To eliminate access types conversions I decided to limit
>>>> myself to use only Base_Element_Access (not accesses to
>>>> derived types) (BTW, Is it right design decision?):
>>>> 
>>>> type Base_Element_Access is access Base_Element'Class;
>>> 
>> Consider:
>> 
>> type Pair is new Base_Element with
>>    record
>>       First, Second: Base_Element_Access;
>>    end record;
>>    
>> The constructor would be just:
>> 
>> function Make_Pair(First, Second: Base_Element_Access)
>>                   return Base_Element_Access is
>> begin
>>    return new Pair'(Base_Element with First=>First, Second=>Second);
>> end;
>> 
>> But if I use types themselves, I need:
>> 
>> function Make_Pair(First, Second: Base_Element'Class)
>>                   return Base_Element_Access is
>> begin
>>    return new Pair'(Base_Element with
>>                     First =>new Base_Element'Class'(First),
>>                     Second=>new Base_Element'Class'(Second));
>> end;
>> -- Requires two copying of probably big objects First and Second
> 
> From this code I see that you want to copy objects (i.e. create new ones).
> A & B creates a copy of A, a copy of B and an object that points to both. It 
> is a questionable design. What if A is A1 & A2? Would you make a deep copy 
> of it then?

Reversely, I want to not copy these as copying would probably slow 
things down. I just shown that if I would not use access types as 
constructor functions arguments I would need to copy the objects.

> And so you probably need no heap allocation, which is used when automatic 
> deallocation is undesirable or when the number and types of the objects are 
> unknown. There is an obvious rule about pointers: avoid copying objects if 
> you use pointers to them.

I want heap allocation by another reasons:

1. Class wide objects cannot be parts of a record. So I need to 
allocate these by "new".

2. I see in Ada no natural and yet efficient syntax for creating trees 
(see below) by constructors with syntax like "A(A(X,Y), B(Z))" without 
using heap allocation.

> I am still unsure what you need. Why Pair has to be in Base_Element'Class? 
> It looks like a container. Or is Pair something like a tree node? Why do 
> not you declare it as:
> 
> type Pair
>      (  First  : access Base_Element'Class;
>         Second : access Base_Element'Class
>      )  is new Base_Element with null record;

Exactly, I construct a tree (or, more generally, it will be probably a 
directed graph). Objects of type Base_Element'Class are tree nodes. 
Pair is a node with two subnodes.

In fact these trees are representation of programs in some programming 
language.

Do I undersood you correctly that you suggest to use access 
discriminants instead of access fields. I see no advantages of 
discriminants over fields in my case.

> I suppose Base_Element is limited. (?)

No, but probably in a future version it will be limited.

> I almost sure that you rather have a case of some well-known problem, which 
> definitely can be solved in Ada.

Let's forgot about of my original problem and discuss constructing and
deallocating trees (or directed graphs) in Ada. Ideologically the best
solution would be to use controlled types with reference counting or
like for full automation, but I want also efficiency.

Re: Composing sequences (interesting to solve)

[Dmitry A. Kazakov]

Victor Porton wrote:

> In article <b09atk$n7ro0$1@id-77047.news.dfncis.de>,
> "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> writes:
>
> Reversely, I want to not copy these as copying would probably slow
> things down. I just shown that if I would not use access types as
> constructor functions arguments I would need to copy the objects.
> 
>> And so you probably need no heap allocation, which is used when automatic
>> deallocation is undesirable or when the number and types of the objects
>> are unknown. There is an obvious rule about pointers: avoid copying
>> objects if you use pointers to them.
> 
> I want heap allocation by another reasons:
> 
> 1. Class wide objects cannot be parts of a record. So I need to
> allocate these by "new".
>
> 2. I see in Ada no natural and yet efficient syntax for creating trees
> (see below) by constructors with syntax like "A(A(X,Y), B(Z))" without
> using heap allocation.

So it is a tree, a binary one.

> Exactly, I construct a tree (or, more generally, it will be probably a
> directed graph). Objects of type Base_Element'Class are tree nodes.
> Pair is a node with two subnodes.
> 
> In fact these trees are representation of programs in some programming
> language.
> 
> Do I undersood you correctly that you suggest to use access
> discriminants instead of access fields. I see no advantages of
> discriminants over fields in my case.

Generally there is only one advantage: you do not have to care if pointer is 
null.

>> I suppose Base_Element is limited. (?)
> 
> No, but probably in a future version it will be limited.
> 
>> I almost sure that you rather have a case of some well-known problem,
>> which definitely can be solved in Ada.
> 
> Let's forgot about of my original problem and discuss constructing and
> deallocating trees (or directed graphs) in Ada. Ideologically the best
> solution would be to use controlled types with reference counting or
> like for full automation, but I want also efficiency.

A simple solution could look like this:

with Ada.Finalization;

package Trees is
   type Node is abstract
      new Ada.Finalization.Limited_Controlled with null record;
   type Node_Ptr is access all Node'Class;
   procedure Delete (N : in out Node_Ptr);

   type Branch (Left, Right : access Node'Class) is
      new Node with null record;
   type Branch_Ptr is access all Branch'Class;
   function "&" (L, R : access Node'Class) return Node_Ptr;
   procedure Finalize (N : in out Branch);

   type Leaf (No : Integer) is new Node with null record;
   type Leaf_Ptr is access all Leaf'Class;
   function New_Leaf (No : Integer) return Node_Ptr;

end Trees;
---------------
with Ada.Unchecked_Deallocation;

package body Trees is
   procedure Free is
      new Ada.Unchecked_Deallocation (Node'Class, Node_Ptr);
   procedure Delete (N : in out Node_Ptr) is
   begin
      Free (N);
   end Delete;

   function "&" (L, R : access Node'Class) return Node_Ptr is
   begin
      return new Branch (L, R);
   end "&";

   procedure Finalize (N : in out Branch) is
      Ptr : Node_Ptr;
   begin
      Ptr := N.Left.all'Unchecked_Access;
      Free (Ptr);
      Ptr := N.Right.all'Unchecked_Access;
      Free (Ptr);
   end Finalize;

   function New_Leaf (No : Integer) return Node_Ptr is
   begin
      return new Leaf (No);
   end New_Leaf;

end Trees;
---------------
with Text_IO;  use Text_IO;
with Trees;    use Trees;

procedure Test_Trees is
   procedure Put (N : Node'Class; I : String := "") is
   begin
      if N in Leaf'Class then
         Put_Line (I & Integer'Image (Leaf'Class (N).No));
      else
         Put (Branch'Class (N).Left.all,  I & "  ");
         Put (Branch'Class (N).Right.all, I & "  ");
      end if;
   end Put;

   A_Tree : Node_Ptr;
begin
   A_Tree := (New_Leaf (1) & New_Leaf (2)) & New_Leaf (3);
   Put (A_Tree.all);
   Delete (A_Tree);
end Test_Trees;
-------------------
As for general problem "efficient graphs", it an endless story. Everything 
depends on which graph operations have to be most efficient. For instance, 
in the project I am working on, the nodes of a fuzzy graph are created and 
deleted more seldom than accessed. Then they are referenced by other 
objects (classifiers, features etc). Then they has to be archived in a data 
base. Then ...

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