On 08.09.23 23:02, Ben Bacarisse wrote:
> "G.B." <bauhaus@notmyhomepage.invalid> writes:
>
>> On 07.09.23 01:32, Ben Bacarisse wrote:
>>
>>
>>> A fix (though it's not really ideal) would be to use function
>>> composition here (inventing . as the composition operator):
>>
>> Hm. A stateful, composed function that needs to be applied
>> in a certain way. Is that so different from calling interface
>> subprograms of a certain type?
>
> There was nothing stateful (as I understand the term) in either function
> being composed.

The "apparatus" that the computation needs in order to remember
"max so far" looks like part of its state to me. Somehow
"the function" needs to operate this state and evaluate it.
Extend this to:
- find the maximum of [the maxima of] these n collections
- find the maximum in this stream at 10 seconds from now.

Is it possible, or practical, to define a pure function so that
calling it will remember the needed information, n >= 0
being arbitrary?

>> So, does type composition help?
>
> My turn to guess now: you are not being serious? I see no connection to
> monads or type composition.

In the following sense:
There is an object of type So_Far that can remember
objects of any type T, them coming from collections
of type C-of-T.

> And why bring C++ into it?

It's already there, you mentioned the pair of iterators, and
there is std::max_element() which finds the greatest element
in any range based solely on these, and optionally using a generic
comparison.
There are similar things in Dmitry's packages. A key difference
seems to be that Ada's Cursors are tied to a specific collection.
I don't know of any convenient way around this, maybe because
type Cursor is just private in every Ada.Containers.Xyz and
there is no common type name for them, or for what some
algorithm might need them to have in common.

I'm not sure if the new Ada.Iterator_Interfaces (LRM 5.5.1)
could solve this, also because I really don't know that yet.
But it looks like I'd need instances of specific containers
for instantiation. (That being consistent with Ada's approach
to the STL, I think.)

On 2023-09-09 02:25, Ben Bacarisse wrote:
> "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> writes:
>
>> On 2023-09-08 03:32, Ben Bacarisse wrote:
>>> "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> writes:
>>>
>>>> On 2023-09-07 01:32, Ben Bacarisse wrote:
>>>>> "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> writes:
>>>>>
> I wanted the maximum of a function over a collection (range, array, map,
> etc). In some languages, collections can be scanned so you don't need
> to know where the data come from.

Hmm, the thing we discussed was a maximum element in array or map rather
than a maximum of a function over the *domain* set of array or map. In a
typed language array /= domain of array.

>>>> Then you would pass Has_Element for it. For integers you would use wrapped
>>>> X'Valid (there is no Integer'Valid, unfortunately. Only X'Valid where X is
>>>> an object).
>>> It's definitely getting what I call cumbersome.
>>
>> Yes, because you try too hard to make it work where it probably should
>> not.
>
> If you think a resuable Ada function that can find the maximum of some F
> over some 'collection' X is possible, I'd like to see how it's done.

To start with, no such function exists. Not in a typed language. Note
that a generic function is not a function. So instead we must consider
language constructs for the purpose. Generic instantiation is one of
them, some class might be another, but in Ada we just use loops. (And
yes, people liking writing programs while standing on their heads, may
use recursion... (:-))

> I
> can do it for some kinds of X but I have no idea how general it can be
> made in Ada. I think the answer is either that it can't be very
> general, or to make it very general is too much work, or that one should
> not be trying in the first place.

The limits of generality are defined by the interfaces. In Ada types are
designed to implement needed interfaces upfront. If you want to do that
after the fact, you need some other adapter types to shove an existing
type into something it was not designed for.

>>> I don't think this is incoherent. The Haskell libraries ensure that any
>>> collection that is logically foldable is indeed foldable.
>>
>> Ada arrays and library containers do not share interfaces.
>
> I was pretty sure that was the case. Thanks for confirming. I think
> that means there can be no truly generic solution. But maybe it's
> possible at least for all container types in the library?

If a library is designed with this purpose in mind, that is trivial as
you just pointed out. All collection types in the library would
implement the required interface. End of story.

> (But I note
> that if you think it /shouldn't/ be done, I won't expect you to show me
> how.)

That is not a language question. It is a question of the library design.
What if the library did not follow the desired design? That would be a
language question and Ada offers some means, but not enough from my
point of view due to the limitation of its type system.

>> Should the language allow adding
>> ad-hoc interfaces to existing types. Yes, and this is possible in Ada in
>> some very uncomfortable AKA cumbersome way, which is why "finding maximum"
>> is not a worthy abstraction in Ada.
>
> I suspected one might have to extend the interfaces.

You cannot in a strongly typed language without breaking too much
things. You must create another type related to the old one and
implementing the new interface (superclass). That would do the trick.
Ada cannot this, so you go for the poor man's substitute: a mix-in. I.e.
you create a new type that references an object of the old type. E.g.
see array cursors example in my earlier post.

>>> What closure is required for a function composition? There is no
>>> environment to "close over".
>>
>> In Ada a function can use anything visible at its declaration point and at
>> the location of its body. You can even declare a function inside a
>> recursively called function and let it see local variables of each
>> recursive call, in effect having an infinite set of functions.
>
> At the point where I want Period.Element I can write the (almost)
> one-line function that takes a Cursor and returns Period(Element(C))
> entirely mechanically. Can't the compiler do that?

