Cambridge Lisp - Atari ST

KI auf dem ST

Während das Stichwort Künstliche Intelligenz (KI) in der Computerszene seit einigen Monaten hoch im Kurs steht, war es lange Zeit im Zusammenhang mit dem ATARI ST kein Thema. Ein Anachronismus, der nicht zuletzt durch METACOMCOs Cambridge Lisp als aufgehoben zu betrachten ist.

Dies ist umso mehr zu begrüßen, als der ATARI ST für diese an Arbeitsgeschwindigkeit und Speicherbedarf anspruchsvollen Produkte die besten Voraussetzungen mitbringt.

Cambridge Lisp verfügt zudem über einige Features, die man selbst bei weit teuereren Lisp-Systemen vergeblich sucht — als besonderen Leckerbissen einen integrierten Compiler.

Lieferumfang und Dokumentation

Das komplette Programmpaket ist auf zwei Disketten verteilt. Auf der ersten befinden sich das Haupt-Programm, eine GEM-Bibliothek und einige Beispielprogramme. Auf der zweiten ein „Image“-Ordner, in dem einige unverzichtbare, zur „imaginären Lisp-Welt“ gehörige Programm-Module enthalten sind. Sie enthält außerdem weitere, von anderen METACOMCO-Produkten bekannte, Programme wie einen unter TOS laufenden Bildschirm-Editor und die GEM-Shell menu + .

Menu+ ist ein weitgehend frei konfigurierbares Hilfsprogramm zum Aufruf anderer Programme. Es erlaubt u. a. eine komfortable Übergabe optionaler Parameter mit Angaben über den von Lisp zu nutzenden oder freizulassenden Speicherplatz, über die aktuelle Ausgabedatei und dergleichen mehr.

Die englischsprachige Dokumentation von weit über 300 Seiten kann sich sehen lassen. Nach der Darstellung der GEM-Shell und des Editors werden in etwas über 80 Seiten die wichtigsten Features von Cambridge Lisp in thematischer Reihenfolge beschrieben. Hieran schließt sich ein 100 Seiten umfassender, bis auf die GEM-Routinen vollständiger Referenzteil an. Den AES- und VDI-Funktionen, die vollständig und mit ihren Standard-Namen implementiert sind, werden 70 Seiten gewidmet. Hier wäre ein zusätzliches Kapitel zur GEM-Programmierung wünschenswert. In verschiedenen Anhängen erhält der Leser weitere Informationen zum Aufruf von BIOS-, XBIOS- und GEMDOS-Befehlen und zu Fragen der Kompatibilität. Schließlich findet man einige hilfreiche Beispielprogramme und einen 19seitigen Index angefügt.

Sprachumfang

Cambridge Lisp wurde ursprünglich für eine Großrechneranlage entwickelt. Im wesentlichen handelt es sich dabei um eine Erweiterung von Standard Lisp, wie es von Marti u. a. formuliert wurde (SIGPLAN Notices 14(10) 1979).

Der implementierte Sprachumfang kann sich sehen lassen: die Objektliste zählt 727 Funktionen der insgesamt 885 implementierten Lisp-Objekte. Bei einem nicht unbeträchtlichen Teil davon handelt es sich jedoch um Hilfsfunktionen des Compilers. Weiterhin ist zu berücksichtigen, daß dabei die GEM-Funk-tionen mitgerechnet sind und viele Funktionen in mehr oder minder effizienten und restriktiven Varianten existieren.

Angesichts dieser Fülle verbietet sich der Yersuch, einen möglichst vollständigen Überblick über den implementierten Sprachumfang zu geben. Unverzichtbar ist die Darstellung der verfügbaren Funktions- und Datentypen. Bevor wir uns schließlich dem Compiler zuwenden, werden wir noch die Bestandteile des Programmpakets betrachten, die aus einer Programmiersprache ein Programmiersystem machen: Editor, Fehlerbehandlung und ein besonderes Feature von Cambridge Lisp - das Module-System.

Funktionstypen und Kontrollfunktionen

