Map iteration and modification

[DrPi]

Hi,

I need to delete nodes from a Hashed_Map. I don't know which nodes to
delete in advance. I have to iterate on the Map keys and delete the
nodes which fulfill a condition.
From the LRM I understand I can't delete nodes within a loop iterating
the Map nodes. That makes sense.
What's the recommended way of doing this ?
Iterate the Map and temporarily store the key nodes to be deleted then
delete the nodes from the key list ?

Nicolas

[DrPi]

Post by DrPi
Iterate the Map and temporarily store the key nodes to be deleted then
delete the nodes from the key list ?

Not clear. Rephrasing it.
Using 2 steps by iterating the Map and temporarily store the keys of
nodes to be deleted then delete the Map nodes using the key list ?

[Dmitry A. Kazakov]

Post by DrPi

Post by DrPi
Iterate the Map and temporarily store the key nodes to be deleted then
delete the nodes from the key list ?

Not clear. Rephrasing it.
Using 2 steps by iterating the Map and temporarily store the keys of
nodes to be deleted then delete the Map nodes using the key list ?

[Disclaimer. I am not talking about the standard library]

Provided a sane implementation of map.

1. It is safe to loop over the map items in the *reverse* order of,
deleting whatever items.

2. It is safe to walk whatever set of map keys, deleting items of the map.

In both cases #1 positions, #2 keys are invariant to the operation of
deletion.

[DrPi]

Post by Dmitry A. Kazakov

Post by DrPi

Post by DrPi
Iterate the Map and temporarily store the key nodes to be deleted
then delete the nodes from the key list ?

Not clear. Rephrasing it.
Using 2 steps by iterating the Map and temporarily store the keys of
nodes to be deleted then delete the Map nodes using the key list ?

[Disclaimer. I am not talking about the standard library]

I'm using the standard library ;)

Post by Dmitry A. Kazakov
Provided a sane implementation of map.
1. It is safe to loop over the map items in the *reverse* order of,
deleting whatever items.
2. It is safe to walk whatever set of map keys, deleting items of the map.
In both cases #1 positions, #2 keys are invariant to the operation of
deletion.

[Randy Brukardt]

"Dmitry A. Kazakov" <***@dmitry-kazakov.de> wrote in message news:umk6ds$e9hc$***@dont-email.me...
...

Post by Dmitry A. Kazakov
Provided a sane implementation of map.
1. It is safe to loop over the map items in the *reverse* order of,
deleting whatever items.

A sane implementation of a map does not have/require an ordering of keys. So
the idea of "reverse" or "forward" does not make sense for a general map.
(There are, of course, special cases where the keys have an order that
matters to the map; the standard ordered map is like that.) Assuming an
ordering is exposing the implementation unnecessarily.

You always complain about mixing implementation with interface, but you are
clearly doing that here. That technique really only works if the data
structure is implemented with an underlying array. If you have separately
allocated nodes, deletion might completely destroy a node that the iterator
is holding onto. Avoiding that takes significant efforts that sap
performance when you don't intend to modify the container you're iterating
(which is the usual case).

My longstanding objection to the entire concept of arrays is that they are
not a data structure, but rather a building block for making data
structures. One wants indexed sequences sometimes, cheap maps othertimes,
but arrays have all of the operations needed for both, along with other
capabilities not really related to data structures at all. It's way better
to declare what you need and get no more (visibly, at least). That makes it
way easier to swap implementations if that becomes necessary - you're not
stuck with a large array that really should be managed piecemeal.

Randy.

[Dmitry A. Kazakov]

Post by Randy Brukardt
...

Post by Dmitry A. Kazakov
Provided a sane implementation of map.
1. It is safe to loop over the map items in the *reverse* order of,
deleting whatever items.

A sane implementation of a map does not have/require an ordering of keys.

Yes, but iterating a map requires ordering regardless properties of the
keys.

Post by Randy Brukardt
So
the idea of "reverse" or "forward" does not make sense for a general map.
(There are, of course, special cases where the keys have an order that
matters to the map; the standard ordered map is like that.) Assuming an
ordering is exposing the implementation unnecessarily.

It always does sense *IF* enumeration (needed for iteration) is
provided. Enumeration of pairs (<key>, <value>) is not same as ordering
values by the keys.

Post by Randy Brukardt
You always complain about mixing implementation with interface, but you are
clearly doing that here. That technique really only works if the data
structure is implemented with an underlying array. If you have separately
allocated nodes, deletion might completely destroy a node that the iterator
is holding onto. Avoiding that takes significant efforts that sap
performance when you don't intend to modify the container you're iterating
(which is the usual case).

No. First, it is two different interfaces. A view of a map as:

1. An ordered set of pairs (<key>, <value>)

2. A mapping <key> -> <value>

Second, the point is that both are array interfaces. The first has
position as the index, the second has the key as the index.

Both are invariant to removal a pair and any *sane* implementation must
be OK with that.

The problem is not whether you allocate pairs individually or not. The
insanity begins with things unrelated to the map:

1. OOP iterator object.

2. FP iteration function.

Both are bad ideas imposed by poor programming paradigms on
implementation of a clear mathematical concept. That comes with
constraints, assumptions and limitation array interface do not have.

for Index in reverse Map'Range loop
Map.Delete (Index);
end loop;

would always work. OOP/FP anti-patterns, who knows?

Post by Randy Brukardt
My longstanding objection to the entire concept of arrays is that they are
not a data structure, but rather a building block for making data
structures.

Arrays have interface and implementation. The array interface is a
mapping key -> value, the most fundamental thing in programming. An
array implementation as a contiguous block of values indexed by a linear
function is a basic data structure that supports the interface.

Post by Randy Brukardt
One wants indexed sequences sometimes, cheap maps othertimes,
but arrays have all of the operations needed for both, along with other
capabilities not really related to data structures at all.

Let me help (:-))

One wants array interface without a built-in array implementation.

Post by Randy Brukardt
It's way better
to declare what you need and get no more (visibly, at least). That makes it
way easier to swap implementations if that becomes necessary - you're not
stuck with a large array that really should be managed piecemeal.

Sure. The problem with Ada is that it does not separate array interface
from its built-in array implementation and does not separate record
interface and implementation either.

Both are mappings. BTW in many cases people could prefer record
interface of a map to array interface:

Map.Key

instead of

Map (Key)

Now, tell me that you have a longstanding objection to the entire
concept of records... (:-))

[G.B.]

Post by Randy Brukardt
...

Post by Dmitry A. Kazakov
Provided a sane implementation of map.
1. It is safe to loop over the map items in the *reverse* order of,
deleting whatever items.

A sane implementation of a map does not have/require an ordering of keys.

Yes, but iterating a map requires ordering regardless properties of the keys.

Suppose that there is a way of orderly proceeding from one item to the next.
It is probably known to the implementation of map. Do single steps
guarantee transitivity, though, so that an algorithm can assume the
order to be invariable?

At the start of the algorithm, the assumption of order of items implies
an ordered sequence of all the keys. Someone might want to use this known
order for a cache of "index values". It might be the implementation
that does so.

Now some item is removed. The cache is no longer valid...

Insane? Or just tampering? (Randy Brukardt's example demonstrates
the mitigation using Cursor, I think.)


Maybe the bulk operations of some DBMS' programming
interfaces work just like this, for practical reasons.
Ada 202x' Ordered_Maps might want to add a feature ;-)

procedure Delete (Container : in out Map;
From : in out Cursor;
To : in out Cursor);

[Dmitry A. Kazakov]

Post by G.B.

Post by Randy Brukardt
...

Post by Dmitry A. Kazakov
Provided a sane implementation of map.
1. It is safe to loop over the map items in the *reverse* order of,
deleting whatever items.

A sane implementation of a map does not have/require an ordering of keys.

Yes, but iterating a map requires ordering regardless properties of the keys.

Suppose that there is a way of orderly proceeding from one item to the next.
It is probably known to the implementation of map. Do single steps
guarantee transitivity, though, so that an algorithm can assume the
order to be invariable?

An insane implementation can expose random orders each time.

Post by G.B.
At the start of the algorithm, the assumption of order of items implies
an ordered sequence of all the keys.

You do not need ordered keys to enumerate pairs. For example, consider a
2D array. As a map it has keys (row, column) which are unordered.

Post by G.B.
Someone might want to use this known
order for a cache of "index values". It might be the implementation
that does so.

If not exposed through an interface the order cannot be known. The
question is whether there must be such interface or not. In my view a
good container library must provide position->pair interface, no OOP's
cursors/iterators and no functional stuff like Foreach.

Post by G.B.
Insane? Or just tampering? (Randy Brukardt's example demonstrates
the mitigation using Cursor, I think.)

Unless removing element invalidates all cursors. Look, insanity has no
bounds. Cursors AKA pointers are as volatile as positions in certain
implementations. Consider a garbage collector running after removing a
pair and shuffling remaining pairs in memory.