No.

(Ada indeed composes functions in some limited number of cases, e.g. an
explicit type conversion of [in] out arguments. But these are predefined.)

> Note I'm not asking if it /should/ (it may not be "Ada-like" to do
> that). I'm just curious if there really is a technical reason it can't
> be done.

Actually compositions might be useful in many cases and adapting
interfaces is one of them.

>>> That's a lot just to use something that is supposed to be reusable.
>>
>> [rant on]
>> An Ada programmer would just write a loop.
>
> Yes, that's fine. Different languages have different objectives. Just
> write the empty range test and the loop you need for each kind of
> collection.

You can loop in Ada over empty ranges, no problem.

> That was definitely the way things were done in the 80s.

Yes, before the Dark Ages of Computing...

>>> It only occurred to me after writing the non-generic solution. I
>>> remember Ada as being something of a pioneer in it's attempt to provide
>>> generic solutions, so I wondered how far things had come. I don't think
>>> something really widely reusable is possible in this case.
>>
>> As I said you think in a wrong direction of abstracting the language
>> "finding maximum" rather than the problem space, e.g. generalization to
>> other bases, other mathematical structures etc.
>
> Generalising to an arbitrary base is local to the function that finds
> the answer for one element. It's an entirely separate axis of
> generalisation to that of where the elements come from.
>
> It's interesting to me that you consider one simply wrong and the other
> natural.

Because one is a software design artifact and another is the result of
problem space analysis.

> In some languages the "wrong" one does not even merit
> consideration as it's just there for free.

Being a part of design it has all possible merits to consider and then
reject it. That is in the position of a puzzle solver. Now in the
position of a library designer, the Ada standard library has an
[informal] interface that supports what you wanted:

1. Cursor
2. Key at the cursor
3. Element at the cursor
4. Iterate procedure

So, for the Ada standard library it might look like this:

generic
type Container_Type (<>) is limited private;
type Element_Type is private;
type Key_Type is private;
type Cursor_Type is private;
with function "<" (Left, Right : Element_Type) return Boolean is <>;
with function Key (Position : Cursor_Type) return Key_Type is <>;
with function Element
( Position : Cursor_Type
) return Element_Type is <>;
with procedure Iterate
( Container : Container_Type;
Process : not null access procedure
(Position : Cursor_Type)
) is <>;
function Generic_Container_Maximum_At (Container : Container_Type)
return Key_Type;