Der Hinweis auf die Abstammung von Standard Lisp sollte nicht darüber hinwegtäuschen, daß es für Lisp keinen Standard gibt, auch wenn gegenwärtig mit Common Lisp versucht wird, einen Standard durchzusetzen. Wer an Common Lisp gewöhnt ist, wird die Spezialformen do und let sowie die Möglichkeit vermissen, &rest-, &aux-, &key- und &optional-Parameter anzugeben. Cambridge Lisp weist hier vielmehr die gleichen Features wie Interlisp auf, einem der auf Großrechnern verbreitetsten Lisp-Dialekte.

In beiden Dialekten werden fehlende aktuelle Parameter automatisch mit nil initialisiert; Funktionen, gleich welchen Typs, können wahlweise als spread (mit einer festen Anzahl von Parametern) oder nospread (mit einer beliebigen Menge von Parametern, deren Werte in Form einer Liste gebunden werden) definiert werden.

Das Fehlen der von Common Lisp bekannten Spezialform „do“, sowie verwandter „Funktionen“ zur Bildung strukturierter Schleifen, erscheint demgegenüber als größeres Manko. Ein Manko, das auch durch den Hinweis, rekursive Funktionsaufrufe seien in Lisp die „natürlichen“ Kontrollstrukturen, nicht wegzudiskutieren ist. Die von Cambridge Lisp zur Verfügung gestellten Makros (for, while, repeat...) sind demgegenüber weniger mächtig und flexibel. Da jedoch die Möglichkeit besteht, Makros selbst zu definieren, kann dies nicht so ins Gewicht fallen: der Benutzer kann solche Spezialformen mit Hilfe des Programm-Features (prog, progn, prog2, go, casego, return) und cond nach seinem eigenen Gutdünken implementieren. Erwähnenswert ist in diesem Zusammenhang noch, daß nichtlokale Ausgänge von Funktionen durch „catch“ und „throw“ unterstützt werden.

Einen anderen Typ von Spezialformen stellen noeval-Funktionen. Ihre Argumente werden, wie die von Makros, beim Einlesen nicht evaluiert. Im Gegensatz zu ihnen führen sie jedoch auch keine zweite Evaluation durch.

Datentypen und Datenstrukturen

Neben den in allen Lisp-Dialekten üblichen Assoziations- und Propertylisten kennt Cambridge Lisp einen weiteren Typ zusammengesetzter Listenstrukturen: AVL-Listen. AVL bezeichnet dabei einen Algorithmus zum Ausbalancieren von Baum-Strukturen und ist ein Akronym für die sowjetischen Wissenschaftler G. M. Adel’son, Vel skii und E. M. Landis. Unter Verwendung der hierfür implementierten Funktionen wird automatisch dafür Sorge getragen, daß die Anzahl der Knoten von jedem Ast nicht um mehr als ± 1 divergieren.

Vektoren spielten traditionell in Lisp gegenüber den flexibleren Listen keine Rolle. Da sie jedoch durch die feste sequentielle Anordnung ihrer Elemente effizienter als über Pointer vermittelte Listenstrukturen sind, werden sie in modernere Dialekte wie Cambridge Lisp als originäre Datentypen aufgenommen. Als Elemente von Vektoren sind beliebige Lisp-Objekte, mithin auch Vektoren, zugelassen.

Neben ganzen Zahlen, die von beliebiger Größe sein können, und Gleitpunktzahlen kennt Cambridge Lisp noch rationale Zahlen, die in Form einer Liste repräsentiert werden.

Die arithmetischen Funktionen schließen Bitoperationen ebenso ein wie trigonometrische Funktionen und Berechnungen mit auf bestimmte Intervalle reduzierten Zahlen.

Ein- und Ausgabe

Das in Cambridge Lisp realisierte Konzept der „Datenströme“ erlaubt, verschiedene Medien wie Terminal, Bildschirm oder Drucker als aktuelle Einoder Ausgabekanäle zu spezifizieren, um den Datenfluß zu lenken. So kann der Benutzer, beispielsweise mit dem Aufruf von Lisp, den Drucker zum aktuellen Ausgabekanal deklarieren und sich ein Ablaufprotokoll ausdrucken lassen.

