Problem with generic linked list package

Problem with generic linked list package

[Laurent]

Hi

As an exercise from my favorite Ada book I have to modify the linked list package into a generic one. 
Not very complicated I got nearly everything done. 

Test program and generic linked list package: https://github.com/Chutulu/Chapter-15.git

The only problem I have is with the Display procedure.

The author gives the ads file the rest is left as exercise.

Just below he explains that the Display procedure needs to be adapted.

Subtype Name_Type is String (1..20);

procedure Display_String (Item : in Name_Type) is
   begin -- Display_String
      Ada.Text_IO.Put (Item => Item);
      Ada.Text_IO.New_Line;
   end Display_String;

and then use it to instantiate the generic list with it.

   package GL is new Linked_Lists_Generic (Element_Type    => Name_Type,
                                           Display_Element => Display_String );

If I need a list with Integers I only have to change the Display procedure and everything is fine. No need to modify the list package. 

I have put that into my test program and the instantiation works so far.

If I want to print the content of my list using simply Display_String (L1); it fails because the procedure expects a String and gets a list. That is clear.

If I use GL.Display_String (L1); I get an error that Display_string is not declared in GL. Clear too. 

(1)Now I just don't know how to get it to work. Comments are welcome.

(2)How would Display_String iterate over the whole list? The Display procedure given in the book for the linked list is a recursive version. I have changed it to an iterative version, I think it was even asked as an exercise too.

So the given Display_String wouldn't work and I need to use my own version and just adapt it?

Would be very happy if I get this package to work because it is needed for the next exercises.

Thanks

Laurent

Re: Problem with generic linked list package

[Jacob Sparre Andersen]

Laurent <daemon2@internet.lu> writes:

> As an exercise from my favorite Ada book I have to modify the linked
> list package into a generic one.  Not very complicated I got nearly
> everything done.
>
> Test program and generic linked list package:
> https://github.com/Chutulu/Chapter-15.git
>
> The only problem I have is with the Display procedure.

What is the problem with the Display procedure (except that you have
commented it out)?

Greetings,

Jacob
-- 
"I remember being impressed with Ada because you could write
 an infinite loop without a faked up condition. The idea
 being that in Ada the typical infinite loop would normally
 be terminated by detonation."                 -- Larry Wall

Re: Problem with generic linked list package

[Laurent]

In this case none. Except that I need to adapt "Word" to "Element_Type".

But if I have correctly understood the paragraph in the book following the spec of the generic package, the idea is to define the display procedure in the client program, in this case the test_linked_list_generic or the other way around. Not writing this from computer so no access to my files. 

So if Element_Type would be a record, I just have to provide in the client program a display procedure for this record and I don't have to modify the generic linked list package. 

The author has given an little example of the used subtype, display proc. and how to instantiate it but not the whole implementation of the package body or the test program on how to use the whole thing.

So I am a bit lost as it doesn't work as I think it should but that's probably because I am just guessing and have actually no idea what I am doing. 

So if someone wants to spoonfeed me with a few more information I would be very happy.

Not a fan of that approach but in this case I have no idea how to keep the list package generic. 

Thanks

Laurent

Re: Problem with generic linked list package

[Stephen Leake]

Laurent <daemon2@internet.lu> writes:

> procedure Display_String (Item : in Name_Type) is
>    begin -- Display_String
>       Ada.Text_IO.Put (Item => Item);
>       Ada.Text_IO.New_Line;
>    end Display_String;

Linked_Lists_Generic.Display must call Display_Element, not Ada.Text_IO.Put.

> (1)Now I just don't know how to get it to work. Comments are welcome.

You need to add Display to the Linked_Lists_Generic spec, and call it.

-- 
-- Stephe

Re: Problem with generic linked list package

[Laurent]

Hi

@Stephen 
Thanks that information helped me very much. I thought that I didn't need anylonger a display proc. in the body of the generic packague. Quite elegant and at the same time a bit of a spaghuetti.