function Generic_Container_Maximum_At (Container : Container_Type)
return Key_Type is
Found : Boolean := False;
Max : Element_Type;
Result : Key_Type;
procedure Walker (Position : Cursor_Type) is
begin
if Found then
if Max < Element (Position) then
Result := Key (Position);
Max := Element (Position);
end if;
else
Result := Key (Position);
Max := Element (Position);
Found := True;
end if;
end Walker;
begin
Iterate (Container, Walker'Access);
if Found then
return Result;
else
raise Constraint_Error with "Empty container";
end if;
end Generic_Container_Maximum_At;

Instantiation:

package Integer_Maps is
new Ada.Containers.Ordered_Maps (Integer, Integer);
use Integer_Maps;
function Integer_Map_Max is
new Generic_Container_Maximum_At (Map, Integer, Integer, Cursor);

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

"G.B." <bauhaus@notmyhomepage.invalid> writes:

> On 08.09.23 23:02, Ben Bacarisse wrote:
>> "G.B." <bauhaus@notmyhomepage.invalid> writes:
>>
>>> On 07.09.23 01:32, Ben Bacarisse wrote:
>>>
>>>
>>>> A fix (though it's not really ideal) would be to use function
>>>> composition here (inventing . as the composition operator):
>>>
>>> Hm. A stateful, composed function that needs to be applied
>>> in a certain way. Is that so different from calling interface
>>> subprograms of a certain type?
>> There was nothing stateful (as I understand the term) in either function
>> being composed.
>
> The "apparatus" that the computation needs in order to remember
> "max so far" looks like part of its state to me.

The "max so far" function is not being composed.

> Somehow
> "the function" needs to operate this state and evaluate it.
> Extend this to:
> - find the maximum of [the maxima of] these n collections
> - find the maximum in this stream at 10 seconds from now.
>
> Is it possible, or practical, to define a pure function so that
> calling it will remember the needed information, n >= 0
> being arbitrary?

I am not sure how the discussion got here. Ada is an imperative
language so of course one would use "running" state to calculate a
maximum. The max_of_F_over_X function just loops like any other loop
from First_Of(X) to Last_Of(X) calculating F(This(X)), comparing that
with Max_So_Far.

These are invented names, of course, because I don't know how it should
be done, but the idea is plain imperative code. In fact, it's possible
that Ada has some entirely different syntax for this kind of imperative
loop.

The "fix" to use a composed function was because one proposed solution
found the maximum of Element(C) (where C was a cursor) because Element
was passed as F, but that of course is not what was wanted. To find the
maximum of F I speculated that one could pass F.Element.

>>> So, does type composition help?
>> My turn to guess now: you are not being serious? I see no connection to
>> monads or type composition.
>
> In the following sense:
> There is an object of type So_Far that can remember
> objects of any type T, them coming from collections
> of type C-of-T.

Given the above confusion about what is being composed, I can see the
connection with monads. But there is no reason to use the concept of a
monad in a language with modifiable state. The maximum should be found
as in the posted code with a simple loop.

> I'm not sure if the new Ada.Iterator_Interfaces (LRM 5.5.1)
> could solve this, also because I really don't know that yet.
> But it looks like I'd need instances of specific containers
> for instantiation. (That being consistent with Ada's approach
> to the STL, I think.)

Thanks for the pointer. I am not sure I have time to look in detail,
but it looks interesting.

--
Ben.

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

> On 2023-09-09 02:25, Ben Bacarisse wrote:
>> "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> writes:

>>> [rant on]
>>> An Ada programmer would just write a loop.
>> Yes, that's fine. Different languages have different objectives. Just
>> write the empty range test and the loop you need for each kind of
>> collection.
>
> You can loop in Ada over empty ranges, no problem.

Yes, but the problem in hand (maximum of F over X) should raise an error
on an empty X. I know there are other options, but you chose to
raise an error so that's the design I was talking about.

>> That was definitely the way things were done in the 80s.
>
> Yes, before the Dark Ages of Computing...

Eh? There have been repeated updates to the Ada language. Are they
taking Ada into the dark ages? If so, what was the golden age of Ada
when its design was perfect for numerical algorithms?

>>> As I said you think in a wrong direction of abstracting the language
>>> "finding maximum" rather than the problem space, e.g. generalization to
>>> other bases, other mathematical structures etc.
>> Generalising to an arbitrary base is local to the function that finds
>> the answer for one element. It's an entirely separate axis of
>> generalisation to that of where the elements come from.
>> It's interesting to me that you consider one simply wrong and the other
>> natural.
>
> Because one is a software design artifact and another is the result of
> problem space analysis.

Which one the wrong one?

>> In some languages the "wrong" one does not even merit
>> consideration as it's just there for free.
>
> Being a part of design it has all possible merits to consider and then
> reject it. That is in the position of a puzzle solver. Now in the position
> of a library designer, the Ada standard library has an [informal] interface
> that supports what you wanted:

Well, there has been some confusion over that, but from what I
understand of the code below, adding in a function to maximise would be
simple.

> 1. Cursor
> 2. Key at the cursor
> 3. Element at the cursor
> 4. Iterate procedure
>
> So, for the Ada standard library it might look like this:
>
> generic
> type Container_Type (<>) is limited private;
> type Element_Type is private;
> type Key_Type is private;
> type Cursor_Type is private;
> with function "<" (Left, Right : Element_Type) return Boolean is <>;
> with function Key (Position : Cursor_Type) return Key_Type is <>;
> with function Element
> ( Position : Cursor_Type
> ) return Element_Type is <>;
> with procedure Iterate
> ( Container : Container_Type;
> Process : not null access procedure
> (Position : Cursor_Type)
> ) is <>;
> function Generic_Container_Maximum_At (Container : Container_Type)
> return Key_Type;
>
> function Generic_Container_Maximum_At (Container : Container_Type)
> return Key_Type is
> Found : Boolean := False;
> Max : Element_Type;
> Result : Key_Type;
> procedure Walker (Position : Cursor_Type) is
> begin
> if Found then
> if Max < Element (Position) then
> Result := Key (Position);
> Max := Element (Position);
> end if;
> else
> Result := Key (Position);
> Max := Element (Position);
> Found := True;
> end if;
> end Walker;
> begin
> Iterate (Container, Walker'Access);
> if Found then
> return Result;
> else
> raise Constraint_Error with "Empty container";
> end if;
> end Generic_Container_Maximum_At;
>
> Instantiation:
>
> package Integer_Maps is
> new Ada.Containers.Ordered_Maps (Integer, Integer);
> use Integer_Maps;
> function Integer_Map_Max is
> new Generic_Container_Maximum_At (Map, Integer, Integer, Cursor);

This is probably the closest we can get to a universal solution.
Vectors don't have a Key function but I am sure I could find out what
should be provided there.

Thanks.

I agree that is does not feel worth it. Just write the loop our each time.

--
Ben.

On 2023-09-10 03:20, Ben Bacarisse wrote:
> "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> writes:
>
>> On 2023-09-09 02:25, Ben Bacarisse wrote:
>>> "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> writes:
>
>>>> [rant on]
>>>> An Ada programmer would just write a loop.
>>> Yes, that's fine. Different languages have different objectives. Just
>>> write the empty range test and the loop you need for each kind of
>>> collection.
>>
>> You can loop in Ada over empty ranges, no problem.
>
> Yes, but the problem in hand (maximum of F over X) should raise an error
> on an empty X. I know there are other options, but you chose to
> raise an error so that's the design I was talking about.

It can be done by a Boolean flag.

>>> That was definitely the way things were done in the 80s.
>>
>> Yes, before the Dark Ages of Computing...
>
> Eh? There have been repeated updates to the Ada language. Are they
> taking Ada into the dark ages? If so, what was the golden age of Ada
> when its design was perfect for numerical algorithms?

I meant the state of computing as a whole.

(Ada is a niche language and "hordes of barbarians" largely missed its
existence... (:-))

>>>> As I said you think in a wrong direction of abstracting the language
>>>> "finding maximum" rather than the problem space, e.g. generalization to
>>>> other bases, other mathematical structures etc.
>>> Generalising to an arbitrary base is local to the function that finds
>>> the answer for one element. It's an entirely separate axis of
>>> generalisation to that of where the elements come from.
>>> It's interesting to me that you consider one simply wrong and the other
>>> natural.
>>
>> Because one is a software design artifact and another is the result of
>> problem space analysis.
>
> Which one the wrong one?

None automatically is. The point is avoiding overdesigning a numeric puzzle.

[...]
> This is probably the closest we can get to a universal solution.
> Vectors don't have a Key function but I am sure I could find out what
> should be provided there.

Vector has To_Index for Key.

In general, note that Ada does not require you to use any library. I
personally dislike cursors in particular because of their "functional"
style. I prefer plain element position and loop iteration of ordered
structures. A container library based on this paradigm would use other
generic abstraction.

Furthermore, I prefer dynamic polymorphism of tagged types over
parametric one of generics. Therefore to me Maximum_At should rather be
a class-wide or primitive operation than a generic.

In Ada you have freedom to choose your way, which also massively reduces
universality of any abstraction, which will never apply universally.

I would like to have means to deal with this problem by means of ad-hoc
supertypes, but that will never happen due to lack of interest in
reworking the language type system and because in "Dark Ages" there is
virtually no research on fundamental language construction topics.

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

On 2023-09-09 10:13, G.B. wrote:

> The "apparatus" that the computation needs in order to remember
> "max so far" looks like part of its state to me. Somehow
> "the function" needs to operate this state and evaluate it.

You can hide explicit state using recursion.

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

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

> On 2023-09-10 03:20, Ben Bacarisse wrote:
>> "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> writes:
>>
>>> On 2023-09-09 02:25, Ben Bacarisse wrote:
>>>> "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> writes:

>>>>> As I said you think in a wrong direction of abstracting the language
>>>>> "finding maximum" rather than the problem space, e.g. generalization to
>>>>> other bases, other mathematical structures etc.
>>>> Generalising to an arbitrary base is local to the function that finds
>>>> the answer for one element. It's an entirely separate axis of
>>>> generalisation to that of where the elements come from.
>>>> It's interesting to me that you consider one simply wrong and the other
>>>> natural.
>>>
>>> Because one is a software design artifact and another is the result of
>>> problem space analysis.
>> Which one the wrong one?
>
> None automatically is. The point is avoiding overdesigning a numeric
> puzzle.

Ah, I thought your criticise was intended to be general -- that
"abstracting the language 'finding maximum' rather than the problem
space" was always wrong, but it seems you meant only in the case of a
puzzle like this. Numeric puzzles like this should only be generalised
in a few "approved" directions?

Obviously I disagree. I would probably not bother doing this sort of
puzzle if it did not spark thoughts that go well beyond getting the
answer and a few obvious variation like using a different base.

Because I am interested in programming languages in general I always
solve such puzzles in more than one language so I can see how well they
express the algorithms involved.

Since prime numbers are crucial here, I had already tried a couple of
prime sieves in one of my solutions. In that Ada solution, I would
probably have to store the primes somewhere and maximise over that.
That's what got me thinking about a general "maximise F over X" function
because if Ada had a simple way to do that, I could try various ways to
write the sieve -- the primes might end up in an array, a set or a map,
and it would make no difference to the rest of the code.

But the conclusion seems to be that maximising over any container is
just too simple to be worth making it a reusable component in Ada. And
even then it would not (as far as I can tell) work for native arrays.

> [...]
>> This is probably the closest we can get to a universal solution.
>> Vectors don't have a Key function but I am sure I could find out what
>> should be provided there.
>
> Vector has To_Index for Key.
>
> In general, note that Ada does not require you to use any library. I
> personally dislike cursors in particular because of their "functional"
> style. I prefer plain element position and loop iteration of ordered
> structures. A container library based on this paradigm would use other
> generic abstraction.
>
> Furthermore, I prefer dynamic polymorphism of tagged types over parametric
> one of generics. Therefore to me Maximum_At should rather be a class-wide
> or primitive operation than a generic.

I was looking for whatever design you thought best, since you know Ada
infinitely better that I do. It would be a shame if something I said
has ended up causing you to propose solutions you don't think are the
best ones for this example.

> In Ada you have freedom to choose your way, which also massively reduces
> universality of any abstraction, which will never apply universally.

That's a strange remark. You have to do things the Ada way. The
freedom is only in choosing how to combine the specific tools in Ada's
toolbox, and Ada also constrains how the tools can be combined. This is
true for any programming language. None of then give you the freedom
choose your way unless your way already aligns with what it permitted!

> I would like to have means to deal with this problem by means of ad-hoc
> supertypes, but that will never happen due to lack of interest in reworking
> the language type system and because in "Dark Ages" there is virtually no
> research on fundamental language construction topics.

I don't believe that to be the case. I can believe that there is little
research into overhauling Ada's type system, but not in general.

--
Ben.

On 2023-09-10 21:22, Ben Bacarisse wrote:
> "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> writes:
>
>> On 2023-09-10 03:20, Ben Bacarisse wrote:
>>> "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> writes:
>>>
>>>> On 2023-09-09 02:25, Ben Bacarisse wrote:
>>>>> "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> writes:
>
>>>>>> As I said you think in a wrong direction of abstracting the language
>>>>>> "finding maximum" rather than the problem space, e.g. generalization to
>>>>>> other bases, other mathematical structures etc.
>>>>> Generalising to an arbitrary base is local to the function that finds
>>>>> the answer for one element. It's an entirely separate axis of
>>>>> generalisation to that of where the elements come from.
>>>>> It's interesting to me that you consider one simply wrong and the other
>>>>> natural.
>>>>
>>>> Because one is a software design artifact and another is the result of
>>>> problem space analysis.
>>> Which one the wrong one?
>>
>> None automatically is. The point is avoiding overdesigning a numeric
>> puzzle.
>
> Ah, I thought your criticise was intended to be general -- that
> "abstracting the language 'finding maximum' rather than the problem
> space" was always wrong, but it seems you meant only in the case of a
> puzzle like this. Numeric puzzles like this should only be generalised
> in a few "approved" directions?

Yes, in the direction of numeric problem space. Universal finding
maximum is another problem space, e.g. a container library design etc.

> Since prime numbers are crucial here, I had already tried a couple of
> prime sieves in one of my solutions. In that Ada solution, I would
> probably have to store the primes somewhere and maximise over that.
> That's what got me thinking about a general "maximise F over X" function
> because if Ada had a simple way to do that, I could try various ways to
> write the sieve -- the primes might end up in an array, a set or a map,
> and it would make no difference to the rest of the code.

And this is exactly wrong. You should think about whether storing
represents an issue, e.g. in terms of performance and/or space. If it
does you should consider suitable implementation of storage that
provides required overall performance of needed operations, like
insertion, search, cleaning up etc.

> But the conclusion seems to be that maximising over any container is
> just too simple to be worth making it a reusable component in Ada. And
> even then it would not (as far as I can tell) work for native arrays.

You do not need *any* container. You need a container, just one.

>> [...]
>>> This is probably the closest we can get to a universal solution.
>>> Vectors don't have a Key function but I am sure I could find out what
>>> should be provided there.
>>
>> Vector has To_Index for Key.
>>
>> In general, note that Ada does not require you to use any library. I
>> personally dislike cursors in particular because of their "functional"
>> style. I prefer plain element position and loop iteration of ordered
>> structures. A container library based on this paradigm would use other
>> generic abstraction.
>>
>> Furthermore, I prefer dynamic polymorphism of tagged types over parametric
>> one of generics. Therefore to me Maximum_At should rather be a class-wide
>> or primitive operation than a generic.
>
> I was looking for whatever design you thought best, since you know Ada
> infinitely better that I do.

The best design is plain loop.

> It would be a shame if something I said
> has ended up causing you to propose solutions you don't think are the
> best ones for this example.

My understanding was that you wanted to see how to use the Ada standard
library containers with generics.

Generic programming in Ada (programming in terms of sets of types) is a
huge, almost infinite topic. One should be rather specific.

>> In Ada you have freedom to choose your way, which also massively reduces
>> universality of any abstraction, which will never apply universally.
>
> That's a strange remark. You have to do things the Ada way. The
> freedom is only in choosing how to combine the specific tools in Ada's
> toolbox, and Ada also constrains how the tools can be combined.

There are more than one way to skin a cat in Ada. You can choose one
drawer in the Ada toolbox and feel comfortable with what it provides all
your life.

"Ada way" among Ada users rather refers to an approach to software
engineering in general. Like upfront specification, separation and
careful design of interfaces, modular design, problem space driven
choice of types, earliest possible error detection etc.

>> I would like to have means to deal with this problem by means of ad-hoc
>> supertypes, but that will never happen due to lack of interest in reworking
>> the language type system and because in "Dark Ages" there is virtually no
>> research on fundamental language construction topics.
>
> I don't believe that to be the case. I can believe that there is little
> research into overhauling Ada's type system, but not in general.

I am not aware of any substantial contributions since Cardelli etc.
Recently designed languages represent a pitiful mess of old wrong ideas
in an ongoing competition to create something more flawed than K&R C...

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

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

> On 2023-09-10 21:22, Ben Bacarisse wrote:
>> "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> writes:
>>
>>> On 2023-09-10 03:20, Ben Bacarisse wrote:
>>>> "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> writes:
>>>>
>>>>> On 2023-09-09 02:25, Ben Bacarisse wrote:
>>>>>> "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> writes:
>>
>>>>>>> As I said you think in a wrong direction of abstracting the language
>>>>>>> "finding maximum" rather than the problem space, e.g. generalization to
>>>>>>> other bases, other mathematical structures etc.
>>>>>> Generalising to an arbitrary base is local to the function that finds
>>>>>> the answer for one element. It's an entirely separate axis of
>>>>>> generalisation to that of where the elements come from.
>>>>>> It's interesting to me that you consider one simply wrong and the other
>>>>>> natural.
>>>>>
>>>>> Because one is a software design artifact and another is the result of
>>>>> problem space analysis.
>>>> Which one the wrong one?
>>>
>>> None automatically is. The point is avoiding overdesigning a numeric
>>> puzzle.
>> Ah, I thought your criticise was intended to be general -- that
>> "abstracting the language 'finding maximum' rather than the problem
>> space" was always wrong, but it seems you meant only in the case of a
>> puzzle like this. Numeric puzzles like this should only be generalised
>> in a few "approved" directions?
>
> Yes, in the direction of numeric problem space. Universal finding maximum
> is another problem space, e.g. a container library design etc.

Noted! I will try to guess what generalisations you might approve of
in future :-)

>> Since prime numbers are crucial here, I had already tried a couple of
>> prime sieves in one of my solutions. In that Ada solution, I would
>> probably have to store the primes somewhere and maximise over that.
>> That's what got me thinking about a general "maximise F over X" function
>> because if Ada had a simple way to do that, I could try various ways to
>> write the sieve -- the primes might end up in an array, a set or a map,
>> and it would make no difference to the rest of the code.
>
> And this is exactly wrong.

In Ada. It works well in some other languages for reasons I'll explain
just below.

> You should think about whether storing
> represents an issue, e.g. in terms of performance and/or space. If it does
> you should consider suitable implementation of storage that provides
> required overall performance of needed operations, like insertion, search,
> cleaning up etc.

Yes, in Ada. Since I can't use universal algorithms, it pays to decide
all this first because changes will be costly. But in some other
languages I can try various schemes and measure or profile to see what
time/space trade-offs there are between different designs. This is
easiest when I don't have to worry about all the changes that simply
switching from, say, a list to an array will incur.

>> But the conclusion seems to be that maximising over any container is
>> just too simple to be worth making it a reusable component in Ada. And
>> even then it would not (as far as I can tell) work for native arrays.
>
> You do not need *any* container. You need a container, just one.

Yes, in Ada. The cost of changing a design is going to be
non-negligible, so we must make sure you get it right before too much
code is written.

>>> [...]
>>>> This is probably the closest we can get to a universal solution.
>>>> Vectors don't have a Key function but I am sure I could find out what
>>>> should be provided there.
>>>
>>> Vector has To_Index for Key.
>>>
>>> In general, note that Ada does not require you to use any library. I
>>> personally dislike cursors in particular because of their "functional"
>>> style. I prefer plain element position and loop iteration of ordered
>>> structures. A container library based on this paradigm would use other
>>> generic abstraction.
>>>
>>> Furthermore, I prefer dynamic polymorphism of tagged types over parametric
>>> one of generics. Therefore to me Maximum_At should rather be a class-wide
>>> or primitive operation than a generic.
>> I was looking for whatever design you thought best, since you know Ada
>> infinitely better that I do.
>
> The best design is plain loop.

Yes, in Ada.

>> It would be a shame if something I said
>> has ended up causing you to propose solutions you don't think are the
>> best ones for this example.
>
> My understanding was that you wanted to see how to use the Ada standard
> library containers with generics.

Well that's what it turned out to be. At first I did not know that
built-in types like arrays can't be covered in the same way.

> Generic programming in Ada (programming in terms of sets of types) is a
> huge, almost infinite topic. One should be rather specific.

Sorry. I was hoping that generalising from a range to an array or some
other container would not be the huge topic it turned out to be.

>>> In Ada you have freedom to choose your way, which also massively reduces
>>> universality of any abstraction, which will never apply universally.
>> That's a strange remark. You have to do things the Ada way. The
>> freedom is only in choosing how to combine the specific tools in Ada's
>> toolbox, and Ada also constrains how the tools can be combined.
>
> There are more than one way to skin a cat in Ada. You can choose one drawer
> in the Ada toolbox and feel comfortable with what it provides all your
> life.
>
> "Ada way" among Ada users rather refers to an approach to software
> engineering in general. Like upfront specification, separation and careful
> design of interfaces, modular design, problem space driven choice of types,
> earliest possible error detection etc.

Yes, I remember the 80s! It's rare to have specifications that don't
change these days. And general remarks like "problem space driven
choice of types" apply to all languages. What matters is what types the
language offers, and what the interfaces to those types are.

>>> I would like to have means to deal with this problem by means of ad-hoc
>>> supertypes, but that will never happen due to lack of interest in reworking
>>> the language type system and because in "Dark Ages" there is virtually no
>>> research on fundamental language construction topics.
>> I don't believe that to be the case. I can believe that there is little
>> research into overhauling Ada's type system, but not in general.
>
> I am not aware of any substantial contributions since Cardelli
> etc. Recently designed languages represent a pitiful mess of old wrong
> ideas in an ongoing competition to create something more flawed than K&R
> C...

Forgive me, but that does not appear to be a well-informed option. You
may be bang up to date as far as research into programming language type
systems is concerned, but that reply does no read as if it were written
by someone who is.

--
Ben.

On 2023-09-11 18:13, Ben Bacarisse wrote:
> "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> writes:
>
>> On 2023-09-10 21:22, Ben Bacarisse wrote:
>>> "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> writes:

>> You should think about whether storing
>> represents an issue, e.g. in terms of performance and/or space. If it does
>> you should consider suitable implementation of storage that provides
>> required overall performance of needed operations, like insertion, search,
>> cleaning up etc.
>
> Yes, in Ada. Since I can't use universal algorithms, it pays to decide
> all this first because changes will be costly.

There are no universally applicable algorithms.

> But in some other
> languages I can try various schemes and measure or profile to see what
> time/space trade-offs there are between different designs.

So you can in Ada.

> This is
> easiest when I don't have to worry about all the changes that simply
> switching from, say, a list to an array will incur.

Measuring performance is not a simple task. Switching from the visitor
pattern to loop is your least problem.

>>> But the conclusion seems to be that maximising over any container is
>>> just too simple to be worth making it a reusable component in Ada. And
>>> even then it would not (as far as I can tell) work for native arrays.
>>
>> You do not need *any* container. You need a container, just one.
>
> Yes, in Ada. The cost of changing a design is going to be
> non-negligible, so we must make sure you get it right before too much
> code is written.

Right, because in that case you would have some non-trivial issue. So it
would take much more efforts than merely calling a different function.
There is an inherent difference between dealing with real size and
complexity projects and hobby examples like this puzzle. The overhead
you get from Ada pays off in programming en large. That was intentional
language design.

>>> It would be a shame if something I said
>>> has ended up causing you to propose solutions you don't think are the
>>> best ones for this example.
>>
>> My understanding was that you wanted to see how to use the Ada standard
>> library containers with generics.
>
> Well that's what it turned out to be. At first I did not know that
> built-in types like arrays can't be covered in the same way.

I know no language where primitive built-in types may have classes. That
is the major problem with type systems that they have first, second and
third class citizens. Ada arrays (and fixed strings) are in a different
basket than containers.

>> Generic programming in Ada (programming in terms of sets of types) is a
>> huge, almost infinite topic. One should be rather specific.
>
> Sorry. I was hoping that generalising from a range to an array or some
> other container would not be the huge topic it turned out to be.

Unfortunately it is, because nobody knows how to design a type system
where proper arrays, that is one you could pass to a system library
function written in C, can be dealt with in the same manner as a
container in some polymorphic body. A mainstream choice is not to have
proper arrays in the language at all. Then, logically, just forget that
they exist in Ada. Problem solved!

>>>> In Ada you have freedom to choose your way, which also massively reduces
>>>> universality of any abstraction, which will never apply universally.
>>> That's a strange remark. You have to do things the Ada way. The
>>> freedom is only in choosing how to combine the specific tools in Ada's
>>> toolbox, and Ada also constrains how the tools can be combined.
>>
>> There are more than one way to skin a cat in Ada. You can choose one drawer
>> in the Ada toolbox and feel comfortable with what it provides all your
>> life.
>>
>> "Ada way" among Ada users rather refers to an approach to software
>> engineering in general. Like upfront specification, separation and careful
>> design of interfaces, modular design, problem space driven choice of types,
>> earliest possible error detection etc.
>
> Yes, I remember the 80s! It's rare to have specifications that don't
> change these days.

I remember a book on structured programming from 80's describing exactly
the way programs are written today as an example how projects are doomed
to fail. As I said, Dark Ages.

> And general remarks like "problem space driven
> choice of types" apply to all languages.

In most languages there is no choice because all scalar types are
predefined.

> What matters is what types the
> language offers, and what the interfaces to those types are.

That does not matter at all. Matters the type algebra by which
programmer can create types suitable to model the problem space entities.

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

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

> On 2023-09-11 18:13, Ben Bacarisse wrote:
>> "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> writes:

>>> You should think about whether storing
>>> represents an issue, e.g. in terms of performance and/or space. If it does
>>> you should consider suitable implementation of storage that provides
>>> required overall performance of needed operations, like insertion, search,
>>> cleaning up etc.
>>
>> Yes, in Ada. Since I can't use universal algorithms, it pays to decide
>> all this first because changes will be costly.
>
> There are no universally applicable algorithms.

This may be just a case where we are using terms to refer to different
things. I find it hard to believe you don't know what I am referring to
since we've had a productive exchange examining an example in detail,
but I can agree it's not a good term. I simply could not come up with a
better one on the fly.

So I'll re-phrase it avoiding the disputed term: simple fibledychops are
not available to the Ada programmer, but they are available in some
other languages. I suspect you are not interested in what simple
fibledychops are, since their absence from Ada means they are not of any
importance (and may even be, in your opinion, detrimental to writing
good programs). If you really want to know what a fibledychop is, I can
have a go at saying more about what they it, but would that be
worthwhile? I think you are sure they are a bad idea already.

>>> My understanding was that you wanted to see how to use the Ada standard
>>> library containers with generics.
>>
>> Well that's what it turned out to be. At first I did not know that
>> built-in types like arrays can't be covered in the same way.
>
> I know no language where primitive built-in types may have classes.

Haskell's type classes are very nice -- every type belongs to one or
more classes that determine the permitted operations. And in some
languages there are essentially no "built-in" types. In ML for example,
the interface to arrays is defined in ML so they can support a universal
set of operations shared with many other types, but they are usually
implemented by the run-time environment for speed.

>> What matters is what types the
>> language offers, and what the interfaces to those types are.
>
> That does not matter at all. Matters the type algebra by which programmer
> can create types suitable to model the problem space entities.

Yes, but... First, almost every language comes with some predefined
types. If the problem space needs fast indexed access to a set of
entities, we don't usually have to define our own arrays or vectors.
It's so often needed that we expect something to be provided, so what
types the language offers /does/ matter. Secondly, the problem space
has two components -- data and actions on that data. I suspect by
"problem space entities" you mean just the data because that what Ada
focuses on. But programming languages can offer tool that help to model
the actions in the problem space as well.

--
Ben.

On 2023-09-13 14:24, Ben Bacarisse wrote:
> "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> writes:
>
>> On 2023-09-11 18:13, Ben Bacarisse wrote:
>>> "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> writes:
>
>>>> You should think about whether storing
>>>> represents an issue, e.g. in terms of performance and/or space. If it does
>>>> you should consider suitable implementation of storage that provides
>>>> required overall performance of needed operations, like insertion, search,
>>>> cleaning up etc.
>>>
>>> Yes, in Ada. Since I can't use universal algorithms, it pays to decide
>>> all this first because changes will be costly.
>>
>> There are no universally applicable algorithms.
>
> This may be just a case where we are using terms to refer to different
> things. I find it hard to believe you don't know what I am referring to
> since we've had a productive exchange examining an example in detail,
> but I can agree it's not a good term. I simply could not come up with a
> better one on the fly.
>
> So I'll re-phrase it avoiding the disputed term: simple fibledychops are
> not available to the Ada programmer, but they are available in some
> other languages. I suspect you are not interested in what simple
> fibledychops are, since their absence from Ada means they are not of any
> importance (and may even be, in your opinion, detrimental to writing
> good programs). If you really want to know what a fibledychop is, I can
> have a go at saying more about what they it, but would that be
> worthwhile? I think you are sure they are a bad idea already.

Each language feature has a purpose. Roughly it is called language
paradigm: how routine programming activities are approached when using
the language. Ada's paradigm is different from what you expect. E.g.
sunroof might be a simple car feature, but a submarine user would not be
impressed.

>>>> My understanding was that you wanted to see how to use the Ada standard
>>>> library containers with generics.
>>>
>>> Well that's what it turned out to be. At first I did not know that
>>> built-in types like arrays can't be covered in the same way.
>>
>> I know no language where primitive built-in types may have classes.
>
> Haskell's type classes are very nice -- every type belongs to one or
> more classes that determine the permitted operations.

No difference to Ada. Integer belongs to an integer class and there is a
formal generic type for the class members. The problem I am talking
about is that there is no run-time objects of and no non-integer type
can be put in that class.

> In ML for example,
> the interface to arrays is defined in ML so they can support a universal
> set of operations shared with many other types, but they are usually
> implemented by the run-time environment for speed.

Can I take integer type, derive a new *integer* type from it such that
it would also implement an array interface? So that I could access
integer decimal digits? Or use your "fibledychops" with on it?

This is impossible in Ada. Which is in particular why Ada ordered
containers do not implement array interface. They simply cannot.

Ada has a generic array interface declared as

generic
type Index_Type is ...
type Element_Type is ...
type Array_Type is array (Index_Type range <>) of Element_Type;

but even that is not implementable by anything except by a proper array.

Yes, there is an ugly iterator hack Georg mentioned in another thread.
The hack allows containers to *look* like arrays in syntax, e.g. you can
loop and index a container this way.

This is possibly what you meant referencing ML. But I do not know ML.

>>> What matters is what types the
>>> language offers, and what the interfaces to those types are.
>>
>> That does not matter at all. Matters the type algebra by which programmer
>> can create types suitable to model the problem space entities.
>
> Yes, but... First, almost every language comes with some predefined
> types. If the problem space needs fast indexed access to a set of
> entities, we don't usually have to define our own arrays or vectors.

Index and element types always same?

When I derive a new type from the array element type, would an array of
such elements related to an array of base element type? Can I control
the decision? Can I have an array of elements from both element types?
How such arrays are related to the specific element type arrays. Then
add the index types hierarchy to the picture...

You would say: uninterested. So I am in "fibledychops"... (:-))

> Secondly, the problem space
> has two components -- data and actions on that data. I suspect by
> "problem space entities" you mean just the data because that what Ada
> focuses on.

No, in Ada it is both. You can add "free functions" as you wish,
anytime, anywhere. It is the classes and their primitive operations (AKA
methods) that pose problems.

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

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

....

I feel it's time to draw this to a close, so I'll just say thank you for
your time. I didn't want you to think I hadn't read your post, but I
think we're starting to repeat ourselves. The only new technical
matters were some questions about ML's type system and that would be
getting very far off-topic for this group.

I always enjoy getting a different perspective on such topics. I hope
you do to.

--
Ben.

On Thursday, September 7, 2023 at 3:31:12 PM UTC+8, Francesc Rocher wrote:
> El dia dilluns, 4 de setembre de 2023 a les 11:19:53 UTC+2, CSYH (QAQ) va escriure:
> > I am new to Ada, I know is there a good way to start this program?
> > thanks
> > https://projecteuler.net/problem=26
> Hi CSHY,
>
> Please take a look at my Euler tools repository, https://github.com/rocher/euler_tools (not the best math lib you'll find, I know).
> I used this library tools to solve problem 26 here: https://github.com/rocher/alice-project_euler-rocher
> Let me know what you think.
sorry for reply so late. I just do not know how to install the lib to my GNAT.