Bemerkenswert ist in diesem Zusammenhang die Flexibilität und Offenheit der Zeichen-Syntax. Es besteht freier Zugang zur Syntax-Tabelle. Ohne Umstände können so die Eigenschaften von Zeichen verändert werden: ob ein Zeichen etwa als Trennzeichen oder als escape-Zeichen wirkt oder ob es als Readmacro fungiert. Durch solche Readmacros - die bekanntesten der bereits implementierten sind das Quote-(’) und Backquote-Zeichen (‘) - können bereits in der Einlese-Phase bestimmte Textersetzungen vorgenommen werden.

Bestandteile des Programmiersystems

Editor : integrierter Bildschirmeditor unter TOS; manövriert auf Lisp-Klammern; Blockoperationen, Such- und Ersetzungsfunktionen; Schnittstelle: ausschließlich Dateien, keine Funktionen

Fehlerbehandlung : über 260 implementierte Fehlermeldungen; Backtrace mit einstellbarer Informationsfülle; error, errorset (zur Kontrolle fehlerhafter Programmabläufe); trace, tracesetq, tracecount und embed - mit Ausnahme von tracesetq auch auf kompilierte Funktionen anzuwenden; kein Break-Modus

Module-System : Einrichten verschiedener Lisp-Welten (core image dumping) in Modulen abgelegte Funktionen werden bei Aufruf automatisch geladen, sofern sie nicht im Speicher sind (load on call)

Sonstiges : Automatische Speicherverwaltung (dem Bedarf anpassende Aufteilung) Prettyprinter mit verschiedenen Optionen: quote als Makro-Zeichen, evaluierbare Ausgabe (mit escape-Zeichen) u.v.a.m.

Editor

Bei dem im Programmpaket enthaltenen Editor handelt es sich um einen unter TOS laufenden Bildschirm-Editor. Er ist in zwei Versionen implementiert: die erste ist vom Desktop oder der GEM-Shell aufrufbar.

Die zweite ist in Lisp integriert, d. h. sie wird durch einen Lisp-Befehl aufgerufen und gibt nach Beendigung die Kontrolle wieder an den Lisp-Interpreter zurück. Unterstützt werden eine Reihe von Editierfunktionen, einschließlich Blockoperationen sowie Such- und Ersetzungsfunktionen. Zudem erlaubt die in Lisp integrierte Version auf Lisp-Ausdrücken zu manövrieren. Über Funktionstasten ist es möglich, den Cursor zur jeweils zugehörigen Klammer einer Liste und zur nächsten oder vorausgehenden Liste zu bewegen. Ein zweifellos für die Lisp-Programmierung nützliches Feature.

Neben der fehlenden GEM-Unterstützung ist zu bemängeln, daß der Zugang zum Editor ausschließlich über Dateien erfolgt. Zu einer komfortablen Entwicklungsumgebung gehört sicherlich auch die Möglichkeit, dem Editor Funktionen zu übergeben. In dieser Hinsicht hat beispielsweise der Editor von DR. LOGO mehr zu bieten, ganz zu schweigen von Lisp-Editoren, die eine Evaluation ermöglichen.

Fehlerbehandlung

Einen wesentlichen Bestandteil eines Programmiersystems stellen die Werkzeuge zur Diagnose und Kontrolle von Fehlern dar.

In Cambridge Lisp sind dazu eine Reihe nützlicher Funktionen vorgesehen. Mit error lassen sich benutzerdefinierte Fehlermeldungen einbauen, mit errorset Fehler abfangen und die Kontrolle über fehlerhafte Programmabläufe sichern. Mit trace kann der Benutzer die aktuellen Werte der Parameter der angegebenen Funktionen sowie deren Funktionswerte verfolgen, mit tracesetq die Wertbindungen der freien Variablen. Tracecount erlaubt, eine bestimmte Anzahl von Trace-Meldungen zu unterdrücken. Zusätzliche Informationen über die jeweils aktuelle Funktionsumgebung können mit embed erhalten werden. Diese Funktion ermöglicht reversible Modifikationen von Funktionen: der alte Funktionskörper wird bis auf Widerruf in einen neuen „eingebettet“. Schließlich erfolgt nach Fehlern ein Backtrace, dessen Informationsfülle vom Benutzer eingestellt werden kann. Einziges Manko dieser sonst vorbildlichen Fehlerbehandlung ist das Fehlen eines Break-Modus, der nach einem Fehler die Untersuchung der aktuellen Umgebung und die Fortführung des Programmablaufs bei korrigierbaren Fehlern ermöglicht.

