Pop function

Pop function

[Rego, P.]

Hello, 

Given a list type 
   type T_List is
      record
         Next : access T_List;
         Item : Integer;
      end record;
   T_List_Ptr is access T_List;

Is it right to implement a pop function like the following? (Free is an Unchecked_Deallocation)
   function Pop (Sender : access T_List) return Integer is
      Current_Sender_Ptr : T_List_Ptr := T_List_Ptr (Sender);
      Current_Item : constant T_List := Sender.Item;
   begin
      if Sender /= null then
         if Sender.Next /= null then
            Current_Sender_Ptr := T_List_Ptr (Current_Sender_Ptr.Next);
         end if;
		 Free (Current_Sender_Ptr);
         return Current_Item;
      else 
         return 0;
      end if;
   end Pop;

I mean, if I set Current_Sender_Ptr := T_List_Ptr (Current_Sender_Ptr.Next), it's equivalent to Sender := Sender.Next? (which I could not do directly due to in this case it would not be allowed an anonymous reference, right?)

Re: Pop function

[Martin Dowie]

"Rego, P." <pvrego@gmail.com> wrote:
> Hello, 
> 
> Given a list type 
>    type T_List is
>       record
>          Next : access T_List;
>          Item : Integer;
>       end record;
>    T_List_Ptr is access T_List;
> 
> Is it right to implement a pop function like the following? (Free is an
> Unchecked_Deallocation)
>    function Pop (Sender : access T_List) return Integer is
>       Current_Sender_Ptr : T_List_Ptr := T_List_Ptr (Sender);
>       Current_Item : constant T_List := Sender.Item;
>    begin
>       if Sender /= null then
>          if Sender.Next /= null then
>             Current_Sender_Ptr := T_List_Ptr (Current_Sender_Ptr.Next);
>          end if;
> 		 Free (Current_Sender_Ptr);
>          return Current_Item;
>       else 
>          return 0;
>       end if;
>    end Pop;
> 
> I mean, if I set Current_Sender_Ptr := T_List_Ptr
> (Current_Sender_Ptr.Next), it's equivalent to Sender := Sender.Next?
> (which I could not do directly due to in this case it would not be
> allowed an anonymous reference, right?)

If Sender is null, your in trouble before you get to "begin".

Also, is it really ok to return 0 from an empty list rather than raising an
exception?

What does Sender "point to" on return if the head of the list is removed?

-- Martin
-- 
-- Sent from my iPad

Re: Pop function

[Jeffrey Carter]

On 12/14/2011 05:06 PM, Rego, P. wrote:

A few unrelated comments:

> Is it right to implement a pop function like the following? (Free is an Unchecked_Deallocation)
>     function Pop (Sender : access T_List) return Integer is

Your public interface should never use access types.

Anonymous types are a bad idea.

Psychologists have found that the 1st few letters of a word are the most 
important to recognizing what you're seeing. If many of your identifiers start 
with the same few letters ("T_"), you are making your code harder to read than 
necessary.

-- 
Jeff Carter
"English bed-wetting types."
Monty Python & the Holy Grail
15

--- Posted via news://freenews.netfront.net/ - Complaints to news@netfront.net ---

Re: Pop function

[Rego, P.]

> If Sender is null, your in trouble before you get to "begin".
> Also, is it really ok to return 0 from an empty list rather than raising an
> exception?
That's the point. Actually I need to return some enumerated like NONE, but 0 would fit as well. 

> What does Sender "point to" on return if the head of the list is removed?
I'd like to return the "next" in the list, or null (so "0" or some NONE), if the the next does not exist. 

Re: Pop function

[Rego, P.]

> Your public interface should never use access types.
> Anonymous types are a bad idea.
Why so does the language allow it? Currently I could not think a better way of running over a pointer list: get the item, run the top of the list to the next one (and also keep the original pointer), free the original pointer and return the (newest) pointer to the top of the list. The problem I got was exactly when I tried to do this directly from the input access (so the anonymous type problem)

> Psychologists have found that the 1st few letters of a word are the most important to recognizing what you're seeing. If many of your identifiers start with the same few letters ("T_"), you are making your code harder to read than necessary.
I agree, but that's ok here. Think this as "be a general list type named T_List ..."