Post by G.B.
Maybe the bulk operations of some DBMS' programming
interfaces work just like this, for practical reasons.
Ada 202x' Ordered_Maps might want to add a feature ;-)
     procedure Delete (Container : in out Map;
                       From      : in out Cursor;
                       To        : in out Cursor);

Here you assume that cursors are ordered and the order is preserved from
call to call. Even if From and To are stable the range From..To can
include random pairs in between.

[G.B.]

Post by Dmitry A. Kazakov

Post by G.B.
Suppose that there is a way of orderly proceeding from one item to the next.
It is probably known to the implementation of map. Do single steps
guarantee transitivity, though, so that an algorithm can assume the
order to be invariable?

An insane implementation can expose random orders each time.

An implementation order should then not be exposed, right?
What portable benefits would there be when another interface
is added to that of map, i.e., to Ada containers for general use?
Would it not be possible to get these benefits using a different
approach? I think the use case is clearly stated:

First, find Cursors in map =: C*.
Right after that, Delete from map all nodes referred to by C*.

Post by Dmitry A. Kazakov
Unless removing element invalidates all cursors. Look, insanity has no bounds. Cursors AKA pointers are as volatile as positions in certain implementations. Consider a garbage collector running after removing a pair and shuffling remaining pairs in memory.

Post by G.B.
Maybe the bulk operations of some DBMS' programming
interfaces work just like this, for practical reasons.
Ada 202x' Ordered_Maps might want to add a feature ;-)
      procedure Delete (Container : in out Map;
                        From      : in out Cursor;
                        To        : in out Cursor);

Here you assume that cursors are ordered and the order is preserved from call to call. Even if From and To are stable the range From..To can include random pairs in between.

Yes, given the descriptions of Ordered_Maps, so long as there is no
tampering, a Cursor will respect an order. Likely the one that the
programmer has in mind.

For deleting, this thread has shown a loop that calls Delete
multiple times right after collecting the cursors.
And it is boilerplate text. Could Maps be improved for this use case?

[Bulk deletion] We do get bulk insertion in containers. Also,
A.18.2 already has bulk Delete operations. Similarly,
the Strings packages have them.

[No thread safety needed] If standard Ada maps are usually operated
by just one task, stability of Cursors is predictable.

Then, with or without automatic management of storage,
when My_Map is from an instance of Ordered_Map,

Start := In_13th_Floor (My_Map.Ceiling (13.0));
Finish := In_13th_Floor (My_Map.Floor (Fxd'Pred (14.0)));
My_Map.Delete (
From => Start,
Through => Finish);

where
function In_13th_Floor (C : Cursor) return Cursor
-- C, if the key at C is in [13.0, 14.0), No_Element otherwise

should therefore do the right thing, in that nothing
is left to chance.

[Dmitry A. Kazakov]

Post by G.B.

Post by Dmitry A. Kazakov

Post by G.B.
Suppose that there is a way of orderly proceeding from one item to the next.
It is probably known to the implementation of map. Do single steps
guarantee transitivity, though, so that an algorithm can assume the
order to be invariable?

An insane implementation can expose random orders each time.

An implementation order should then not be exposed, right?

IMO, an order should be exposed. Not necessarily the "implementation
order" whatever that might mean.

Post by G.B.
What portable benefits would there be when another interface
is added to that of map, i.e., to Ada containers for general use?

It is same benefit Ada arrays have over C's T* pointers and arithmetic
of. Cursor is merely a fat pointer.

Post by G.B.
Would it not be possible to get these benefits using a different
First, find Cursors in map =: C*.
Right after that, Delete from map all nodes referred to by C*.

Right. Find cursors, store cursors in another container, iterate that
container deleting elements of the first. Now, consider that the cursors
in the second container become invalid (dangling pointers). If you
wanted to delete them immediately from the second container, you would
return the square one! (:-))

With a positional access interface it would be just (pure Ada 95):

for Index in reverse 1..Number_Of_Elements (Container) loop
if Want_To_Delete (Get (Container (Index))) then
Delete (Container, Index);
end if;
end loop;

Post by G.B.
For deleting, this thread has shown a loop that calls Delete
multiple times right after collecting the cursors.
And it is boilerplate text.  Could Maps be improved for this use case?

See above.

Post by G.B.
[Bulk deletion] We do get bulk insertion in containers.  Also,
A.18.2 already has bulk Delete operations.  Similarly,
the Strings packages have them.
[No thread safety needed] If standard Ada maps are usually operated
by just one task, stability of Cursors is predictable.
Then, with or without automatic management of storage,
when My_Map is from an instance of Ordered_Map,
   Start  := In_13th_Floor (My_Map.Ceiling (13.0));
   Finish := In_13th_Floor (My_Map.Floor (Fxd'Pred (14.0)));
   My_Map.Delete (
      From    => Start,
      Through => Finish);

The case is more general: delete pairs satisfying certain criterion.

[G.B.]

Post by G.B.
Would it not be possible to get these benefits using a different
First, find Cursors in map =: C*.
Right after that, Delete from map all nodes referred to by C*.

Right. Find cursors, store cursors in another container, iterate that container deleting elements of the first. Now, consider that the cursors in the second container become invalid (dangling pointers). If you wanted to delete them immediately from the second container, you would return the square one! (:-))

OK, yet if indicating nodes in a container is designed to survive
any deletions, leaving nothing dangling i.e., doesn't this limit
the way in which implementations can store nodes?
Seems like every "pointer" (= (Container, Position)) needs to know
its element, and/or the container will have to equip its storage
management with a "vacuuming" algorithm accordingly.

Transactions seem more flexible (a locking flag in a sequential
algorithm?), a dedicated operation looks simpler than both.

[Dmitry A. Kazakov]

Post by G.B.

Post by Dmitry A. Kazakov

Post by G.B.
Would it not be possible to get these benefits using a different
First, find Cursors in map =: C*.
Right after that, Delete from map all nodes referred to by C*.

Right. Find cursors, store cursors in another container, iterate that
container deleting elements of the first. Now, consider that the
cursors in the second container become invalid (dangling pointers). If
you wanted to delete them immediately from the second container, you
would return the square one! (:-))

OK, yet if indicating nodes in a container is designed to survive
any deletions, leaving nothing dangling i.e., doesn't this limit
the way in which implementations can store nodes?

Unless the container keeps references to all pointers and corrects them
as necessary. Which basically defeats the only advantage of pointers.
They have O(1) complexity in large non-contiguous containers while
positions without caching are likely O(log(n)).

Post by G.B.
Seems like every "pointer" (= (Container, Position)) needs to know
its element, and/or the container will have to equip its storage
management with a "vacuuming" algorithm accordingly.
Transactions seem more flexible (a locking flag in a sequential
algorithm?), a dedicated operation looks simpler than both.

For large and persistent containers. But that requires a lot of work for
the client and it is slow and resource consuming on the container side.
A general-purpose container must be as simple as tooth powder.

[Randy Brukardt]

"Dmitry A. Kazakov" <***@dmitry-kazakov.de> wrote in message news:umv8rg$2b4on$***@dont-email.me...
...

It is same benefit Ada arrays have over C's T* pointers and arithmetic of.
Cursor is merely a fat pointer.

A cursor is an abstract reference. It *might* be implemented with a pointer
or with an array index. Indeed, the bounded containers pretty much have to
be implemented with an underlying array.

It would be nice if there was some terminology for abstract references that
hadn't been stolen by some programming language. Terms like "pointer" and
"access" and "reference" all imply an implementation strategy. That's not
relevant most of the time, and many programming language design mistakes
follow from that. (Anonymous access types come to mind).

Randy.

[moi]

Post by Randy Brukardt
...

It is same benefit Ada arrays have over C's T* pointers and arithmetic of.
Cursor is merely a fat pointer.

A cursor is an abstract reference. It *might* be implemented with a pointer
or with an array index. Indeed, the bounded containers pretty much have to
be implemented with an underlying array.
It would be nice if there was some terminology for abstract references that
hadn't been stolen by some programming language. Terms like "pointer" and
"access" and "reference" all imply an implementation strategy. That's not
relevant most of the time, and many programming language design mistakes
follow from that. (Anonymous access types come to mind).

What about "currency", as used in DB systems?

[Randy Brukardt]

Post by Dmitry A. Kazakov

Post by Randy Brukardt
...

Post by Dmitry A. Kazakov
Provided a sane implementation of map.
1. It is safe to loop over the map items in the *reverse* order of,
deleting whatever items.

A sane implementation of a map does not have/require an ordering of keys.

Yes, but iterating a map requires ordering regardless properties of the
keys.

Only as far as there is an order implied by the order that things are
returned. That order doesn't have any meaning, and certainly there isn't any
such thing as "forward" or "reverse" to it. (Which was the original claim,
after all.) There is no "natural" order to the key/element pairs; they are
effectively unordered.

...

Post by Dmitry A. Kazakov

Post by Randy Brukardt
So
the idea of "reverse" or "forward" does not make sense for a general map.
(There are, of course, special cases where the keys have an order that
matters to the map; the standard ordered map is like that.) Assuming an
ordering is exposing the implementation unnecessarily.

It always does sense *IF* enumeration (needed for iteration) is provided.
Enumeration of pairs (<key>, <value>) is not same as ordering values by
the keys.

True, but it doesn't imply any particular ordering. Certainly, no concept of
"forward" or "reverse" applies to such an ordering (nor any stability
requirement). Practically, you'll get the same order each time if the
container isn't modified, but if it is, all bets are off. (If the container
is changed by element addition or deletion, the index may get rebuilt [hash
table reconstructed if too full, tree-index rebalanced, etc.] and that can
change the iteration order dramatically.)