Thanks

Laurent

Re: Problem with generic linked list package

[Laurent]

Hi

I have added an Insert_In_Order procedure to my generic package.

The normal version given by the book is working.

I have modified "Word" to "Element" so that it is generic.
Compiler wasn't happy because "<" and ">=" were not defined for Element_Type.
Ok so I added 


function "<" (Left,Right: Element_Type) return Boolean is
  begin
      return Left< Right;
   end "<";

function ">=" (Left,Right: Element_Type) return Boolean is
  begin
      return Left>= Right;
   end ">=";

I got a warning about infinite recursion and the possibility of a stack overflow.

So I tested the package and I got a stack overflow.

I changed the 2 operators to:

function "<" (Left, Right : Element_Type) return Boolean is
   begin
      if Left < Right then
         return True;
      else
         return False;
      end if;
   end "<";

function ">=" (Left, Right : Element_Type) return Boolean is
   begin
      if Left >= Right then
         return True;
      else
         return False;
      end if;
   end ">=";

The warnings are gone but not the stack overflow.

The test program dies as soon as it gets to if Element < Head....

https://github.com/Chutulu/Chapter-15.git

Result of test_generic_linked_list.adb:

Content of L3
List is empty

inserting 5000 in L3
Content of L3
5000. . .

inserting 123 in L3

raised STORAGE_ERROR : stack overflow

[2014-08-07 21:05:15] process exited with status 1, elapsed time: 00.61s

Why do I get this error ?

Thanks

Laurent

Re: Problem with generic linked list package

[Adam Beneschan]

On Thursday, August 7, 2014 12:07:15 PM UTC-7, Laurent wrote:

> Compiler wasn't happy because "<" and ">=" were not defined for Element_Type.
> Ok so I added 

> function "<" (Left,Right: Element_Type) return Boolean is
>   begin
>       return Left< Right;
>    end "<";


The expression "Left < Right" just causes the function to call itself recursively.  What did you want it to do?  (The same kind of problem exists in other places.)

                           -- Adam

Re: Problem with generic linked list package

[Adam Beneschan]

I responded a bit too quickly, so here's a bit more of an explanation:

On Thursday, August 7, 2014 12:21:52 PM UTC-7, Adam Beneschan wrote:
> On Thursday, August 7, 2014 12:07:15 PM UTC-7, Laurent wrote:

> > function "<" (Left,Right: Element_Type) return Boolean is
> >   begin
> >       return Left< Right;
> >    end "<";
> 
The expression "Left < Right" just causes the "<" function to call itself recursively.  Changing it to

   function "<" (Left, Right : Element_Type) return Boolean is 
   begin 
      if Left < Right then 
         return True; 
      else 
         return False; 
      end if; 
   end "<"; 

doesn't help at all.  The function still calls itself recursively. 

When you wrote "Left < Right", what "<" were you hoping it would use?

                              -- Adam

Re: Problem with generic linked list package

[Laurent]

I thought that if the package was instantiated with an integer for element_type, "<" defined for element_type would "see" that oh yes I know how to compare 2 integers and use the "<" defined in the standart package for integers. Same for char, float whatever.

Didn't think that "<" element_type could be chasing his own tail.

Perhaps I am just to naive to believe that the compiler knows  what I want to do.

Re: Problem with generic linked list package

[Adam Beneschan]

On Thursday, August 7, 2014 3:20:00 PM UTC-7, Laurent wrote:
> I thought that if the package was instantiated with an integer for element_type, "<" defined for element_type would "see" that oh yes I know how to compare 2 integers and use the "<" defined in the standart package for integers. Same for char, float whatever.

This is how generics are in Ada.  The compiler needs to know when it's compiling the generic, *before* the generic is instantiated, whether it can compare the types.  Since you said

    type Element_Type is private;

this means Element_Type can be any type (almost), and the compiler therefore won't know whether the type's values can be compared.  If you had said

    type Element_Type is range <>;