Das Module-System

Mit dem Module-Sytem weist Cambridge Lisp ein äußerst nützliches Feature auf, das von seiner Großrechner-Herkunft zeugt.

Das Module-System erlaubt nämlich, verschiedene „Lisp-Welten“ mit eigenem Sprachumfang und eigener Syntax zu schaffen. Daß sich dies nicht nur als nützlich erweist, wenn mehrere Benutzer einer Anlage mit ihrer persönlichen „Lisp-Welt“ arbeiten möchten, braucht wohl nicht weiter erläutert zu werden. Es bietet jedoch noch mehr Vorteile und ist es wert, seine Funktionsweise genauer darzustellen.

Von den im Lieferumfang enthaltenen Modulen hat eines einen besonderen Status - das Modul Lisproot. In dieser „Wurzel“ ist die Umgebung festgelegt, in der sich der Benutzer nach dem Laden des Lisp-Programms findet. Mit preserve können in ihr neue Funktionen und Lisp-Objekte ebenso bewahrt werden wie Modifikationen der implementierten. Es ist sogar möglich, eine Funktion anzugeben, mit der das System nach dem Laden startet. Weniger angenehm ist, daß Lisp automatisch verlassen wird, nachdem mit preserve ein neues „core image“ geschaffen wurde.

Das Module-System enthält ferner ein nützliches Instrumentarium, um mit den bei größeren Programmiersystemen auftretenden Speicherplatz-Problemen umzugehen. Praktisch machen sich solche Probleme bei Lisp oft durch erheblich reduzierte Ablaufgeschwindigkeiten bemerkbar. (Eine Erfahrung, die jeder auch mit einem kleinen Programm wie XLISP machen kann, wenn er nicht mit expand genügend Speicherplatz reserviert.)

Ruft man die Funktion module auf, so werden bis auf Widerruf die im folgenden kompilierten Funktionen im Binärcode abgespeichert. Gleichzeitig werden sie in die Objektliste mit einem speziellen Wert aufgenommen. Sofern solcherart gespeicherte Funktionen sich nicht im Speicher befinden, bewirkt ihr Aufruf, daß das zugehörige Modul geladen wird, bevor sie ausgewertet werden. Die Module können auch wieder aus der aktuellen „Lisp-Welt“ verbannt werden. Wird der Speicherplatz zu eng, übernimmt diese Aufgabe der garbage col-lector. Für das Nachladen solcher Module ist eigens eine fast-load-Funktion eingebaut. Arbeitet man mit einer Ramdisk, so benötigt das Laden des knapp 70 KB großen Compiler-Moduls ca. 2 Sekunden.

„Integrierter“ Compiler für „Inkrementelle“ Kompilation

Lisp-Compiler stellen immer noch eine Rarität unter den vielen Lisp-Implementationen dar - gerade auf Mikrocomputern. Ein Umstand, der sicherlich nicht wenig zu dem Haupt-einwand gegen diese mächtige Sprache, sie sei zu langsam, beigetragen hat.

Die Praxis, Lisp vorrangig als Interpreter zu implementieren, hängt wohl nicht zuletzt mit ihrem Verwendungszweck zusammen: vom Standpunkt der experimentellen Erforschung „künstlicher Intelligenz“ ist die effiziente, interaktive Programmentwicklung wichtiger als die Ablaufgeschwindigkeit eines bereits entwickelten Programms.

Die Kommerzialisierung der Kl-Pro-dukte mag ein Beweggrund dafür gewesen sein, dies zu verändern. Wenn aber die Arbeit mit Compilern auf eigens für Lisp konstruierte Maschinen, sogenannten Lisp-Maschinen, zur gängigen Praxis geworden ist, so liegt das wohl eher daran, daß diese Compiler mit der in der “Lisp-Gemeinde“ bevorzugten Programmiermethodik des „strukturierten Wachstums“ nicht im Widerspruch stehen.

Was das heißt, wird verständlicher, wenn wir die Arbeit mit dem Cambridge Lisp Compiler betrachten.

