LISP

Speicherrückgewinnung (Garbage Collection)

Im Verarbeitungsmodell von LISP werden Paare und Atome bei Bedarf erzeugt. Es kann geschehen, dass Paare oder Atome im weiteren Verlauf der Programmausführung zu einem bestimmten Augenblick verworfen werden. Sie sind dann nicht mehr Teil irgendeines Ausdrucks.

Beispiel

Erzeugte Strukturen werden einfach aufgegeben, wenn sie nicht mehr erreichbar sind.

Eine Implementierung von LISP muss ein Verfahren bereitstellen, aufgegebene Paare und Atome zu identifizieren und für die erneute Verwendung zurückzugewinnen.

Begriffe

• Freispeicherliste
• Erreichbarkeit
• Markierungsalgorithmus
• lokale Referenz
• Traversion des Kellerspeichers
• traversierungspflichtige Variable
• traversierungspflichtiges Aufrufsegment
• Traversierungsprozedur

Beschreibung der Aufgabe

Spätestens in dem Augenblick, zu dem es nicht mehr möglich ist, ein neues Paar oder ein neues Atom bereitzustellen, muss untersucht welche Atome und Paare noch erreichbar sind. Nicht erreichbare Paare und nicht erreichbare Atome werden in die Freispeicherlisten eingetragen und damit zur erneuten Verwendung verfügbar gemacht.

Skizze einer einfachen Lösung der Aufgabe

Erreichbare Paare und erreichbare Atome werden markiert. Ein Markierungsbit könnte den Strukturen element und atomType beigefügt werden:

   type
         atomType   = record
                        atomFound : boolean;
                        case atomTag : kindOfAtom of
                          symbol  : (name : alfa);
                          numeric : (val  : real);
                          unused  : (next : - nroOfAtoms .. 0)
                      end;
         element   =  record
                        found : boolean;
                        car : reference;
                        cdr : reference
                      end;

Da praktisch alle Compiler für die booleschen Werte atomFound, found mindestens 1 Byte, unter Umständen sogar bis zu 8 Bytes Speicher reservieren, ist es allerdings geschickter, die Markierungsbits aus den Typdefinitionen heraus­zu­nehmen und in gepackten Feldern zu speichern:

var  found     : packed array [1 .. nroOfPairs] of boolean;
     atomFound : packed array [-nroOfAtoms .. -1] of boolean;

Der Zugriff auf ein Element eines gepackten Feldes verlangt allerdings eine kompliziertere Spei­cher­ab­bil­dungs­funk­tion als der Zugriff auf die Elemente eines nicht gepackten Feldes.

Die Markierung der Paare und Atome eines Ausdrucks kann jetzt so programmiert werden: (einfache rekursive Formulierung)

procedure mark(ref : reference);
begin
  if ref < 0
    then
       atomFound[ref] := true;
    else if ref > 0
    then
        if not found[ref] 
           then begin
                   found[ref] := true;
                   mark(pairs[ref].car);
                   mark(pairs[ref].cdr);
                end
end;

Vorbesetzung der Markierungsbits

Aufbau der neuen Freispeicherlisten und Löschung der Markierungsbits

Eine sehr einfache Lösung

Der Markierungsalgorithmus ist auf alle Ausdrücke anzuwenden, die über die Variablen des Interpreters erreichbar sind.

Jede Funktion und jede Prozedur, die lokal vereinbarte [traversionspflichtige Variablen] Variablen enthält, über die Strukturen erreichbar sind, die der Markierungsalgorithmus durchlaufen muss, erhält eine lokal vereinbarte Prozedur, die alle erforderlichen Aufrufe des Markierungsalgorithmus ausführt.

Jede dieser lokal vereinbarten ***Prozeduren erledigt die Markierung erreichbarer Strukturen für alle Aufrufsegmente der Prozedur, in der die ***Prozedur vereinbart ist.

Wenn alle Prozeduren und Funktionen mit einer lokal vereinbarten Prozedur für die Durchführung des Markierungsalgorithmus ausgestattet werden, bilden die für das Durchlaufen der Aufrufsegmente mitgeführten Prozeduren die dynamische Verweiskette mit den Mitteln von Pascal nach.

Dies ist eine besondere Art der Rekursion, die Rekursion über ausgezeichnete Aufrufsegmente.

Das Verfahren hat bei aller Einfachheit schwerwiegende Nachteile:

• Der Markierungsalgorithmus ist rekursiv.
• Die Durchmusterung aller Aufrufsegmente des Interpreters ist ebenfalls rekursiv, die Rekursion erstreckt sich über die Aufrufsegmente von Prozeduren, die ihrerseits rekursiv aufgerufen werden!

Anmerkungen:

In den Traversierungsprozeduren kommen nur schlichte Aufrufe vor.

Unter Fachleuten für Compilerbau ist bekannt, dass schlichte Aufrufe so transformiert werden können, dass das Anwachsen des Laufzeitkellers vermieden wird. Da allerdings kein Pascal-Compiler existiert, der derartige Programm­trans­for­ma­ti­onen tatsächlich ausführt, hat diese Tatsache aber keinerlei praktische Bedeutung.

Textvariante:

In der Terminologie des Lehrwerks von Bauer und Wössner sind dies schlichte Aufrufs. Für solche Aufrufe sind Übersetzungsverfahren bekannt, die das Anwachsen des Kellerspeichers vermeiden. Im Prinzip zielen diese Verfahren darauf ab, das Aufrufsegment des aufrufenden Prozedur aus der Kellerspeicher zu entfernen, bevor der schlichte Aufruf ausgeführt wird.

Mögliche Verbesserungen

Auf die Durchmusterung aller Aufrufsegmente kann verzichtet werden, wenn alle Lisp-Ausdrücke in einer Liste verwaltet werden und dem Markierungsalgorithmus somit jederzeit sichtbar sind. (Bei diesem Ansatz werden für die Liste aller sichtbaren Ausdrücke zusätzlich Paare verbraucht).

Eine weitere, wesentliche Verbesserung ist erreichbar, wenn statt eines rekursiven Markierungs­algorithmus ein nicht­rekursiver Markierungs­algorithmus verwendet wird. Das ist schwierig, aber möglich.

Mängel der einfachen Lösung

Man sollte einen Interpreter mit diesem einfachen Algorithmus bereitstellen.

...