...

Post by Dmitry A. Kazakov
1. An ordered set of pairs (<key>, <value>)

This is not a map (in general). There is an *unordered* set of pairs. You
can retrieve them all, but the order that is done is meaningless and is an
artifact of the implementation. There's a reason that maps don't have
reverse iterators.

Post by Dmitry A. Kazakov
2. A mapping <key> -> <value>
Second, the point is that both are array interfaces. The first has
position as the index, the second has the key as the index.

"Position" is not a property of an (abstract) map. That's my complaint about
looking at everything as an array -- one starts thinking in terms of
properties that things don't have (or need).

Post by Dmitry A. Kazakov
Both are invariant to removal a pair and any *sane* implementation must be
OK with that.

The only sort of position that you could possibility talk about for a map is
the ordinal order that an iterator returns key/element pairs. But that
necessarily changes when you insert/delete a pair, as that pair will occur
at some (unspecified) point in the ordinal order. Otherwise, you won't have
the performance expected for key lookup in a map.

Post by Dmitry A. Kazakov
The problem is not whether you allocate pairs individually or not. The
1. OOP iterator object.
2. FP iteration function.
Both are bad ideas imposed by poor programming paradigms on implementation
of a clear mathematical concept. That comes with constraints, assumptions
and limitation array interface do not have.

??? Abstractions are "poor ideas"? You have some problem with an iterator
interface as opposed to an array interface?? That make no sense at all given
your other positions.

Post by Dmitry A. Kazakov
for Index in reverse Map'Range loop
Map.Delete (Index);
end loop;
would always work.

It only works if you think of Map'Range as an iterator object. Otherwise,
you would have to impose an extra "position" interface on the map (or other
container), and at a substantial additional cost in time/space. Containers
in general don't have "positions", elements are unordered unless the
container imposes one.



...

Post by Dmitry A. Kazakov
Arrays have interface and implementation. The array interface is a mapping
key -> value, the most fundamental thing in programming.

That's only part of it. It also includes the idea of "position", including
calculated positions, the operations of concatenation and slicing, and (for
Ada at least) ordering operations. If the array interface was *only* a
mapping I would not object to it. Maps do not have a natural order, and
nothing should be depending on such order. There is no meaning to the third
pair in a map.

Post by Dmitry A. Kazakov
An array implementation as a contiguous block of values indexed by a
linear function is a basic data structure that supports the interface.

Right: the much more complex interface I note above. And that's the problem.
You don't even seem to realize all of the unnecessary baggage that arrays
carry with them.

...

Post by Dmitry A. Kazakov
Sure. The problem with Ada is that it does not separate array interface
from its built-in array implementation and does not separate record
interface and implementation either.

Not arguing this. (Other than this is way down the list of problems with
Ada, there are many that are worse.)

...

Post by Dmitry A. Kazakov
Now, tell me that you have a longstanding objection to the entire concept
of records... (:-))

Nope. There has to be a hetrogenous grouping of values, and records do it as
well as anything else. I do agree that more abstraction would be nice.

The problem with arrays is that the mapping part is tied to many other
supposedly fundamental capabilities that aren't fundamental at all. Even
intellegent people such as yourself have been using arrays so long and so
primitively that you've gotten blinded to the fact that basic data
structures really have only a handful of operations, and the majority of the
"fundamental" capabilities aren't needed much of the time and certainly
should only be provided when needed.

Randy.

[Dmitry A. Kazakov]

Post by Randy Brukardt

Post by Dmitry A. Kazakov

Post by Randy Brukardt
...

Post by Dmitry A. Kazakov
Provided a sane implementation of map.
1. It is safe to loop over the map items in the *reverse* order of,
deleting whatever items.

A sane implementation of a map does not have/require an ordering of keys.

Yes, but iterating a map requires ordering regardless properties of the
keys.

Only as far as there is an order implied by the order that things are
returned. That order doesn't have any meaning, and certainly there isn't any
such thing as "forward" or "reverse" to it. (Which was the original claim,
after all.) There is no "natural" order to the key/element pairs; they are
effectively unordered.

Iteration = order. It is the same thing. If you provide iteration of
pairs in the mapping by doing so you provide an order of.

Post by Randy Brukardt

Post by Dmitry A. Kazakov
It always does sense *IF* enumeration (needed for iteration) is provided.
Enumeration of pairs (<key>, <value>) is not same as ordering values by
the keys.

True, but it doesn't imply any particular ordering. Certainly, no concept of
"forward" or "reverse" applies to such an ordering (nor any stability
requirement).

It does. You have a strict total order of pairs which guarantees
existence of previous and next pairs according to.

Post by Randy Brukardt
Practically, you'll get the same order each time if the
container isn't modified, but if it is, all bets are off. (If the container
is changed by element addition or deletion, the index may get rebuilt [hash
table reconstructed if too full, tree-index rebalanced, etc.] and that can
change the iteration order dramatically.)

True, an operation may invalidate whatever invariants. It applies
equally to any orders, any cursors and pointers, any hidden states of
pending foreach operations. Sanity means which invariants the
implementation keeps.

I would argue that for general-case containers keeping
iterators/pointers and hidden states would be far more difficult than
keeping an order.

Post by Randy Brukardt

Post by Dmitry A. Kazakov
1. An ordered set of pairs (<key>, <value>)

This is not a map (in general). There is an *unordered* set of pairs. You
can retrieve them all, but the order that is done is meaningless and is an
artifact of the implementation. There's a reason that maps don't have
reverse iterators.

Unless you provide iteration of the map. Most applications want
iteratable maps. Then a finite maps is still iteratable regardless best
efforts, though by crude means. E.g. once have an array (ordered set) of
keys, you are done.

Post by Randy Brukardt

Post by Dmitry A. Kazakov
2. A mapping <key> -> <value>
Second, the point is that both are array interfaces. The first has
position as the index, the second has the key as the index.

"Position" is not a property of an (abstract) map. That's my complaint about
looking at everything as an array -- one starts thinking in terms of
properties that things don't have (or need).

Yes position is a property of enumeration.

Post by Randy Brukardt

Post by Dmitry A. Kazakov
Both are invariant to removal a pair and any *sane* implementation must be
OK with that.

The only sort of position that you could possibility talk about for a map is
the ordinal order that an iterator returns key/element pairs.

It is the reverse. Iterators is secondary to the order. Iterator walks
pairs in the order of pairs = in the order their positions.

Post by Randy Brukardt
But that
necessarily changes when you insert/delete a pair, as that pair will occur
at some (unspecified) point in the ordinal order. Otherwise, you won't have
the performance expected for key lookup in a map.

If you provide a random order, then yes. This is what an "insane"
implementation would do. A "sane" implementation would deploy orders
with reasonable properties. E.g. an obvious: k1/=k2/=k3 then (k1,v1) <
(k2,v2) is preserved when (k3,v3) is added or removed.

Post by Randy Brukardt

Post by Dmitry A. Kazakov
The problem is not whether you allocate pairs individually or not. The
1. OOP iterator object.
2. FP iteration function.
Both are bad ideas imposed by poor programming paradigms on implementation
of a clear mathematical concept. That comes with constraints, assumptions
and limitation array interface do not have.

??? Abstractions are "poor ideas"?

Neither is an abstraction [as they are not entities of the problem
space, but programming techniques artifacts, [anti-]patterns]. Iterator
is an object of an unrelated type. Foreach is a stateful operation
unrelated to the pure map interface.

Post by Randy Brukardt
You have some problem with an iterator
interface as opposed to an array interface??

Yes, I am against pointers (referential semantics) in general. BTW, Ada
should have abstract pointer interface allowing the programmer to
implement iterators = fat pointers.

[ It would be fun with the pure unordered maps you suggested, the
implementation of the pointer (iterator) would keep an array or an
ordered set of keys... (:-)) ]

Post by Randy Brukardt

Post by Dmitry A. Kazakov
for Index in reverse Map'Range loop
Map.Delete (Index);
end loop;
would always work.