Re: Pop function

[Adam Beneschan]

On Dec 14, 4:06 pm, "Rego, P." <pvr...@gmail.com> wrote:
> Hello,
>
> Given a list type
>    type T_List is
>       record
>          Next : access T_List;
>          Item : Integer;
>       end record;
>    T_List_Ptr is access T_List;
>
> Is it right to implement a pop function like the following? (Free is an Unchecked_Deallocation)
>    function Pop (Sender : access T_List) return Integer is
>       Current_Sender_Ptr : T_List_Ptr := T_List_Ptr (Sender);
>       Current_Item : constant T_List := Sender.Item;

that should be "constant Integer", right?

>    begin
>       if Sender /= null then
>          if Sender.Next /= null then
>             Current_Sender_Ptr := T_List_Ptr (Current_Sender_Ptr.Next);
>          end if;
>                  Free (Current_Sender_Ptr);
>          return Current_Item;
>       else
>          return 0;
>       end if;
>    end Pop;
>
> I mean, if I set Current_Sender_Ptr := T_List_Ptr (Current_Sender_Ptr.Next), it's
> equivalent to Sender := Sender.Next?

No.  Current_Sender_Ptr is a local variable.  When you set
Current_Sender_Ptr, you're changing the value of the local variable,
but that does not affect *anything* outside the Pop procedure.  Free
(Current_Sender_Ptr) will then set Current_Sender_Ptr to null.  Then
Pop will return and Current_Sender_Ptr will go away since it's a local
variable, so the work you've done of setting it to the "Next" value
will be lost.  If you call
   N := Pop (Sender);
assuming that Sender points to the head of the list, this call won't
change Sender at all.  After the call, Sender will point to an item
that has been deallocated, which is very, very bad.

What you're probably missing is that Sender is treated as an IN
parameter here, so it can't be modified.  You probably want to make it
an IN OUT parameter, which means that Pop can't be a function (up
through Ada 2005; I think that rule is changing in Ada 2012).  So I'd
do something like

   procedure Pop (List_Head : in out T_List_Ptr; Item : out Integer)
is ...

and then in Pop, at some point, List_Head := List_Head.Next.  Plus
you'll need to rearrange the code so that you don't try to access
Sender.Item before checking to make sure Sender isn't null, as Martin
pointed out.  (Also, it wouldn't be my style to reserve a special
Integer value to indicate an empty list.  It might be OK in some
applications, but it makes the code that calls Pop more difficult to
follow.)

                                -- Adam

Re: Pop function

[Adam Beneschan]

On Dec 14, 4:29 pm, Martin Dowie <mar...@re.mo.ve.thedowies.com>
wrote:
> "Rego, P." <pvr...@gmail.com> wrote:
> > Hello,
>
> > Given a list type
> >    type T_List is
> >       record
> >          Next : access T_List;
> >          Item : Integer;
> >       end record;
> >    T_List_Ptr is access T_List;
>
> > Is it right to implement a pop function like the following? (Free is an
> > Unchecked_Deallocation)
> >    function Pop (Sender : access T_List) return Integer is
> >       Current_Sender_Ptr : T_List_Ptr := T_List_Ptr (Sender);
> >       Current_Item : constant T_List := Sender.Item;
> >    begin
> >       if Sender /= null then
> >          if Sender.Next /= null then
> >             Current_Sender_Ptr := T_List_Ptr (Current_Sender_Ptr.Next);
> >          end if;
> >             Free (Current_Sender_Ptr);
> >          return Current_Item;
> >       else
> >          return 0;
> >       end if;
> >    end Pop;
>
> > I mean, if I set Current_Sender_Ptr := T_List_Ptr
> > (Current_Sender_Ptr.Next), it's equivalent to Sender := Sender.Next?
> > (which I could not do directly due to in this case it would not be
> > allowed an anonymous reference, right?)
>
> If Sender is null, your in trouble before you get to "begin".

First it's "here" instead of "hear", now it's "your" instead of
"you're"..........

:)
                      -- Adam

Re: Pop function

[Alex Mentis]

Rego, P. wrote:

