SECD-Maschine

Die SECD-Maschine ist eine virtuelle Maschine, die als Zielarchitektur für Compiler funktionaler Programmiersprachen gedacht ist. Die Buchstaben stehen für Stack, Environment, Control, Dump, welches die internen Register der Maschine sind. Diese Register enthalten Zeiger auf Listen im Speicher.

Die SECD-Maschine war die erste virtuelle Maschine, die ausdrücklich dazu entworfen wurde, Ausdrücke des Lambda-Kalküls auszuwerten. Sie wurde ursprünglich im Jahr 1963 von Peter J. Landin als Teil der Definition seiner Programmiersprache ISWIM beschrieben. Die von Landin publizierte Beschreibung war ziemlich abstrakt und ließ viele Implementierungsentscheidungen offen, wie zum Beispiel die Frage einer operationalen Semantik. Deshalb wird die SECD-Maschine oft auch in detaillierterer Form vorgestellt, wie zum Beispiel in Peter Hendersons Lispkit-LISP-Compiler, der seit 1980 verteilt wird. Sie wird auch als Zielarchitektur für verschiedene andere experimentelle Compiler verwendet.

Im Jahr 1989 arbeiteten Forscher an der University of Calgary an einer Hardware-Implementierung der Maschine.[1]

Register und Speicher

Die SECD-Maschine ist eine Stapelmaschine, deren Instruktionen ihre Hauptargumente von einem Stapel nehmen. Zusätzliche Parameter für eine Instruktion können hinter dem Instruktionsnamen angegeben werden. Der Stapel wird wie alle anderen internen Datenstrukturen durch eine Liste dargestellt, wobei das Register S auf den Anfang der Liste zeigt. Diese Liste wird auf einem Heap gespeichert, so dass der Stapel nicht unbedingt in einem zusammenhängenden Speicherblock enthalten sein muss. So lange noch freie Speicherzellen vorhanden sind, ist auch noch Stapelspeicherplatz verfügbar. Wenn alle Speicherzellen verwendet wurden, kann eine Garbage Collection möglicherweise wieder Speicher besorgen.

Das Register C zeigt zu Beginn auf die erste Instruktion aus dem auszuwertenden Programm, das als Liste von Instruktionen dargestellt wird. Nach jeder Auswertung einer Instruktion zeigt das C-Register auf die nächste Instruktion in der Liste und verhält sich damit ähnlich einem Befehlszähler mit der Ausnahme, dass nachfolgende Instruktionen nicht in unmittelbar nachfolgenden Speicherplätzen enthalten sein müssen.

Das Register E enthält die momentane Variablenumgebung, einen Zeiger auf eine Liste von Listen. Jede einzelne Liste beinhaltet die Variablenbindungen einer bestimmten Abstraktionsstufe: die erste Liste enthält die Parameter der laufenden Funktion; Variablen, die in der laufenden Funktion frei sind, aber in einer umgebenden Funktion gebunden werden, finden sich in nachfolgenden Listen.

Der „Dump“, auf dessen Anfang das Register D zeigt, wird als temporärer Speicher für die Inhalte anderer Register verwendet, die im Zusammenhang mit Funktionsaufrufen gerettet werden müssen. Er spielt insofern ungefähr die Rolle des Aufrufstapels bei anderen Maschinen.

Die Speicherorganisation der SECD-Maschine ist ähnlich dem Modell, das von den Interpretern der meisten funktionalen Programmiersprachen verwendet wird: Der Speicher ist eine Menge von Speicherzellen, die jeweils entweder ein Atom, das heißt, einen primitiven Wert, oder eine leere oder nicht-leere Liste enthalten können. Nicht-leere Listen sind dabei durch ein Paar von Zeigern dargestellt, die traditionell durch car und cdr bezeichnet werden. Modernere Entwicklungen verwenden stattdessen häufig die Bezeichnungen head und tail. Die verschiedenen Typen von Werten, die in einer Zelle enthalten sein können, werden durch eine Typenmarke (type tag) unterschieden. Oft werden dabei auch die verschiedenen Typen von Atomen (Zahlen, Zeichenketten etc.) unterschiedlich markiert.

Beispielsweise könnte eine Liste, welche die Zahlen 1, 2 und 3 enthält und normalerweise in der Form „(1 2 3)“ notiert wird, wie folgt dargestellt werden:

Adresse   Tag       Inhalt
----------------------------
      9 [ integer |     2 ]
      8 [ integer |     3 ]
      7 [ list    | 8 | 0 ]
      6 [ list    | 9 | 7 ]
      ...
      2 [ list    | 1 | 6 ]
      1 [ integer |     1 ]
      0 [ nil             ]