It only works if you think of Map'Range as an iterator object. Otherwise,
you would have to impose an extra "position" interface on the map (or other
container), and at a substantial additional cost in time/space. Containers
in general don't have "positions", elements are unordered unless the
container imposes one.

Yes, I would impose positions in all general case containers.

Specialized very large containers where an implementation without
cashing would become O(log n) rather than O(1) deploy other means of
traversal anyway.

Post by Randy Brukardt

Post by Dmitry A. Kazakov
Arrays have interface and implementation. The array interface is a mapping
key -> value, the most fundamental thing in programming.

That's only part of it. It also includes the idea of "position",

Yes. Position in array is a mapping key/index <-> Natural.

Post by Randy Brukardt
including calculated positions,

Yes. Natural numbers have numeric operations.

Post by Randy Brukardt
the operations of concatenation and slicing,

That depends, but like with maps, it is expected. Maps as containers are
expected to provide "concatenations" of pairs (set-theoretic union) and
slicing (submaps). Because mathematically maps are sets of pairs and
sets can be manipulated in many ways. Ordering does not add much to the
interface.

Post by Randy Brukardt
and (for
Ada at least) ordering operations. If the array interface was *only* a
mapping I would not object to it. Maps do not have a natural order, and
nothing should be depending on such order. There is no meaning to the third
pair in a map.

Yes, but those are not iteratable. We are talking about maps one can
iterate. That requires an order. The question is only about the forms of
exposure of that order in the interface. My objection is that iterators
and foreach are poor forms.

Post by Randy Brukardt

Post by Dmitry A. Kazakov
An array implementation as a contiguous block of values indexed by a
linear function is a basic data structure that supports the interface.

Right: the much more complex interface I note above. And that's the problem.
You don't even seem to realize all of the unnecessary baggage that arrays
carry with them.

I don't see anything that is not already there. What are reasons for not
providing:

M (n) [ e.g. M (n).Key, M (n).Value ]
M (n1..n2) [ in mutable contexts too ]
M'First
M'Last
M1 & M2 [ M1 or M2 ]

They are all well-defined and useful operations.

Post by Randy Brukardt
The problem with arrays is that the mapping part is tied to many other
supposedly fundamental capabilities that aren't fundamental at all.

I disagree in the case of 1D arrays. There is of course interesting
issues with nD arrays but that is where multiple inheritance kicks in,
because in mathematics you can have "continuations" of concepts in more
than one direction. So 1D array might be both an nD array and something
else too.

Post by Randy Brukardt
Even
intellegent people such as yourself have been using arrays so long and so
primitively that you've gotten blinded to the fact that basic data
structures really have only a handful of operations, and the majority of the
"fundamental" capabilities aren't needed much of the time and certainly
should only be provided when needed.

That is true. But again, it is solved by inheritance already. You can
have an unordered map interface separately inherited by a general-case
map. You can split interfaces to refine what operations they include
from the implementation constraints point of view. So you can have a
very flexible mesh of implementations sharing some interfaces, but not
others. The best example is, of course, various types strings.

[Randy Brukardt]

"Dmitry A. Kazakov" <***@dmitry-kazakov.de> wrote in message news:umotm2$18lqm$***@dont-email.me...
...

Post by Randy Brukardt
Only as far as there is an order implied by the order that things are
returned. That order doesn't have any meaning, and certainly there isn't any
such thing as "forward" or "reverse" to it. (Which was the original claim,
after all.) There is no "natural" order to the key/element pairs; they are
effectively unordered.

Iteration = order. It is the same thing. If you provide iteration of pairs
in the mapping by doing so you provide an order of.

Certainly not. An iteration presents all of the elements in a container, but
there is no requirement that there is an order. Indeed, logically, all of
the elements are presented at the same time (and parallel iteration provides
an approximation of that).

If you try to enforce an order on things that don't require it, you end up
preventing useful parallelism (practically, at least, no one has succeeded
at providing useful parallelism to sequential code and people have been
trying for about 50 years -- they were trying when I was a university
student in the late 1970s).

Post by Randy Brukardt

Post by Dmitry A. Kazakov
It always does sense *IF* enumeration (needed for iteration) is provided.
Enumeration of pairs (<key>, <value>) is not same as ordering values by
the keys.

True, but it doesn't imply any particular ordering. Certainly, no concept of
"forward" or "reverse" applies to such an ordering (nor any stability
requirement).

It does. You have a strict total order of pairs which guarantees existence
of previous and next pairs according to.

Again, this is unrelated. Iteration can usefully occur in unordered
containers (that is, "foreach"). Ordering is a separate concept, not always
needed (certainly not in basic structures like maps, sets, and bags).

...

True, an operation may invalidate whatever invariants. It applies equally
to any orders, any cursors and pointers, any hidden states of pending
foreach operations. Sanity means which invariants the implementation
keeps.

Ada requires that cursors continue to designate the same element through all
operations other than deletion of the element or movement to a different
container. Specific containers have additional invariants, but this is the
most general one. No other requirement is needed in many cases.

...

Post by Randy Brukardt
"Position" is not a property of an (abstract) map. That's my complaint about
looking at everything as an array -- one starts thinking in terms of
properties that things don't have (or need).

Yes position is a property of enumeration.

Surely not. This is a basis for my disagrement with you here. The only
requirement for enumeration is that all elements are produced. The order is
an artifact of doing it an inherently parallel operation sequentally. We
don't care about or depend on artifacts.

...

It is the reverse. Iterators is secondary to the order. Iterator walks
pairs in the order of pairs = in the order their positions.

Nope, this is completely wrong. Once you start with a bogus premise, of
course you will get all kinds of bogus conclusions!!

...

Post by Randy Brukardt
You have some problem with an iterator
interface as opposed to an array interface??

Yes, I am against pointers (referential semantics) in general.

This is nonsense - virtually everything is referential semantics (other than
components). Array indexes are just a poor mans pointer (indeed, I learned
how to program in Fortran 66 initially, and way one built useful data
structures was to use array indexes as stand-ins for pointers). In A(1), 1
is a reference to the first component of A.

So long as you are using arrays, you are using referential semantics. The
only way to avoid it is to directly embed an object directly in an enclosing
object (as in a record), and that doesn't work for many problems.

...

I don't see anything that is not already there. What are reasons for not
M (n) [ e.g. M (n).Key, M (n).Value ]
M (n1..n2) [ in mutable contexts too ]
M'First
M'Last
M1 & M2 [ M1 or M2 ]
They are all well-defined and useful operations.

Performance. If all of these things are user-definable, then one has to use
subprogram calls to implement all of them. That can be very expensive,
particularly in the case of mutable operations (and mutable slices are the
worst of all). Moreover, since one would want the ability to have generic
and runtime parameters that only meet this interface (and the ability to
pass slices to subprograms that take unconstrained array parameters), you
would have to be able to pass all of these subprograms along with
parameters, even when you don't need them. That would make array operations
far more expensive than they are today.

I think it is much better to get rid of most of these operations as built-in
things and just let the programmer build their own operations as needed.
That keeps the cost confined to those who use them. Distributed overhead is
the worst kind, and slices in particular have a boatload of that overhead.

Randy.

[Dmitry A. Kazakov]

Post by Randy Brukardt
...

Post by Randy Brukardt
Only as far as there is an order implied by the order that things are
returned. That order doesn't have any meaning, and certainly there isn't any
such thing as "forward" or "reverse" to it. (Which was the original claim,
after all.) There is no "natural" order to the key/element pairs; they are
effectively unordered.

Iteration = order. It is the same thing. If you provide iteration of pairs
in the mapping by doing so you provide an order of.

Certainly not. An iteration presents all of the elements in a container, but
there is no requirement that there is an order.

The meaning of the word "iterate" is doing something (e.g. visiting an
element) again. That *is* an order.

Post by Randy Brukardt
Indeed, logically, all of
the elements are presented at the same time (and parallel iteration provides
an approximation of that).

Parallel iteration changes nothing because involved tasks are enumerated
and thus ordered as well.

Post by Randy Brukardt
If you try to enforce an order on things that don't require it, you end up
preventing useful parallelism (practically, at least, no one has succeeded
at providing useful parallelism to sequential code and people have been
trying for about 50 years -- they were trying when I was a university
student in the late 1970s).

Ordering things does not prevent parallelism. But storing cursors for
later is a mother of all Sequentialisms! (:-))

Whether a container elements can be effectively deleted in parallel is
an interesting but rather unpractical one. Nobody, literally nobody,
cares because any implementation would be many times slower than the
worst sequential one! (:-))

Post by Randy Brukardt

Post by Randy Brukardt

Post by Dmitry A. Kazakov
It always does sense *IF* enumeration (needed for iteration) is provided.
Enumeration of pairs (<key>, <value>) is not same as ordering values by
the keys.

