Elemente der künstlichen Intelligenz (2): Funktionsdefinitionen
Eine Einführung in Programmiermethoden und Sprachen der KI
Benutzerdefinierte Funktionen
Im ersten Teil der Serie haben wir uns mit dem Gebrauch von primitiven (d. h. eingebauten) Listenfunktionen beschäftigt. Die volle Leistungsfähigkeit einer Sprache steht natürlich erst dann zur Verfügung, wenn man Primitive selbst zu Funktionsblöcken zusammenfaßt und diese wiederum zu immer komplexeren Blöcken vereinigt, die schließlich das gestellte Problem lösen (Bottom-Up-Methode). Die Definition von Funktionen in LISP und LOGO erfolgt nach dem sogenannten LAMBDA-Kalkül von Alonzo Church (siehe Literaturangaben). Der Aufbau einer Funktionsdefinition sieht demnach folgendermaßen aus (LISP):
(DEFUN Name ( Parameterliste )
( Anweisung )...)
Es bedeuten:
DEFUN:
Der Definitionsoperator. Er teilt LISP mit, daß die folgenden Listenelemente eine Funktion darstellen sollen.
NAME:
Unter diesem Namen wird die Funktion nach ihrer Definition aufgerufen.
PARAMETERLISTE:
Die in dieser Liste stehenden Parameter werden per Wert an die Funktion übergeben. D. h. sie stehen nur innerhalb der Funktion zur Verfügung und werden beim Verlassen der Funktion ungültig. Sie sind also an die Funktion gebunden).
ANWEISUNGEN:
Dies ist eine Folge von nacheinander auszuführenden LISP-Anweisungen (auch wieder Listen). Alle nicht in der Parameterliste stehenden Variablen (symbolische Atome) werden als globale Variablen (LISP: freie Variablen) interpretiert. Steht in einer Anweisung eine noch nicht an einen Wert gebundene Variable, erhält man eine Fehlermeldung.
Listing 1 enthält ein Beispielprogramm, das den Gebrauch von lokalen und globalen Variablen mit Hilfe der beiden Funktionen TEST und TEST2 demonstriert. Bitte beachten Sie, daß der Wert LOKAL (symbolisches Atom) zweimal ausgegeben wird. Das erste Mal als Ergebnis der Anweisung (print v3) in der Funktion TEST; das zweite Mal, weil aufgrund der letzten Anweisung von TEST (d. h. (print v3)) das Atom LOKAL den Wert der Funktion TEST darstellt und als dieser Wert ausgegeben wird, zusätzlich zum Nebeneffekt des Ausdruckens. Völlig analog erfolgt die Definition einer Funktion in LOGO:
TO NAME .PARI :PAR2 ...
ANWEISUNGEN
END
Listing2 enthält das zu Listing1 analoge Testprogramm für LOGO. Es enthält die gleichen Ergebnisse. Mit einer Ausnahme: Da in Logo die Rückgabe eines Atoms oder einer Liste als Wert der Funktion nur explizit mit Hilfe der OUTPUT-Anweisung geschehen kann, fehlt die doppelte Ausgabe von LOKAL.
Das LAMBDA-Kalkül
Manchmal ist es lästig, eine Funktion eigens namentlich zu definieren und sie dann aufzurufen. Bei kleineren Problemen ist es dagegen praktischer, eine namenlose Funktion an Ort und Stelle zu definieren und aufzurufen. Das ist der Kerngedanke des LAMBDA-Kalküls. Solch eine namenlose Funktionsdefinition hat dann in LISP folgende Form:
(LAMBDA ( Parameterliste )
( Anweisung )...)
Eine so definierte anonyme Funktion gibt dann einen Wert an das aufrufen-
(defun test ()
(setq vl 'global)
(setq v2 ’parameter!
(test2 v2)
(print v2)
(print v3))
(defun test2 (par)
(print v1)
(print par)
(setq par 'neuer_parameter)
(setq v3 'lokal))
(test)
GLOBAL <— Print v1 in test2
PARAMETER <— Print par in test2
NEUER_PARAMETER <— Print par in test2
PARAMETER <— Print v2 in test
LOKAL <— Print v3 in test
LOKAL <- Rückgabe des momentanen Wertes von test.
Stammt aus der Anweisung (print v3), die den
Wert LOKAL an die Funktion test zurückgegeben hat.
Listing 1: Zum Test lokaler und globaler Variablen in LISP
TO TEST1
MAKE "V1 "GLOBAL
MAKE "V2 "PARAMETER
TEST2 :V2
PRINT :V2
PRINT :V3
END
TO TEST2 :PAR
PRINT :V1
PRINT :PAR
MAKE "PAR "NEUER_PARAMETER
MAKE "V3 "LOKAL
PRINT :PAR
END
TEST1
GLOBAL <— PRINT :V1 IN TEST2
PARAMETER <— PRINT :PAR IN TEST2
NEUER_PARAMETER <- PRINT :PAR IN TEST2
PARAMETER <— PRINT :V2 IN TEST1
LOKAL <- PRINT :V3 IN TEST1
Listing 2: Zum Test lokaler und globaler Variablen in LOGO
de Programm zurück, der dort weiterverarbeitet wird. Eine vergleichbare Möglichkeit bietet in LOGO die Anweisung RUN. Sie benötigt als Parameter eine Befehlsliste, die bei Abarbeitung dieser Zeile ausgeführt wird:
RUN [(Anweisung ) ... ]
Allerdings fehlt in dieser Anweisung die Möglichkeit der Parameterübergabe. Solche anonymen Funktionen werden in LOGO nicht besonders unterstützt, und es ist in der Tat gerade rar den Anfänger besser, auf ihren Gebrauch zu verzichten.
Der Steuerfluß in Programmen
LISP als Muttersprache der KI und LOGO als deren Tochter verfügen noch nicht über neue Programmablaufmechanismen, wie sie PROLOG zu bieten hat. Hier muß (wie in PASCAL, BASIC und C auch) zuerst ein Algorithmus entwickelt werden, der dann in die entsprechende Sprache übersetzt wird. Die Befehle von LISP und LOGO sind lediglich mehr an symbolsichen Problemen (eben Problemen der KI) orientiert. Auch in
LISP und LOGO benötigen wir also Möglichkeiten, den Programmablauf in die eine oder andere Richtung zu lenken. In LOGO erledigt dies die IF-Anweisung. Ihre Semantik dürfte aus BASIC, PASCAL und C bekannt sein. Etwas eigenwilliger (und mächtiger) gibt sich dagegen die entsprechende Anweisung in LISP, COND ( wie Condition) genannt. Im Prinzip ist diese Anweisung eine Mixtur aus IF-THEN und CASE-Anweisungen. Ihre Syntax lautet:
/COND ((Test1) (Anweisung)
... (Ergebnisi))
((Test2) (Anweisung) ... (Ergebnis2))
((Testn) (Anweisung)... (Ergebnisn)))
Jede Liste wird Klausel genannt. Jede Klausel wird daraufhin untersucht, ob der Test erfolgreich ist oder nicht. Im Erfolgsfall wird der Rest der entsprechenden Klausel evaluiert. Der Wert der letzten Anweisung dieser Klausel wird als Ergebnis zurückgegeben (immer daran denken: LISP ist eine funktionale Sprache!). Die restlichen Klauseln (sie mögen den Test bestehen oder auch nicht) werden ignoriert! Falls kein einziger Test bestanden wird, gibt COND NIL zurück. Besteht die Klausel nur aus dem Test, so wird COND das Ergebnis dieses Tests als Wert zurückgeben. Der Test ist nichs anderes als eine LISP-Funktion, die nur zwei Ergebnisse zurückgeben kann: Bedingung erfüllt (in LISP: T, d. h. true) oder Bedingung nicht erfüllt (LISP: NIL, d. h. nothing in List bzw. false). Solche Funktionen heißen in LISP „Prädikatenfunktionen“. Sie sind vielleicht aus PASCAL unter dem Namen Boolesche Funktionen bekannt. Im XLISP-Artikel in Heft 1/87 dieser Zeitschrift ist eine Liste aller Prädikatenfunktionen von XLISP angegeben. Wie in der Prädikatenlogik üblich, lassen sich die Ergebnisse von Prädikatenfunktionen mit der logischen Verknüpfung UND, ODER, NICHT (in LISP AND, OR NOT) verknüpfen. Wie immer in LISP, sind auch die logischen Verknüpfungen als Präfix-Operatoren vereinbart. Das heißt, das erst das Verknüpfungszeichen angegeben wird, dann die zu verknüpfenden Elemente:
/NOT pr#dikat)
/AND element1 element2 element3...)
/OR element1 element2 element3...)
Die Funktion von NOT bedarf wohl kaum einer Erläuterung: NOT ergibt NIL, wenn prädikat nicht NIL ist, und T, wenn prädikat NIL ist. Am Beispiel der AND- und OR-Verknüpfung erkennt man den Vorteil der Präfixnotation: Es können beliebig viele Elemente verknüpft werden. Da das AND-Prädi-kat bereits dann NIL liefert, wenn nur ein einziges Element den Wert NIL besitzt, arbeitet diese Funktion ihre Argumente in folgender Weise ab:
Die Elemente werden von links nach rechts evaluiert. Bereits beim ersten Auftreten von NIL bricht die Funktion ab und gibt NIL als Funktionwert zurück. Evaluiert keines der Elemente zu NIL, so wird der Wert des letzten Argumentes zurückgegeben, also nicht notwendigerweise T!
Analog bei der OR-Funktion. Hier wird allerdings nur dann NIL zurückgegeben, wenn alle Argumente zu NIL evaluieren: Die Elemente werden von links nach rechts evaluiert. Wenn etwas anderes als NIL entdeckt wird, wird es sofort zurückgegeben. Die restlichen Argumente werden dann gar nicht erst evaluiert. Nur wenn alle Argumente zu NIL evaluieren, wird NIL zurückgegeben.
Beachten Sie bitte, daß alle Werte außer NIL dem Booleschen Wert TRUE entsprechen, auch wenn sie nicht zu T evaluieren. Nehmen Sie das folgende Beispiel:
(setq Computer ’(st amiga))
(ST AMIGA)
(and (member ’st Computer)
(member ’amiga Computer))
(AMIGA)
(or (member ’st Computer)
(member ’pc Computer))
(ST AMIGA)
Bei der Beurteilung der Ergebnisse ist zu berücksichtigen, daß member eben nicht nur Wahr oder nicht wahr antwortet, sondern die Liste aller Restargumente ab dem übereinstimmenden widergibt. Und nur, wenn diese Liste leer ist (d. h. NIL ist), interpretiert LISP dies als Mißerfolg! Die unterschiedlichen Ergebnisse der AND-und OR-Anfrage sind also darauf zurückzuführen, daß im Falle der AND-Funktion alle Argumente evaluiert werden und der letzte Wert evaluiert zu (AMIGA), weil dies der letzte (in der Liste Computer) ist. Da die OR-Funktion bereits beim ersten Erfolg mit der Evaluierung der Argumente abbricht, gibt die member-Funktion in der ersten Evaluierung bereits (ST AMIGA) zurück, weil dies der erste Computer (in der Liste) ist. Daß pc in der Liste nicht auftaucht (member ’pc Computer), also NIL ergibt stört die OR-Funktion nicht, da sie bereits vor der Evaluierung des zweiten Terms abbricht.
Auch LOGO kennt Prädikatsfunktionen, erkennbar am P als letzten Buchstaben des Namens, die in ihrer Bedeutung im allgemeinen von den fast namensgleichen LISP-Vorbildern nicht abweichen. Nur liefern diese Funktionen eben nur die Booleschen Werte TRUE und FALSE und akzeptieren im Fall von AND und OR nur zwei Argumente. Hier ist wohl im Laufe der Vererbung etwas von den großartigen (und leider komplizierten) Eigenschaften von LISP verlorengegangen.
Besondere Funktionsvereinbarungen in LISP: FUNCALL und LET
Das Einfache zuerst: FUNCALL bedeutet den Aufruf einer Funktion: FUNction CALL. Es wurde bereits gesagt, daß eine Besonderheit von Sprachen der KI in der Aufhebung der Grenze zwischen Daten und Programm zu sehen ist. Nehmen wir als Beispiel folgenden Ausschnitt aus einem LISP-Dialog:
(setq wurzel ’sqrt)
SQRT
(funcall wurzel 2)
1.4142
Hier wird also der Wert von Wurzel zu SQRT evaluiert und als Programm ausgeführt. Parameter 2 wird dabei an SQRT übergeben. Funcall kann aber noch mehr. Da das erste Argument evaluiert wird, kann funcall leicht für eine Menüsteuerung eingesetzt werden.
Beispiel:
(defun f-c (t) (/(- t 32) 1.8))
F-C
(defun c-f (t) (+ 32 (* 1.8 t)))
C-F
(defun fehlermeldung (t)
(print '(keine gültige Einheit)))
FEHLERMELDUNG
(setq temp ’fahrenheit)
FAHRENHEIT
(setq t 100)
100
(funcall (cond
((equal temp ’celsius) ’c-f)
((equal temp ’fahrenheit) ’f-c)
(t 'fehlermeldung)) t)
37.7777
Im Aufruf von FUNCALL wird also zunächst die Bedingung evaluiert und abhängig von deren Ergebnis die entsprechende Funktion aufgerufen, in diesem Fall die Konversion von Fahrenheit in Grad Celsius.
Eine andere Möglichkeit, Funktionen zu vereinbaren ist die Anweisung LET. Hier die Syntax:
/LET ((Parameter1 Wert1)
(Parameter2 Wert2)
...
(Parametern Wertn))
Programmkörper)
Die LET-Anweisung beginnt mit einer Liste von zweielementigen Listen, von denen das erste Element einem Parameter und das zweite Element einem Startwert entspricht. Danach kommt der LISP-Programmkörper, der nach der Initialisierung ausgeführt wird. „Uralt-BASIC“-Freunde werden einen Teil der gleichnamigen BASIC-Anweisung wiedererkannt haben. Das Besondere an der LISP-Anweisung ist, daß die Initialisierungsliste parallel initialisiert wird. Ich möchte das an folgendem Beispiel erläutern:
(let ((alpha 1)
(beta alpha))
(print alpha)
(print beta))
Obwohl in diesem Programmausschnitt alpha in der Initialisierungsliste definiert wird, steht es in der Definition von beta nicht zur Verfügung, weil beta parallel zu alpha definiert wird. LISP bricht diese Anweisung ab mit der Fehlermeldung:
error: unbound variable - ALPHA
Das Beispielprogramm
Das Beispielprogramm in Listing3 ermöglicht dem Benutzer die Durchführung von einfachen Mengenoperationen, nämlich die Bestimmung von Schnittmenge, Vereinigungsmenge und Differenzmenge zweier Mengen. Ich höre die Freunde des heiligen Turbo P. schon maulen: „Na und? Kann mein Turbo schon lange!“ Stimmt. Allerdings nur mit aufzählenden Datentypen - und das gibt Schwierigkeiten mit der Ein- und Ausgabe. LISP als intelligente Symbolmanipulationssprache erlaubt selbstverständlich die Verwendung beliebiger Datenelemente als Elemente von Mengen. Abb. 1 zeigt einen Beispieldialog mit dem Programm Listing3. Die Funktionen Schnittmenge, Vereinigungsmenge und Differenzmenge bedürfen wohl keiner weiteren Erläuterung; sie geben einfach die entsprechende Menge als Funktionswert zurück. Die Funktion „Machmenge“ macht aus der Parameterliste eine Menge, indem sie alle mehrfach vorkommenden Elemente nur einmal in die Menge aufnimmt. „Inmengep“ ist die Prädikatsfunktion, die abtestet, ob ein Element bereits in der Menge vorliegt. Die Funktion „druckmenge“ schließlich druckt die Menge in der mathematischen Form aus. Dazu bedient sich diese Funktion der rekursiv definierten Funktion „druckinhalt“. Aus dem Beispieldialog sollte hervorgehen, daß Symbolmanipulationssprachen wie LISP in allen Fällen, in denen Freiheit vom Diktat der Datenstruktur erforderlich ist, ungleich einfacher zu benutzen sind als ihre numerisch orientierten Kollegen PASCAF, C und BASIC. Vielleicht versuchen Sie mal, die Mengenoperationen in PASCAF zu programmieren (wohlgemerkt: keine Beschränkung der Mächtigkeit der Menge und der Struktur der Daten!)?
Wie geht’s weiter?
In der nächsten Ausgabe verlasse ich den LISP-FOGO-Trampelpfad, um Sie etwas näher mit der Verwendung der mathematischen Logik bei der Programmierung von Computern vertraut zu machen. Ich habe ja auch heute schon sehr viel von den Prädikaten-funktionen in LISP und LOGO gesprochen und so scheint es mir sinnvoll, einen Abstecher in den Bereich der Logik als Programmiersprache selbst zu machen. Natürlich benutze ich dazu die heißgeliebte PD-PROLOG-Version. Diese Diskette sollten Sie sich also besorgen — wenn Sie sie nicht schon längst besitzen.
In diesem Aufsatz besprochene Programmteile
AND
Logische Verknüpfung UND. Hat in LISP und LOGO verschiedene Syntax und Semantik. In beiden Sprachen wird AND als Präfixoperator verwendet.
In LISP können aber beliebig viele zu verknüpfenden Argumente folgen. AND liefert das letzte Argument als Funktionswert, wenn keines der Argumente NIL war. Falls nur ein einziges Argument NIL ist, ist AND auch NIL. Beispiel:
(AND ’kaufer ’auto 'liquide)
ergibt LIQUIDE als Wert, der logisch als TRUE zu interpretieren ist.
In LOGO sind nur zwei Argumente zulässig. Als Ergebnis sind nur die beiden Booleschen Werte TRUE und FALSE zu erwarten. Beispiel:
AND (NUMBERP 1.2) (LISTP [LISTE])
Ergibt den Wert TRUE.
COND
Verzweigungsanweisung in LISP. Ist eine Kombination von IF-THEN Anweisung und CASE Anweisung in PASCAL und BASIC. Aufbau:
(COND ((TEST 1) (Anweisung) ... (Anweisung)
((Test2) (Anweisung) ... (Anweisung))
...
((Testn) (Anweisung)...(Anweisung)))
Es wird diejenige Liste von Anweisungen ausgeführt, deren Test in der gegebenen Reihenfolge als erste nicht NIL ergibt. Die letzte Anweisung dieser Liste bestimmt gleichzeitig den Wert, den COND zurückgibt.
DEFUN
Definiert eine Funktion in LISP. Aufbau:
(DEFUN Name (Parameterliste)
(Anweisung)
...
(Anweisung))
Der Aufruf einer so definierten Funktion erfolgt mit:
(Name Parameter... Parameter)
Dabei ist darauf zu achten, daß die Anzahl der formalen Parameter (in der Parameterliste der Definition) mit der Anzahl der aktuellen Parameter (im Aufruf) übereinstimmt.
FUNCALL
Aufruf einer Funktion, deren Namen als Wert des 1. Parameters evaluiert wird. Beispiel:
FUNCALL Wurzel 4)
In diesem Beispiel wird Wurzel zu SQRT evaluiert und 4 als Parameter an SQRT übergeben. Dem Aufruf FUNCALL Name müssen also noch die Parameter folgen, die die Funktion benötigt, in diesem Beispiel das Argument der Wurzelfunktion.
LAMBDA
Definition einer anonymen Funktion. Aufbau der Anweisung wie bei DEFUN, allerdings wird auf einen Namen verzichtet. Beispiel:
((LAMBDA (X) (* X (* X X))) 2)
Diese anonyme (d. h. namenlose) Funktion berechnet x' für das Argument 2 und gibt 2' = 8 als Funktionswert zurück.
LET
Definition einer anonymen Funktion, bei der eine Liste von Variablen parallel initialisiert weren, d. h. die einzelnen zu initialisierenden Parameter stehen in der Initialisierungsphase gegenseitig nicht zur Verfügung.
NOT
Negation. In LISP ergibt NOT dann NIL, wenn das Argument nicht NIL ist. Ist das Argument gleich NIL, so ergibt die Negation T. Beispiel:
(NOT 'hallo)
NIL
In LOGO gilt wieder die Einschränkung der Werte auf TRUE und FALSE. Beispiel:
NOT "TRUE FALSE
OR
Logisches Oder. Gibt in LISP nur dann NIL zurück, wenn alle Argumente gleich NIL sind. Ist nur ein einziges Argument ungleich NIL, so wird dieses zurückgegeben und die ODER-Redingung gilt als erfüllt. Beispiel:
(OR NIL NIL 'Otto NIL)
(OTTO)
In LOGO gelten die gleichen Einschränkungen wie bei AND. D. h. es sind nur zwei Argumente erlaubt und die Werte TRUE und FALSE sind die einzigen zulässigen Ergebnisse. Beispiel:
OR "TRUE "FALSE
TRUE
TO
Funktionsdefinition in LOGO. Aufbau:
TO NAME PARAMETER ... .PARAMETER
ANWEISUNG
...
ANWEISUNG
END
Die verschiedenen Parameter stehen als lokal gebundene Variablen innerhalb der LOGO-Funktion zur Verfügung. END beendet die Definition der Funktion.
[1] Church, Alonzo. The Calculi of Lambda Conversion. Annals of Mathe-matical Studies. Vol.6. Princeton University Press. Princeton. 1942.
[2] Sarnow, Karl. XLISP Review. ST-Computer 1/87.
(defun inmengep (object menge)
(cond ((null menge) nil)
((equal (car menge) object) t)
( t (inmengep object (cdr menge)))
)
)
(defun vereinigungsmenge (mengel menge2)
(cond ((null mengel) menge2)
((inmengep (car mengel) menge2) (vereinigungsmenge (cdr mengel) menge2))
(t (vereinigungsmenge (cdr mengel) (cons (car mengel) menge2)))
)
)
(defun schnittmenge (mengel menge2)
(cond ((null mengel) ())
((inmengep (car menge1) menge2)
(cons (car menge1) (schnittmenge (cdr menge1) menge2)))
(t (schnittmenge (cdr mengel) menge2))
)
)
(defun differenzmenge (menge1 menge2)
(cond ((null menge1) ())
((null menge2) mengel)
((inmengep (car menge2) menge1)
(differenzmenge (remove (car menge2) menge1) (cdr menge2)))
(t (differenzmenge mengel (cdr menge2)))
)
)
(defun machmenge (liste)
(cond ((null liste) ())
((inmengep (car liste) (cdr liste))
(machmenge (cdr liste)))
(t (cons (car liste) (machmenge (cdr liste))))
)
)
(defun druckmenge (menge)
(prinl '()
(druckinhalt menge)
)
defun druckinhalt (menge)
(cond ((null menge) (print '|))
(t (prin1 (car menge))
(princ "\t")
(druckinhalt (cdr menge)) )
)
)
Listing 3