Die Speicherzellen 3 bis 5 wurden hier ausgelassen, weil sie nicht zu unserer Beispielliste gehören, die beliebig über den Speicher verteilt sein kann. Die Zelle 2 enthält den Kopf der Liste. Sie zeigt auf die Zelle 1, in der das erste Element der Liste zu finden ist, und auf die Zelle 6, in der sich die Restliste findet. Die Restliste besteht aus einem Verweis auf die Zelle 9, in der sich das zweite Element („2“) der Liste findet und die Zelle 7, die wiederum eine Restliste beschreibt. Nun besteht die Restliste aus einem Verweis auf die Zelle 8 mit dem dritten Element („3“) und einem Verweis auf eine leere Liste (nil) als Abschluss. In der SECD-Maschine bezeichnet die Zelle mit der Adresse 0 immer implizit die leere Liste, so dass eine spezielle Markierung für die leere Liste überflüssig ist.

Das Prinzip, dass der zweite Zeiger („cdr“) in einer Listenzelle immer auf eine andere Liste zeigen muss, ist reine Konvention. Wenn sowohl „car“ als auch „cdr“ auf Atome zeigen, kann dies auch gleich als Paar dargestellt werden, das normalerweise als „(1 . 2)“ notiert wird.

Instruktionen

Die wesentlichen Instruktionen der SECD-Maschine sind die folgenden:

  • nil schreibt einen nil-Zeiger auf den Stapel
  • ldc c schreibt ein konstantes Argument c auf den Stapel
  • ld v schreibt den Wert einer Variablen v auf den Stapel. Variablen werden dabei durch Paare (l . p) dargestellt, wobei l die Abstraktionsstufe bezeichnet und p die Position innerhalb der Parameter dieser Stufe. Als Beispiel bezeichnet „(1 . 3)“ den dritten Parameter der aktuellen Funktion (Abstraktionsstufe = 1).
  • sel l1,l2 entfernt einen Wert vom Stapel und macht eine Fallunterscheidung über den vorgefundenen Wert: Wenn die Spitze des Stapels verschieden von nil war, wird die Instruktionsfolge ausgeführt, auf die l1 zeigt, anderenfalls diejenige, auf die l2 zeigt. Es wird also das Register C durch l1 beziehungsweise l2 ersetzt; in jedem Fall wird ein Zeiger auf die dem sel nachfolgende Instruktion auf dem Dump gerettet.
  • join entfernt einen Listenzeiger vom Dump und macht daraus den neuen Wert des Registers C. Diese Instruktion kommt am Ende der beiden Alternativen einer sel-Instruktion vor.
  • ldf f erwartet ein Listenargument, das den Code einer Funktion darstellt. Daraus wird eine Closure hergestellt: ein Paar, bestehend aus dem Code der Funktion und dem aktuellen Environment E. Diese Closure wird auf dem Stapel gespeichert.
  • ap entfernt eine Closure und eine Liste von Parameterwerten vom Stapel. Die Closure wird auf die Parameter angewendet, indem sie ihr eigenes Environment zu dem aktuellen macht, die Parameterliste davor schreibt, den Stapel leert und das C-Register auf den Funktionszeiger aus der Closure setzt. Die vorherigen Werte von S und E und die Fortsetzungsadresse aus C werden auf den Dump gerettet.
  • ret entfernt einen Rückgabewert vom Stapel, stellt die Register S, E und C aus dem Dump wieder her, entfernt das oberste Element aus dem Dump und schiebt den zuvor entfernten Rückgabewert auf den wiederhergestellten Stapel.
  • dum schreibt ein „dummy“, eine leere Liste, an die Spitze der Environment-Liste.
  • rap funktioniert wie ap mit der Ausnahme, dass es ein Vorkommen eines Dummy-Environments durch das augenblickliche Environment ersetzt. Auf diese Weise werden rekursive Funktionen möglich.

Dazu kommt noch eine Anzahl von Instruktionen für primitive Funktionen wie „car“, „cdr“, Listenkonstruktion, Addition, Ein-/Ausgabe und andere. Eventuell nötige Argumente nehmen diese Funktionen vom Stapel.

Literatur

  • Landin, Peter J. 1966: The next 700 programming languages. Commun. ACM 9, 3, 157–166.
  • Kogge, Peter M: The Architecture of Symbolic Computers. ISBN 0-07-035596-7.
  • Danvy, Olivier: A Rational Deconstruction of Landin's SECD Machine. BRICS research report RS-04-30, 2004. ISSN 0909-0878.
  • Field, Anthony J. Field and Peter G. Harrison: Functional Programming. Addison-Wesley, 1988, ISBN 0-201-19249-7.
  • Landin, Peter J: 1964. The mechanical evaluation of expressions. Comput. J. 6, 4, 308–320.
  • Graham, Brian T: The SECD Microprocessor: A Verification Case Study. Springer, 1992, ISBN 0-7923-9245-0.
  • Henderson, Peter: Functional Programming: Application and Implementation. Prentice Hall, 1980, ISBN 0-13-331579-7.

Weblinks

Einzelnachweise

  1. ↑ Ein Bericht über den Entwurf ist verfügbar unter SECD: DESIGN ISSUES.