Path: utzoo!mnetor!uunet!husc6!cmcl2!nrl-cmf!ames!pasteur!ucbvax!unizh.UUCP!nagler%olsen
From: nagler%olsen@unizh.UUCP (Robert Nagler)
Newsgroups: comp.lang.modula2
Subject: Re: Garbage collection
Message-ID: <8803231100.AA08757@klaus.olsen.uucp>
Date: 23 Mar 88 11:00:52 GMT
Sender: usenet@ucbvax.BERKELEY.EDU
Reply-To: Info-Modula2 Distribution List <INFO-M2%UCF1VM.bitnet@jade.berkeley.edu>
Organization: The Internet
Lines: 176

> From Erland Sommarskog
> Not so much for a allocation routine, you quite often need an
> initiation routine, anyway. But do I need a deallocation routine?
> If there is garbage collection, I don't have to think of this problem.
...

Automatic garbage collection (AGC) is not the answer to all memory
allocation problems.  Cedar (from Xerox) is a typical structured language
which has AGC.  I have read articles on Cedar (never used it) and
they say that allocators and deallocators are *required* for circular
data structures, e.g. trees with "parent-links", doubly-linked lists,
circular lists, etc.  Another problem with AGC is that it consumes
CPU time.  If you are writing real-time applications (often what Modula-2
is used for), this can be annoying and dangerous.

Although many objects in programs are "just memory", some objects are
connected to other real-world entities, e.g. files, devices, etc.
With these objects, you always need a instantiation and destruction routine,
because they must open/close files, turn-on/off interrupts, etc.  AGC
doesn't even solve these problems.

With all this talk about AGC, no one is discussing the *need* for it.
My experience with AGC is that is required for applications which run
for extended periods of time or do lots of allocation and deallocation.
For example, if you are writing an operating system kernel, you don't
want it to lose memory.  However, if you are writing a compiler, it is
*ok* if it loses memory, because the whole memory space is wiped away
when the compiler exits after a few minutes at most.  Languages like Lisp
do a lot of allocation and deallocation, because the coding style requires
it.  In Modula-2, this is less often the case and in most of the code
I have seen, there is little dynamic memory allocation (here "little"
means 100K or so).  The primary reason for this is the lack of object-
oriented libraries available, e.g. ones that provide ADTs like lists.

> Generally, garbage collection is a must in object-oriented programming.

We have developed a real-time distributed information system consisting of
about 150K lines of code in 500 modules (or so).  Development time
was about a year and a half.  Coding and testing took about 9 months.
The software runs non-stop (excepting bugs and reconfiguration).  Some
of the processes have run for weeks.  We don't have memory leakage problems.
*All* of our software is object-oriented.  We program with Modula-2 as it
was intended to be programmed and we don't try to simulate Ada or Lisp
(although we borrow ideas occasonally).

> From Snorri Agnarsson:
> Not true.  It is not possible in general to "roll-your-own" in a
> satisfactory manner.  ... abstraction garbage collection is a necessity.

Somehow, I think you will be difficult to satisfy, but here goes:

The example of Modula-2 list code you gave seems kind of like Lisp and not M2.
>        X := CONS(Y,Z);
>        X := HEAD(Y);
>        X := TAIL(Y);

The first question I ask is: what does it do?  Program fragments taken
out of context are always difficult, but this piece of code is beyond me.
Why would anyone construct a list he never uses?  Why would he get tail
and head into a variable and not reference them?

We have a module called lists.  A typical usage is:
    Lists.MakeFirstNext( elements );
    WHILE Lists.Next( elements, element, data ) DO
        (* Do something with "element" and "data" *)
    END; (* WHILE *)

You might want to insert into the list:
    Lists.Insert( elements, newElement, itsData );

You might want to delete an element from a list:
    IF Lists.Find( elements, element, data ) THEN
        Lists.DeleteCurrent( elements );
    END;

The Lists module supports an abstraction of lists which is useful
in Modula-2, but maybe not Ada or Lisp.  You create a list by saying:
    Lists.Create( elements, Lists.typeCard, Lists.stack );