Der erste Unterschied zu Verfahrensweisen in anderen Sprachen besteht darin, daß der Compiler von Lisp aufgerufen wird. Dies kann explizit geschehen, indem der Funktion compile eine Liste mit den zu kompilierenden Funktionen übergeben wird. Es kann aber auch automatisch geschehen, indem der Systemvariablen ★comp ein Wert ungleich nil zugewiesen wird. Im letzten Fall werden die Funktionsdefinitionen, sobald sie dem System übergeben werden, unmittelbar kompiliert. Das geht bei den in Lisp üblichen Funktionsgrößen so schnell, daß man den Unterschied zum Interpretermodus kaum bemerkt. Und wenn man will, kann man — wiederum durch Setzen einer Systemvariablen — dafür Sorge tragen lassen, daß der „Lisp-Quell-Code gesichert wird.

Die Arbeit mit dem Compiler gestaltet sich insofern kaum anders als die mit dem Interpreter: einzelne Funktionen können geschrieben, getestet, beliebig von anderen Funktionen aufgerufen und kompiliert werden. All dies geschieht, ohne daß sie etwa von einem „Hauptprogramm“ aufgerufen werden müßten, oder daß ein externer Linkvorgang eingeleitet werden müßte. Ganz zu schweigen von der Notwendigkeit, ein Batch-Programm schreiben zu müssen, das den Quellcode durch den Compiler leitet.

Die kompilierten Funktionen können dabei nach Belieben mit zu interpretierenden gemischt werden. Ob kompiliert oder nicht, jede definierte Funktion erweitert den Sprachumfang der aktuellen „Lisp-Welt“ und kann genauso benutzt werden wie eine Systemfunktion. Insofern bleibt das Konzept der „Spracherweiterung“ voll erhalten.

Semantische Besonderheiten des Compilers

Einschränkend muß jedoch darauf hingewiesen werden, daß der Compiler einige semantische Besonderheiten aufweist.

Abgesehen von dem Unikum, daß das kompilierte prog2 sich wie progn verhält, sind folgende Unterschiede zu beachten.

Zum einen müssen freie Variablen als fluid deklariert sein. Dies geschieht automatisch, wenn ihnen auf Toplevel ein Wert zugewiesen wird, nicht jedoch wenn die WertzuWeisung lediglich innerhalb eines Funktionskörpers erfolgt.

Weitere Besonderheiten treten im Zusammenhang mit Spezialformen auf, den lambdaq-Ausdrücken und den Makros. Werden Funktionen kompiliert, die noch nicht definierte Makros auf-rufen, so muß dies dem Compiler mitgeteilt werden. Insbesondere muß darauf geachtet werden, daß Makros während der Kompilation expandiert werden. Hat man beispielsweise eine Funktion kompiliert, in der ein Makro aufgerufen wird, und ändert man anschließend die Definition dieses Makros, so hat diese Änderung keinen Einfluß auf das Verhalten der kompilierten Funktion. Die Merkwürdigkeit, daß Funktionen mit Makros effizienter sein können als mit „normalen“ Lisp-Funktionen, ist wohl darauf zurückzuführen, daß aufgrund der Makroexpansion Funktionsaufrufe unterbleiben.

Zwar unterstützt Cambridge Lisp die Möglichkeit, auch „normale“ Funktionen ohne Funktionsaufruf zu kodieren, die zu dieser inline-Kodierung notwendigen internen Kenntnisse werden jedoch vom Handbuch nicht vermittelt.

Benchmarks

Wenn auch bei einer Sprache wie Lisp die Frage der maschinellen Effizienz gegenüber der kognitiven, die Frage der Ablaufgeschwindigkeit gegenüber der des Instrumentariums rationeller und komfortabler Programmierung „künstlicher Intelligenz“ an Gewicht verliert, so ist sie dennoch von nicht unerheblichem Interesse.

Die in der Tabelle abgedruckten Ergebnisse eines Vergleichs zwischen dem Public-Domain-Programm XLISP und Cambridge Lisp bedürfen einiger Kommentare. Es sollte grundsätzlich klar sein, daß hier Unterschiedliches auf Gleiches reduziert wird. Man muß davon ausgehen, daß Cambridge Lisp bei der Evaluation einiges mehr zu tun hat als XLISP. Daher sollte es nicht verwundern, daß dieser Interpreter „langsamer“ ist. Ein kaum lösbares Problem stellen die Unterschiede beider Dialekte hinsichtlich der Datentypen und Systemfunktionen dar. Es gibt kaum zwei Funktionen in ihnen, die sich exakt gleich verhalten.