True, but it doesn't imply any particular ordering. Certainly, no concept of
"forward" or "reverse" applies to such an ordering (nor any stability
requirement).

It does. You have a strict total order of pairs which guarantees existence
of previous and next pairs according to.

Again, this is unrelated. Iteration can usefully occur in unordered
containers (that is, "foreach").

"An enumeration is a complete, ordered listing of all the items in a
collection."
-- Wikipedia

If "foreach" exposes an arbitrary ordering rather than some meaningful
(natural) one, that speaks for "insanity" but changes nothing.

Post by Randy Brukardt
Ordering is a separate concept, not always
needed (certainly not in basic structures like maps, sets, and bags).

Right. But no ordering means no iteration, no foreach etc. If I can
iterate, that I can create an ordered set of (counter, element) pairs. Done.

Post by Randy Brukardt

Yes position is a property of enumeration.

Surely not. This is a basis for my disagrement with you here.

Then you are disagreeing with core mathematics... (:-))

Post by Randy Brukardt
The only
requirement for enumeration is that all elements are produced.

Produced in an order. Elements only produced" is merely an opaque set.
Enumeration of that set is ordering its elements.

Post by Randy Brukardt
The order is
an artifact of doing it an inherently parallel operation sequentally.

Yes, ordering is an ability to enumerate elements of a set. It is not an
artifact it is the sole semantics of.

[...]

Post by Randy Brukardt

Post by Randy Brukardt
You have some problem with an iterator
interface as opposed to an array interface??

Yes, I am against pointers (referential semantics) in general.

This is nonsense - virtually everything is referential semantics (other than
components). Array indexes are just a poor mans pointer (indeed, I learned
how to program in Fortran 66 initially, and way one built useful data
structures was to use array indexes as stand-ins for pointers). In A(1), 1
is a reference to the first component of A.
So long as you are using arrays, you are using referential semantics. The
only way to avoid it is to directly embed an object directly in an enclosing
object (as in a record), and that doesn't work for many problems.

The key difference is that index does not refer any element. It is
container + index that do.

From the programming POV it is about avoiding hidden states when you
try to sweep the container part under the rug.

Post by Randy Brukardt

I don't see anything that is not already there. What are reasons for not
M (n) [ e.g. M (n).Key, M (n).Value ]
M (n1..n2) [ in mutable contexts too ]
M'First
M'Last
M1 & M2 [ M1 or M2 ]
They are all well-defined and useful operations.

Performance.

Irrelevant so long it does not tamper implementations of other operations.

Post by Randy Brukardt
If all of these things are user-definable, then one has to use
subprogram calls to implement all of them. That can be very expensive,
particularly in the case of mutable operations (and mutable slices are the
worst of all).

But better, faster, safer when implemented ad-hoc by the programmer? See
how this thread started. An elementary task, solved in a most
inefficient, crude and unmaintainable way...

Post by Randy Brukardt
Moreover, since one would want the ability to have generic
and runtime parameters that only meet this interface (and the ability to
pass slices to subprograms that take unconstrained array parameters), you
would have to be able to pass all of these subprograms along with
parameters, even when you don't need them. That would make array operations
far more expensive than they are today.

Yes, and the language separates mutable and immutable stuff when using
containers already. You cannot get around this issue.

Post by Randy Brukardt
I think it is much better to get rid of most of these operations as built-in
things and just let the programmer build their own operations as needed.

Well, if you'd proposed throwing containers out the standard library I
would believe that you believe in that... (:-))

Post by Randy Brukardt
That keeps the cost confined to those who use them. Distributed overhead is
the worst kind, and slices in particular have a boatload of that overhead.

Usability always trumps performance. And again, looking at the standard
containers and all these *tagged* *intermediate* objects one needs in
order to do elementary things, I kind of in doubts... (:-))

[Randy Brukardt]

...

Post by Dmitry A. Kazakov
The meaning of the word "iterate" is doing something (e.g. visiting an
element) again. That *is* an order.

The order is an artifact. One logically visits all of the elements at the
same time (certainly in an unordered container like a general map).

Post by Dmitry A. Kazakov

Post by Randy Brukardt
Indeed, logically, all of
the elements are presented at the same time (and parallel iteration provides
an approximation of that).

Parallel iteration changes nothing because involved tasks are enumerated
and thus ordered as well.

Nonsense. There is no interface in Ada to access logical threads (the ones
created by the parallel keyword).

Post by Dmitry A. Kazakov

Post by Randy Brukardt
If you try to enforce an order on things that don't require it, you end up
preventing useful parallelism (practically, at least, no one has succeeded
at providing useful parallelism to sequential code and people have been
trying for about 50 years -- they were trying when I was a university
student in the late 1970s).

Ordering things does not prevent parallelism.

Yes it does, because it adds unnecessary constraints. It's those constraints
that make parallelizing normal sequenatial code hard. A parallelizer has to
guess which ones are fundamental to the code meaning and which ones are not.

...

Post by Dmitry A. Kazakov

Post by Randy Brukardt
Ordering is a separate concept, not always
needed (certainly not in basic structures like maps, sets, and bags).

Right. But no ordering means no iteration, no foreach etc. If I can
iterate, that I can create an ordered set of (counter, element) pairs. Done.

Post by Randy Brukardt

Post by Dmitry A. Kazakov
Yes position is a property of enumeration.

Surely not. This is a basis for my disagrement with you here.

Then you are disagreeing with core mathematics... (:-))

You are adding an unnecessary property to the concept of iteration.
Iteration does not necessarily imply enumeration (it can, of course).
Iteration /= enumeration.

...

Post by Dmitry A. Kazakov

Post by Randy Brukardt
The order is
an artifact of doing it an inherently parallel operation sequentally.

Yes, ordering is an ability to enumerate elements of a set. It is not an
artifact it is the sole semantics of.

Iteration is not necessarily enumeration. It is applying an operation to all
elements, and doing that does not require an order. Some specific operations
might require an order, and clearly for those one needs to use a data
structure that inherently has an order.
...

Post by Dmitry A. Kazakov

Post by Randy Brukardt
So long as you are using arrays, you are using referential semantics. The
only way to avoid it is to directly embed an object directly in an enclosing
object (as in a record), and that doesn't work for many problems.

The key difference is that index does not refer any element. It is
container + index that do.

That's not a "key difference". That exactly how one should use cursors,
especially in Ada 2022. The Ada containers do have cursor-only operations,
but those should be avoided since it is impossible to provide useful
contracts for those operations (the container is unknown, so the world can
be modified, which is bad for parallelism and understanding). Best to
consider those operations obsolete. (Note that I was *always* against the
cursor-only operations in the containers.)

So, using a cursor implies calling an operation that includes the container
of its parameter.

Post by Dmitry A. Kazakov
From the programming POV it is about avoiding hidden states when you try
to sweep the container part under the rug.

That's easily avoided -- don't use the obsolete operations. (And a style
tool like Jean-Pierre's can enforce that for you.)

Post by Dmitry A. Kazakov

Post by Randy Brukardt

Post by Dmitry A. Kazakov
I don't see anything that is not already there. What are reasons for not
M (n) [ e.g. M (n).Key, M (n).Value ]
M (n1..n2) [ in mutable contexts too ]
M'First
M'Last
M1 & M2 [ M1 or M2 ]
They are all well-defined and useful operations.

Performance.

Irrelevant so long it does not tamper implementations of other operations.

Exactly. These operations, especially slicing, have a huge impact on the
cost of parameter passing for arrays (whether or not they are used). And
that's a pretty fundamental operation.

Post by Dmitry A. Kazakov

Post by Randy Brukardt
If all of these things are user-definable, then one has to use
subprogram calls to implement all of them. That can be very expensive,
particularly in the case of mutable operations (and mutable slices are the
worst of all).

But better, faster, safer when implemented ad-hoc by the programmer?

As with all programming problems, you can only have two of the three. ;-)

If the underlying programming language is already better and safer, that
extends to user-written operations. (If it doesn't, it is a failure.)

...
...

Post by Dmitry A. Kazakov

Post by Randy Brukardt
I think it is much better to get rid of most of these operations as built-in
things and just let the programmer build their own operations as needed.

Well, if you'd proposed throwing containers out the standard library I
would believe that you believe in that... (:-))

The standard library is not part of the programming language. It's a
necessary adjunct, but it could be completely replaced without changing the
language at all. It's necessary mainly so that basic operations are provided
in the same way by all implementations, but there is little requirement to
use it.

Specifically, the containers are separate from Ada. Plenty of programmers
use their own container libraries, with different performance and safety
profiles. That's expected and intended. There is no one-size-fits-all (or
even one-size-fits-many) container library.

Post by Dmitry A. Kazakov

Post by Randy Brukardt
That keeps the cost confined to those who use them. Distributed overhead is
the worst kind, and slices in particular have a boatload of that overhead.

Usability always trumps performance.

