Re: newbie Q: storage management

[eachus@spectre.mitre.org (Robert I. Eachus)]

In article <5k5hif$7r5@bcrkh13.bnr.ca> kaz@vision.crest.nt.com (Kaz Kylheku) writes:

  > I've looked at the ISO standard and the relevant FAQ's and
  > tutorials, but I still need some discussion or clarification about
  > the management of objects obtained via ``new'', because what I
  > have read so far seemed rather vague in one respect.

  > Whose responsibility is it to destroy these objects? The Ada 95
  > standard says that an implementation is permitted to implement
  > garbage collection, but not required to do so.

    The rules are difficult to understand, but are "in there."
Basically, the compiler/run-time is required to reclaim the storage if
the scope of the type declaration is left, except to tasks, the type
Ada.Strings.Unbounded.Unbounded_String, and for types for which the
pragma Controlled applies.

  > I know that it is possible to instantiate a generic freeing
  > function for explicitly destroying objects. But why is there is
  > this lack of symmetry in the language?  On the one hand, you have
  > a slick ``new''-expression to create objects, but the
  > complementary deletion operation is totally obscured.

    In general, this asymmetry reflects the domain for which Ada was
originally intended.  Most safety-critical emebedded systems used to
be designed with a rule that all allocations were done once at
start-up so nothing was ever freed.  Also in real-time systems you
can't just shut down to do garbage collection at random times.  There
are real-time garbage collection algorithms now, but just using Ada
controlled types in a real-time system is enough of a headache.

   In more modern Ada embedded systems (and in non-embedded systems),
allocations at any time are allowed.  But trusting the user of an
abstraction to know how and when to deallocate things is tricky.  So
the usual is to hide the deallocation inside the abstraction anyway.

  > Does this mean that explicit freeing of objects via an instance of
  > Unchecked_Deallocation is discouraged (due to the potential
  > creation of dangling references)?

   No, it means that the name is intended to warn the programmer that
dangling references are his or her responsibility.  The idea was that
the programmer instantiates Unchecked_Deallocation, then wraps the
call in whatever checks he or she knows are required, thus creating a
checked deallocation routine.

  > Is it the reponsibility of the language implementation to
  > automagically detect when an object is no longer reachable and do
  > the appropriate deallocation, even if garbage is not collected?

   Only for types derived from Unbounded_String, Controlled,
Limited_Controlled, and types derived from them.  For types derived
from Controlled or Limited_Controlled, you or whoever creates the type
needs to pay attention to storage reclamation when defining Finalize,
and the compiler will do the rest.  This usually amounts to four or
five lines of code.  Every once in a while I think about defining a
"Managed" type derived from Controlled or Limited_Controlled, but it
doesn't seem worth the effort.

    For instance, here is a list abstraction with storage management.
The reason I didn't use an "off-the-shelf" implementation was that I
wanted part of the abstraction to be getting the contents of the list
as an array.  How much of the abstraction is devoted to storage
management?  Less than ten lines, and the bulk of that is freeing list
elements in the right order.  (I could have made List_Element a
controlled type as well, simplifying the code for Empty but adding
complexity elsewhere.  This approach seemed cleaner and more
efficient.)

    (Flame retardant: I deleted lots of comments and blank lines, and
put some loops and if statements on a single line to include these
files here.  Not my usual style. ;-)

with Ada.Finalization;
generic
  type Element is private;
  type Element_Array is array (Positive range <>) of Element;
package Lists is

  type List is new Ada.Finalization.Controlled with private;
  function Length(L: List) return Integer;
  procedure Append(L: in out List; E: in Element);
  procedure Prepend(L: in out List; E: in Element);
  function Contents(L: in List) return Element_Array;
  procedure Empty(L: in out List);

private

  type List_Element;
  type Pointer is access List_Element;
  type List is new Ada.Finalization.Controlled with record
    LP: Pointer;
  end record;
  type List_Element is record
     Value: Element;
     Next:  Pointer;
  end record;
  procedure Finalize(Object: in out List);

end Lists;

------------------------------------------------------------------------

with Unchecked_Deallocation;
package body Lists is

  procedure Free is new Unchecked_Deallocation(List_Element,Pointer);

  function Length(L: List) return Integer is
     Count: Integer := 0;
     Temp: Pointer := L.LP;
  begin
     while Temp /= null loop
       Temp := Temp.Next;
       Count := Count + 1;
     end loop;
     return Count;
  end Length;

  procedure Append(L: in out List; E: in Element) is
     Temp: Pointer := L.LP;
  begin
     if Temp = null then L.LP := new List_Element'(E,null); return; end if;
     while Temp.Next /= null loop Temp := Temp.Next; end loop;
     Temp.Next := new List_Element'(E,null);
     return;
  end Append;

  procedure Prepend(L: in out List; E: in Element) is
  begin L.LP := new List_Element'(E,L.LP); end;

  function Contents(L: in List) return Element_Array is
    EA: Element_Array(1..Length(L));
    Temp: Pointer := L.LP;
  begin
    for I in EA'Range loop EA(I) := Temp.Value; Temp := Temp.Next; end loop;
    return EA;
  end Contents;
 
  procedure Empty(L: in out List) is
    Temp: Pointer := L.LP;
  begin
    while Temp /= null loop 
      Free(L.LP);
      Temp := Temp.Next;
      L.LP := Temp;
    end loop;
  end Empty;

  procedure Finalize(Object: in out List) is
  begin Empty(Object); end Finalize;

end Lists;

----------------------------------------------------------------------------
--

					Robert I. Eachus

with Standard_Disclaimer;
use  Standard_Disclaimer;
function Message (Text: in Clever_Ideas) return Better_Ideas is...