Die Tests zur rekursiven Berechnung der Fakultät sind zugleich ein Beispiel für die Verarbeitung ungewöhnlich großer - über eine Bildschirmseite reichender - Zahlen. Auffallend ist, daß bei diesen Zahlen der Unterschied zwischen Compiler und Interpreter nahezu bedeutungslos wird. Bei den anderen Funktionen ist er jedoch gravierend -die kompilierten Funktionen sind bis über fünfzigmal schneller.

Bei der Funktion Q, entnommen aus D. R. Hofstadters „Gödel, Escher, Bach“ (1985, 149), handelt es sich um eine hochgradig rekursive arithmetische Funktion. Sie wurde in diesen Test nicht zuletzt deswegen aufgenommen, weil die in ihr vorkommenden Zahlen auch von XLISP bewältigt werden können.

Queen ist ein Programm zur Lösung einer Denksportaufgabe: wie können acht Damen so auf einem Schachbrett positioniert werden, daß sie sich nicht gegenseitig bedrohen. Das Programm wurde der hervorragenden Lisp-Ein-führung von P. EI. Winston und B. K. P. Horn entnommen (LISP, 2. Auflage, Addison-Wesley 1984). Um bessere Vergleichsmöglichkeiten zu haben, wurde die Aufgabe auf kleinere Felder übertragen. Es ist insofern typisch für Lisp, als seine Abarbeitung über viele, teilweise indirekt-rekursive Funktionsaufrufe, sowie listenverarbeitende Funktionen erfolgt.

Um das Verhalten bei einem etwas komplexeren Programm zu testen, wurde ein ATN-Parser zur Syntax-Analyse „natürlicher“ Sprache ausgewählt. Hier zeigt sich die Problematik solcher Vergleichstests besonders deutlich. Ursprünglich in XLISP geschrieben, mußten wichtige in XLISP bereits implementierte Funktionen für die Cambridge Lisp-Version von Hand geschrieben werden. Eine die Möglichkeiten von Cambridge Lisp besser nutzende Version ist etwas effizienter. Während sie interpretiert aber immer noch langsamer als das XLISP-Programm ist, läuft sie kompiliert über zwanzigmal so schnell.

Gesamteindruck

Mit Cambridge Lisp bietet META-COMCO ein ebenso mächtiges wie flexibles und komfortables Programmiersystem an, das meines Erachtens zu den besten Software-Produkten gehört, die derzeit für den Atari ST verfügbar sind.

Zu wünschen ist allerdings, daß die angesprochenen Mängel wie die fehlende GEM-Unterstützung bald behoben werden. Auch würde die Aufnahme des einen oder anderen Konzepts moderner Lisp-Dialekte dieses Produkt bereichern und die Lisp-Programmierung auf dem Atari ST noch attraktiver machen. Ich denke dabei an Flavors zur objektorientierten Programmierung, wie sie bereits von XLISP unterstützt wird, an das von Common Lisp bekannte Konzept der multiple values sowie die Möglichkeit der lokalen Bindung von Funktionen, wie sie SCHEME bietet.

Am positiven Gesamteindruck ändert dies nichts. Kein Zweifel, mit Cambridge Lisp läßt sich der Atari ST zu einem Instrument ausbauen, das für ernsthafte Kl-Projekte gut gerüstet ist und auch einen Vergleich mit teuereren Systemen nicht zu scheuen braucht.

Benchmarks

Programm	n	XLISP	Cambridge	Lisp
		interpretiert	kompiliert
Fakultät	100	—	1.75”	0.56”
500	-	16.81”	11”
1000 -	60.47”	49”
Q	10	2.84”	5.60”	-
12	7.85”	15.54”	—
14	22.03”	41.94”	0.78”
Queen	4	2.47”	4.16”	-
5	10.75”	17.62”	-
6	49.50”	77”	2.72”
ATN-Parser	1	0.81”	3.20”/ 1.53	-
(n Beispielsätze)	10	5.88”	29.22”/13.13”	-
30	18.97”	86.60”/38.53”	0.81”

---

---