That's the philosophy of languages like Python, not Ada. If you truly
believe this, then you shouldn't be using Ada at all, since it makes lots of
compromises to usability in order to get performance.

Post by Dmitry A. Kazakov
And again, looking at the standard containers and all these *tagged*
*intermediate* objects one needs in order to do elementary things, I kind
of in doubts... (:-))

The standard containers were designed to make *safe* containers with decent
performance. As I noted, they're not a built-in part of the programming
language, and as such have no impact on the performance of the language
proper. One could easily replace them with an unsafe design to get maximum
performance -- but that would have to return pointers to elements, and
you've said you don't like referential semantics. So you would never use
those.

You also can avoid all of the "tagged objects" (really controlled objects)
by using function Element to get a copy of the element rather than some sort
of reference to it. That's preferred if it doesn't cost too much for your
application.

Randy.

[Dmitry A. Kazakov]

[...]

Post by Randy Brukardt

Post by Dmitry A. Kazakov
Yes, ordering is an ability to enumerate elements of a set. It is not an
artifact it is the sole semantics of.

Iteration is not necessarily enumeration. It is applying an operation to all
elements, and doing that does not require an order.

That is not iteration, it is unordered listing, a totally useless thing
because the result is the same unordered set.

You could not implement it without prior ordering of the elements you
fed to the threads. If the threads picked up elements concurrently there
would be no way to do that without ordering elements into a taken / not
yet taken order. Hell, you cannot even get an element from a truly
unordered set, no way! If the programmer tried to make any use of the
listing he would again have to impose ordering when collecting results
per some shared object.

The unordered listing is a null operation without ordering.

Post by Randy Brukardt

Post by Dmitry A. Kazakov
The key difference is that index does not refer any element. It is
container + index that do.

That's not a "key difference". That exactly how one should use cursors,
especially in Ada 2022. The Ada containers do have cursor-only operations,
but those should be avoided since it is impossible to provide useful
contracts for those operations (the container is unknown, so the world can
be modified, which is bad for parallelism and understanding). Best to
consider those operations obsolete. (Note that I was *always* against the
cursor-only operations in the containers.)
So, using a cursor implies calling an operation that includes the container
of its parameter.

OK. It is some immensely over-designed index operation, then! (:-)) So,
my initial question is back, why all that overhead? When you cannot do
elementary things like preserving your indices from a well-defined set
of upon deleting elements with indices outside that set?

Post by Randy Brukardt

Post by Dmitry A. Kazakov

Post by Randy Brukardt

Post by Dmitry A. Kazakov
I don't see anything that is not already there. What are reasons for not
M (n) [ e.g. M (n).Key, M (n).Value ]
M (n1..n2) [ in mutable contexts too ]
M'First
M'Last
M1 & M2 [ M1 or M2 ]
They are all well-defined and useful operations.

Performance.

Irrelevant so long it does not tamper implementations of other operations.

Exactly. These operations, especially slicing, have a huge impact on the
cost of parameter passing for arrays (whether or not they are used). And
that's a pretty fundamental operation.

It is not slicing it is dynamically constrained arrays which are
required anyway. A general problem of language design is how to treat
statically known constraints effectively.

Ada arrays are pretty good to me. Note, I am saying that after years of
using Ada arrays for interfacing C! Yes, I would like having more
support for flattening arrays, but the mere fact that Ada can interface
C using *in-place* semantics invalidates your point.

Post by Randy Brukardt
Specifically, the containers are separate from Ada.

Not really. Like STL with C++ it massively influenced the language
design motivating adding certain language features and shifting general
language paradigm in certain direction.

Post by Randy Brukardt

Post by Dmitry A. Kazakov
Usability always trumps performance.

That's the philosophy of languages like Python, not Ada.

Ah, this is why Python is totally unusable? (:-))

Ada is usable and performant because of right abstractions it deploys.
If you notice performance problems then, maybe, just my guess, you are
using a wrong abstraction?

Post by Randy Brukardt

Post by Dmitry A. Kazakov
And again, looking at the standard containers and all these *tagged*
*intermediate* objects one needs in order to do elementary things, I kind
of in doubts... (:-))

The standard containers were designed to make *safe* containers with decent
performance.

Well, we always wish the best... (:-))

[Randy Brukardt]

"Dmitry A. Kazakov" <***@dmitry-kazakov.de> wrote in message news:un64o3$3krch$***@dont-email.me...
...

Post by Randy Brukardt
Exactly. These operations, especially slicing, have a huge impact on the
cost of parameter passing for arrays (whether or not they are used). And
that's a pretty fundamental operation.

It is not slicing it is dynamically constrained arrays which are required
anyway. A general problem of language design is how to treat statically
known constraints effectively.

No, it's the combination of slicing and passing arrays with unknown (at
compile-time) constraints that causes problems. And it only causes problems
if you want to separate the array interface and the array implementation
(which we both want to do). In such a case, you are passing arrays with
unknown constraints and implementation. Assignable slices don't work with
that, as they require a contiguous implementation of elements. You could
work around that in various ways (passing slices by copy-result, passing an
assignment routine along with the parameter), but all of them have
substantial performance impacts that would make traditional array
implementations much slower.

Ada arrays are pretty good to me. Note, I am saying that after years of
using Ada arrays for interfacing C! Yes, I would like having more support
for flattening arrays, but the mere fact that Ada can interface C using
*in-place* semantics invalidates your point.

Inferfacing is using the array implementation, not the array interface. Of
course it works great, as you note Ada commingles those in a way that makes
them inseparable. To separate them, you are going to have to lose something.
I chose slices and other array-specific operations as a built-in as that
something. YMMV.

...

Post by Randy Brukardt

Post by Dmitry A. Kazakov
Usability always trumps performance.

That's the philosophy of languages like Python, not Ada.

Ah, this is why Python is totally unusable? (:-))

I would tend to argue that it is indeed the case that you get dubious
results when you put usability first. Ada puts
readability/understandability, maintainability, and consistency first (along
with performance). Those attributes tend to provide usability, but not at
the cost of making things less consistent or understandable.

I wrote an article on this topic a year and a half ago that I wanted to
publish on Ada-Auth.org. But I got enough pushback about not being "neutral"
that I never did so. (I don't think discussing why we don't do things some
other languages do is negative, but whatever.) I've put this on RR's blog at
http://www.rrsoftware.com/html/blog/consequences.html so it isn't lost.

Randy.

[Simon Wright]

Post by Randy Brukardt
I wrote an article on this topic a year and a half ago that I wanted to
publish on Ada-Auth.org. But I got enough pushback about not being "neutral"
that I never did so. (I don't think discussing why we don't do things some
other languages do is negative, but whatever.) I've put this on RR's blog at
http://www.rrsoftware.com/html/blog/consequences.html so it isn't lost.

Thanks for this!

[Dmitry A. Kazakov]

Post by Randy Brukardt
...

Post by Randy Brukardt
Exactly. These operations, especially slicing, have a huge impact on the
cost of parameter passing for arrays (whether or not they are used). And
that's a pretty fundamental operation.

It is not slicing it is dynamically constrained arrays which are required
anyway. A general problem of language design is how to treat statically
known constraints effectively.

No, it's the combination of slicing and passing arrays with unknown (at
compile-time) constraints that causes problems.

As well as passing non-null pointers, discriminated objects, class-wide
objects...

Post by Randy Brukardt
And it only causes problems
if you want to separate the array interface and the array implementation
(which we both want to do). In such a case, you are passing arrays with
unknown constraints and implementation. Assignable slices don't work with
that, as they require a contiguous implementation of elements.

Only if the base type implementation is contiguous. A slice of a
non-contiguous container is non-contiguous. If you can deal with the
first you can do with the second.

The crucial point is removing static constraints from the instances
which Ada does on some occasions and not on others, especially for the
user-defined types.

Post by Randy Brukardt
Inferfacing is using the array implementation, not the array interface. Of
course it works great, as you note Ada commingles those in a way that makes
them inseparable. To separate them, you are going to have to lose something.

Sure, but the point is that the loss should never happen when
constraints are static when the callee knows them. When the callee does
not, then a constraint must be passed to it.

Post by Randy Brukardt

Post by Randy Brukardt

Post by Dmitry A. Kazakov
Usability always trumps performance.

That's the philosophy of languages like Python, not Ada.

Ah, this is why Python is totally unusable? (:-))

I would tend to argue that it is indeed the case that you get dubious
results when you put usability first. Ada puts
readability/understandability, maintainability, and consistency first (along
with performance). Those attributes tend to provide usability, but not at
the cost of making things less consistent or understandable.
I wrote an article on this topic a year and a half ago that I wanted to
publish on Ada-Auth.org. But I got enough pushback about not being "neutral"
that I never did so. (I don't think discussing why we don't do things some
other languages do is negative, but whatever.) I've put this on RR's blog at
http://www.rrsoftware.com/html/blog/consequences.html so it isn't lost.