You can have sorted (forward and reverse) lists and also queues.
Importers can create new types easily (typeCard seemed like an
obvious built-in).

This simple module handles a majority of our M2 list processing code.
If special list processing or very high performance is required
(e.g. ready queue processing), we copy code and adapt it to the
special needs.  I've included a bastardized def mod (at the end of
this message) to give you an idea of what our Lists module is like.

BTW, you could implement a garbage collecting Modula-2 implementation,
but no one has bothered to do it.  The code to manage it is large
and often takes advantage of special hardware which makes it non-portable.

Object-oriented programming is a state of mind not a language feature.
I've found many people talk about it, but very few people are really
willing to commit to it.

Rob Nagler
mcvax!olsen!nagler@uunet.uu.net
------------------------------------------------------------------
Disclaimer:
    This module is a very much abbreviated version of Lists.  There
    are many features and comments which I have edited out, because
    they would add nothing to the discussion.  The real implementation
    and definition will be available in our ``soon-to-be-released''
    public domain library.

    For those backwards M2 implementations that only support SYSTEM.WORD,
    this module will still work, but you will have to change SYSTEM.BYTE
    to SYSTEM.WORD.  This implementation is in heavy use with Sun Modula-2
    and Logitech Modula-2/86.

DEFINITION MODULE Lists;
(*
 * Provides a simple method for managing lists of "keys".  One can specify
 * either sorted (reverse or forward), queued (FIFO), or stacked (LIFO)
 * orderings.  Keys need not be unique, but they must be non-zero in length.
 * This is a generic module, that is, you must provide a specific "type"
 * for the keys in the list.  The types are specified at run-time.
 *)
TYPE
    Object;     (* A list *)
    Orderings = (
        forwardSorted, (* the lesser keys are returned first *)
        reverseSorted, (* the greater keys are returned first *)
        queue,         (* first key Inserted, first returned by Next *)
        stack          (* first key Inserted, is the last returned *)
    );
PROCEDURE Create(
    VAR list          : Object;         (* "in" value is ignored *)
        typeName      : ARRAY OF CHAR;  (* must be registered *)
        howToTraverse : Orderings       (* How to go about finding things *)
    );
PROCEDURE Destroy(
    VAR list : Object   (* deallocates list and its elements, but not impObjs *)
    );
PROCEDURE Insert(
    list           : Object;               (* Must be a valid list *)
    key            : ARRAY OF SYSTEM.BYTE; (* to be inserted *)
    importerObject : SYSTEM.ADDRESS        (* data value associated with key *)
    );
PROCEDURE DeleteCurrent(
    list : Object       (* "current" must be valid *)
    );
PROCEDURE Find( (* key in list and set "current" *)
        list           : Object;                (* must be valid *)
        key            : ARRAY OF SYSTEM.BYTE;  (* set to "current" *)
    VAR importerObject : SYSTEM.ADDRESS         (* found data value *)
    )                  : BOOLEAN;  (* FALSE => not found; impObj invalid *)

PROCEDURE Next( (* traverse element after "current" or "first" *)
        list            : Object;               (* traverse *)
    VAR key             : ARRAY OF SYSTEM.BYTE; (*
    VAR importerObject  : SYSTEM.ADDRESS
    )                   : BOOLEAN;

PROCEDURE MakeFirstNext( (* first element in list will be returned by "Next" *)
    list : Object       (* Must be valid list *)
    );

(* Registering new types *)
TYPE
    AssertProc = PROCEDURE (
        SYSTEM.ADDRESS  (* pointer to object to be assertion checked. *)
    );
    CompareProc = PROCEDURE (
        SYSTEM.ADDRESS, (* pointer to "left" side of comparison *)
        SYSTEM.ADDRESS  (* pointer to "right" side of comparison *)
    ) : Intrinsics.CompareResults;

PROCEDURE Register( (* a new type with this module for use by others *)
    typeName    : ARRAY OF CHAR; (* must be unique *)
    assertProc  : AssertProc;    (* Procedure to check inserted values *)
    compareProc : CompareProc;   (* For sorting and finding *)
    keySize     : CARDINAL       (* SYSTEM.TSIZE( Type ) *)
    );
END Lists.