> > Your public interface should never use access types.
> > Anonymous types are a bad idea.
> Why so does the language allow it? Currently I could not think a
> better way of running over a pointer list: 

Instead of

type T_List is
   record
      Next : access T_List;
      Item : Integer;
   end record;
T_List_Ptr is access T_List;

you should use an incomplete declaration (ARM 3.10.1):

type T_List; -- incomplete declaration

type T_List_Ptr is access T_List;

type T_List is
   record
      Next : T_List_Ptr;
	Item : Integer;
   end record;


-Alex

Re: Pop function

[Alex Mentis]

Alex Mentis wrote:

> Rego, P. wrote:
> 
> > > Your public interface should never use access types.
> > > Anonymous types are a bad idea.
> > Why so does the language allow it? Currently I could not think a
> > better way of running over a pointer list: 
> 
> Instead of
> 
> type T_List is
>    record
>       Next : access T_List;
>       Item : Integer;
>    end record;
> T_List_Ptr is access T_List;
> 
> you should use an incomplete declaration (ARM 3.10.1):
> 
> type T_List; -- incomplete declaration
> 
> type T_List_Ptr is access T_List;
> 
> type T_List is
>    record
>       Next : T_List_Ptr;
> 	Item : Integer;
>    end record;
> 
> 
> -Alex

I meant to add, that would alleviate a lot of the type conversion
you're doing.

Re: Pop function

[Jeffrey Carter]

On 12/14/2011 06:35 PM, Rego, P. wrote:
>> Your public interface should never use access types. Anonymous types are a
>> bad idea.
> Why so does the language allow it? Currently I could not think a better way
> of running over a pointer list: get the item, run the top of the list to the
> next one (and also keep the original pointer), free the original pointer and
> return the (newest) pointer to the top of the list. The problem I got was
> exactly when I tried to do this directly from the input access (so the
> anonymous type problem)

The language allows lots of things that are bad ideas: anonymous types, 
programming by extension, the list goes on. That's not a reason to use them.

While an unbounded list undoubtedly is implemented using access values, there is 
no reason to expose them to your clients.

The best way to run over a list is to reuse an existing implementation, such as 
Ada.Containers.Doubly_Linked_List, or PragmARC.List_Unbounded_Unprotected if you 
don't have access to a compiler for the current language. One wonders why you 
are trying to write another one.

>> Psychologists have found that the 1st few letters of a word are the most
>> important to recognizing what you're seeing. If many of your identifiers
>> start with the same few letters ("T_"), you are making your code harder to
>> read than necessary.
> I agree, but that's ok here. Think this as "be a general list type named
> T_List ..."

It's never OK to make your code harder to read.

-- 
Jeff Carter
"English bed-wetting types."
Monty Python & the Holy Grail
15

--- Posted via news://freenews.netfront.net/ - Complaints to news@netfront.net ---

Re: Pop function

[Rego, P.]

> that should be "constant Integer", right?
Oh yes, sorry!!

> No.  Current_Sender_Ptr is a local variable.  When you set
> Current_Sender_Ptr, you're changing the value of the local variable,
> but that does not affect *anything* outside the Pop procedure.  Free
> (Current_Sender_Ptr) will then set Current_Sender_Ptr to null.  Then
> Pop will return and Current_Sender_Ptr will go away since it's a local
> variable, so the work you've done of setting it to the "Next" value
> will be lost.  If you call
>    N := Pop (Sender);
> assuming that Sender points to the head of the list, this call won't
> change Sender at all.  After the call, Sender will point to an item
> that has been deallocated, which is very, very bad.
Ok.
 
> What you're probably missing is that Sender is treated as an IN
> parameter here, so it can't be modified.  You probably want to make it
> an IN OUT parameter, which means that Pop can't be a function (up
> through Ada 2005; I think that rule is changing in Ada 2012).  So I'd
> do something like
> 
>    procedure Pop (List_Head : in out T_List_Ptr; Item : out Integer)
> is ...
> 
> and then in Pop, at some point, List_Head := List_Head.Next.  Plus
> you'll need to rearrange the code so that you don't try to access
> Sender.Item before checking to make sure Sender isn't null, as Martin
> pointed out.  (Also, it wouldn't be my style to reserve a special
> Integer value to indicate an empty list.  It might be OK in some
> applications, but it makes the code that calls Pop more difficult to
> follow.)