Thanks for posting this.

I disagree with what you wrote on several points:

1. Your premise was that use = writing. To me using includes all aspects
of software developing and maintenance process. Writing is only a small
part of it.

2. You argue for language regularity as if it were opposite to
usability. Again, it is pretty much obvious that a regular language is
easier to use in any possible sense.

3. Removing meaningless repetitions contributes to usability. But X := X
+ Y is only one instance where Ada required such repetition. There are
others. E.g.

if X in T'Class then
declare
XT : T'Class renames T'Class (X);

T'Class is repeated 3 times. A discussion point is whether a new name XT
could be avoided etc.

Introducing @ for a *single* purpose contradicts the principle of
regularity. I would rather have a regular syntax for most if not all
such instances.

[Randy Brukardt]

...

Post by Dmitry A. Kazakov
Thanks for posting this.
1. Your premise was that use = writing. To me using includes all aspects
of software developing and maintenance process. Writing is only a small
part of it.

Perhaps I didn't make it clear enough, but my premise was that many people
making suggestions for Ada confuse "ease-of-use" with "ease-of-writing". I
said "mischaracterized" for a reason (and I see that "mis" was missing from
the first use, so I just added that). "Ease-of-writing" is not a thing for
Ada, and it isn't considered while the other aspects are weighed. And as I
said in my last message, there is a difference in that writing more can help
understandability, but it never helps writing.

Post by Dmitry A. Kazakov
2. You argue for language regularity as if it were opposite to usability.
Again, it is pretty much obvious that a regular language is easier to use
in any possible sense.

But not necessarily easier to write, which was the primary topic I was
dealing with.

Post by Dmitry A. Kazakov
3. Removing meaningless repetitions contributes to usability. But X := X +
Y is only one instance where Ada required such repetition. There are
others. E.g.
if X in T'Class then
declare
XT : T'Class renames T'Class (X);
T'Class is repeated 3 times. A discussion point is whether a new name XT
could be avoided etc.

Of course, this example violates OOP dogma, and some people would argue that
should be harder than following it. That's the same reason that Ada doesn't
have that many implicit conversions. In this particular example, I tend to
think the dogma is silly, but I don't off-hand see a way to avoid the
conversion being somewhere (few implicit conversions after all).

Post by Dmitry A. Kazakov
regularity. I would rather have a regular syntax for most if not all such
instances.

@ is regular in the sense that it is allowed anywhere in an expression. If
you tried to expand the use to other contexts, you would have to
differentiate them, which would almost certainly require some sort of
declaration. But doing that risks making the mechanism as wordy as what it
replaces (which obviously defeats the purpose).

We looked at a number of ideas like that, but they didn't seem to help
comprehension. In something like:
LHS:(X(Y)) := LHS + 1;
(where LHS is an arbitrary identifier), if the target name is fairly long,
it could be hard to find where the name for the target is given, and in any
case, it adds to the name space that the programmer has to remember when
reading the source expression. That didn't seem to add to readability as
much as the simple @ does.

In any case, these things are trade-offs, and certainly nothing is absolute.
But @ is certainly much more general than ":=+" would be, given that it
works with function calls and array indexing and attributes and user-defined
operations rather than just a single operator.

Randy.

[Jeffrey R.Carter]

Post by Randy Brukardt
@ is regular in the sense that it is allowed anywhere in an expression. If
you tried to expand the use to other contexts, you would have to
differentiate them, which would almost certainly require some sort of
declaration. But doing that risks making the mechanism as wordy as what it
replaces (which obviously defeats the purpose).
We looked at a number of ideas like that, but they didn't seem to help
LHS:(X(Y)) := LHS + 1;
(where LHS is an arbitrary identifier), if the target name is fairly long,
it could be hard to find where the name for the target is given, and in any
case, it adds to the name space that the programmer has to remember when
reading the source expression. That didn't seem to add to readability as
In any case, these things are trade-offs, and certainly nothing is absolute.
works with function calls and array indexing and attributes and user-defined
operations rather than just a single operator.

For the 9X and 0X revisions I suggested adding "when <condition>" to return and
raise statements, similar to its use on exit statements. This was rejected
because the language already has a way to accomplish this: if statements.

Given that one can do

declare
V : T renames Very_Long_Identifier;
begin
V := V - 23;
end;

it seems that @ should also have been rejected. Probably more so, since @ is
completely new syntax rather than reusing existing syntax on some additional
statements. What is the justification of accepting @ while still rejecting the
other?

[Randy Brukardt]

"Jeffrey R.Carter" <***@spam.acm.org.not> wrote in message news:uneel2$12ufr$***@dont-email.me...
...

Post by Jeffrey R.Carter
For the 9X and 0X revisions I suggested adding "when <condition>" to
return and raise statements, similar to its use on exit statements. This
was rejected because the language already has a way to accomplish this: if
statements.

I don't recall ever seriously considering this (might just my memory getting
old). I suspect that didn't get rejected so much as not making the cut as
important enough. We do try to limit the size of what gets added, not just
adding everyone's favorite feature.

I'd guess that "raise Foo when Something" would get rejected now as it would
be confusing with "raise Foo with Something" which means something very
different. (At least the types of "Something" are different in these two.)
OTOH, we added "when condition" to loops (which I thought was unnecessary,
but I lost that), so argubly it would be consistent to add it to other
statements and expressions as well. Perhaps you should raise it again on the
Github.

Randy.

Post by Jeffrey R.Carter
Given that one can do
declare
V : T renames Very_Long_Identifier;
begin
V := V - 23;
end;
is completely new syntax rather than reusing existing syntax on some
still rejecting the other?
--
Jeff Carter
"If I could find a sheriff who so offends the citizens of Rock
Ridge that his very appearance would drive them out of town ...
but where would I find such a man? Why am I asking you?"
Blazing Saddles
37

[Lawrence D'Oliveiro]

Post by Randy Brukardt
OTOH, we added "when condition" to loops (which I thought
was unnecessary, but I lost that) ...

I can see that conditional exits are a very common case, and because Ada
requires “end if” on if-statements, they wanted to shorten the common
case, hence exit-when.

Not sure if conditional raises are that common. If my Python experience is
any guide, I don’t do that much.

[Jeffrey R.Carter]

Post by Randy Brukardt
I don't recall ever seriously considering this (might just my memory getting
old). I suspect that didn't get rejected so much as not making the cut as
important enough.

I don't consider special syntax to shorten names in assignment statements
important at all. We have renames for that, and it is a more general mechanism,
applying to more than just assignments.

[Cóilín Nioclás Pól Glostéir]

Post by Randy Brukardt
...

[. . .]

Post by Randy Brukardt

Post by Dmitry A. Kazakov

Post by Randy Brukardt

Post by Dmitry A. Kazakov
Usability always trumps performance.

That's the philosophy of languages like Python, not Ada.

Ah, this is why Python is totally unusable? (:-))

I would tend to argue that it is indeed the case that you get dubious
results when you put usability first. Ada puts
readability/understandability, maintainability, and consistency first (along
with performance). Those attributes tend to provide usability, but not at
the cost of making things less consistent or understandable.
I wrote an article on this topic a year and a half ago that I wanted to
publish on Ada-Auth.org. But I got enough pushback about not being "neutral"
that I never did so. (I don't think discussing why we don't do things some
other languages do is negative, but whatever.) I've put this on RR's blog at
http://www.rrsoftware.com/html/blog/consequences.html so it isn't lost.

Thanks for posting this."

Dear all,

Thanks indeed.

"[. . .]

3. Removing meaningless repetitions contributes to usability. But X := X + Y
is only one instance where Ada required such repetition. [. . .]

[. . .]"

I wrote a function to increment as a workaround but opinionated Anita
Enmark did not like it. Engineering and opinions.

" if X in T'Class then
declare
XT : T'Class renames T'Class (X);

T'Class is repeated 3 times."

Sorry: 2 times.

With best regards.
Nioclás Pól Caileán de Ghloucester

[Lawrence D'Oliveiro]

Post by Randy Brukardt

Post by Dmitry A. Kazakov

Post by Randy Brukardt

Post by Dmitry A. Kazakov
Usability always trumps performance.

That's the philosophy of languages like Python, not Ada.

Ah, this is why Python is totally unusable? (:-))

I would tend to argue that it is indeed the case that you get dubious
results when you put usability first. ...
http://www.rrsoftware.com/html/blog/consequences.html

Without reading that, I would never have understood “usability” to mean
“ease of writing”. I learned from early on in my programming career that
readability was more important than writability. So “using” a language
doesn’t end with writing the code: you then have to test and debug it--
basically lick it into shape--then maintain it afterwards.

[Randy Brukardt]

Post by Randy Brukardt

Post by Dmitry A. Kazakov

Post by Randy Brukardt

Post by Dmitry A. Kazakov
Usability always trumps performance.

