LISP - Eine Einführung (IDE)

Kapitel 1 - Grundlagen von LISP

| Wichtige Datentypen | Conses | Evaluierung von S - Expression|

1.4 Wichtige Datentypen

Wie jede andere moderne Programmiersprache unterscheidet CL eine große Zahl von Datentypen. Zu den wichtigsten Datentypen in CL gehören die folgenden:

Diese Datentypen lassen sich nach verschiedenen semantischen Kriterien klassifizieren: So bilden z.B. alle Datentypen mit Ausnahme des Datentyps der Listen die Klasse der atomaren Datentypen oder kurz der Atome.

Atome

selbstevaluierende Objekte

Zahlen

Zeichen

Zeichenketten

Symbole

Streams

Strukturen

Funktionen

Arrays

Listen werden aus noch zu erläuternden Gründen auch als CONSes bezeichnet.

Conses

Paarlisten

einfache Listen

Assoziationslisten

Property - Listen

Listen

Für einige dieser Datentypen gibt es verschiedene Subtypen: So werden z.B. verschiedene Klassen von Zahlen unterschieden: natürliche Zahlen, reele Zahlen, komplexe Zahlen, etc.
In vielen Fällen unterscheidet sich die Repräsentation von Elementen eines Datentyps nicht von der aus anderen Programmiersprachen vertrauten Repräsentation:

Beispiele - Datentypen

Natürliche Zahlen	1 - 37466 0
Dezimalzahlen	0.0 3.14 6.02+E23 -0.0000000000009
Zeichen	#\a #\Z #\9 #\( #\= #\Newline
	Neben den üblichen alphanumerischen Zeichen gibt es Zeichen, die nicht direkt sichtbar sind (sogen. whitespace character) wie z.B. #\Newline und #\Space. Alle Zeichen beginnen mit einer #\-Kombination.

