Recursive algebraic data types

[hn...@yahoo.de]

Does somebody have a generic package on recursive data types in Ada and is willing to share?

[hn...@yahoo.de]

On Tuesday, March 6, 2018 at 8:47:00 PM UTC+1, hn...@yahoo.de wrote:
> Does somebody have a generic package on recursive data types in Ada and is willing to share?

for definition: please have a look at https://en.wikipedia.org/wiki/Recursive_data_type

[Randy Brukardt]

<hn...@yahoo.de> wrote in message
news:e3aea96c-8c5d-4569...@googlegroups.com...

> Does somebody have a generic package on recursive data types in Ada and is
> willing to share?

A "recursive data type" is illegal in Ada: a type can never depend on
itself, directly or indirectly. You have to break this sort of thing with an
intervening access type, which brings a world of complications in storage
management.

Perhaps you meant something else???

Randy.

[gautier...@hotmail.com]

> for definition: please have a look at https://en.wikipedia.org/wiki/Recursive_data_type

"In computer programming languages, a recursive data type (also known as a recursively-defined, inductively-defined or inductive data type) is a data type for values that may contain other values of the same type."

The definition given above is nonsensical: either the data type is empty or infinitely large...

In the examples given (List), the type names can mean either a pointer to the real data, or the data itself (a list's node in that case). Clearly they are playing with words there: a node doesn't really contain the next node, but a pointer (or a reference) to the next node. So it's not really recursive, only in appearance. They play with a shortcut notation.

[Jeffrey R. Carter]

On 03/06/2018 09:28 PM, Randy Brukardt wrote:
>
> A "recursive data type" is illegal in Ada: a type can never depend on
> itself, directly or indirectly. You have to break this sort of thing with an
> intervening access type, which brings a world of complications in storage
> management.

You have to break it with something, but that doesn't need to be an access type.
Consider S expressions (usually shortened to sexes), which are either an atom or
a list of zero or more sexes:

type Sex (Is_Atom : Boolean := False) is tagged private;
private
type Root is interface;

package Sex_Lists is new
Ada.Containers.Indefinite_Vectors (Positive, Root'Class);

type Sex (Is_Atom : Boolean := False) is new Root with record
case Is_Atom is
when False =>
List : Sex_Lists.Vector;
when True =>
Atom : Atom_Value;
end case;
end record;

The only downside of this is that any element you obtain from S.List has to be
converted to Sex, which is just noise. Better would be if we could instantiate
Indefinite_Vectors with type Sex directly, before it's full definition is seen.

--
Jeff Carter
"He that hath no beard is less than a man."
Much Ado About Nothing
132

[Dmitry A. Kazakov]

On 2018-03-06 21:28, Randy Brukardt wrote:
> <hn...@yahoo.de> wrote in message
> news:e3aea96c-8c5d-4569...@googlegroups.com...
>> Does somebody have a generic package on recursive data types in Ada and is
>> willing to share?
>
> A "recursive data type" is illegal in Ada: a type can never depend on
> itself, directly or indirectly. You have to break this sort of thing with an
> intervening access type,

Right, but it is self-referential nonetheless.

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

[Dmitry A. Kazakov]

On 2018-03-06 20:46, hn...@yahoo.de wrote:
> Does somebody have a generic package on recursive data types in Ada and is willing to share?

That is impossible because generics are instantiated manually, so
recursion cannot be built on instantiation.

Otherwise self-referential types are allowed on generics.

P.S. As it was already said the definition from Wikipedia does not make
sense.

[hn...@yahoo.de]

On Tuesday, March 6, 2018 at 8:47:00 PM UTC+1, hn...@yahoo.de wrote:

> Does somebody have a generic package on recursive data types in Ada and is willing to share?

It is mentioned at several places e.g. in

http://web.mit.edu/6.005/www/fa16/classes/16-recursive-data-types/recursive/

that an implementation exists. Can it be simulated in Ada from Java or Haskell?

[Niklas Holsti]

On 18-03-06 22:45 , gautier...@hotmail.com wrote:
>> for definition: please have a look at
>> https://en.wikipedia.org/wiki/Recursive_data_type
>
> "In computer programming languages, a recursive data type (also known
> as a recursively-defined, inductively-defined or inductive data type)
> is a data type for values that may contain other values of the same
> type."
>
> The definition given above is nonsensical: either the data type is
> empty or infinitely large...

No, the definition makes mathematical sense. Even if the "contained"
values are of the same _type_ as the containing value, they are
different (and "smaller") _values_, so the recursive containment can
terminate.

For example, in mathematics the set of natural numbers, N, is usually
defined in this recursive way:

"zero", 0, is the empty set: {}
"one", 1, is the set that contains zero: {0}
"two", 2, is the set that contains zero and one: {0,1}
and so on.

Inductively, a number n is the set that contains the numbers smaller
than n: {0, 1, ..., n-1}.

> In the examples given (List), the type names can mean either a
> pointer to the real data, or the data itself (a list's node in that
> case). Clearly they are playing with words there: a node doesn't
> really contain the next node, but a pointer (or a reference) to the
> next node. So it's not really recursive, only in appearance. They
> play with a shortcut notation.

They are defining a mathematical (view of a) "type", which can be
implemented in various ways in a programming language. Of course I agree
that implementations normally use pointers, mainly to avoid copying
large values (and to allow values with cycles). In the example, I think
List is simply a "by reference" type, so all "List" variables are pointers.

One can certainly implement this "List" type in Ada, without pointers,
by implementing a List-of-A as the Ada type array (Positive range <>) of
A, where the head element of a list L is L(L'First) and the tail is
L(L'First+1 .. L'Last). Each "cons" operation would of course require
making a copy of the operand list, but that is just implementation detail.

--
Niklas Holsti
Tidorum Ltd
niklas holsti tidorum fi
. @ .

[Jacob Sparre Andersen]

hn...@yahoo.de writes:

> http://web.mit.edu/6.005/www/fa16/classes/16-recursive-data-types/recursive/

Implementing that in Ada isn't too hard. But it is also a part of the
Ada standard library, so why worry about writing it yourself?

See <http://www.ada-auth.org/standards/rm12_w_tc1/html/RM-A-18-3.html>.

Greetings,

Jacob
--
Beware of people with Gnus, they may Hurd you.

[Dmitry A. Kazakov]

On 07/03/2018 06:53, Niklas Holsti wrote:
> On 18-03-06 22:45 , gautier...@hotmail.com wrote:
>>> for definition: please have a look at
>>> https://en.wikipedia.org/wiki/Recursive_data_type
>>
>> "In computer programming languages, a recursive data type (also known
>> as a recursively-defined, inductively-defined or inductive data type)
>> is a data type for values that may contain other values of the same
>> type."
>>
>> The definition given above is nonsensical: either the data type is
>> empty or infinitely large...
>
> No, the definition makes mathematical sense. Even if the "contained"
> values are of the same _type_ as the containing value, they are
> different (and "smaller") _values_, so the recursive containment can
> terminate.

I disagree. The value terminates, the type does not. It is supposed to
be a type algebra, not an algebra of values, e.g. to produce an infinite
set of values as in your example with natural numbers.

A recursive definition of a type could deploy generics when a generic
instance were used in another instance. The progression would stop at
some point. E.g. a multidimensional array defined recursively

generic
N : Natural;
package Generic_Array
type Array_Type is array (Positive range <>)
of Generic_Array (N - 1);
end Generic_Array;

Once instantiated with some N there will be no recursion, because type
algebra is a meta-language to object language of normal types and values.

I would say where it comes to the type algebra, languages like Ada have
much better type operations than recursion: built-in arrays, access
types, class-wide types/inheritance.