That's the philosophy of languages like Python, not Ada.

Ah, this is why Python is totally unusable? (:-))

I would tend to argue that it is indeed the case that you get dubious
results when you put usability first. ...
http://www.rrsoftware.com/html/blog/consequences.html

Without reading that, I would never have understood "usability" to mean
"ease of writing". I learned from early on in my programming career that
readability was more important than writability. So "using" a language
doesn't end with writing the code: you then have to test and debug it--
basically lick it into shape--then maintain it afterwards.

Usability is of course not just ease-of-writing, but a lot of people tend to
co-mingle the two. For readability, too little information can be just as
bad as too much. For writability, the less you have to write, the better.

Randy.

[Niklas Holsti]

Post by Randy Brukardt

Post by Randy Brukardt

Post by Dmitry A. Kazakov

Post by Randy Brukardt

Post by Dmitry A. Kazakov
Usability always trumps performance.

That's the philosophy of languages like Python, not Ada.

Ah, this is why Python is totally unusable? (:-))

I would tend to argue that it is indeed the case that you get dubious
results when you put usability first. ...
http://www.rrsoftware.com/html/blog/consequences.html

Without reading that, I would never have understood "usability" to mean
"ease of writing". I learned from early on in my programming career that
readability was more important than writability. So "using" a language
doesn't end with writing the code: you then have to test and debug it--
basically lick it into shape--then maintain it afterwards.

Usability is of course not just ease-of-writing, but a lot of people tend to
co-mingle the two. For readability, too little information can be just as
bad as too much. For writability, the less you have to write, the better.

I feel that is too narrow a definition of writability (and perhaps you
did not intend it as a definition). Before one can start typing code,
one has to decide what to write -- which language constructs to use. A
systematically constructed, regular language like Ada makes that mental
effort easier, even if it results in more keystrokes; a plethora of
special-case syntaxes and abbreviation possibilities makes it harder.

Perhaps "writability" should even be taken to cover the whole process of
creating /correct/ code, and include all the necessary testing,
debugging and corrections until correct code is achieved. Here of course
Ada shines again, with so many coding errors caught at compile time.

[Lawrence D'Oliveiro]

Post by Randy Brukardt
For writability, the less you have to write, the better.

I write code for readability, and I think avoiding repetition fits into
that as well. Thus, factoring repeated sequences into a common function/
class, and just putting calls to that in all the relevant places, is, I
find, generally a Good Thing.

Bugs seem to be measured per line of code. Therefore, fewer lines of code
means fewer bugs overall.

[J-P. Rosen]

Post by Randy Brukardt
Usability is of course not just ease-of-writing, but a lot of people tend to
co-mingle the two. For readability, too little information can be just as
bad as too much. For writability, the less you have to write, the better.

Yes, I'm always surprised to see many languages (including Rust)
praising themselves of being "concise". Apart from saving some
keystrokes, I fail to see the benefit of being concise...

[Bill Findlay]

Post by J-P. Rosen

Post by Randy Brukardt
Usability is of course not just ease-of-writing, but a lot of people tend to
co-mingle the two. For readability, too little information can be just as
bad as too much. For writability, the less you have to write, the better.

Yes, I'm always surprised to see many languages (including Rust)
praising themselves of being "concise". Apart from saving some
keystrokes, I fail to see the benefit of being concise...

Agreed. However, it is a bit of a totem in the FP cult.

[Lawrence D'Oliveiro]

Post by J-P. Rosen
Yes, I'm always surprised to see many languages (including Rust)
praising themselves of being "concise". Apart from saving some
keystrokes, I fail to see the benefit of being concise...

How about this for an example. I created a Python wrapper around the Cairo
graphics library <https://www.cairographics.org/>. There are already other
Python wrappers, which are little more than transliterations of the C API.
I wanted to go one step further. So whereas in C you might write

x1 = - scope_radius * sin(trace_width_angle);
y1 = scope_radius * cos(trace_width_angle);
cairo_line_to(ctx, x1, y1);

my Python wrapper reduces this down to

ctx.line_to(Vector(0, scope_radius).rotate(trace_width_angle))

How’s that for “concise”?

[Randy Brukardt]

Post by DrPi

Post by DrPi
Iterate the Map and temporarily store the key nodes to be deleted then
delete the nodes from the key list ?

Not clear. Rephrasing it.
Using 2 steps by iterating the Map and temporarily store the keys of nodes
to be deleted then delete the Map nodes using the key list ?

If the keys are messy to save (as say with type String), it might be easier
to save the cursor(s) of the nodes to delete. You would probably want to use
a cursor iterator (that is, "in") to get the cursors. Code would be
something like (declarations of the Map and List not shown, nor is the
function Need_to_Delete which is obviously application specific, Save_List
is a list of cursors for My_Map, everything else is standard, not checked
for syntax errors):

Save_List.Empty; -- Clear list of saved cursors.
-- Find the nodes of My_Map that we don't need.
for C in My_Map.Iterate loop
if Need_to_Delete (My_Map.Element(C)) then
Save_List.Append (C);
-- else no need to do anything.
end if;
end loop;
-- Delete the cursors of the nodes we don't want anymore.
for C of Save_List loop
My_Map.Delete(C);
end loop;



Randy.

[DrPi]

Post by Randy Brukardt

Post by DrPi

Post by DrPi
Iterate the Map and temporarily store the key nodes to be deleted then
delete the nodes from the key list ?

Not clear. Rephrasing it.
Using 2 steps by iterating the Map and temporarily store the keys of nodes
to be deleted then delete the Map nodes using the key list ?

If the keys are messy to save (as say with type String), it might be easier
to save the cursor(s) of the nodes to delete. You would probably want to use
a cursor iterator (that is, "in") to get the cursors. Code would be
something like (declarations of the Map and List not shown, nor is the
function Need_to_Delete which is obviously application specific, Save_List
is a list of cursors for My_Map, everything else is standard, not checked
Save_List.Empty; -- Clear list of saved cursors.
-- Find the nodes of My_Map that we don't need.
for C in My_Map.Iterate loop
if Need_to_Delete (My_Map.Element(C)) then
Save_List.Append (C);
-- else no need to do anything.
end if;
end loop;
-- Delete the cursors of the nodes we don't want anymore.
for C of Save_List loop
My_Map.Delete(C);
end loop;

That's what I did but I saved the keys (String) instead of the cursors.
Does it make a difference ? Performance maybe ?

Nicolas

Post by Randy Brukardt
Randy.

[Randy Brukardt]

"DrPi" <***@drpi.fr> wrote in message news:ummj1i$e64$***@rasp.pasdenom.info...
... (Example eliminated)

Post by DrPi
That's what I did but I saved the keys (String) instead of the cursors.
Does it make a difference ? Performance maybe ?

It certainly will make a performance difference; whether that difference is
significant of course depends on the implementation. There's two parts to it
(one of which I thought of yesterday and the other which I forgot):
(1) The cost of storing keys vs. storing cursors. Cursors are going to be
implemented as small record types (cannonically, they are two pointers, one
to the enclosing container and one to the specific node/element). A key can
be most anything, and storing that can be more costly.
(2) The cost of looking up a key. A map is a set of nodes, and there
needs to be some operation to associate a key with the correct node. Those
operations take some time, of course: for a hashed map, the key has to be
hashed and then some sort of lookup performed. Whereas a cursor generally
contains an indication of the node, so the access is more direct.

For a lot of applications, this difference won't matter enough to be
significant. But I'd probably lean toward using cursors for this sort of job
as that would minimize performance problems down the line. (Of course, if
the container gets modified after you save the cursors, then they could
become dangling, which is a problem of it's own. If that's a possibility,
saving the keys is better.)

Randy.

[DrPi]

Post by Randy Brukardt
... (Example eliminated)

Post by DrPi
That's what I did but I saved the keys (String) instead of the cursors.
Does it make a difference ? Performance maybe ?

It certainly will make a performance difference; whether that difference is
significant of course depends on the implementation. There's two parts to it
(1) The cost of storing keys vs. storing cursors. Cursors are going to be
implemented as small record types (cannonically, they are two pointers, one
to the enclosing container and one to the specific node/element). A key can
be most anything, and storing that can be more costly.
(2) The cost of looking up a key. A map is a set of nodes, and there
needs to be some operation to associate a key with the correct node. Those
operations take some time, of course: for a hashed map, the key has to be
hashed and then some sort of lookup performed. Whereas a cursor generally
contains an indication of the node, so the access is more direct.
For a lot of applications, this difference won't matter enough to be
significant. But I'd probably lean toward using cursors for this sort of job
as that would minimize performance problems down the line. (Of course, if
the container gets modified after you save the cursors, then they could
become dangling, which is a problem of it's own. If that's a possibility,
saving the keys is better.)

I modified my code to use cursors.
Thanks for your help.

Nicolas