Zeichenketten	"Hallo", "Noch ein String" , "\""
	Zeichenketten können beliebige Zeichen enthalten. Sie werden durch doppelte Hochkommata (") begrenzt. Wie das letzte Beispiel zeigt, kann auch das zur Markierung von Zeichenkettengrenzen verwendete Zeichen in einem String vorkommen, wenn ihm ein Backslash (\) vorangestellt wird.

Symbole	HALLO, Hallo, mein-symbol, datei1.lsp
	Symbolbezeichner können aus beliebigen alpha-numerischen Zeichen und bestimmten Sonderzeichen gebildet werden, müssen aber mit einem Buchstaben beginnen. Zwischen Groß- und Kleinschreibung wird anders als bei Zeichenketten normalerweise nicht unterschieden.

Listen	(), (77 listen), (noch (eine (Liste))), (eine . LISTE?)
	Eine nicht-leere Liste kann Objekte beliebigen Typs enthalten: Zahlen, Symbole oder auch andere Listen.

1.5 Conses

Ein CONS ist ein komplexes Objekt, das durch die geordnete Verbindung zweier LISP-Objekte gebildet wird, von denen jedes selbst wieder ein Objekt beliebigen Typs (z.B ein CONS ) sein kann; d.h., CONSes bilden eine rekursive Datenstruktur. Objekte dieses Typs werden häufig durch sogen. CONS-Zellen repräsentiert, die zwei Zeiger enthalten, wobei der erste auf das erste Objekt und der zweite auf das zweite Objekt weist:

Es gibt zwei Typen von CONSes: Listen und Paarlisten (dotted pairs). Der Unterschied zwischen diesen beiden Typen von CONSes besteht darin, daß bei Listen der CDR-Zeiger der letzten CONS-Zelle immer auf das die leere Liste repräsentierende Symbol NIL weist; bei den Paarlisten dagegen auf ein beliebiges LISP-Objekt. Listen bilden also einen speziellen Subtyp von Paarlisten - es sind Paarlisten, bei denen der CDR-Zeiger der letzten CONS-Zelle auf NIL weist.
Um für den Benutzer die Unterscheidung von Listen und Paarlisten transparent zu gestalten, werden Paarlisten vom System auf dem Bildschirm anders dargestellt als 'echte' Listen: Bei der Repräsentation von Paarlisten wird der Punkt "." verwendet, um die beiden Objekte der Paarliste voneinander zu trennen; d.h. der Punkt "." trennt den CAR-Teil vom CDR-Teil einer CONS-Zelle.

Beispiele CONS

(X . Y) ; Paarliste, die aus den Objekten X und Y besteht

(X Y) ; Liste, die auch diese Objekte enthält

(X . (Y . Z)) ; Paarliste, die aus X und der Paarliste (Y . Z) besteht

(X Y Z) ; Liste mit den Objekten X, Y, Z

Tatsächlich lassen sich auch Listen in dieser Punktnotation darstellen:

(X . (Y . NIL))

(X . (Y . (Z . NIL)))

Allerdings wird diese Repräsentation vom System direkt in die Standardlistenrepräsentation ohne Punkt überführt. Durch Verwendung von CONS-Zellen läßt sich die Struktur von Listen und Paarlisten sehr anschaulich darstellen; die Liste (X Y Z) z.B. läßt sich so repräsentieren als:

Die Liste besteht in dieser Repräsentationsform aus drei CONS-Zellen: Der CAR-Zeiger der ersten weist auf das Objekt X, der CDR-Zeiger auf ein CONS, das aus den CONS-Zellen 2 und 3 besteht. Der CAR-Zeiger der zweiten CONS-Zelle weist auf das Objekt Y, der CDR-Zeiger auf ein CONS, das aus der CONS-Zelle 3 besteht, und der CAR-Zeiger der dritten CONS-Zelle weist auf das Objekt Z, der CDR-Zeiger auf NIL. Dieser Punkt ist, wie schon erwähnt, entscheidend: Der CDR-Zeiger der letzten CONS-Zelle einer Liste weist immer auf NIL. So ergibt sich z.B. für die Liste (X (Y Z)) folgende Struktur:

Zur Erzeugung von CONSes gibt es in LISP die Funktion CONS (construct )

	CONS
	CONS Objekt1 Objekt2	[Funktion]
	CONS erzeugt ein komplexes Objekt mit Objekt1 als erster und Objekt2 als zweiter Komponente.

Beispiele - CONS

	(CONS 'A ())
	(A)

	(CONS 'A '(B))
	(A B)

Die Listen (X Y Z) und (X (Y Z)) kann man - statt sie durch eine Terminaleingabe direkt zu notieren - durch folgende Anweisungen generieren :

(CONS 'X (CONS 'Y (CONS 'Z ()))) bzw. (CONS 'X (CONS (CONS 'Y (CONS 'Z ())) ()))

Natürlich lassen sich durch CONS nicht nur Listen, sondern auch Paarlisten generieren:

	(CONS 'A 'B)
	(A . B)

	(CONS 'X (CONS 'Y 'Z))
	(X . (Y . Z))

	(CONS '(X Y) 'Z)
	((X Y) . Z))

Als CONS-Zellen notiert:

Obwohl Paarlisten den fundamentaleren Objekttyp bilden, ist für die LISP-Programmierung in vielen Fällen die Verwendung von Listen vorzuziehen und der Rückgriff auf Paarlisten nur in bestimmten Situationen sinnvoll bzw. erforderlich. Manche LISP-ProgrammiererInnen lehnen die Verwendung von Paarlisten grundsätzlich ab

1.6 Evaluierung von S-Expression

LISP-Datenstrukturen werden als S-Expressions (symbolic expressions) bezeichnet. Es sind nur eine geringe Zahl einfacher semantischer Regeln erforderlich um festzulegen, wie eine S-Expression zu interpretieren (evaluieren ) ist.

1.6.1 Selbstevaluierende Objekte

Zahlen, Zeichen und Zeichenketten (strings ) werden als selbstevaluierende Objekte bezeichnet. Die Evaluierung von S-Expressions dieses Typs, wird durch folgende Regel bestimmt:

	Regel 1
	Zahlen, Zeichen und Zeichenketten evaluieren zu sich selbst.

Beispiele - Selbstevaluierende Objekte

	3
	3

	#\a
	#\a

	"Ein alter Hut"
	"Ein alter Hut"

1.62 LISP - Symbole

LISP-Symbole sind komplexe Objekte, die in Common LISP Implementationen aus mindestens den folgenden fünf Teilen bestehen:

Print-Name: Der print-name des Symbols legt den Namen fest, den das System zur Verwaltung des Symbols verwendet. Da in Common LISP bei der Bildung von Symbolnamen nicht zwischen Groß- und Kleinbuchstaben unterschieden wird (Kleinbuchstaben werden automatisch in Großbuchstaben konvertiert), besteht der print-name eines Symbols in der Regel aus Großbuchstaben und anderen in Symbolnamen zulässigen Zeichen.

Beispiele - Symbole (print-name)

TEILCHENBESCHLEUNIGER ODER TEilchenBESCHLeunIGER ODER teilchenbeschleuniger

Drei verschiedene Möglichkeiten, das Symbol mit dem print-name TEILCHENBESCHLEUNIGER zu bezeichnen.

*globale-variable*

ein-datei.name

ein/pfad/name

Drei Symbole, deren print-name Sonderzeichen enthält.

Symbolen können Werte zugewiesen werden, die abhängig von der Art des Wertes und der Form der Wertzuweisung in dem mit value-binding , function-binding (im folgenden auch: Wertbindung bzw. Funktionsbindung ) bzw. property-list bezeichneten Teil des Symbols gespeichert werden. Wir werden uns zunächst auf die Wert- und Funktionsbindung von Symbolen beschränken.

Wertbindung: Da es möglich ist, Symbolen Werte zuzuweisen, können sie als Variablen verwendet werden. Als Werte für Symbole sind beliebige LISP-Objekte zulässig. So kann z.B. der Wert eines Symbols ein anderes Symbol sein.

Einige Symbole haben eine vordefinierte Bedeutung, die durch den Benutzer nicht verändert werden sollte (System-Konstanten). Die beiden wichtigsten Symbole dieses Typs sind:

T bezeichnet den booleschen Wert True ;

NIL bezeichnet den booleschen Wert False (und gleichzeitig auch die leere Liste).

Die Evaluation eines Symbols wird durch den Kontext gesteuert, in dem es vorkommt. Zunächst gilt:

	Regel 2
	Wenn keine andere Regel anwendbar ist, dann evaluiert ein Symbol zu seiner Wertbindung.

Beispiele - Symbole (Wertbindung)

Ausgehend von den links stehenden Wertbindungen, ergeben sich folgende Resultate:

	PI
	(A)

	Name
	"Otto Mustermann"

Die Evaluatierung von Symbolen, denen zuvor kein Wert zugewiesen wurde, führt zu einer entsprechenden Fehlermeldung und der Aktivierung eines break-levels.

	A
	Fehlermeldung

Wertzuweisung: Es gibt in Common LISP eine ganze Reihe von Funktionen bzw. special forms die es ermöglichen, einem Symbol einen Wert zuzuweisen. In den meisten Fällen wird die SETQ special form verwendet

	SETQ
	SETQ {Symbol NeuerWert}*	[Special Form]

	SETQ nimmt eine Folge von Symbol -NeuerWert Paaren als Argumente und weist Symbol den Wert von NeuerWert zu (value-binding ). Symbol wird nicht evaluiert. Der Wert der letzten NeuerWert -Form wird als Wert der SETQ-Form zurückgegeben.

Beispiele - Symbole (Wertzuweisung)

	(SETQ A 8)	Per Seiteneffekt wird das Symbol A an den Wert 8 gebunden (value-binding ).
	8	A => 8

	(SETQ A "Karl" B PI)	Per Seiteneffekt wird A an den Wert "Karl" und B an 3.14159 gebunden.
	3.14159	A => "Karl"
		B => 3.14159

	*(SETQ A 8 B ( A 3))**	Sequentielle Evaluierung: Zunächst wird A an den Wert 8 gebunden. Diese Wertbindung wird dann verwendet, um den Wert von B zu berechnen.
	24	A => 8
		B => 24

Während SETQ nur die Veränderung der Wertbindung von Symbolen erlaubt, ermöglicht der SETF-Makro (siehe Kapitel 1) auch die Veränderung der Funktionsbindung und der property-list eines Symbols, sowie den Zugriff auf die Komponenten von Arrays und Listen.

1.6.3 Listen

Wenn LISP eine Liste evaluiert, dann werden sequentiell alle Elemente der Liste evaluiert. Zu beachten ist allerdings, daß das erste Element der Liste als Funktionsname und die übrigen Elemente als Bezeichner der Argumente dieser Funktion aufgefaßt werden. Eine Liste repräsentiert in diesem Fall also einen Funktionsaufruf.

Nach Auswertung der Argumentsbezeichner wird die Funktion auf die Argumente angewendet und der aus der Funktionsanwendung resultierende Wert wird als Wert der Evaluation der Liste zurückgegeben.

	Regel 3
	Wenn ein Symbol als erstes Element einer zu evaluierenden Liste vorkommt, wird bei der Evaluation der Liste die Funktionsbindung des Symbols verwendet.
	Die dort gespeicherte Funktion wird auf das Resultat der Evaluierung aller übrigen Ausdrücke der Liste angewendet.Wenn keine andere Regel anwendbar ist, dann evaluiert ein Symbol zu seiner Wertbindung.

Beispiele - Listen

	(+ 9 6)	Zunächst wird die durch "+" bezeichnete Funktion lokalisiert (Funktionsbindung ). Dann werden "9" und "6" evaluiert und anschließend die Funktion auf die errechneten Werte angewendet.
	15

	(+ (- 5 7) 3)	Zunächst wird die durch "+" bezeichnete Funktion lokalisiert. Das zweite Element der Liste ist selbst wieder eine Liste, also wird zunächst die durch "-" bezeichnete Funktion lokalisiert und anschließend auf die Werte von "5" und "7" angewendet. Als Zwischenergebnis erhalten wir -2. Dann wird 3 evaluiert und mit -2 addiert.
	1

	(8 9 8)	Bei komplexen Listen wird, wie das letzte Beispiel zeigt, die Regel 3 rekursiv angewendet. Allerdings wird jedes Objekt nur einmal evaluiert: evaluiert z.B. ein Symbol S1 zu einem Symbol S2, wird S2 selbst nicht wieder evaluiert.
	Fehlermeldung	da "8" keine Funktion bezeichnet.

Wie die Struktur von Symbolen schon vermuten läßt, kann ein Symbol gleichzeitig als Variable und als Funktionsname verwendet werden.

1.6.4 Unterdrücken und Erzwingen einer Evaluierung

In vielen Fällen ist es sinnvoll, die Evaluierung von S-Expressions zu verhindern, da sie zu unerwünschten Resultaten führen würde (z.B. '(8 9 10)'). Zu diesem Zweck gibt es in LISP eine special form mit dem Namen QUOTE:

	QUOTE
	QUOTE Objekt	[Special Form]
	QUOTE verhindert die Evaluierung des LISP-Objekts Objekt und liefert als Wert Objekt.

Da diese special form sehr häufig benötigt wird, gibt es für sie eine Kurzschreibweise (read-macro ): das Hochkomma ('). Es gilt also:

(QUOTE Object ) = 'Object

Andererseits gibt es eine Funktion, die wir im Zusammenhang mit der kurzen Charakterisierung der Funktionsweise des LISP-Interpreters erwähnt hatten, die eine zusätzliche Evaluierung erzwingt:

	EVAL
	EVAL *Form*	[Funktion]
	Evaluierung; d.h., eine Evaluierung des Wertes von Form.

Beispiele - Quote / Eval

	A
	Fehlermeldung	ungebundenes Symbol

	(QUOTE A)
	A

	'A
	A

	(EVAL 'A)
	Fehlermeldung	ungebundenes Symbol

	(EVAL "A)
	A

	(SETQ A 0)
	0

	A
	0

	(EVAL 'A)
	0

	'(8 9 10)
	(8 9 10)

Kapitel 2 - Funktionen

| über dieses projekt | kontakt | zurück zur übersicht |