From 04e68443040c7abad84d66477e98f93bed701760 Mon Sep 17 00:00:00 2001 From: Lars-Dominik Braun Date: Mon, 4 Feb 2019 13:09:03 +0100 Subject: Initial import --- lang/lisp/1.8.7/doc/lisp handbuch | 2260 +++++++++++++++++++++++++++++++++++++ 1 file changed, 2260 insertions(+) create mode 100644 lang/lisp/1.8.7/doc/lisp handbuch (limited to 'lang/lisp/1.8.7/doc/lisp handbuch') diff --git a/lang/lisp/1.8.7/doc/lisp handbuch b/lang/lisp/1.8.7/doc/lisp handbuch new file mode 100644 index 0000000..022c561 --- /dev/null +++ b/lang/lisp/1.8.7/doc/lisp handbuch @@ -0,0 +1,2260 @@ +____________________________________________________________________________ + + +#on("b")##on ("u")# +#center#Betriebssystem E U M E L +#off ("u")# + + +#center#Lisp + + + + +#off("b")# +#center#Lizenzfreie Software der +#on ("b")# + +#center#Gesellschaft für Mathematik und Datenverarbeitung mbH, +#center#5205 Sankt Augustin + + +#off("b")# +#center#Die Nutzung der Software ist nur im Schul- und Hochschulbereich für +#center#nichtkommerzielle Zwecke gestattet. + +#center#Gewährleistung und Haftung werden ausgeschlossen + + +____________________________________________________________________________ +#page# +#free(7.0)# +#center#LISP - Handbuch +#free(2.0)# +Stand: 08.08.86 + +Installation von LISP + +begin ("LISP") +reserve ("sprachen",archive) +fetch all(archive) +insert ("lisp.1") +insert ("lisp.2") +insert ("lisp.3") +insert ("lisp.4") +global manager +begin ("lisp","LISP") +fetch ("lisp.bootstrap") +lisp +#page# +#start(2.5,1.5)# +#block# +#pageblock# +#head# +#center#LISP-Handbuch +#center#% + + +#end# + + +#center#L I S P H a n d b u c h + + +#center#Autor: John Mc.Carthy (M.I.T.1962) +#center#übersetzt und angepaßt von J.Durchholz, P.Heyderhoff +#center#Gesellschaft für Mathematik und Datenverarbeitung Sankt Augustin + + + +Inhaltsverzeichnis + + + +1. Die Sprache LISP #right##topage("p1")# + +1.1 Symbolische Ausdrücke #right##topage("p1.1")# +1.2 Elementare Funktionen #right##topage("p1.2")# +1.3 Listen Notation #right##topage("p1.3")# +1.4 Syntax und Semantik der Sprache #right##topage("p1.4")# + +2. Das LISP-Interpreter-System #right##topage("p2")# + +2.1 Die universelle LISP-Funktion "evalquote" #right##topage("p2.1")# +2.2 Anwendungsregeln und Beispiele #right##topage("p2.2")# +2.3 Variablen #right##topage("p2.3")# +2.4 Konstanten #right##topage("p2.4")# +2.5 Funktionen #right##topage("p2.5")# + +3. Erweitertes LISP #right##topage("p3")# + +3.1 Gequotete Parameter #right##topage("p3.1")# +3.2 Funktionen mit beliebig vielen Parametern #right##topage("p3.2")# +3.3 Funktionale Parameter #right##topage("p3.3")# +3.4 Prädikate und boolesche Konstanten #right##topage("p3.4")# +3.5 Unbenannte Atome #right##topage("p3.5")# +3.6 Aufruf von EUMEL aus #right##topage("p3.6")# + +4. Detailbeschreibungen #right##topage("p4")# + +4.1 Grundfunktionen #right##topage("p4.1")# +4.2 Weitere Funktionen sowie Eingabe und Ausgabe #right##topage("p4.2")# +4.3 Interpreter #right##topage("p4.3")# +4.4 Kommandoprozeduren #right##topage("p4.4")# +#page# + +1. Die Sprache LISP#goalpage("p1")# + + + +Die Sprache LISP ist primär für die Symbolmanipulation entworfen. Sie wurde für +symbolische Berechnungen in verschiedenen Gebieten der künstlichen Intelligenz +eingesetzt, u.a. für Differential- und Integralrechnung, Schaltkreistheorie, Mathemati­ +sche Logik, Spiele, etc.. + +LISP ist eine formale mathematische Sprache. Daher ist es möglich, eine genaue und +vollständige Beschreibung zu geben. Das ist der Sinn des ersten Abschnitts dieses +Handbuchs. Andere Abschnitte werden Möglichkeiten zum vorteilhaften Einsatz von +LISP und die Erweiterungen, die die Benutzung erleichtern, beschreiben. + +LISP unterscheidet sich von den meisten Programmiersprachen in drei Punkten. + +Der erste Punkt liegt in der Natur der Daten. In der Sprache LISP haben alle Daten +die Form symbolischer Ausdrücke, die wir verkürzend LISP-Ausdrücke nennen wer­ +den. LISP-Ausdrücke haben keine Längenbegrenzung und eine verzweigte Baum­ +struktur, so daß Unterausdrücke leicht isoliert werden können. In LISP wird der meiste +Speicherplatz für das Abspeichern der LISP-Ausdrücke in Form von Listenstruktu­ +ren gebraucht. + +Der zweite wichtige Teil der Sprache LISP ist die Quellsprache, die festlegt, wie die +LISP-Ausdrücke verarbeitet werden sollen. + +Drittens kann LISP als LISP-Ausdrücke geschriebene Programme interpretieren und +ausführen. Deshalb kann man die Sprache analog zu Assemblersprachen und im +Gegensatz zu den meisten anderen höheren Programmiersprachen einsetzen, um +Programme zu generieren, die gleich ausgeführt werden sollen. + + +#page# + +1.1 Symbolische Ausdrücke #goalpage("p1.1")# + + + +Ein elementarer Ausdruck ist ein Atom. + +Definition: Ein Atom ist eine Zeichenkette bestehend aus Großbuchstaben und + Ziffern. + + +Beispiele: A + APFEL + TEIL2 + EXTRALANGEZEICHENKETTEAUSBUCHSTABEN + A4B66XYZ2 + + +Diese Symbole werden atomar genannt, weil sie als Ganzes aufgefaßt werden, das +durch die LISP-Funktionen nicht weiter geteilt werden kann. A, B, und AB haben +keinerlei Beziehung zueinander, außer der, daß sie alle verschiedene Atome sind. + +Alle LISP-Ausdrücke werden aus Atomen und den Satzzeichen "(", ")" und "." +aufgebaut. Die grundlegende Operation zum Aufbau von LISP-Ausdrücken ist die, +zwei LISP-Ausdrücke zusammenzufassen, um einen größeren herzustellen. Aus den +zwei Atomen A und B kann man so den LISP-Ausdruck (A.B) bilden. + +Definition: Ein LISP-Ausdruck ist entweder ein Atom, oder aus folgenden Elemen­ + ten in dieser Reihenfolge aufgebaut: Eine öffnende Klammer, ein + LISP-Ausdruck, ein Punkt, ein LISP-Ausdruck, eine schließende + Klammer. Zwischen den Bestandteilen eines nichtatomaren LISP-Aus­ + druck können beliebig viele Leerzeichen eingestreut sein. + +Diese Definition ist rekursiv. + + +Beispiele: ATOM + (A . B) + (A . (B . C)) + ((A1 . A2) . B) + ((U . V) . (X . Y)) + ((U . V) . (X . (Y . Z))) + + +Um die Struktur solcher Ausdrücke zu verdeutlichen, wird in diesem Handbuch oft +eine graphische Darstellung gewählt. In dieser Darstellung sind die Atome weiterhin +Zeichenketten, statt der Paare steht jetzt aber ein Kasten + + + +-----+-----+ + | o | o | + +-----+-----+ + + +von dem zwei Zeiger ausgehen, die auf die graphische Darstellung des ersten bzw. +zweiten Elements des Paars zeigen. + + + +Beispiele: (A . B) +-----+-----+ + | o | o | + +--+--+--+--+ + | | + V V + A B + + (A . (B . C)) +-----+-----+ + | o | o | + +--+--+--+--+ + | | + V V + A +-----+-----+ + | o | o | + +--+--+--+--+ + | | + V V + B C + + ((U . V) . (X . (Y . Z))) +-----+-----+ + | o | o | + +--+--+--+--+ + | | + V V + +-----+-----+ +-----+-----+ + | o | o | | o | o | + +--+--+--+--+ +--+--+--+--+ + | | | | + V V V V + U V X +-----+-----+ + | o | o | + +--+--+--+--+ + | | + V V + Y Z + + + + + + +#page# + +1.2 Elementare Funktionen #goalpage("p1.2")# + + +Wir werden einige elementare Funktionen auf LISP-Ausdrücken einführen. Um die +Funktionen von den LISP-Ausdrücken zu unterscheiden, werden wir Funktionsnamen +mit Klein- statt Großbuchstaben schreiben. Außerdem steht der Funktionsname +gefolgt von den Argumenten, auf die die Funktion angewendet werden soll, in Klam­ +mern eingeschlossen in einer Liste. Dabei sind die Argumente durch Blanks vonein­ +ander getrennt. + +Die erste Funktion, die wir einführen, heißt "cons". Sie hat zwei Argumente und wird +dafür benutzt, LISP-Ausdrücke aus kleineren LISP-Ausdrücken aufzubauen. + + + Funktionsaufruf: Ergebnis: + +Beispiele: (cons A B) = (A . B) + (cons (A . B) C) = ((A . B) . C) + (cons (cons A B) C) = ((A . B) . C) + + +Die Beispiele zeigen Funktionsaufrufe. Ein Funktionsaufruf ist eine Liste beginnend +mit einem Funktionsnamen, gefolgt von Argumenten. Alle Funktionsaufrufe haben ein +Ergebnis, das im Fall von LISP-Funktionen immer ein LISP-Ausdruck ist. + +In diesen Beispielen kommt nur die Funktion "cons" vor. Das letzte Beispiel ist ein +Fall von Funktionsverkettung, das heißt, als Argument steht ein Funktionsaufruf. Um +das Ergebnis eines Funktionsaufrufs zu berechnen, das Funktionsaufrufe als Argu­ +mente enthält, muß man statt dieser Argumente die Ergebnisse dieser Funktionsaufru­ +fe einsetzen, so daß man den äußeren Funktionsaufruf in einen Aufruf ohne Funk­ +tionsaufrufe als Argumente umwandelt. + + +Beispiel: (cons (cons A B) C) = (cons (A . B) C) = ((A . B) . C) + + +Es ist möglich, durch Verkettung der Funktion "cons" jeden LISP-Ausdruck aus +seinen atomaren Komponenten aufzubauen. + +Die folgenden beiden Funktionen tun das genaue Gegenteil von "cons": sie liefern +die Unterausdrücke eines gegebenen LISP-Ausdrucks. + +Die Funktion "head" hat ein Argument. Ihr Wert ist der erste Unterausdruck des +zusammengesetzen Arguments. Der "head" eines Atoms ist nicht definiert. + + +Beispiele: (head (A . B)) = A + (head (A . (B1 . B2))) = A + (head ((A1 . A2) . B)) = (A1 . A2) + (head A) ist nicht definiert + + +Die Funktion "tail" hat ebenfalls ein Argument, und sie liefert das Argument bis auf +dessen "head". + + +Beispiele: (tail (A . B)) = B + (tail (A . (B1 . B2))) = (B1 . B2) + (tail ((A1 . A2) . B)) = B + (tail A) ist nicht definiert + (head (tail (A . (B1 . B2)))) = B1 + (head (tail (A . B))) ist nicht definiert + (head (cons A B)) = A + + +Es ist bei jedem LISP-Ausdruck möglich, durch eine geeignete Verkettung von +"head" und "tail" zu jedem Atom im Ausdruck zu gelangen. + +Wenn "x" und "y" irgendwelche LISP-Ausdrücke repräsentieren, gelten die folgen­ +den Gleichungen immer: + + + (head (cons x y)) = x + (tail (cons x y)) = y + + +Außerdem gilt die folgende Gleichung für jeden nichtatomaren LISP-Ausdruck "z": + + + (cons (head z) (tail z)) = z +9 + +Die Symbole "x", "y" und "z", die wir in diesen Gleichungen benutzt haben, nennt +man Variablen. In LISP werden Variable benutzt, um LISP-Ausdrücke zu repräsentie­ +ren, und zwar repräsentiert eine Variable in einer Gleichung immer denselben +LISP-Ausdruck. Variablennamen werden wie Funktionsnamen gebildet, d.h. sie +können Kleinbuchstaben und Ziffern enthalten. + +Eine Funktion, deren Wert "wahr" oder "falsch" sein kann, wird Prädikat genannt. In +LISP werden die Werte "wahr" und "falsch" durch die Atome "T" (true) und "F" +(false) vertreten. Ein LISP-Prädikat ist also eine Funktion, deren Wert entweder "T" +oder "F" ist. + +Das Prädikat "eq" ist ein Gleichheitstest für Atome. Es ist bei nicht atomaren Argu­ +menten nicht definiert. + + +Beispiele: (eq A A) = T + (eq A B) = F + (eq A (A . B)) ist nicht definiert + (eq (A . B) B) ist nicht definiert + (eq (A . B) (A . B)) ist nicht definiert + + +Das Prädikat "atom" hat das Ergebnis ("liefert") "T", wenn sein Argument atomar ist, +und "F", wenn sein Argument zusammengesetzt ist. + + +Beispiele: (atom EXTRALANGEZEICHENKETTE) = T + (atom (U . V)) = F + (atom (head (U . V))) = T + +#page# + +1.3 Listen-Notation #goalpage("p1.3")# + + + +Alle LISP-Ausdrücke, die wir bisher gesehen haben, waren in Punkt-Notation +geschrieben. Normalerweise ist es allerdings einfacher, statt der vielen Punkte und +Klammern Listen von LISP-Ausdrücken zu schreiben, etwa in der Art (A B C XYZ). + +LISP bietet eine solche Alternative zur Punkt-Notation an: + +Definition: Die Liste (a1 a2 ... an) ist äquivalent zum LISP-Ausdruck + (a1 . (a2 . (... . (an . NIL) ... ))). + +Graphisch ausgedrückt heißt das: + + + +-----+-----+ + | o | o | + +--+--+--+--+ + | | + V V + a1 +-----+-----+ + | o | o | + +--+--+--+--+ + | | + V V + a2 + . + . + . + + +-----+-----+ + | o | o | + +--+--+--+--+ + | | + V V + an NIL + + + +Oft werden wir für Listen auch die graphische Form + + + +-----+-----+ +-----+-----+ +-----+-----+ + | o | o--+-->| o | o--+--> . . . | o | o--+--> NIL + +--+--+-----+ +--+--+-----+ +--+--+-----+ + | | | + V V V + a1 a2 an + + +benutzen. + +Aus der Graphik wird deutlich, daß NIL als eine Art Abschlußmarkierung für Listen +dient. + +Eine leere Liste wird durch das Atom NIL dargestellt. Das Prädikat "null" liefert "T", +wenn sein Argument eine leere Liste ist, sonst "F". + + +Beispiele: (null NIL) = T + (null () ) = T + (null (A B)) = F + + +Die Listenelemente können selbst wieder Listen oder Paare in Punkt-Notation sein, +so daß Listen- und Punkt-Notation beliebig kombinierbar sind. + + + Beispiele: (A B C) = (A . (B . (C . NIL))) + + +-----+-----+ +-----+-----+ +-----+-----+ + | o | o--+-->| o | o--+-->| o | o--+--> NIL + +--+--+-----+ +--+--+-----+ +--+--+-----+ + | | | + V V V + A B C + + ((A . B) C) = ((A . B) . (C . NIL)) + + +-----+-----+ +-----+-----+ + | o | o--+-->| o | o--+--> NIL + +--+--+-----+ +--+--+-----+ + | | + V V + +-----+-----+ C + | o | o | + +--+--+--+--+ + | | + V V + A B + + ((A B) C) = ((A . (B . NIL)) . (C . NIL)) + + +-----+-----+ +-----+-----+ + | o | o--+--------------->| o | o--+--> NIL + +--+--+-----+ +--+--+-----+ + | | + | V + V C + +-----+-----+ +-----+-----+ + | o | o--+-->| o | o--+--> NIL + +--+--+-----+ +--+--+-----+ + | | + V V + A B + + (A) = (A . NIL) + + +-----+-----+ + | o | o--+--> NIL + +--+--+-----+ + | + V + A + + ((A)) = ((A . NIL) . NIL) + + +-----+-----+ + | o | o--+--> NIL + +--+--+-----+ + | + V + +-----+-----+ + | o | o--+--> NIL + +--+--+-----+ + | + V + A + + + + + +Es ist sehr hilfreich, mit den Ergebnissen der elementaren Funktionen vertraut zu +sein, wenn diese Listen als Argumente erhalten. Zwar können die Ergebnisse notfalls +immer durch Übersetzung in Punkt-Notation bestimmt werden, aber ein direktes +Verständnis ist einfacher. + + +Beispiele: (head (A B C)) = A + (tail (A B C)) = (B C) + + + (Daher auch die Namen "head" und "tail"! Frei übersetzt heißen die + beiden Funktionen "anfang" und "rest".) + + + (cons A (B C)) = (A B C) + +#page# + +1.4 Syntax und Semantik der Sprache #goalpage("p1.4")# + + + +Wir haben bisher einen Datentyp (LISP-Ausdrücke) und fünf elementare Funktionen +eingeführt. Außerdem haben wir die folgenden Eigenschaften der Sprache beschrie­ +ben: + +1. Funktions- und Variablennamen werden wie die Namen von Atomen geschrie­ + ben, außer, daß dafür Klein- statt Großbuchstaben verwendet werden. +2. Die Argumente einer Funktion folgen dieser in der Liste. Eine solche Liste von + Funktion und folgenden Argumenten heißt Funktionsaufruf und hat einen LISP- + Ausdruck als Ergebnis. +3. Funktionen können dadurch verkettet werden, daß ein Argument aus einem Funk­ + tionsaufruf selbst wieder ein Funktionsaufruf ist, dessen Argumente selbst wieder + Funktionsaufrufe sein können, usw. + +Diese Regeln erlauben es, Funktionsdefinitionen wie + + + (third x) = (head (tail (tail x))) + + +zu schreiben. "third" holt das dritte Element aus einer Liste. + +Die Klasse der Funktionen, die man auf diese Weise bilden kann, ist ziemlich be­ +schränkt und nicht sehr interessant. Eine viel größere Funktionenklasse kann man mit +Hilfe des bedingten Ausdrucks schreiben; es handelt sich dabei um eine Möglichkeit, +Verzweigungen in Funktionsdefinitionen einzubauen. + +Ein bedingter Ausdruck hat die Form + + + (cond (p1 a1) (p2 a2) ... (pn an) ) + + +Jedes pi ist ein Ausdruck, dessen Wert "T" oder "F" ist, also ein Prädikat. Die ai +sind beliebige LISP-Ausdrücke. + +Die Bedeutung eines bedingten Ausdrucks ist folgende: Wenn p1 wahr ist, ist a1 der +Wert des ganzen Ausdrucks. Wenn p1 falsch ist, wird getestet, ob p2 wahr ist; wenn +das der Fall ist, ist a2 der Wert des Ausdrucks. Die pi werden also von links nach +rechts durchgegangen, bis ein wahrer Ausdruck gefunden ist; das zugehörige ai ist +dann der Wert des bedingten Ausdrucks. Wenn kein wahres pi gefunden ist, ist der +bedingte Ausdruck nicht definiert. +Jedes pi oder ai kann selbst wieder ein LISP-Ausdruck, ein Funktionsaufruf oder ein +bedingter Ausdruck sein. + + +Beispiel: (cond ((eq (head x) A) (cons B (tail x))) (T x) ) + + +Das Prädikat "T" ist immer wahr. Man liest es am besten als "SONST". Den Wert +dieses Ausdruck erhält man, wenn man "head" von x durch B ersetzt, wenn der +gerade gleich mit A ist, und sonst erhält man x. + +Der Hauptzweck von bedingten Ausdrücken ist die rekursive Definition von Funktio­ +nen. + + +Beispiel: (firstatom x) = (cond ((atom x) x) + ( T (firstatom (head x))) + ) + + +Dies Beispiel definiert die Funktion "firstatom", die das erste Atom jedes LISP-Aus­ +drucks bestimmt. Diesen Ausdruck kann man so lesen: wenn "x" ein Atom ist, ist "x" +selbst die Antwort; sonst muß "firstatom" auf "head" von "x" angewandt werden. + +Wenn also "x" ein Atom ist, wird der erste Zweig gewählt, der "x" liefert; sonst wird +der zweite Zweig "firstatom (head x)" gewählt, weil "T" immer wahr ist. + +Die Definition von "firstatom" ist rekursiv, d.h. "firstatom" ist mit durch sich selbst +definiert. Allerdings, wenn man immerzu den "head" von irgendeinem LISP-Aus­ +druck nimmt, errreicht man irgendwann ein Atom, so daß der Prozeß immer wohlde­ +finiert ist. + +Es gibt rekursive Funktionen, die nur für bestimmte Argumente wohldefiniert sind, für +bestimmte andere dagegen unendlich rekursiv. Wenn das EUMEL-LISP-System +einen Funktionsionsaufruf mit einer solchen Funktion und "kritischen" Argumenten +interpretiert, gerät es in unendliche Rekursion, bis entweder der zur Verfügung ste­ +hende Platz im LISP-Heap ausgeschöpft ist (im Heap werden die LISP-Ausdrücke +gespeichert) oder bis der Laufzeitstack überläuft (der Laufzeitstack ist ein normaler­ +weise unsichtbarer Bestandteil des ELAN-Systems). +Wir werden jetzt die Berechnung von "(firstatom ((A . B) . C))" durchführen. Zunächst +ersetzen wir die Variable x in der Funktionsdefinition durch ((A . B) . C) und erhalten + + + (firstatom ((A . B) . C)) = + (cond ( (atom ((A . B) . C)) ((A . B) . C) ) + ( T (firstatom (head ((A . B) . C))) ) + ) + +((A . B) . C) ist kein Atom, deshalb wird daraus + + = (cond ( T (firstatom (head ((A . B) . C)))) ) + = (firstatom (head ((A . B) . C)) ) + = (firstatom (A . B)) + + + +An diesem Punkt müssen wir wieder die Definition von "firstatom" benutzen, diesmal +aber für "x" überall "(A . B)" einsetzen. + + + (firstatom (A . B)) = (cond ( (atom (A . B)) (A . B) ) + (T (firstatom (head (A . B))) ) + ) + = (cond (T (firstatom (head (A . B))) ) ) + = (firstatom (head (A . B)) ) + = (firstatom A) + = (cond ((atom A) A) + (T (firstatom (head A)) ) + ) + = A + + +Wenn in den bedingten Ausdrücken statt der LISP-Ausdrücke arithmetische Aus­ +drücke verwendet würden, könnte man damit auch numerische Rechenvorschriften +definieren, wie z.B. den Betrag einer Zahl durch + + + (abs x) = (cond ((x < 0) -x) (T x) ) + + +oder die Fakultät durch + + + (fak n) = (cond ((n = 0) 1) + (T (x * (fak (n - 1)))) + ) + + +Die Fakultät terminiert bei negativen Argumenten nicht. + +Es ist bei den meisten Mathematikern (außer den Logikern) üblich, das Wort "Funk­ +tion" nicht präzise zu verwenden und auf Ausdrücke wie "2x+y" anzuwenden. Da wir +Ausdrücke benutzen werden, die Funktionen repräsentieren, benötigen wir eine +Notation, die Funktionen und Ausdrücke unterscheidet. Dafür ist die Lambda-Nota­ +tion von Alonzo Church geeignet. +"f" soll ein Ausdruck sein, der für eine Funktion zweier ganzzahliger Variablen steht. + +Dann sollte es sinnvoll sein, den Funktionsaufruf + + + (f 3 4) + + +zu schreiben, so daß man dadurch den Wert dieses Funktionsaufrufs berechnen kann; +z.B. könnte "(summe 3 4) = 7" gelten. + +Wenn man "2x + y" als Funktion ansieht, kann man den Funktionsaufruf + + + ((2x + y) 3 4) + + +schreiben. Der Wert dieses Ausdrucks ist aber nicht eindeutig bestimmt, denn es ist +überhaupt nicht klar, ob nun "2*3+4" oder 2*4+3" gemeint ist. Eine Zeichenfolge +wie "2x + y" werden wir deshalb Ausdruck und nicht Funktion nennen. Ein Ausdruck +kann in eine Funktion umgewandelt werden, indem man die Zuordnung von Argumen­ +ten und Variablen festlegt. Bei "2x + y" könnte man beispielsweise festlegen, daß +"x" immer das erste und "y" immer das zweite Argument sein soll. +Wenn "a" ein Ausdruck in den Variablen x1, ... xn ist, dann ist + + + (lambda (x1 ... xn) a) + + +eine Funktion mit n Argumenten. Den Wert der Funktionsaufrufe mit dieser Funktion +(also der Ausdrücke der Form + + + ((lambda (x1 ... xn) a) (b1 ... bn)) + erhält man, indem man die Variablen x1 ... xn durch die n Argumente des Aufrufs +ersetzt. Beispielsweise ist + + + ((lambda (x y) (2*x + y)) (3 4)) = 2*3 + 4 = 10 , + + +während + + + ((lambda (y x) (2*x + y)) (3 4)) = 2*4 + 3 = 11 + + +ist. + +Die Variablen in einem Lambdaausdruck sind sogenannte Parameter (oder gebundene +Variable). Interessant ist, daß eine Funktion sich nicht ändert, wenn man eine Variable +systematisch durch eine andere Variable ersetzt, die nicht bereits im Lambdaausdruck +vorkommt. + + + (lambda (x y) (2*y + x)) + + +ist also dasselbe wie + + + (lambda (u v) (2*v + u)) . + + +Manchmal werden wir Ausdrücke benutzen, in denen eine Variable nicht durch das +Lambda gebunden ist. Beispielsweise ist das n in + + + (lambda (x y) (x*n + y*n)) + + +nicht gebunden. Eine solche nicht gebundene Variable nennt man frei. +Wenn für eine freie Variable vor der Benutzung kein Wert vereinbart wurde, ist der +Wert des Funktionsaufrufs nicht definiert, falls der Wert der Variablen auf das Ergeb­ +nis einen Einfluß hat. + +Die Lambdanotation reicht allein für die Definition rekursiver Funktionen nicht aus. +Neben den Variablen muß auch der Name der Funktion gebunden werden, weil er +innerhalb der Funktion für eine Zeichenfolge steht. + +Wir hatten die Funktion "firstatom" durch die Gleichung + + + (firstatom x) = (cond ((atom x) x) + (T (firstatom (head x))) + ) + + +definiert. Mit der Lambda-Notation können wir schreiben: + + + firstatom = (lambda (x) (cond ((atom x) x) + (T (firstatom (head x))) + ) ) + + + +Das Gleichheitszeichen ist in Wirklichkeit nicht Teil der LISP-Sprache, sondern eine +Krücke, die wir nicht mehr brauchen, wenn wir die richtige Schreibweise eingeführt +haben. + +Die rechte Seite der obigen Gleichung ist als Funktion nicht vollständig, da dort nichts +darauf hinweist, daß das "firstatom" im einem bedingten Ausdruck für eben die rechte +Seite steht. Deshalb ist die rechte Seite als Definition für die linke Seite ("firstatom") +noch nicht geeignet. + +Damit wir Definitionen schreiben können, in denen der Name der gerade definierten +Funktion auftaucht, führen wir die Label-Notation ein (engl. label = Marke, (Preis-) +Schildchen). Wenn "a" eine Funktion ist, und "n" ihr Name, schreiben wir "(label n +a)". + +Nun können wir die Funktion "firstatom" ohne Gleichheitszeichen schreiben: + + + (label firstatom (lambda (x) (cond ((atom x) x) + (T (firstatom (head x))) + ) ) ) + + +In dieser Definition ist "x" eine gebundene Variable und "firstatom" ein gebundener +Funktionsname. +#page# + +2. Das LISP-Interpreter-System#goalpage("p2")# + + + +2.1 Die universelle LISP-Funktion + "evalquote" #goalpage("p2.1")# + + + +Ein Interpreter oder eine allgemeine Funktion ist eine Funktion, die den Wert jedes +gegebenen Ausdrucks berechnen kann, wenn der Ausdruck in einer geeigneten Form +vorliegt. (Wenn der zu interpretierende Ausdruck einen Aufruf einer unendlich rekur­ +siven Funktion enthält, wird der Interpreter natürlich ebenfalls unendlich rekursiv.) +Wir sind jetzt in der Lage, eine allgemeine LISP-Funktion + + + (evalquote function arguments) + + +zu definieren. "evalquote" muß als erstes Argument ein LISP-Ausdruck übergeben +werden. Dieser wird als Funktion aufgefasst und auf die folgenden Argumente ange­ +wendet. + +Im Folgenden sind einige nützliche Funktionen zur Manipulation von LISP-Aus­ +drücken angegeben. Einige von ihnen werden als Hilfsfunktionen für die Definition von +"evalquote" gebraucht, die wir uns vorgenommen haben. + + + (equal x y) + + +ist ein Prädikat, das wahr ist, wenn seine Argumente gleiche LISP-Ausdrücke sind. +(Das elementare Prädikat "eq" ist ja nur für Atome definiert.) + +Die Definition von "equal" ist ein Beispiel für einen bedingten Ausdruck innerhalb +eines bedingten Ausdrucks. + + +(label equal + (lambda (x y) + (cond + ((atom x) (cond + ((atom y) (eq x y)) + (T F) + ) + ) + ((equal (head x) (head y)) (equal (tail x) (tail y))) + (T F) + ) + ) +) + + + +Folgende Funktion liefert einen LISP-Ausdruck, der gleich mit "destination" ist, +außer daß darin überall statt "old" "new" steht. + + +(changeall (destination old new)) + += (cond ((equal destination old) new) + ((atom destination) destination) + (T (cons (changeall (head destination) old new) + (changeall (tail destination) old new) + ) + ) + ) + + +Beispielsweise gilt + + +(changeall ((A . B) . C) B (X . A)) = ((A . (X . A)) . C) + + +Die folgenden Funktionen sind nützlich, wenn Listen verarbeitet werden sollen. + +1. (append x y) + hängt an die Liste "x" den LISP-Ausdruck "y". + + + (append x y) = + (cond ((null x) y) + (T (cons (head x) (append (tail x) y) )) + ) + + +2. (member list pattern) + Dies Prädikat testet, ob der LISP-Ausdruck "pattern" in der Liste "list" vor­ + kommt. + + + (member list pattern) = + (cond ((null list) F) + ((equal (head list) pattern) T) + (T (member (tail list) pattern)) + ) + + +3. (pairlist list1 list2 oldpairlist) + Diese Funktion liefert eine Liste von Paaren, die die sich entsprechenden Elemen­ + te der Listen "list1" und "list2" enthalten, und an der noch die Liste "oldpairlist" + hängt. + + + + (pairlist list1 list2 oldpairlist) = + (cond ((null list1) oldpairlist) + (T (cons (cons (head list1) (head list2)) + (pairlist (tail list1) (tail list2) oldpairlist) + ) + ) + ) + + +Beispiel: + (pairlist (A B C) (U V W) ((D . X) (E . Y)) ) = + ((A . U) (B . V) (C . W) (D . X) (E . Y)) + + +Eine solche Liste von Paaren wird auch Assoziationsliste genannt, wenn das erste +Element jedes Paars ein Atom ist, das über diese Liste mit dem zweiten Element +assoziiert ist. + +5. (association pattern associationlist) + Wenn "association list" eine Assoziationsliste wie oben beschrieben ist, liefert + "association" das Paar der Liste, dessen erstes Element "pattern" ist. Es ist also + eine Funktion zum Durchsuchen von Tabellen. + + + (association pattern alist) = + (cond ((eq (head (head alist)) pattern) (head alist)) + (T (association pattern (tail alist))) + ) + +Beispiel: + +(association B ( (A . (M N)) + (B . (HEAD X)) + (C . (QUOTE M)) + (B . (TAIL X)) + ) ) = (B . (HEAD X)) + + +(replace expr alist) + "alist" muß eine Assoziationsliste sein. "replace" produziert einen Ausdruck, der + "expr" sehr ähnlich ist, nur sind alle Atome darin durch den LISP-Ausdruck + ersetzt, mit dem sie in "alist" assoziiert sind. + + + (replace expr alist) = + (cond ((atom expr) (association expr alist)) + (T (cons (replace (head expr) alist) + (replace (tail expr) alist) + ) + ) + ) + +Beispiel: + + (replace (X SCHRIEB Y) + ((Y . (GOETZ VON BERLICHINGEN)) (X . GOETHE)) + ) + + = (GOETHE SCHRIEB (GOETZ VON BERLICHINGEN)) + + + +Die allgemeine Funktion "evalquote", die wir jetzt definieren wollen, gehorcht der +folgendem Beispiel zugrundeliegenden Regel: + + +Beispiel: + (evalquote +Funktion: (LAMBDA (X Y) (CONS (HEAD X) Y) ) +Argumente: (A B) (C D) + ) += + (apply +Funktion: (LAMBDA (X Y) (CONS (HEAD X) Y)) +Argumentliste: ((QUOTE (A B)) (QUOTE (C D))) +Bindung: NIL + ) + + +Die Argumente von "evalquote" werden also zu einer gequoteten Argumentliste von +"apply". Die QUOTE-Funktion bewirkt, daß das Argument der QUOTE-Funktion +wörtlich genommen, also nicht weiter evaluiert wird. Das dritte Argument von "apply", +das NIL ist eine leere Bindeliste zur Bindung von Parametern und Argumenten im +nächsten Schritt: + + += + (eval +Argumente: (CONS (HEAD X) Y) +Bindung: ((X.(A B)) (Y . (C D))) + ) += + (cons (head (A B)) (C D)) += + (A C D) = Ergebnis von "evalquote" . + + +"evalquote" wird hauptsächlich durch die Hilfsfunktion "apply" definiert. "apply" +berechnet Funktionsaufrufe, indem es die Argumente und die Parameter der Funktion +bindet und den Funktionsrumpf berechnet. Die Bindungen werden in einer Assozia­ +tionsliste, der Bindeliste, gespeichert. Da bedingte Ausdrücke und Konstanten formal +wie Funktionsaufrufe von Funktionen "cond" und "quote" aussehen, werden sie auch +so behandelt. + +Wir definieren also: + + + (evalquote fkt expr) = (apply fkt (quote expr) NIL) . + + +sowie : + + + (eval expr binding) = + (cond ((atom expr) (tail (association expr binding))) + (T (apply (head expr) (tail expr) binding)) + ) + + +"eval" stellt also erst fest, ob es sich um ein Atom oder um einen Funktionsaufruf +handelt. Da es nur diese beiden Möglichkeiten gibt, ist diese Einteilung vollständig. + +Atome sind immer Übersetzungen von Variablen, für die eine Bindung existieren muß, +so daß ihr Wert aus der Bindeliste geholt wird. + +Funktionsaufrufe sind immer Listen; im zweiten Zweig werden die Funktion und die +Parameterliste getrennt und an "apply" übergeben. + +Um sich die Aktionen in diesem zweiten Zweig von "eval" genauer vorstellen zu +können, ist vielleicht die in Abschnitt 1.1 beschriebene graphische Darstellungsmetho­ +de hilfreich; beispielsweise würde sich ein Lambda-Ausdruck so ausnehmen: + + + +-----+-----+ +-----+-----+ +-----+-----+ + | o | o--+-->| o | o--+-->| o | o--+-->NIL + +--+--+-----+ +--+--+-----+ +--+--+-----+ + | | | + V V V + LAMBDA Parameterliste Ausdruck + + +"apply" bekommt nun von "eval" eine Funktion und eine Parameterliste sowie die +Bindeliste übergeben. Mit diesen beiden macht es folgendes: + + + (apply fn args binding) = +(cond + ((atom fn) + (cond ((eq fn HEAD) (head (eval (head args) binding))) + ((eq fn TAIL) (tail (eval (head args) binding))) + ((eq fn CONS) (cons (eval (head args) binding) + (eval (head (tail args)) binding) + ) ) + ((eq fn ATOM) (atom (eval (head args) binding))) + ((eq fn EQ) (eq (eval (head args) binding) + (eval (head (tail args)) binding) + ) ) + ((eq fn QUOTE) (head args)) + ((eq fn COND) (evalcond args binding)) + (T (apply (tail (association fn binding)) args binding)) + ) + ((eq (head fn) LABEL) + (apply (head (tail (tail fn))) + args (cons (cons (head (tail fn)) + (head (tail (tail fn))) + ) + binding) + ) ) + ((eq (head fn) LAMBDA) (eval (head (tail (tail fn))) + (pairlist (head (tail fn)) + args binding) + ) ) +) + + + + + + +Das erste Argument von "apply" ist eine Funktion (unter der Voraussetzung, daß +"quote" und "cond" als Funktionen anerkannt werden). + +Wenn es eine der elementaren Funktionen "head", "tail", "cons", "atom" oder "eq" +ist, wird die jweilige Funktion auf die Argumente angewandt, die vorher berechnet +werden. Diese Berechnung erfolgt mit "eval", das ja für Variablen Werte aus der +Bindeliste liefert und für Funktionsaufrufe das, was "apply" mit ihnen machen kann. + +Wenn es sich um "quote" handelt, wird das erste Argument unverändert geliefert +"quote" heißt ja "dies ist eine Konstante, die so, wie sie da steht, übernommen wer­ +den soll". + +Wenn es sich um "cond" handelt, wird die Funktion "eval cond" aufgerufen, doch +auch ihre Argumente werden nicht berechnet, außerdem gehört die Assoziationsliste +zu den Argumenten: + + + eval (cond condlist, binding) = + (cond ((eval (head (head condlist)) binding) + (eval (head (tail (head condlist))) binding) + ) + (T (cond (tail condlist) binding)) + ) + + + +Hier empfiehlt es sich, einen bedingten Ausdruck in graphischer Form hinzuschreiben +und die Auswertung anhand der Zeichnung nachzuvollziehen. + +Wenn die Funktion nichts von alledem ist, wird in der Bindeliste nachgesehen, ob +dies Atom nicht an eine Funktion gebunden ist; falls ja, wird eine Auswertung dieser +Funktion mit den gleichen Argumenten versucht. + +Wenn das erste Argument von "apply" kein Atom ist, muß es ein LABEL- oder ein +LAMBDA-Ausdruck sein. + +Ein LABEL-Ausdruck hat die Form + + + +-----+-----+ +-----+-----+ +-----+-----+ + | o | o--+-->| o | o--+-->| o | o--+--> NIL + +--+--+-----+ +--+--+-----+ +--+--+-----+ + | | | + V V V + LABEL Name Funktion + + +Funktionsname und Definition werden in einem funktionalen Eintrag in die Bindeliste +eingefügt, so daß der Name an die Funktion gebunden ist. + +Ein LAMBDA-Ausdruck hat die Form + + + +-----+-----+ +-----+-----+ +-----+-----+ + | o | o--+-->| o | o--+-->| o | o--+--> NIL + +--+--+-----+ +--+--+-----+ +--+--+-----+ + | | | + V V V + LAMBDA Parameterliste Ausdruck + + +Dabei ist die Parameterliste eine Liste von Atomen, den Parametern. Die Auswertung +läuft so ab, daß die Parameter durch "pairlist" an die Argumente gebunden werden +und mit dieser neuen Bindeliste der Ausdruck berechnet wird. + +Das EUMEL-LISP bietet eine Reihe weiterer Möglichkeiten, die erst später beschrie­ +ben werden. Hier können wir allerdings schon die folgenden Punkte abhandeln: + +1. Jede LISP-Eingabe ist ein LISP-Ausdruck. Der "head" dieses Ausdrucks wird + als Funktion aufgefaßt und auf den gequoteten "tail" des Ausdrucks, nämlich die + nicht zu evaluierenden Argumente angewandt. Die Übersetzung von Kleinbuchsta­ + ben in Großbuchstaben wird vom LISP-System übernommen. + +2. In der Theorie des reinen LISP müssen alle Funktionen außer den fünf Basisfunk­ + tionen an allen Stellen wieder definiert werden, an denen sie aufgerufen werden. + Das ist eine für die Praxis äußerst unhandliche Regelung; das EUMEL-LISP- + System kennt weitere vordefinierte Funktionen und bietet die Möglichkeit, beliebig + viele weitere Standardfunktionen einzuführen, auch solche Funktionen, deren + Argumente nicht berechnet werden (wie "quote") oder solche, die beliebig viele + Argumente haben dürfen (wie "cond"). + +3. Die Basisfunktion "eq" hat immer einen wohldefinierten Wert, dessen Bedeutung + im Fall, daß Nicht-Atome verglichen werden, im Kapitel über Listenstrukturen + erklärt wird. + +4. Außer in sehr seltenen Fällen schreibt man nicht (quote T), (quote F) oder (quote + NIL), sondern T, F und NIL. + +5. Es besteht die Möglichkeit, mit Ganzzahlen zu rechen, die als weiterer Typ von + Atomen gelten. Außerdem können TEXTe und Einzelzeichen (CHARACTERs) + gespeichert werden. + +6. Es besteht die Möglichkeit der Ein- und Ausgabe von LISP-Ausdrücken, Ganz­ + zahlen, TEXTen und CHARACTERs. + +WARNUNG: Die oben angegebenen Definitionen von "eval" und "apply" dienen nur + pädagogischen Zwecken und sind nicht das, was wirklich im Interpreter + abläuft. + Um zu entscheiden, was wirklich vor sich geht, wenn der Interpreter + aufgerufen wird, sollte man sich an die ELAN-Quellprogramme halten. +#page# + +2.2 Anwendungsregeln und Beispiele #goalpage("p2.2")# + + + +Die Funktionsweise des LISP-Interpreteres kann bequem unter Verwendung der +Funktion "trace" verfolgt werden. Der Aufruf: + + + (trace) + + +schaltet den Trace-Protokollmodus des Interpreters ein bzw. aus. + +Das folgende Beispiel ist ein LISP-Programm, das die drei Funktionen "union", +"intersection" und "member" als Standardfunktionen einführt Die Funktionen lauten +folgendermaßen: + + + (member pattern list) = (cond ((null list) F) + ((eq (head list) pattern) T) + (T (member pattern (tail list))) + ) + + (union x y) = (cond ((null x) y) + ((member (head x) y) (union (tail x) y)) + (T (cons (head x) (union (tail x) y))) + ) + + (intersection x y) = (cond ((null x) NIL) + ((member (head x) y) + (cons (head x) (intersection + (tail x) y)) + ) + (T (intersection (tail x) y)) + ) + + +Um die Funktionen als neue Standardfunktionen einzuführen, benutzen wir die Pseu­ +dofunktion "define": + + + (DEFINE + (MEMBER . (LAMBDA (PATTERN LIST) + (COND ((NULL LIST) F) + ((EQ (HEAD LIST) PATTERN) T) + (T (MEMBER PATTERN (TAIL LIST))) + ) ) ) + (UNION . (LAMBDA (X Y) + (COND ((NULL X) Y) + ((MEMBER (HEAD X) Y) (UNION (TAIL X) Y)) + (T (CONS (HEAD X) (UNION (TAIL X) Y))) + ) ) ) + (INTERSECTION . (LAMBDA (X Y) + (COND ((NULL X) NIL) + ((MEMBER (HEAD X) Y) + (CONS (HEAD X) (INTERSECTION (TAIL + X) Y)) + ) + (T (INTERSECTION (TAIL X) Y)) + ) ) ) + ) + + +Die Funktion DEFINE, liefert als Pseudofunktion nicht nur einen LISP-Ausdruck als +Ergebnis, sondern hat auch einen bleibenden Effekt, nämlich eine Veränderung im +LISP-Heap. + +DEFINE hat beliebig viele Parameter der Form (Name . Funktion) und bewirkt, daß die +Funktionen unter dem jeweiligen Namen im System verfügbar werden, also für die +weitere Programmausführung definiert werden. Das Ergebnis von DEFINE ist eine +Liste der neuen Funktionsnamen, also hier + + + (MEMBER UNION INTERSECTION) + + +Der Wert den der LISP-Interpreter bei Eingabe von + + + (intersection (a1 a2 a3) (a1 a3 a5)) + + +liefert ist (A1 A3) , + + +Die Funktion + + + (union (x y z) (u v w x)) + + +liefert (Y Z U V W X) . + + + +Es folgen einige elementare Regeln für LISP-Programme: + +1. Ein LISP-Programm besteht aus einem Funktionsaufruf. Im Beispiel ist das die + Funktion DEFINE, die ihre Parameter (beliebig viele) berechnet und ausgibt. Die + Berechnung der Parameter erfolgt dabei in der Reihenfolge der Parameter (norma­ + le LISP-Funktionen mit mehreren Parametern berechnen standardmäßig alle + Parameter, allerdings in irgendeiner Reihenfolge). + +2. LISP ist formatfrei, d.h. jedes Symbol kann in jeder Spalte stehen. Für die Bedeu­ + tung des Programms ist nur die Reihenfolge der Symbole maßgeblich. Zeilen­ + wechsel wird als Leerzeichen aufgefaßt. + +3. Atome müssen mit einem Buchstaben anfangen, damit sie nicht mit Zahlen ver­ + wechselt werden. + +4. Ein LISP-Ausdruck der Form (A B C . D) ist eine Abkürzung für (A.(B.(C.D))). + Jede andere Plazierung des Punkts ist ein Fehler (falsch wäre z.B. (A . B C) ). + +5. Eine Anzahl von Basisfuntionen existiert von Anfang an, ohne daß sie durch + DEFINE eingeführt wurden. Der Programmierer kann weitere Funktionen bleibend + oder für die Dauer eines Programmlaufs einführen; dabei ist die Reihenfolge der + neuen Funktionen gleichgültig. +#page# + +2.3 Variablen#goalpage("p2.3")# + + + +Eine Variable ist ein Symbol, das ein Argument einer Funktion repräsentiert. Man +kann also schreiben: "a + b, wobei a = 3 und b = 4". In dieser Situation ist keine +Verwechslung möglich, so daß klar ist, daß das Ergebnis 7 ist. Um zu diesem Ergeb­ +nis zu kommen, muß man die Zahlen anstelle der Variablen einsetzen und die Opera­ +tion ausführen, d.h. die Zahlen addieren. + +Ein Grund, weshalb das eindeutig ist, liegt darin, daß "a" und "b" nicht "direkt" +addiert werden können, so daß etwa "ab" entsteht. In LISP kann die Situation viel +komplizierter sein. Ein Atom kann eine Variable oder ein Atom sein. + +Sollte der zukünftige LISP-Benutzer an dieser Stelle entmutigt sein, sei ihm gesagt, +daß hier nichts Neues eingeführt wird. Dieser Abschnitt ist nur eine Wiederholung der +Überlegungen aus Abschnitt 1.4. Alles, was wir in diesem Abschnitt sagen, kann man +aus den Regeln für LISP-Ausdrücke oder aus der allgemeinen Funktion "evalquote" +ableiten. + +Der Formalismus, der in LISP die Variablen kennzeichnet, ist die Lambdanotation von +Church. Der Teil des Interpreters, der die Variablen an Werte bindet, heißt "apply". +Wenn "apply" auf eine Funktion stößt, die mit LAMBDA anfängt, wird die Variablenli­ +ste (Argumentliste) mit der Parameterliste gepaart und am Anfang der Bindeliste +eingefügt. + +Während der Berechnung des Funktionsrumpfs müssen manchmal Variablen durch +ihre Werte ersetzt werden. Das geschieht dadurch, daß ihr Wert in der Bindeliste +nachgesehen wird. Wenn eine Variable mehrmals gebunden wurde, wird die zuletzt +etablierte Bindung verwendet. Der Teil des Interpreters, der diese "Berechnungen" +und die Berechnung von Funktionsaufrufen durchführt, heißt "eval". + + + +#page# + +2.4 Konstanten#goalpage("p2.4")# + + + +Manchmal heißt es, eine Konstante stehe für sich selbst, im Gegensatz zu einer +Variablen, die für etwas anderes, nämlich ihren Wert, steht. +Dies Konzept funktioniert in LISP nicht so ohne weiteres; es ist hier sinnvoller, zu +sagen, eine Variable ist konstanter als die andere, wenn sie in einer höheren Ebene +gebunden ist und ihren Wert seltener ändert. +In LISP bleibt eine Variable im Bereich des LAMBDA konstant, von dem sie gebunden +ist. Wenn eine Variable einen festen Wert hat, unabhängig davon, was in der Bindeli­ +ste steht, wird sie (echte) Konstante genannt. Dies wird mit Hilfe der Eigenschaftsliste +(E-Liste) des Atoms erreicht. +Jedes Atom hat eine E-Liste, in der Paare von Atomen und beliebigen Strukturen +gespeichert sind. Ein Atom hat die Eigenschaft A, wenn in seiner E-Liste ein Paar +mit dem Atom A enthält; die dazugehörige "beliebige Struktur" heißt Wert dieser +Eigenschaft. +Wenn ein Atom die Eigenschaft APVAL besitzt, ist es eine Konstante, deren Wert der +Wert der Eigenschaft ist. +Konstanten können durch die Pseudofunktion + + + (set atom wert) + + +gesetzt werden; nach der Auswertung eines solchen Aufrufs hat das Atom "atom" +immer den Wert "wert" - bis zum nächsten "set". Eine interessante Klasse von +Konstanten sind solche Konstanten, die sich selbst als Wert haben. Ein Beispiel dafür +ist NIL. Der Wert dieser Konstanten ist wieder NIL. Daher kann NIL nicht als Variable +benutzt werden, da es ja eine Konstante ist. (T und F gehören ebenfalls zu dieser +Klasse). + +#page# + +2.5 Funktionen#goalpage("p2.5")# + + + +Wenn ein LISP-Ausdruck für eine Funktion steht, ist die Situation ähnlich der, in der +ein Atom für einen Wert steht. Wenn die Funktion rekursiv ist, muß sie einen Namen +bekommen. Das geht mit einem LABEL-Ausdruck, der den Namen mit der Funk­ +tionsdefinition in der Bindeliste paart. Dadurch wird der Name an die Funktionsdefini­ +tion gebunden, so wie eine Variable an ihren Wert gebunden wird. In der Praxis setzt +man LABEL selten ein. Normalerweise ist es einfacher, Name und Definition wie bei +den Konstanten zu verknüpfen. Dies geschieht mit der Pseudofunktion DEFINE, die +wir am Anfang des Kapitels benutzt haben. +Diese Funktion kann beliebig viele Parameter der Form + + + (atom . funktion) + + +haben, wobei "atom" der Name der zu definierenden Funktion "funktion" werden soll. +Sie bewirkt, daß die Definition unter der Eigenschaft FUNCTION in der E-Liste des +Atoms abgelegt wird. +#page# + +3. Erweitertes LISP#goalpage("p3")# + + +In diesem Kapitel werden wir einige Erweiterungen zum reinen LISP einführen. Zu +diesen Erweiterungen gehören Möglichkeiten für Arithmetik, Zeichenkettenverarbei­ +tung, Funktionen, die spezielle Argumente erwarten, und Ein- und Ausgabe. + +In allen Fällen handelt es sich bei den Erweiterungen um zusätzliche Funktionen. So +heißt das Kommando für die Ausgabe eines LISP-Ausdrucks PUT. Syntaktisch ist +PUT nichts anderes als eine Funktion mit einem Argument. Sie kann mit anderen +Funktionen verkettet werden, und diese Verkettung wird ganz auf die übliche Art +behandelt, zuerst Berechnung der innern, dann der äußeren Funktionsaufrufe. Ein +Ergebnis ist nur in dem trivialen Sinn vorhanden, daß PUT sein Argument wieder +liefert, also die Identität ist. + +Funktionen, die eine Aktion wie Ein- oder Ausgabe bewirken, oder die Langzeitwir­ +kung (gesehen auf die Ausführungsdauer des Programms) haben, wie DEFINE und +SET, heißen Pseudofunktionen. Es ist eine Besonderheit von LISP, daß alle Funktio­ +nen einschließlich den Pseudofunktionen ein Ergebnis haben müssen. In einigen +Fällen ist das Ergebnis trivial und kann ignoriert werden. + +In diesem Kapitel beschreiben wir verschiedene Erweiterungen der Sprache LISP, die +im System fest enthalten sind. + + +#page# + +3.1 Gequotete Parameter #goalpage("p3.1")# + + + +Bevor ein Argument an eine Funktion übergeben wird, wird erst sein Wert in der +Bindeliste nachgesehen, d.h. es wird nicht der Name der Variablen übergeben, son­ +dern ihr Wert. Wenn das Argument als Konstante behandelt werden soll, muß es +ge"quotet" werden, d.h. statt "argument" steht (quote argument). Wenn ein Argument +einer Funktion immer als Konstante behandelt werden soll, ist es bequemer, das +Argument nicht jedesmal zu quoten. Das EUMEL-LISP-System erlaubt, in diesem +Fall den formalen Parameter in der Funktionsdefinition bereits zu quoten. + +Dieser Mechanismus wurde auch benutzt, um QUOTE zu implementieren; die Funk­ +tion lautet + + + quote = (lambda ((QUOTE x)) x) + + + + +#page# + +3.2 Funktionen mit beliebig vielen + Argumenten #goalpage("p3.2")# + + + +Ein Beispiel ist "list", das beliebig viele Argumente haben kann, die zu einer Liste +zusammengefaßt werden. Da eine Funktion nur eine feste Anzahl von Parametern +haben kann, eine Funktion mit beliebig vielen Argumenten aber gewiß keine feste +Anzahl von Argumenten hat, werden die beliebig vielen Argumente zu einer Liste +zusammengefaßt und ein einziger Parameter wird an diese Liste gebunden. Da "list" +genau diese Liste liefern soll, wird diese Funktion ebenfalls zu einer "Identität": + + + list = (lambda ((INDEFINITE x)) x) + + +Solche Parameter werden durch INDEFINITE gekennzeichnet. Sie können auch ge­ +quotet werden, indem man (INDEFINITE QUOTE parameter) schreibt; das wirkt so, als +wären alle Argumente, die diesem Parameter zugeordnet werden, einzeln gequotet +worden. + + + evalquote = (lambda (fkt (INDEFINITE QUOTE expr)) + (apply fkt expr NIL) ) + + + +#page# + +3.3 Funktionale Parameter #goalpage("p3.3")# + + + +In der Mathematik gibt es Funktionen, die andere Funktionen als Argument haben. In +der Algebra könnte man die Funktion "(operation operator a b)" definieren, wobei +"operator" ein funktionales Argument ist, das die Operation festlegt, die auf "a" und +"b" ausgeführt werden soll. Beispielsweise gilt + + + operation (+ 3 4) = 7 + operation (* 3 4) = 12 + + +In LISP sind funktionale Argumente sehr nützlich. Eine wichtige Funktion mit einem +Argument ist MAPLIST. Ihre Definition ist + + + (LAMBDA (LIST (FUNCTION FN)) + (COND ((NULL LIST) NIL) + (T (CONS (FN (HEAD LIST)) (MAPLIST (TAIL LIST) FN))) + ) ) + + +Diese Funktion nimmt eine Liste und eine Funktion als Argument und wendet die +Funktion auf die Listenelemente an. + + +#page# + +3.4 Prädikate und boolesche Konstanten #goalpage("p3.4")# + + + +Die booleschen Werte sind, wie in Kapitel 1 gesagt, T und F. Bei LISP-Ausdrücken +müßte daraus (quote T) und (quote F) werden, aber da die APVALs dieser Atome +wieder den Wert T und F haben, ist das quoten nicht nötig. + +Prädikate sind Funktionen, die T oder F als Ergebnis haben; es gibt also keine forma­ +len Unterschiede zwischen anderen Funktionen und Prädikaten. + +Daher ist es durchaus möglich, daß eine Funktion einen Wert liefert, der weder T +noch F ist, daß aber durch einen bedingten Ausdruck an dieser Stelle ein boolescher +Ausdruck verlangt wird. In diesem Fall ist die Wirkung des Ausdrucks nicht definiert. + +Das Prädikat EQ hat folgendes Verhalten: +1. Wenn seine Argumente verschieden sind, ist das Ergebnis F. +2. Wenn die Argumente dasselbe Atom sind, ist das Ergebnis T. +3. Wenn die Argumente gleich, aber nicht atomar sind, ist das Ergebnis T oder F, je + nachdem, ob sie ein und dasselbe Objekt im Heap sind oder nicht. + +#page# + +3.5 Unbenannte Atome #goalpage("p3.5")# + + + +Die meisten Atome im EUMEL-LISP haben einen Namen, der sie bei Ein- und +Ausgabeoperationen identifiziert. +Es gibt aber auch Atome, die keinen Namen haben und stattdessen durch ihre Werte +repräsentiert werden. Momentan sind das Ganzzahlen und Zeichenketten (TEXTe); +auch die booleschen Werte kann man in einem weiteren Sinn dazurechnen. + + + + +3.5.1 Ganzzahlen + + + +Im EUMEL-LISP gibt es Funktionen, die Basisoperationen und Tests durchführen. + +Ganzzahlen haben folgende Eigenschaften: + +1. Eine Ganzzahl besteht aus einem optionalen Vorzeichen und einer Folge von + Ziffern; zwischen Vorzeichen und Ziffern können Leerzeichen stehen. +2. Der Wert einer Ganzzahl liegt zwischen -32768 und 32767 (minint und maxint). +3. Eine Ganzzahl kann überall dort stehen, wo ein Atom stehen kann, außer als + Parameter. +4. Ganzzahlen sind Konstanten; sie brauchen also nicht gequotet werden. +#page# + +3.5.2 Arithmetische Funktionen und Prädikate + + + +Es folgt eine Liste aller arithmetischen Funktionen. +Wenn ein Argument einer dieser Zahlen keine Ganzzahl ist, erfolgt eine Fehlermel­ +dung. + + (sum x1 ... xn) liefert die Summe der xi; wenn keine Argumente gege­ + ben werden, wird 0 geliefert. + (difference x y) liefert die Differenz von x und y. + (product x1 ... xn) liefert das Produkt seiner Argumente; wenn + keine Argumente gegeben werden, wird 1 + geliefert. + (quotient x y) liefert den Quotienten von x und y, ohne den + Rest zu berücksichtigen. + (remainder x y) liefert den Rest der Division von x und y. + (getint) liest eine Zahl vom Bildschirm ein und + liefert sie. + (putint x) gibt x auf den Bildschirm aus. Identitäts funktion. + + + + + +3.5.3 Zeichenkettenverarbeitung + + + +Im Moment ist nur Zeichenketten-Ein- und Ausgabe implementiert. +Die Ausgabe löst bei Argumenten, die keine Zeichenketten sind, eine Fehlermeldung +aus. + + (gettext) liest eine Zeichenkette ein und liefert sie. + (puttext x) gibt eine Zeichenkette aus. + + + + +3.5.4 Test auf Gleichheit + + + + (equal x y) testet, ob x und y vom gleichen Typ sind, und wenn ja, ob sie gleich + sind. +#page# + +3.6 Aufruf von EUMEL aus #goalpage("p3.6")# + + +Bevor man den LISP-Interpreter benutzen kann, muß er folgendermaßen implemen­ +tiert werden: + +archive ("lisp") +fetch all (archive) +release (archive) +check off +insert ("lisp.1") +insert ("lisp.2") +insert ("lisp.3") +insert ("lisp.4") +check on + + +Das LISP-System verfügt über einen Heap, in dem alle LISP-Ausdrücke gespei­ +chert sind. Standardmäßig enthält der Heap eine Reihe von Funktionen, die nicht in +den LISP-Programmen definiert werden müssen (Übersichten über die Standardfunk­ +tionen siehe Kapitel 3.5). + +Mit + lisp + +wird das LISP-System im EUMEL-Dialog gestartet. In einem Eingabefenster wird +mit Hilfe des Paralleleditors eine LISP-EINGABE-Möglichkeit angeboten. Die Aus­ +gabe erfolgt in dem LISP-AUSGABE-Fenster. +Das LISP-System kann folgendermaßen verlassen werden: + break lisp . + +Statt dieser direkten Art der Benutzung der LISP-Maschine ist auch eine an ELAN +angelehnte Art mit den Prozeduren "run lisp", insert lisp" usw. vorgesehen: + +Mit + + run lisp (TEXT CONST dateiname) + +wird eine Kopie des Heaps angelegt, das Programm aus der Datei "dateiname" in die +Kopie eingelesen und gestartet. Durch diesen Kopiermechanismus wird der Original­ +heap vor Zusammenbrüchen des LISP-Systems geschützt. + + insert lisp (TEXT CONST dateiname) + +bewirkt dasselbe wie "run lisp"; allerdings wird jetzt direkt auf dem Originalheap +gearbeitet. Dadurch sind alle Änderungen im Heap, die das Programm verursacht +(meist Definition von Funktionen durch DEFINE) bleibend, aber auch ein Zusammen­ +bruch ist insoweit endgültig, als das LISP-System jetzt neu gestartet werden muß. +Das geschieht mit + + start lisp system (DATASPACE CONST dsname) + +"dsname" gibt dabei den Datenraum an, der die zum Hochfahren notwendigen Daten +enthält. Solche Daten im richtigen Format enthält der Datenraum "lisp.bootstrap". +Wenn der zuletzt benutzte Heap mit nicht mehr durch LISP-Programme erreich­ +bare Strukturen vollgestopft ist, schafft die Prozedur + + collect lisp heap garbage + +Abhilfe; mit + + lisp storage info + +kann man den Erfolg kontrollieren. +#page# + +4. Detailbeschreibungen#goalpage("p4")# + + + + + +4.1 Grundfunktionen #goalpage("p4.1")# + + + +Die Datei "lisp.1" enthält ein Paket, das die Grundlage des LISP-Systems bildet. Es +implementiert + + - die primitiven LISP-Funktionen wie "cons", "null", etc., + - die Verwaltung des Heaps, in dem die LISP-Strukturen und die Objektliste + (Oblist) gespeichert sind, + - einen Datentyp SYM, dessen Wertevorrat aus Zeigern auf die im Heap gespei­ + cherten Strukturen besteht, + - Funktionen zur Konversion allgemeiner Daten in LISP-Strukturen (bisher reali­ + siert: TEXT <--> SYM und INT <--> SYM). + +Durch die Implementation der Basisoperationen als exportierte und damit allgemein +verfügbare ELAN-Prozeduren ist es möglich, LISP-Strukturen durch ELAN-Prog­ +ramme zu manipulieren; insbesonders können ELAN- und LISP-Programme über +diese Strukturen miteinander kommunizieren. + +Anmerkung: +Wenn Eigenschaften von "SYM"-Objekten beschrieben werden, sind immer die +Eigenschaften der Strukturen gemeint, auf die die Objekte zeigen, wenn nichts ande­ +res angegeben wird. + + +Es werden folgende Prozeduren exportiert: + + PROC initialize lisp system (DATASPACE CONST new heap): + "new heap" ist der neue Datenraum, in dem der LISP-Heap ab sofort geführt + wird. + Vorsicht: Beim Wechsel zu einem neuen Datenraum sind die Werte der + SYM-Variablen, die auf Strukturen im alten Heap zeigen, natürlich wertlos! + + PROC dump lisp heap (FILE VAR f): + In "f" wird ein Dump des Heaps erstellt. Dieser Dump ist nur mit Kenntnis des + Programmtextes aus "lisp 1" verständlich; er wird hier nicht beschrieben. + + PROC lisp storage (INT VAR size, used): + Nach dem Aufruf gibt "size" die maximal verfügbare Anzahl von Knoten an, + während "used" die Anzahl der tatsächlich von LISP-Strukturen belegten + Knoten enthält. Zu diesen Strukturen können auch solche zählen, die nicht mehr + durch "head" oder "tail" etc. erreichbar sind. + + PROC collect lisp heap garbage: + Löscht die im LISP-Heap nicht mehr durch "atom (TEXT CONST)", "proper­ + ty", "head" und "tail" erreichbaren Strukturen. Es werden auch alle nur von + ELAN-Programmen aus über SYM-Variable erreichbare Strukturen gelöscht, so + daß die Werte dieser Variablen undefiniert werden. + Die Müllabfuhr wird von keiner Prozedur dieses Pakets aufgerufen, d.h. der + Benutzer, der ELAN-Programme einsetzt, braucht nicht alle Strukturen in den + Eigenschaftslisten von Atomen aufzubauen, um sie vor einer versehentlichen + Löschung durch die Müllabfuhr zu schützen, vorausgesetzt, er ruft sie nicht + selbst auf. Er muß allerdings darauf achten, daß im Heap noch genug Platz + bleibt. + + OP := (SYM VAR left, SYM CONST right): + Nach der Zuweisung zeigt "left" auf die gleiche Struktur wie vorher "right". + + SYM CONST nil, pname; + Zwei Konstanten, die dem LISP-System ständig zur Verfügung stehen müs­ + sen. Ihre Drucknamen sind "NIL" bzw. "PNAME" (vgl. Schlußbemerkungen) + + SYM PROC head (SYM CONST sym): + Entspricht der im Handbuch beschriebenen Funktion "head". + + SYM PROC tail (SYM CONST sym): + Entspricht der im Handbuch beschriebenen Funktion "tail". + + SYM PROC cons (SYM CONST head, tail): + Liefert einen SYM-Wert "zeiger" auf eine neue Struktur. Es gilt: + head ("zeiger") = "head" und tail ("zeiger") = "tail". + + BOOL PROC eq (SYM CONST sym 1, sym 2): + Prüft, ob "sym 1" und "sym 2" auf dieselbe Struktur zeigen. Das ist genau dann + der Fall, wenn sie durch Zuweisung auseinander hervorgegangen sind oder wenn + sie auf das gleiche benannte Atom zeigen. + + BOOL PROC equal (SYM CONST sym 1, sym 2): + Prüft, ob "sym 1" und "sym 2" dieselbe Struktur haben; "dieselbe Struktur" + braucht aber nicht "Identität" zu bedeuten, wie "eq" das verlangt. + Umgewandelte TEXTe und INTs werden richtig verglichen (siehe "sym (INT + CONST)" und "sym (TEXT CONST)"). + + BOOL PROC null (SYM CONST sym): + Prüft, ob "sym" gleich der Konstanten "NIL" ist (entspricht + eq ("sym", "NIL"), ist aber schneller). + + BOOL PROC atom (SYM CONST sym): + Prüft, ob "sym" ein ( benanntes oder unbenanntes) Atom ist. + + BOOL PROC is named atom (SYM CONST sym): + Prüft, ob "sym" ein benanntes Atom ist. + + PROC begin oblist dump: + Vorbereitung für "next atom". + + SYM PROC next atom: + Liefert das nächste Atom aus der Objektliste. In der Objektliste sind alle benann­ + ten Atome, die der Heap enthält, aufgeführt (bis auf Ausnahmen; s."delete + atom"). "NIL" wird immer als letzte Atom geliefert. + + SYM PROC atom (TEXT CONST name): + Liefert einen Zeiger auf das Atom mit dem Namen "name". Wenn kein solches + Atom in der Objektliste vorhanden ist, wird "NIL" geliefert. + + SYM PROC new atom (TEXT CONST name): + Liefert einen Zeiger auf das Atom mit dem Namen "name". Wenn kein solches + Atom in der Objektliste vorhanden ist, wird ein neues mit diesem Namen in sie + eingefügt. + + PROC create atom (TEXT CONST name): + Fügt ein Atom mit dem Namen "name" in die Objektliste ein. Wenn ein solches + Atom bereits existiert, wird stattdessen eine Fehlermeldung ausgegeben. + + PROC delete atom (SYM CONST atom): + Streicht das Atom "atom" aus der Objektliste. + + PROC begin property list dump (SYM CONST atom): + Vorbereitung für "next property". + + PROC next property (SYM VAR property id, property): + Liefert die nächste Eigenschaft aus der Eigenschaftsliste des zuletzt durch + "begin property list dump" vorbereiteten Atoms. Wenn es sich bei der Eigen­ + schaft um eine Flagge handelt, wird "property" auf "NIL" gesetzt; wenn es keine + nächste Eigenschaft mehr gibt, werden "property" und "property id" auf "NIL" + gesetzt. + Der Dump der Eigenschaftsliste beeinträchtigt die "Verwendbarkeit" des Atoms in + keiner Weise; es ist während des Dumps sogar möglich, Eigenschaften und + Flaggen zu lesen. Wenn während des Dumps Eigenschaften oder Flaggen geän­ + dert oder geschrieben werden, ist mit fehlerhaften Dumpergebnissen zu rechnen. + + PROC add property (SYM CONST atom, property id, property): + "property id" muß ein benanntes Atom sein. Führt eine neue Eigenschaft mit der + Bezeichnung "property id" und dem Wert "property" ein. Wenn bereits eine + Eigenschaft mit der gleichen Bezeichnung existiert, wird die alte Version über­ + deckt, ist aber weiter vorhanden. + + PROC alter property (SYM CONST atom, property id, property): + Bringt die Eigenschaft mit der Bezeichnung "property id" auf den neuen Wert + "property". Wenn eine Eigenschaft mit dieser Bezeichnung noch nicht existiert, + wird eine Fehlermeldung ausgegeben. + + BOOL PROC property exists (SYM CONST atom, property id): + Prüft, ob das Atom eine Eigenschaft mit der Bezeichnung "property id" besitzt. + + SYM PROC property (SYM CONST atom, property id): + Liefert den Wert der gerade sichtbaren Eigenschaft des Atoms, die die Bezeich­ + nung "property id" hat. Falls die Eigenschaft nicht existiert, wird "NIL" geliefert. + + PROC delete property (SYM CONST atom, property id): + Löscht den gerade sichtbaren Wert der Eigenschaft des Atoms, die die Bezeich­ + nung "property id" hat. Wenn eine ältere Version dieser Eigenschaft durch "add + property" überdeckt wurde, wird diese jetzt wieder sichtbar. Jede Eigenschaft + bildet also für jedes Atom einen Stapel (Stack). + + PROC add flag (SYM CONST atom, flag id): + Das Atom "atom" erhält die Flagge "flag id". Ein Atom kann dieselbe Flagge + durchaus mehrmals haben. + + BOOL PROC flag (SYM CONST atom, flag id): + Prüft, ob "atom" mindestens eine Flagge "flag id" hat. + + PROC delete flag (SYM CONST atom, flag id): + Löscht eine Flagge "flag id" von "atom". Wenn keine Flagge existiert, wird + nichts getan. + + SYM PROC sym (TEXT CONST text): + Konvertiert "text" in ein unbenanntes Atom und liefert einen Zeiger auf dies + Atom. + + TEXT PROC text (SYM CONST sym): + Konvertiert "sym" in einen TEXT zurück, wenn es sich um einen konvertierten + TEXT handelt; wenn nicht, wird eine Fehlermeldung ausgegeben. + + BOOL PROC is text (SYM CONST sym): + Prüft, ob "sym" ein konvertierter TEXT ist. + + SYM PROC sym character (TEXT CONST text): + "text" muß genau ein Zeichen enthalten. Das Zeichen wird in ein + CHARACTER-Objekt im Heap konvertiert und ein Zeiger auf dies Objekt gelie­ + fert. + + INT PROC character (SYM CONST sym): + "sym" muß auf ein CHARACTER-Objekt zeigen. Geliefert wird der Code des + dort gespeicherten Zeichens. + + SYM PROC sym (INT CONST i 1, i 2): + Konvertiert "i 1" und "i 2" in ein unbenanntes Atom und liefert einen Zeiger + darauf. + + INT PROC int 1 (SYM CONST sym): + INT PROC int 2 (SYM CONST sym): + Holt die Werte der ersten bzw. zweiten Ganzzahl aus "sym", wenn es sich um + ein konvertiertes INT-Paar handelt; wenn nicht, wird eine Fehlermeldung ausge­ + geben. + + BOOL PROC is int pair (SYM CONST sym): + Prüft, ob "sym" ein konvertiertes INT-Paar ist. + + +Prozedurübergreifende Aussagen über das Paket "lisp.1": + + - Es gibt benannte und unbenannte Atome. + + - Die unbenannten Atome sind Konversionsprodukte. + + - Vor dem ersten Aufruf von "delete atom" sind alle benannten Atome in der Ob­ + jektliste enthalten; d.h. sie können alle durch "begin oblist dump" und wiederhol­ + ten Aufruf von "next atom" erreicht werden. + + - Jedes benannte Atom hat genau einen Namen, der immer gleich bleibt. Der + Name ist als Eigenschaft mit der Bezeichnung "pname" in der Eigenschaftsliste + gespeichert. "add property", "alter property" und "delete property" geben des­ + halb eine Fehlermeldung aus, statt ihre normalen Aktionen durchzuführen, wenn + ihnen als Eigenschaftsbezeichnung "pname" übergeben wird. + + - Es gibt keine zwei Atome, die denselben Namen haben; dadurch reduziert sich + die bei "eq" angegebene Fallunterscheidung auf einen Fall. + + - Es kann durchaus zwei unbenannte Atome mit gleichen Werten geben, die von + "eq" nicht als gleich anerkannt werden, weil sie in verschiedenen Strukturen + gespeichert sind. "equal" achtet nicht auf die Position, sondern auf die Werte + der zu vergleichenden Strukturen. + + - Mehrfache Zugriffe auf die gleiche Eigenschaft desselben Atoms werden so opti­ + miert, daß die Eigenschaftsliste nur beim ersten Zugriff (meist durch "property + exists") durchsucht werden muß. + + + +#page# + +4.2 Weitere Funktionen sowie Eingabe und + Ausgabe #goalpage("p4.2")# + + + +Die Datei "lisp.2" enthält diverse Pakete, die die Verbindung vom LISP-System zur +normalen EUMEL-Umgebung bilden. Momentan sind das Ein- und Ausgabe und +(exemplarisch) die fünf Grundrechenarten für Ganzzahlen. + +Die Ein- und Ausgabe von LISP-Strukturen wird durch das Paket namens "lisp io" +mit den folgenden Prozeduren ermöglicht: + + PROC get (FILE VAR f, SYM VAR sym): + Nach dem Aufruf zeigt "sym" auf eine neue aus "f" eingelesene Struktur. + In der ersten und hinter der letzten Zeile des S-Ausdrucks dürfen keine weiteren + Daten stehen. + + PROC get all (FILE VAR f, SYM VAR sym): + Wie "get (FILE V, SYM V)", nur daß die Datei nichts als den S-Ausdruck ent­ + halten darf. + + PROC get (SYM VAR sym): + Es wird mit "get all" ein S-Audruck von einer Scratch-Datei eingelesen, die + dem Benutzer vorher zum Editieren angeboten wird. Bei Einlesefehlern wird die + Datei zu Korrigieren angeboten, bis keine Fehler mehr auftreten. + + PROC put (FILE VAR f, SYM CONST sym): + Wenn "sym" ein Ganzzahlpaar ist, wird die erste Zahl ausgegeben; wenn es ein + konvertierter TEXT ist, wird der ursprüngliche TEXT wieder ausgegeben; bei + einem benannten Atom oder einer allgemeinen LISP-Struktur wird ein S-Aus­ + druck ausgegeben. + + PROC put (SYM CONST sym): + Wie "put (FILE V, SYM CONST), außer daß die Augabe direkt auf den Bildschirm + erfolgt. + + +Das Paket "lisp int" enthält die Prozeduren + + SYM PROC sum (SYM CONST summandenliste); + Erwartet eine Liste von "int pair"-Summanden und liefert deren Summe. + + SYM PROC difference (SYM CONST minuend, subtrahend): + Liefert die Differenz der Parameter. + + SYM PROC product (SYM CONST faktorenliste): + Liefert das Produkt der Listenelemente. + + SYM PROC quotient (SYM CONST dividend, divisor): + Liefert den Quotienten der Parameter. + + SYM PROC remainder (SYM CONST dividend, divisor): + Liefert den Rest. + +#page# + +4.3 Interpreter #goalpage("p4.3")# + + +Die Datei "lisp.3" enthält das Paket "lisp interpreter", das die Prozedur + + SYM PROC evalquote (SYM CONST expression) + +exportiert. Es handelt sich dabei um den im EUMEL-LISP-Handbuch beschriebe­ +nen Interpreter. + +Wenn "expression" ein LISP-Ausdruck ist, liefert die Prozedur den Wert des Aus­ +drucks (vorausgesetzt, der LISP-Heap ist vorbereitet, siehe lisp.1). + +Wirkungsweise: +"evalquote" ruft im Wesentlichen die Prozedur "eval" auf. +"eval" erwartet als Argumente einen solchen LISP-Ausdruck wie "evalquote", benö­ +tigt aber zusätzlich eine sog. Bindeliste. In einer Bindeliste sind durch LAMBDA- und +LABEL-Ausdrücke bereits gebundene Variable und ihre Werte gespeichert. Die +Manipulation der Bindeliste ist durch eine Reihe von Refinements, die am Schluß des +Pakets stehen, realisiert. + +Da bisher noch keine LAMBDA- oder LABEL-Ausdrücke verarbeitet wurden, über­ +gibt "evalquote" die leere Bindeliste. + +Wirkungsweise von + + SYM PROC eval (SYM CONST expression, association list): + +"eval" kann als erstes Argument ein Atom oder eine zusammengesetzte Struktur +erhalten. + +Atome werden als Variable aufgefaßt, deren Wert in der Bindeliste aufzusuchen ist. +Vor der Konsultation der Bindeliste wird allerdings noch nach der Eigenschaft APVAL +des Atoms gesehen; wenn sie vorhanden ist, handelt es sich um eine Konstante wie +NIL, T oder F, die einen festen Wert hat, nämlich den Wert dieser Eigenschaft. Da +diese Konstanten sich selbst als Wert haben, gilt "eval (NIL, Bindeliste) = NIL" +(entsprechend für "T" und "F"). + +Wenn das erste Arugment von "eval" zusammengesetzt ist, wird angenommen, daß +es sich um einen Funktionsaufruf der Form + + + +-----+-----+ + | o | o--+--> Argumentliste + +--+--+-----+ + | + V + Funktion + + +handelt. Die Bestandteile "Funktion" und "Argumentliste" werden mit der Bindeliste +übergeben an: + + SYM PROC apply (SYM CONST function, arguments, association list): + +"apply" hat die Aufgabe, die Argumente durch "eval" berechnen zu lassen (das +unterbleibt allerdings unter bestimmten Umständen) und die Berechnungergebnisse an +die Parameter der Funktion zu binden; zum Schluß muß der Wert des Funktions­ +rumpfs in Abhängigkeit von diesen neuen Bindungen als Ergebnis der gesamten +Prozedur "apply" berechnet werden; diese Berechnung geschieht wieder durch +"eval". + +Nur in einem LAMBDA-Ausdruck ist direkt bekannt, wo die Parameterliste steht.So­ +lange das nicht der Fall ist, muß entweder ein LABEL-Ausdruck oder ein Atom +vorliegen. +Ein LABEL-Ausdruck hat die Form + + + +-----+-----+ +-----+-----+ +-----+-----+ + | o | o--+--->| o | o--+--->| o | NIL | + +--+--+-----+ +--+--+-----+ +--+--+-----+ + | | | + V V V + LABEL Name Funktion + + +Da der Name für die Dauer der Auswertung des Funktionsrumpfs an die Funktion +gebunden sein muß, wird dis Paar als funktionaler Bindelisteneintrag gespeichert. +Funktionale und nichtfunktionale Bindelisteneinträge sind eindeutig unterschieden. + +Nach dem Abspeichern wird wieder getestet, ob die Funktion diesmal ein +LAMBDA-Ausdruck ist; wenn nicht, wird ein weiterer Schritt zum "Ablättern" von +LABELs und Atomen versucht, usw. + +Wenn die Funktion ein Atom ist, werden analog zu den Vorgängen in "eval" erst die +Eigenschaftsliste und dann die Bindeliste durchsucht. + +Ist die Eigenschaft FUNCTION in der Eigenschaftsliste vorhanden, ist der Wert der +Eigenschaft die (evtl. weiter "abzublätternde") Funktion; ist die Eigenschaft nicht +vorhanden, muß das Atom an eine Funktion gebunden sein, die dann aus der Binde­ +liste geholt werden kann. + +Da alle Funktionen (auch die Standardfunktionen) letztendlich als LAMBDA-Aus­ +drücke definiert sind, kommt "apply" auf diese Weise zuletzt zu einem LAMBDA- +Ausdruck. + +Ein LAMBDA-Ausdruck hat die Form + + + +-----+-----+ +-----+-----+ +-----+-----+ + | o | o--+--->| o | o--+--->| | | + +--+--+-----+ +--+--+-----+ +-----+-----+ + | | + V V + LAMBDA Parameterliste + + +Als nächster Schritt werden die Argumente für die zu berechnende Funktion an die +Parameter der Parameterliste gebunden, d.h. es werden Parameter-Argument-Paare +in die Bindeliste eingetragen. + +Die Methode des Eintrags ist je nach Art des Parameters unterschiedlich. Es gibt die +folgenden Arten von Parametern: + + + 1. | + | + V + Name + + + "Name" ist hier - wie bei den restlichen Fällen - der Name des Parame­ + ters. Diese Art von Parametern ist der Normalfall; die Argumente, die einem + solchen Parameter entsprechen, werden durch "eval" berechnet und zusammen + mit dem Parameter in einem Bindelisteneintrag gespeichert. + + + 2. | + | + V + +-----+-----+ +-----+-----+ + | o | o--+--->| o | NIL + + +--+--+-----+ +--+--+-----+ + | | + V V + QUOTE Name + + + In diesem Fall wird das Argument ohne weitere Verarbeitung in die Bindeliste + übernommen. Die Wirkung ist die gleiche, als wäre das Argument durch + "(QUOTE ... )" eingeschlossen. + + + 3. | + | + V + +-----+-----+ +-----+-----+ + | o | o--+--->| o | NIL | + +--+--+-----+ +--+--+-----+ + | | + V V + FUNCTION Name + + + Hier wird ein funktionaler Bindelisteneintrag erzeugt, so daß "Name" im Funk­ + tionsrumpf als Name einer Funktion auftreten kann. + + + 4. | + | + V + +-----+-----+ +-----+-----+ + | o | o--+--->| o | NIL | + +--+--+-----+ +--+--+-----+ + | | + V V + INDEFINITE Name + + + Dies ist ein Parameter, der beliebig viele berechnete Argumente aufnehmen + kann. Der Einfachheit halber werden die Ergebnisse zu einer Liste zusammen­ + gefaßt und mit "Name" in einen Bindelisteneintrag gesteckt. + + + 5. | + | + V + +-----+-----+ +-----+-----+ +-----+-----+ + | o | o--+--->| o | o--+--->| o | NIL | + +--+--+-----+ +--+--+-----+ +--+--+-----+ + | | | + V V V + INDEFINITE QUOTE Name + + + Dieser Parameter kann wie der in Fall 4. aufgeführte beliebig viele Argumente + aufnehmen, die zu einer Liste zusammengefaßt werden. Im Gegensatz zu 4. + wird aber wie bei 2. nichts durch "eval" berechnet, sondern die Argumente so + wie sie vorkommen übernommen. + +Auf einen Parameter der Form 4. oder 5. darf kein weiterer Parameter folgen, weil +solch ein Parameter alle restlichen Argumente verbraucht. Solchen Parametern darf - +als Ausnahme - auch kein Argument entsprechen; dann werden sie an die leere +Liste (d.h. NIL) gebunden. + +Der letzte Kasten in der Beschreibung des LAMBDA-Ausdrucks ist mit Absicht leer +geblieben; er kann eine der Formen + + + +-----+-----+ +----------+----------+ + | o | NIL | oder | Ganzzahl | XXXXXXXX | + +--+--+-----+ +----------+----------+ + | + V + Funktionsrumpf + + +annehmen. + +Die erste Form heißt, daß die Funktion durch Berechnung des Funktionsrumpfs mittels +"eval" berechnet werden soll; die zweite Form bewirkt den Aufruf einer der Standard­ +funktionen, je nachdem, welche Funktionsnummer bei "Ganzzahl" steht. In diesem +zweiten Fall werden die Argumente aber nicht durch den Namen des Parameters +identifiziert, sondern durch die Position des Eintrags in der Bindeliste. Dieser Pro­ +grammteil hängt also wesentlich von der Reihenfolge ab, in der die Bindelisteneinträ­ +ge, die bei der Parameter-Argument-Zuordnung entstehen, in die Bindeliste einge­ +fügt werden. Zur Zeit ist das die Umkehrung der Reihenfolge der Parameter. + +Die Namen der Refinements "arg 1", "arg 2", "arg 3" beziehen sich auch nicht auf +die Position des Arguments in der Argumentsliste, sondern auf die Position des +Eintrags in der Bindeliste. + +#page# + +4.4 Kommandoprozeduren #goalpage("p4.4")# + + + +Die Datei "lisp.4" enthält eine Reihe von Prozeduren, mit denen der LISP-Interpre­ +ter ähnlich wie der ELAN-Compiler aufgerufen werden kann. + +Die Prozedur + + start lisp system + +ermöglicht das erneute Starten des LISP-Systems, oder wenn "übersetzte" Pro­ +gramme, die in einem Heap einer anderen Task liegen, in dieser Task verarbeitet +werden sollen. + +Die Prozedur + + lisp + +stellt die LISP-Maschine in einem Doppelfenster im Bildschirmdialog zur Verfügung. +Bei der erstmaligen Benutzung muß die Datei "lisp.bootstrap" vorhanden sein. + +Die Prozedur + + break lisp + +koppelt die LISP-Task vom Benutzer-Terminal ab und baut das Doppelfenster für +den Bildschirmdialog neu auf. + + +Die Prozedur + + run lisp + +bewirkt, daß ein LISP-Programm eingelesen und ausgeführt wird; nach der Ausfüh­ +rung wird das Ergebnis der Berechnung ausgegeben. Diese Operationen werden auf +einer Kopie des Heaps ausgeführt, so daß Änderungen keine Dauerwirkung haben. +Mit + + run lisp again + +wird das zuletzt eingelesene Programm noch einmal gestartet; da dafür die gleiche +Kopie des Heaps wie bei "run" benutzt wird, kann das Ergebnis diesmal anders sein. + + insert lisp + +wirkt wie "run lisp", außer daß diesmal alle Änderungen, die durch das Einlesen und +Ausführen im Heap entstehen, dauerhaft sind. + + + PROC start lisp system (DATASPACE CONST heap): + Eine Kopie von "heap" wird der neue LISP-Heap. Wenn es sich um "nilspa­ + ce" handelt, werden einige organisatorische Strukturen im Heap aufgebaut und + die Atome "NIL" und "PNAME" erzeugt. + + PROC start lisp system (DATASPACE CONST heap, FILE VAR f): + Zunächst wird "start lisp system (heap)" gegeben. + Danach werden die Eigenschaftsbeschreibungen aus "f" in Strukturen im Heap + umgesetzt. + + Jede Beschreibung in "f" muß mit dem Zeilenanfang beginnen und kann sich + über mehrere Zeilen erstrecken. Jede Beschreibung besteht aus den Elementen + + wobei der Name einer Eigenschaft (i.a. APVAL oder FUNCTION) + und ein beliebiger S-Ausdruck sein müssen. Die drei Elemente müs­ + sen jeweils durch mindestens ein Leerzeichen getrennt sein. + + Wenn das Atom nicht existiert, wird es erzeugt; danach wird + unter in der Eigenschaftsliste eingetragen. + + Wenn NIL ist, muß wegfallen; dann wird nichts in die + Eigenschaftsliste eingetragen. + + DATASPACE PROC lisp heap: + Liefert den LISP-Heap. Das ist manchmal für Sicherheitskopien etc. nützlich. + Die durch "run lisp" erzeugten Kopien sind nicht zugänglich. + + PROC run lisp: + Ruft "run lisp (last param)" auf. + + PROC run lisp (TEXT CONST file name): + Das in der Datei "file name" stehende LISP-Programm (d.h. der dort stehende + in einen S-Ausdruck übersetzte M-Ausdruck) wird in eine neue Kopie des + LISP-Heaps eingelesen und ausgeführt. Evtl. vorher durch "run lisp" erzeugte + Kopien des Heaps werden vorher gelöscht. + + Wenn das Programm syntaktisch nicht korrekt ist, wird es im Paralleleditor zur + Korrektur angeboten. + + PROC run lisp again: + Führt das zuletzt eingelesene Programm noch einmal im gleichen Heap aus. + + PROC insert lisp: + Ruft "insert lisp (last param)" auf. + + PROC insert lisp (TEXT CONST file name): + Wirkt wie "run lisp (file name)", nur daß alle Operationen auf dem Originalheap + ausgeführt werden. Auch "run lisp again" wirkt nun nicht mehr auf der Kopie. + -- cgit v1.2.3