then Element_Type could only be instantiated with an integer type, and therefore the compiler would know that the values *can* be compared.  But this isn't the case with a "private" generic type.  Since the compiler can't confirm, when the body is compiled, whether there will be a "<" for the type, the compiler won't let you use "<".  That's what Shark8's solution does: it guarantees that there will be "<" and "=" functions for your type.  When you instantiate the generic, you have the choice of supplying some functions to be used for "<" or "=" (which can be a different name), or if you don't, it will look to see if "<" and "=" are defined.  And if they're not (if you pass it a record type that you haven't defined "<" for), the instantiation will be illegal.


> Didn't think that "<" element_type could be chasing his own tail.

When you write

   function "<" (Left, Right : Element_Type) return Boolean is
   begin
      if Left < Right then ...

Even if there were a "<" defined outside, this would still be infinite recursion, because of Ada's rules about visibility.  It's the same as if you wrote 

   procedure Some_Procedure (X : Integer) is
   begin
        Some_Procedure (X);
        ...

Even if there were some other Some_Procedure somewhere else that could be called, inside the body of Some_Procedure, the name Some_Procedure means itself.  Same for "<".  Inside the body of "<", the < symbol means that function itself (when it's called on the same types of arguments).  There are ways around this, though, for example:

   procedure Some_Procedure (X : Integer) is
   begin
        Some_Other_Package.Some_Procedure (X);
        ...

> 
> 
> Perhaps I am just to naive to believe that the compiler knows  what I want to do.

Compilers are not allowed to read minds.  That would be very bad, because it's important to have well-defined rules about what your code means.  If I put something into a Google search, sometimes Google makes some assumptions about what it thinks I *really* want, but it's OK because if it's wrong, I can just try again.  But it would be bad if compilers were allowed to do that--you could distribute a program but have no idea what it really does, since there wouldn't be any clear rules about how the compiler interprets your code.

                               -- Adam

Re: Problem with generic linked list package

[Laurent]

@Adam: thanks for this detailed answer. 

I'll try to get this working when I'm at home again.

Thanks

Laurent

Re: Problem with generic linked list package

[Laurent]

Hi

My Insert_In_Order test works now but honestly I have to admit that I don't understand why it works.

   with function "<"(Left, Right : Element) return Boolean is <>; 
   with function "="(Left, Right : Element) return Boolean is <>; 

There is no "<" and "=" defined for Element_Type, normally. So the "<>" seems to do the trick but why?
The box tells the compiler that it will get the info it needs later. But in this case there is no later, isn't it?

There are 3,5 lines of code compared to what I have tried before. So for me it looks like magic^^.
So if someone could enlighten me I would be quite happy.

Thanks

Laurent

Re: Problem with generic linked list package

[AdaMagica]

There is a declaration of Element before the functions:

     type Element is private;
>
>    with function "<"(Left, Right : Element) return Boolean is <>; 
>    with function "="(Left, Right : Element) return Boolean is <>; 
>
> There is no "<" and "=" defined for Element_Type, normally. So the "<>" seems to do the trick but why?
>
> The box tells the compiler that it will get the info it needs later. But in this case there is no later, isn't it?

There is a later indeed! It's when and where you instantiate the generic.

The actual type for Element you use to instantiate must have functions < and =. If not, the instantiation is illegal. The box <> tells the compiler: "Look at the place of the instantiation for those functions. If they exist, take them; if they don't exist, don't accept the instantiation."

Re: Problem with generic linked list package

[Jeffrey Carter]

On 08/09/2014 07:32 AM, Laurent wrote:
>
>     with function "<"(Left, Right : Element) return Boolean is <>;
>     with function "="(Left, Right : Element) return Boolean is <>;
>
> There is no "<" and "=" defined for Element_Type, normally. So the "<>" seems to do the trick but why?
> The box tells the compiler that it will get the info it needs later. But in this case there is no later, isn't it?

The box means, if no explicit actual subprogram is provided, and there is 
visible at the point of instantiation a subprogram with the same name and the 
same parameter and return type profile (substituting the actual for Element), 
then the instantiation will use that visible subprogram.

You can still provide an explicit actual subprogram:

"<" => "<"

"=" => Equal

Now, suppose you have a type T for which "<" is not meaningful. You want to have 
a linked list of T, but will never use Insert_In_Order. Can you still use your 
package to do this? If not, how could you change your package to support this, 
while still providing Insert_In_Order for types with "<"?

-- 
Jeff Carter
"Insufficient laughter--that's grounds for divorce."
Play It Again, Sam
126

Re: Problem with generic linked list package

[Shark8]

On 09-Aug-14 08:32, Laurent wrote:
>     with function "<"(Left, Right : Element) return Boolean is <>;
>     with function "="(Left, Right : Element) return Boolean is <>;
>
> There is no "<" and "=" defined for Element_Type, normally. So the "<>"
> seems to do the trick but why?
> The box tells the compiler that it will get the info it needs later.
> But in this case there is no later, isn't it?

Nope; the "is <>" tells the compiler that the function named doesn't 
have to be explicitly named in the instantiation *if it is visible*.

This means that the above 'automatically' uses "<" and '=' at the point 
of instantiation (if there's a conformant function that's visible).

Re: Problem with generic linked list package

[Laurent]

>Now, suppose you have a type T for which "<" is not meaningful. You want to have 
>a linked list of T, but will never use Insert_In_Order. Can you still use your 
>package to do this? If not, how could you change your package to support this, 
>while still providing Insert_In_Order for types with "<"? 

Yes indeed if Element would be a record then insert_in_order wouldn't work as it is. Because "<" and "=" don't exist for this type. Perhaps if I compared the components of the record I would but for now I don't see how I would do that. Problem for later when I have to use my package for a real program.

Otherwise I have some procedures which just add the Element to the front/end but the list wouldn't be sorted.  

"with function "<"(Left, Right : Element) return Boolean is <>; " That was introduced with Ada 2005?

Because the book I learn from is about Ada 95 and I don't remember having seen a similar construction or already forgotten. I have both versions of John Barnes (2005/2012) but for me it feels like learning to use a phone from the phone book so I prefer the Ada 95 one which uses a more practical examples to explain.

Thanks @everyone for the explanations.

Laurent

Re: Problem with generic linked list package

[Jeffrey Carter]

On 08/09/2014 02:53 PM, Laurent wrote:
>
> "with function "<"(Left, Right : Element) return Boolean is <>; " That was introduced with Ada 2005?

No, that dates back at least to Ada 83.

-- 
Jeff Carter
"I fart in your general direction."
Monty Python & the Holy Grail
05

Re: Problem with generic linked list package

[Simon Wright]

Laurent <daemon2@internet.lu> writes:

> Yes indeed if Element would be a record then insert_in_order wouldn't
> work as it is. Because "<" and "=" don't exist for this type. Perhaps
> if I compared the components of the record I would but for now I don't
> see how I would do that. Problem for later when I have to use my
> package for a real program.

   type Rec is record
      B : Boolean;
      I : Integer;
   end record;
   function "<" (L, R : Rec) return Boolean is
   begin
      return L.I < R.I;
   end "<";

and similarly for "=".

I've found it's less confusing for me if I don't actually call these
functions "<", "=" but rather Less_Than, Equals. You lose the (minor)
inconvenience of being able to use the default comparison when
instantiating your generic, but gain clarity. This is presumably why we
have Ada.Strings.Less_Case_Insensitive and Equal_Case_Insensitive;
if they were called "<", "=" there could easily be ambiguity with the
default String subprograms.

Re: Problem with generic linked list package

[Simon Wright]

Simon Wright <simon@pushface.org> writes:

> You lose the (minor) inconvenience of being able to use the default
> comparison when instantiating your generic

*convenience*

Re: Problem with generic linked list package

[Laurent]

@Simon

Thanks for the example.

   type Rec is record 
      B : Boolean; 
      I : Integer; 
   end record; 
   function "<" (L, R : Rec) return Boolean is 
   begin 
      return L.I < R.I; 
   end "<"; 

Would that work for a record like this or would I have to define a function for every imaginable record?

ie:  type Rec is record
             S: String;
             I: Integer;
             D: Date;
     end record;

Or could I do this (just a little piece of code hope you understand what I mean):

els if Element.Rec.I < L.Head.all.Element.Rec.I then 
         Add_To_Front (L, Element);

Thanks

Laurent

Re: Problem with generic linked list package

[Simon Wright]

Laurent <daemon2@internet.lu> writes:

(actually I wrote this next section)
>    type Rec is record 
>       B : Boolean; 
>       I : Integer; 
>    end record; 
>    function "<" (L, R : Rec) return Boolean is 
>    begin 
>       return L.I < R.I; 
>    end "<"; 

> Would that work for a record like this or would I have to define a
> function for every imaginable record?
>
> ie:  type Rec is record
>              S: String;
>              I: Integer;
>              D: Date;
>      end record;
>
> Or could I do this (just a little piece of code hope you understand
> what I mean):
>
> els if Element.Rec.I < L.Head.all.Element.Rec.I then 
>          Add_To_Front (L, Element);

You have (after Shark8's suggestion, I think) a generic package which
starts something like

   generic
      type T is private;
      with function "<" (L, R : T) return Boolean is <>;
   package P is
      ...

If you want to instantiate it with a type Rec1

   type Rec1 is record
      B : Boolean;
      I : Integer;
   end record;

then you have somehow to provide a function to take the place of the "<"
in the generic formal part.

   package P_For_Rec1 is new P (T => Rec1, "<" => ?something?);

where ?something? is a function which takes two parameters of type Rec1
and returns Boolean. It will be a Good Thing if ?something? returns True
if the first parameter is "less than" the second, *whatever "less than"
means in your application*.

If you want the comparison to be on the I component of Rec1, then you
could supply Less where

   function Less (L, R : Rec1) return Boolean is (L.I < R.I);

(that's in Ada 2012), in which case you'd instantiate with

   package P_For_Rec1 is new P (T => Rec1, "<" => Less);

The "is <>" in the formal part of package P means that you could
alternatively write

   function "<" (L, R : Rec1) return Boolean is (L.I < R.I);

and

   package P_For_Rec1 is new P (T => Rec1);


If you now decide you want to instantiate P with

   type Rec2 is record
      S: String;
      I: Integer;
      D: Date;
   end record;

then you have to decide how

   function Less (L, R : Rec2) return Boolean is (?);

needs to work. Do you need to compare the S component? the I component?
the D component? or some combination? But however it has to work, it has
to be a new function.

Re: Problem with generic linked list package

[Jeffrey Carter]

On 08/10/2014 02:57 PM, Simon Wright wrote:
>
> You have (after Shark8's suggestion, I think) a generic package which
> starts something like
>
>     generic
>        type T is private;
>        with function "<" (L, R : T) return Boolean is <>;
>     package P is

Specifically, a linked-list pkg, which only uses "<" for its Insert_In_Order 
subprogram. There are plenty of times when you want to keep things in a list and 
don't care about their order; this pkg requires that the client supply a "<" 
that will never be used in that case. And there are times when you want to 
allocate things like tasks and keep them in a data structure such as a linked 
list. There is no meaningful definition of "<" in such a case.

task type T;

type T_Ptr is access T;

How would one create a linked list of T_Ptr? One could fake up a "<" that 
returns True, but that's wasted effort.

The intention of my post which started off this sub-thread (about writing "<" 
for record types) was to get the OP thinking about how to write a linked-list 
pkg that would be useful for such a case (not requiring "<" to be instantiated) 
but still able to provide Insert_In_Order for cases where "<" is meaningful and 
an ordered list is desired.

-- 
Jeff Carter
"Little blondes with long hair and short skirts and
boots and big chests and bright, witty, and perceptive."
Play It Again, Sam
128

Re: Problem with generic linked list package

[Laurent]

@Simon: a lot of info to think about. Thanks
@Jeffrey: a list of objects which don'tneed any specific order is no problem. This pkg is needed in the book for a later example for implementing a generic stack. The operations required for that have been given by the author.

I was just hanging myself by thinking about a use of this pkg after the book. A thought about an program to manage my stuff at home (screws, paint, ...). So I don't know what info would put into the record. 

So I think the best idea would be to do it like the display_procedure and provide the "<" or whatever in the client program.

And of course it would depend how I would want to sort them. Name, quantity or perhaps expiry date? Have no idea?

Thanks

Laurent

Re: Problem with generic linked list package

[Jeffrey Carter]

On 08/10/2014 09:51 PM, Laurent wrote:
>
> I was just hanging myself by thinking about a use of this pkg after the book.
> A thought about an program to manage my stuff at home (screws, paint, ...).
> So I don't know what info would put into the record.

The package is in the book to introduce you to certain concepts. I doubt if 
you'd ever actually use it; you'd be much more likely to use 
Ada.Containers.Doubly_Linked_Lists instead (ARM A.18.3). A review of 
Ada.Containers.Doubly_Linked_Lists, and its nested generic pkg Generic_Sorting, 
might expose you to another concept.

-- 
Jeff Carter
"Little blondes with long hair and short skirts and
boots and big chests and bright, witty, and perceptive."
Play It Again, Sam
128

Re: Problem with generic linked list package

[Laurent]

Yes why bother with getting a pkg together if there exits a better one ready to use. I have taken a look at it when I had problems to implement the copy procedure. But there are so many things in the double linked list pkg that I was immediately lost. The other problem is that I learn best by solving the problem myself. So even if I will never use this simple list pkg, it will still help me understanding and getting some routine with programming. 

If I scratch everything together I have perhaps been programming ( banging my head against a wall) about 150 hrs. Ada contains so many features. If I have a problem which I can't solve myself than I probably won't forget the solution later. 

Laurent

Re: Problem with generic linked list package

[Shark8]

On 07-Aug-14 13:07, Laurent wrote:
> Hi
>
> I have added an Insert_In_Order procedure to my generic package.
>
> The normal version given by the book is working.
>
> I have modified "Word" to "Element" so that it is generic.
> Compiler wasn't happy because "<" and ">=" were not defined for Element_Type.

Alter your Generic.

generic
   type Element_Type is private;
   with procedure Display_Element (Item : in Element_Type);
   with function "<"(Left, Right : Element) return Boolean is <>;
   with function "="(Left, Right : Element) return Boolean is <>;
package Linked_Lists_Generic is
-- ...
    Function ">=" (Left, Right) Return Boolean is
      ( not (Left < Right) );
end Linked_Lists_Generic;

If you're not using Ada 2012 then you'll have to put the implementation 
of >= in the body.

Re: Problem with generic linked list package

[Laurent]

@Shark8: don't know if I understand your solution. I have to check that out when I am (1) infront of my computer (2) have slept a few hours.

The book I use was written 1998, but I have the latest version of gnat and I do this as hobby. So I can use whatever I want. If ada 2012 has an easier way to realise something I will use it.

Btw I have no computerscience background at all.

Thanks 

Laurent

Re: Problem with generic linked list package

[Shark8]

On 07-Aug-14 16:30, Laurent wrote:
> The book I use was written 1998, but I have the latest version of
> gnat and I do this as hobby. So I can use whatever I want. If ada
> 2012 has an easier way to realise something I will use it.

Then you have Ada 2012 capabilities.
The real point of the example I gave is altering the formal parameters 
of the generic so that you have access to the "<" and "=" functions.

This is to say that the ">=" function was only an example to show how 
you could get that functionality from both.