Ok. So it would be like

   procedure Pop (Sender : in out T_List_Ptr;
                  T_Item : out Integer) is
	  Previous_Sender : T_List_Ptr;
   begin
      if Sender /= null then
	     Previous_Sender := Sender;
	     T_Item := Sender.Item;
         if Sender.Next /= null then
            Sender := T_List_Ptr (Sender.Next);
         end if;
		 Free (Previous_Sender);
      else
         T_Item := 0;
      end if;
   end Pop;

but in this case I could not call 
   Some_Obj : access T_List;
   Other_Int : Integer;
   ...
   Other_Int := Some_Obj.Pop;
because Pop is not a primitive of T_List. The notation Some_Obj.Pop would be just sintatic sugar, but would exist a way we can implement Pop for using with this? (but sure...that's also ok for the non-sugar case)

Re: Pop function

[Rego, P.]

> The best way to run over a list is to reuse an existing implementation, such as Ada.Containers.Doubly_Linked_List, or PragmARC.List_Unbounded_Unprotected if you don't have access to a compiler for the current language. One wonders why you are trying to write another one.
Well, I did not try Ada.Containers.Doubly_Linked_List before, but it's worth trying for sure.

Re: Pop function

[Dmitry A. Kazakov]

On Wed, 14 Dec 2011 17:34:57 -0700, Jeffrey Carter wrote:

> Your public interface should never use access types.

Yes, but since list as a data structure has the semantics of objects
accessed by references it would make sense to have this reflected in the
interface. But of course the list element must be

   type List_Item is access Integer; -- Only the data, no other mess

Fortunately Ada supports such implementations (via storage pools).

Otherwise, it is not a list what OP wants, but rather a container, e.g.
set, bag, maybe an array (map).

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

Re: Pop function

[Simon Wright]

"Rego, P." <pvrego@gmail.com> writes:

> Ok. So it would be like
>
>    procedure Pop (Sender : in out T_List_Ptr;
>                   T_Item : out Integer) is
> 	  Previous_Sender : T_List_Ptr;
[...]
> but in this case I could not call 
>    Some_Obj : access T_List;
>    Other_Int : Integer;
>    ...
>    Other_Int := Some_Obj.Pop;
> because Pop is not a primitive of T_List. The notation Some_Obj.Pop
> would be just sintatic sugar, but would exist a way we can implement
> Pop for using with this? (but sure...that's also ok for the non-sugar
> case)

I don't see why Pop takes T_List_Ptr as an argument. I would have
written

    procedure Pop (Sender : in out T_List;
                   T_Item : out Integer) is

and then it would be primitive (assuming T_List is tagged).

And why is the parameter called Sender? that sounds like a name in the
domain of the problem you're trying to solve, rather than in the domain
of popping an item from a List. Maybe From would be better.

And how come a List has an operation Pop? sounds more like a Stack or a
Queue.

Re: Pop function

[Adam Beneschan]

On Dec 15, 4:43 am, Simon Wright <si...@pushface.org> wrote:
> "Rego, P." <pvr...@gmail.com> writes:
> > Ok. So it would be like
>
> >    procedure Pop (Sender : in out T_List_Ptr;
> >                   T_Item : out Integer) is
> >      Previous_Sender : T_List_Ptr;
> [...]
> > but in this case I could not call
> >    Some_Obj : access T_List;
> >    Other_Int : Integer;
> >    ...
> >    Other_Int := Some_Obj.Pop;
> > because Pop is not a primitive of T_List. The notation Some_Obj.Pop
> > would be just sintatic sugar, but would exist a way we can implement
> > Pop for using with this? (but sure...that's also ok for the non-sugar
> > case)
>
> I don't see why Pop takes T_List_Ptr as an argument. I would have
> written
>
>     procedure Pop (Sender : in out T_List;
>                    T_Item : out Integer) is
>
> and then it would be primitive (assuming T_List is tagged).

I'm not following.  Assuming you have some object that represents a
"list", that object is going to have to point to the "head" of the
list somehow, and the Pop operation is going to have to change that
head.  Since the OP has defined T_List as one of the elements of the
list, rather than as an object that represents the "list" in its
entirety, passing an "in out T_List" isn't going to get the job
done.

You could quibble about whether T_List is an appropriate name to
represent a list element.  Fine.  I would too.  But I think our first
objective should get our OP to help write code that works, which
involves making sure he (I assume) understands the Ada language issues
involved, and not adding to any confusion he might have.  We can
quibble about the names, readability issues, encapsulation issues,
etc., later.

                           -- Adam

Re: Pop function

[Adam Beneschan]

On Dec 14, 7:27 pm, "Rego, P." <pvr...@gmail.com> wrote:
> > that should be "constant Integer", right?
>
> Oh yes, sorry!!
>
> > No.  Current_Sender_Ptr is a local variable.  When you set
> > Current_Sender_Ptr, you're changing the value of the local variable,
> > but that does not affect *anything* outside the Pop procedure.  Free
> > (Current_Sender_Ptr) will then set Current_Sender_Ptr to null.  Then
> > Pop will return and Current_Sender_Ptr will go away since it's a local
> > variable, so the work you've done of setting it to the "Next" value
> > will be lost.  If you call
> >    N := Pop (Sender);
> > assuming that Sender points to the head of the list, this call won't
> > change Sender at all.  After the call, Sender will point to an item
> > that has been deallocated, which is very, very bad.
>
> Ok.
>
>
>
>
>
> > What you're probably missing is that Sender is treated as an IN
> > parameter here, so it can't be modified.  You probably want to make it
> > an IN OUT parameter, which means that Pop can't be a function (up
> > through Ada 2005; I think that rule is changing in Ada 2012).  So I'd
> > do something like
>
> >    procedure Pop (List_Head : in out T_List_Ptr; Item : out Integer)
> > is ...
>
> > and then in Pop, at some point, List_Head := List_Head.Next.  Plus
> > you'll need to rearrange the code so that you don't try to access
> > Sender.Item before checking to make sure Sender isn't null, as Martin
> > pointed out.  (Also, it wouldn't be my style to reserve a special
> > Integer value to indicate an empty list.  It might be OK in some
> > applications, but it makes the code that calls Pop more difficult to
> > follow.)
>
> Ok. So it would be like
>
>    procedure Pop (Sender : in out T_List_Ptr;
>                   T_Item : out Integer) is
>           Previous_Sender : T_List_Ptr;
>    begin
>       if Sender /= null then
>              Previous_Sender := Sender;
>              T_Item := Sender.Item;
>          if Sender.Next /= null then
>             Sender := T_List_Ptr (Sender.Next);
>          end if;
>                  Free (Previous_Sender);
>       else
>          T_Item := 0;
>       end if;
>    end Pop;
>
> but in this case I could not call
>    Some_Obj : access T_List;
>    Other_Int : Integer;
>    ...
>    Other_Int := Some_Obj.Pop;
> because Pop is not a primitive of T_List. The notation Some_Obj.Pop would be just sintatic sugar, but would exist a way we can implement Pop for using with this? (but sure...that's also ok for the non-sugar case)

I don't like picking on people's naming conventions when they seem to
be asking about how to get the language to work.  But in this case,
I'm afraid you've been tripped up by your choice of type names, so I
think we do need to go into it this time.

You're dealing with two abstract concepts here: a "list" and an
"element".  A "list" is a collection of "elements" that are ordered,
or organized, in a certain way.  (I'm not going to worry about how
they're organized, since that isn't relevant to my point about
naming.)  The Pop operation is an operation that applies to a "list",
so it should be a primitive of a "list".

But I think your problem is that you've defined T_List to be a type
that represents one "element", not the entire "list".  And so it would
make sense that Pop is not a primitive operation of T_List, because
Pop should be a primitive operation of the "list" type, and T_List
isn't really the "list" type.

What I think you want is more like this:  (This is how I'd write it,
because I don't like anonymous access types in this situation, but
that's up to you.)

  type T_List_Element;
  type T_List_Element_Acc is access all T_List_Element;
  type T_List_Element is record
    Item : Integer;
    Next : T_List_Element_Acc;
  end record;
  type T_List is tagged record
    Head : T_List_Element_Acc;
  end record;

Now you actually could write a Pop function that is a primitive of a
List:

  function Pop (List : access T_List) return Integer is
  begin
    if List.Head /= null then
      ...
      List.Head := List.Head.Next; -- or something like that
      ...

I'll leave the rest of the details up to you.  But note that there's a
big difference between this access parameter and the one you coded
originally: in my example, "access T_List" is an access to a record
that *contains* a pointer to the first element of the list, not the
pointer to the first element itself.  This is what makes it possible
to change the list head pointer.

Anyway, hopefully this will get you started on the right path.
**Then**, after you have the basics down, we can have some long
arguments about what names you should pick, whether you should start
type names with T_, what types should be made private and how things
should be encapsulated, whether it's appropriate to return a special
value for an empty list or raise an exception, whether anonymous
access types are evil, etc.  I'm sure everyone on this group has some
pretty strong opinions on all those questions.  But I'm hoping this
will get you started.

                           -- Adam

Re: Pop function

[Simon Wright]

Adam Beneschan <adam@irvine.com> writes:

> On Dec 15, 4:43 am, Simon Wright <si...@pushface.org> wrote:

>> I don't see why Pop takes T_List_Ptr as an argument. I would have
>> written
>>
>>     procedure Pop (Sender : in out T_List;
>>                    T_Item : out Integer) is
>>
>> and then it would be primitive (assuming T_List is tagged).

> You could quibble about whether T_List is an appropriate name to
> represent a list element.  Fine.  I would too.  But I think our first
> objective should get our OP to help write code that works, which
> involves making sure he (I assume) understands the Ada language issues
> involved, and not adding to any confusion he might have.  We can
> quibble about the names, readability issues, encapsulation issues,
> etc., later.

I see what you mean; you've realised that OP is probably confused,
whereas I just got confused myself.

I agree about writing code that works, but that does sometimes involve
working out how best to state the problem. I don't think that it's
quibbling to point to unclear thinking; if the design is wrong that's
not an Ada language issue, and using inappropriate names is a red flag
for design problems.

Here, for example, if I write

      L : aliased T_List;
      ...
   begin
      ...
      J := Pop (L'Access);

I'm going to get a crash at runtime because I'm trying to deallcate
memory that was never allocated.

I have in the past implemented lists where the 'head' element was just
another member which -- by convention -- wasn't part of the list. That
sort of thing needs to be done by consenting adults in private, though.

Re: Pop function

[Dmitry A. Kazakov]

On Thu, 15 Dec 2011 18:34:53 +0000, Simon Wright wrote:

> Here, for example, if I write
> 
>       L : aliased T_List;
>       ...
>    begin
>       ...
>       J := Pop (L'Access);
> 
> I'm going to get a crash at runtime because I'm trying to deallcate
> memory that was never allocated.

Another reason to have it an explicit access type, BTW. If L were access to
specific pool you would not be able to declare L on the stack.

> I have in the past implemented lists where the 'head' element was just
> another member which -- by convention -- wasn't part of the list.

I tried:

   type Item is access Element_Type;
   type List is new Item;

and then to separate elements and lists in operations. E.g.

   procedure Delete (Container : in out List; Element : in out Item);

Item becomes null, Container set to the new head.

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

Re: Pop function

[Jeffrey Carter]

On 12/15/2011 01:38 AM, Dmitry A. Kazakov wrote:
> On Wed, 14 Dec 2011 17:34:57 -0700, Jeffrey Carter wrote:
>
>> Your public interface should never use access types.
>
> Yes, but since list as a data structure has the semantics of objects
> accessed by references it would make sense to have this reflected in the
> interface. But of course the list element must be
>
>     type List_Item is access Integer; -- Only the data, no other mess

No, a public interface should never use access types, ever. Hiding those is what 
abstraction is about. Any public interface that uses access types is poorly 
designed.

-- 
Jeff Carter
"I would never want to belong to any club that
would have someone like me for a member."
Annie Hall
41

--- Posted via news://freenews.netfront.net/ - Complaints to news@netfront.net ---

Re: Pop function

[Dmitry A. Kazakov]

On Thu, 15 Dec 2011 12:57:47 -0700, Jeffrey Carter wrote:

> On 12/15/2011 01:38 AM, Dmitry A. Kazakov wrote:
>> On Wed, 14 Dec 2011 17:34:57 -0700, Jeffrey Carter wrote:
>>
>>> Your public interface should never use access types.
>>
>> Yes, but since list as a data structure has the semantics of objects
>> accessed by references it would make sense to have this reflected in the
>> interface. But of course the list element must be
>>
>>     type List_Item is access Integer; -- Only the data, no other mess
> 
> No, a public interface should never use access types, ever. Hiding those is what 
> abstraction is about. Any public interface that uses access types is poorly 
> designed.

In that case there should be no linked lists at all. A linked list is per
its definition a set of elements accessed using pointers.

It is possible that the OP wanted something else, but that is another
question.

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

Re: Pop function

[Simon Wright]

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

> On Thu, 15 Dec 2011 12:57:47 -0700, Jeffrey Carter wrote:
>
>> On 12/15/2011 01:38 AM, Dmitry A. Kazakov wrote:
>>> On Wed, 14 Dec 2011 17:34:57 -0700, Jeffrey Carter wrote:
>>>
>>>> Your public interface should never use access types.
>>>
>>> Yes, but since list as a data structure has the semantics of objects
>>> accessed by references it would make sense to have this reflected in the
>>> interface. But of course the list element must be
>>>
>>>     type List_Item is access Integer; -- Only the data, no other mess
>> 
>> No, a public interface should never use access types, ever. Hiding
>> those is what abstraction is about. Any public interface that uses
>> access types is poorly designed.
>
> In that case there should be no linked lists at all. A linked list is per
> its definition a set of elements accessed using pointers.

I don't think that using the word "linked" in the name is the same as
"using access types in the abstraction"!

I've seen linked lists that were implemented (under the hood) with
indices into an array of items.

Re: Pop function

[Jeffrey Carter]

On 12/15/2011 02:02 PM, Simon Wright wrote:
> "Dmitry A. Kazakov"<mailbox@dmitry-kazakov.de>  writes:
>
>> On Thu, 15 Dec 2011 12:57:47 -0700, Jeffrey Carter wrote:
>>
>>> No, a public interface should never use access types, ever. Hiding
>>> those is what abstraction is about. Any public interface that uses
>>> access types is poorly designed.
>>
>> In that case there should be no linked lists at all. A linked list is per
>> its definition a set of elements accessed using pointers.
>
> I don't think that using the word "linked" in the name is the same as
> "using access types in the abstraction"!
>
> I've seen linked lists that were implemented (under the hood) with
> indices into an array of items.

Precisely. That's a bounded list; see PragmARC.List_Bounded_Unprotected for an 
example.

And see Ada.Containers.Doubly_Linked_Lists for an example of an unbounded list 
abstraction with no visible access types.

-- 
Jeff Carter
"I would never want to belong to any club that
would have someone like me for a member."
Annie Hall
41

--- Posted via news://freenews.netfront.net/ - Complaints to news@netfront.net ---

Re: Pop function

[Martin Dowie]

Adam Beneschan <adam@irvine.com> wrote:
> On Dec 14, 4:29 pm, Martin Dowie <mar...@re.mo.ve.thedowies.com>
> wrote:
>> "Rego, P." <pvr...@gmail.com> wrote:
>>> Hello,
>> 
>>> Given a list type
>>>    type T_List is
>>>       record
>>>          Next : access T_List;
>>>          Item : Integer;
>>>       end record;
>>>    T_List_Ptr is access T_List;
>> 
>>> Is it right to implement a pop function like the following? (Free is an
>>> Unchecked_Deallocation)
>>>    function Pop (Sender : access T_List) return Integer is
>>>       Current_Sender_Ptr : T_List_Ptr := T_List_Ptr (Sender);
>>>       Current_Item : constant T_List := Sender.Item;
>>>    begin
>>>       if Sender /= null then
>>>          if Sender.Next /= null then
>>>             Current_Sender_Ptr := T_List_Ptr (Current_Sender_Ptr.Next);
>>>          end if;
>>>             Free (Current_Sender_Ptr);
>>>          return Current_Item;
>>>       else
>>>          return 0;
>>>       end if;
>>>    end Pop;
>> 
>>> I mean, if I set Current_Sender_Ptr := T_List_Ptr
>>> (Current_Sender_Ptr.Next), it's equivalent to Sender := Sender.Next?
>>> (which I could not do directly due to in this case it would not be
>>> allowed an anonymous reference, right?)
>> 
>> If Sender is null, your in trouble before you get to "begin".
> 
> First it's "here" instead of "hear", now it's "your" instead of
> "you're"..........
> 
> :)
>                       -- Adam

Groan...I need a holiday...and glasses...and 10 years taken off my
age...and the kids to GO TO BED...and to really read what I'm writing
(minor dyslexia doesn't help)...before I hit send! :-)

-- Martin

Re: Pop function

[Randy Brukardt]

"Jeffrey Carter" <spam.jrcarter.not@spam.not.acm.org> wrote in message 
news:jcdjfs$atd$1@adenine.netfront.net...
...
> No, a public interface should never use access types, ever. Hiding those 
> is what abstraction is about. Any public interface that uses access types 
> is poorly designed.

Geee, even I wouldn't go quite *that* far. There are some cases where you 
have to have reference semantics (the "Parent" function in Claw is an 
example), and in those cases ONLY it might make sense to visibly use an 
access type.

Ada 2012 provides "aliased" parameters to force reference semantics, and 
it's possible to encapsulate the access type so that it can't be abused, so 
this can actually be done safely. But that is an advanced topic.

                                               Randy.

Re: Pop function

[Dmitry A. Kazakov]

On Thu, 15 Dec 2011 21:02:09 +0000, Simon Wright wrote:

> "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> writes:
> 
>> On Thu, 15 Dec 2011 12:57:47 -0700, Jeffrey Carter wrote:
>>
>>> On 12/15/2011 01:38 AM, Dmitry A. Kazakov wrote:
>>>> On Wed, 14 Dec 2011 17:34:57 -0700, Jeffrey Carter wrote:
>>>>
>>>>> Your public interface should never use access types.
>>>>
>>>> Yes, but since list as a data structure has the semantics of objects
>>>> accessed by references it would make sense to have this reflected in the
>>>> interface. But of course the list element must be
>>>>
>>>>     type List_Item is access Integer; -- Only the data, no other mess
>>> 
>>> No, a public interface should never use access types, ever. Hiding
>>> those is what abstraction is about. Any public interface that uses
>>> access types is poorly designed.
>>
>> In that case there should be no linked lists at all. A linked list is per
>> its definition a set of elements accessed using pointers.
> 
> I don't think that using the word "linked" in the name is the same as
> "using access types in the abstraction"!

Not exactly same, right, but still it assumes referential semantics of the
list elements. Access type is one possible implementation of.

> I've seen linked lists that were implemented (under the hood) with
> indices into an array of items.

In that case the index must be exposed in the interface, or a private type
encapsulating that index.

The bottom line, you need some referential object to refer the list element
in the interface. You cannot have linked lists defined solely in the terms
of element values. List elements have an identity.

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

Re: Pop function

[georg bauhaus]

Martin Dowie <martin@re.mo.ve.thedowies.com> wrote:


>> First it's "here" instead of "hear", now it's "your" instead of
>> "you're"..........
>> 
>> :)
>>                       -- Adam
> 
> Groan...I need a holiday...and glasses...and 10 years taken off my
> age...and the kids to GO TO BED...and to really read what I'm writing
> (minor dyslexia doesn't help)...before I hit send! :-)

Ada's doubly shouting her current location
made me wonder who was calling, and why.
If this is all a misinterpretation of the original
string literal, then maybe "Sorry, father!" is
what she might have answered?

Re: Pop function

[Rego, P.]

Adam, I've redesigned the lists this way you suggested and, because of this change, I discovered a deeper bug when I used some limited withs. So, thanks twice :-)
And thank you all people too :-)