Ein Interpreter für LISP

Überblick

Auswahl einer Datenstruktur (Pascal)

Da Listen dynamische Gebilde sind, ist es verführerisch naheliegend, eine Datenstruktur mit Referenztypen zu wählen, etwa:

type zeiger = ^element;
     art = (atomar, paar);
     alfa = packed record [1 .. 10] of char;
     element = record
                 case tag : art of
                   atomar :  (name : alfa);
                   paar   :  (car, cdr : zeiger);
               end;

Die dazugehörenden Funktionen sind von der Art:

Diese Lösung ist jedoch abzulehnen, weil unzugänglich gewordene Objekte vom Typ "element" nicht zurückgewonnen werden können. ...

Für den LISP-Interpreter werden die folgenden Datentypen und Variablen vereinbart:

   const nroOfAtoms           =  800;
         nroOfPairs           =  3500;
         stringLength         =  16;

   type  alfa       = packed array [1 .. stringLength] of char;
         reference  = - nroOfPairs .. nroOfPairs;
         kindOfAtom = (symbol, numeric, unused);
         atomType   = record
                        case atomTag : kindOfAtom of
                          symbol  : (name : alfa);
                          numeric : (val  : real);
                          unused  : (next : - nroOfAtoms .. 0)
                      end;
         element   =  record
                        car : reference;
                        cdr : reference
                      end;

   var   atoms    : array [ -nroOfAtoms .. -1 ] of atomType;
         pairs    : array [ 1 .. nroOfPairs ] of element;
         atomlist : - nroOfAtoms .. 0;
         pairlist : 0 .. nroOfPairs;

Dieser Programmabschnitt ist sehr übersichtlich: Er enthält drei Konstanten, fünf Typvereinbarungen und vier Variablenvereinbarungen. Allerdings sind in diesen Programmabschnitt ziemlich viele Überlegungen eingeflossen:

• Die vereinbarten Konstanten legen die Größe des Arbeitsspeichers des Interpreters fest. Durch einfache Änderung der Werte kann die Größe des Arbeitsspeichers verändert werden.

• Der Datentyp reference legt den Wertebereich für die beiden Felder eines cons-Paares fest. Dabei gilt:

  • Ein positiver Wert ist ein Verweis auf ein anderes Paar.

  • Ein negativer Wert ist einVerweis auf ein Atom.

  • Der Wert 0 stellt das Element nil dar.

• Es werden literale und numerische Atome unterschieden; numerische Atome speichern eine Gleitkommazahl. Eine weitere Unterscheidung zwischen Gleitkommazahlen und Ganzzahlen wäre mit geringem Aufwand realisierbar. Um Atome in einer Freispeicherliste verwalten zu können, wird zusätzlichder Atomtyp unused eingeführt.

• Der Datentyp element stellt die beiden Felder eines cons-Paares zur Verfügung.

• In der Variablen atomlist steht der Index des ersten Atoms der Freispeicherliste der Atome.

• In der Variablen pairlist steht der Index des ersten Paars der Freispeicherliste der Paare.

Auf Paare wird mit positiven Indices zugegriffen, auf Atome mit negativen Indices.

Freispeicherlisten:

Die im Feld pairs bereitgestellten Paare werden in einer Freispeicherliste verwaltet, aus der die LISP-Funktion cons neue Paare entnimmt. In gleicher Weise werden die im Feld atoms bereitgestellten Atome in einer Frei­speicher­liste verwaltet.

Die Herstellung beider Freispeicherlisten geschieht mit diesem Programmabschnitt:

for i := nroOfPairs downto 1 do
  with pairs[i] do
  begin
    car := 0;
    cdr := i - 1;
  end;
pairlist := nroOfPairs;
for i := -nroOfAtoms to -1 do
  with atoms[i] do
  begin
    atomTag := unused;
    next := i + 1;
  end;
atomlist := - nroOfAtoms;

Die hier gezeigten Anweisungen sind Teil der Initialisierung des Interpreters. Sie werden beim Pro­gramm­start einmalig ausgeführt, um die Betriebsfähigkeit des Interpreters herzustellen.

Anmerkung

In den Freispeicherlisten werden die Feldelemente nach absolut fallenden Indices miteinander verkettet. Das ist nicht zwangsläufig, aber es ist geschickt, weil dadurch in das letzte Element der Freispeicherliste der Wert 0 für den Index des nachfolgenden Elements eingetragen wird. Wenn die Verkettung der Elemente in umgehkehrter Reihenfolge vorgenommen werden soll, wird die Herstellung der Freispeicherlisten komplizierter, da die Ein­tra­gung der Nullverweise in die jeweils letzten Listenelemente extra zu programmieren ist.

for i := 1 to numberOfPairs - 1 do
  with pairs[i] do
  begin
    car := 0;
    cdr := i + 1;
  end;
with pairs[numberOfPairs] do
  begin
  car := 0;
  cdr := 0;
end;
pairlist := 1;

for i := -1 downto -nroOfAtoms + 1 do
  with atoms[i] do
  begin
    atomTag := unused;
    next := i - 1;
  end;

with atoms[-nroOfAtoms] do
begin
  atomTag := unused;
  next := 0;
end;
atomlist := - 1;

Die Erzeugung eines Paares geschieht dann, indem ein Paar aus der Freispeicherliste entnommen wird. Sobald die Freispeicherliste erschöpft ist, löst der Versuch, ein weiteres Paar zu erzeugen, die Speicher­rück­ge­win­nung aus:

function cons(a, b : reference) : reference;
  var  p : reference;
begin
  if pairlist = 0
     then begin
              { hier findet Speicherrückgewinnung statt }
             if pairlist = 0
                then error (noPairAvailable);
          end;
  p := pairlist;
  pairlist := pairs[pairlist].cdr;

  with pairs[p] do
  begin
    car := a;
    cdr := b;
  end;
  cons:= p;
end;

Die Speicherrückgewinnung wird später behandelt. Im hier gezeigten Programmstück ist nur wichtig, dass die Speicher­rück­ge­win­nung erfolglos sein kann: Wenn die Freispeicherliste auch nach der Durch­füh­rung der Speicher­rück­ge­win­nung leer ist, steht tatsächlich kein Paar mehr zur Verfügung.

In ganz ähnlicher Weise werden Atome durch Entnahme aus der Freispeicherliste neu erzeugt:

function createLiteralAtom(str : alpa) :reference;
  var   i, j : reference;
begin

  createLiteralAtom := i;
end;

Verwendung verschiedener Arten von Zahlen

Für einen einfachen Lisp-Interpreter ist es ausreichend, für die Zahlen­dar­stel­lung das Format real, also Gleit­komma­zahlen, zu verwenden. **** Tatsächlich stellte bereits Lisp 1.5, eine der frühesten dokumentierten Lisp-Implementierungen, sowohl Ganzzahlen als auch Gleitkommazahlen zur Verfügung.

         kindOfAtom = (symbol, intNumber, floatNumber, unused);
         atomType   = record
                        case atomTag : kindOfAtom of
                          symbol      : (name : alfa);
                          intNumber   : (intVal  : integer);
                          floatNumber : (floatVal  : real);
                          unused      : (next : - nroOfAtoms .. 0)
                      end;

Wenn unterschiedliche Zahlenformate zur Verfügung gestellt werden, sollten auch Funktionen für die Identifikation von Zahlen­formaten sowie Funktionen für die Umwandlung zwischen verschiedenen Zahlen­formaten bereitgestellt werden. Die Funktionen für die Identifikation von Zahlenformaten heißen in vielen älteren Lisp-Systemen FIXP und FLOATP, in CommonLisp heißen sie INTEGERP und FLOATP.