Lisp

Lisp
Basisdaten
Paradigmen:	multiparadigmatisch: funktional, prozedural; manche Dialekte außerdem modular, objektorientiert, reflexiv
Erscheinungsjahr:	1958
Designer:	John McCarthy
Entwickler:	Steve Russell, Timothy P. Hart, Mike Levin
Typisierung:	dynamisch
Dialekte:	Common Lisp, Scheme, Emacs Lisp und viele weitere
Beeinflusst von:	Lambda-Kalkül, Fortran, IPL
Beeinflusste:	Logo, Perl, Smalltalk, Clojure, Python, RPL, Ruby, Dylan, Mathematica, REBOL, Haskell, Snap! / BYOB

Lisp ist eine Familie von Programmiersprachen, die 1958 erstmals spezifiziert wurde und am Massachusetts Institute of Technology (MIT) in Anlehnung an den ungetypten Lambda-Kalkül entstand. Es ist nach Fortran die zweitälteste Programmiersprache, die noch verbreitet ist.

Auf Basis von Lisp entstanden zahlreiche Dialekte. Zu den bekanntesten zählen Common Lisp und Scheme. Daher bezieht sich der Begriff Lisp oft auf die Sprachfamilie und nicht auf einen konkreten Dialekt oder eine konkrete Implementierung.

Geschichte

Lisp steht für List Processor (Listenprozessor). Damit waren ursprünglich Fortran-Unterprogramme gemeint, mit denen symbolische Berechnungen durchgeführt werden sollten, wie sie der Lambda-Kalkül definiert. Steve Russell, einer der Studenten von John McCarthy, kam dann auf die fundamentale Idee, auf Grundlage dessen Formulierung eines „Lisp-Interpreters in Lisp“ einen Interpreter für diese Ausdrücke für die IBM 704 zu schreiben. Damit war die Programmiersprache Lisp geboren.

Die Grunddatenstrukturen von Lisp sind Einzelwerte (z. B. Symbole, Zahlen, Zeichenketten), die Atome genannt werden, und Cons-Zellen, aus denen Listen gebildet werden. Die Listen können beliebig verschachtelt werden (Listen von Listen). Damit lassen sich auch leicht Datenstrukturen wie ein assoziatives Array implementieren. Listen werden zur Darstellung in Lisp in runde Klammern gefasst:

(A B C)

Auch Programmanweisungen sind (verschachtelte) Listen, bei denen das jeweils erste Listenelement die auszuführende Funktion identifiziert. Es gibt somit keinen grundsätzlichen Unterschied zwischen Daten und Programmen; diese Eigenschaft wird Homoikonizität genannt. Der Programmierer kann so beispielsweise neue Kontrollstrukturen oder Objektsysteme (OOP) entwickeln (Metaprogrammierung, Makros). Es ermöglicht aber auch Programmteile zur Laufzeit beliebig zu manipulieren.

Lisp bietet dem Programmierer große Flexibilität und weitreichende Einflussmöglichkeiten, weshalb es manchmal auch als programmierbare Programmiersprache bezeichnet wird. Datenstrukturen werden dynamisch aufgebaut, ohne dass der Programmierer explizit Speicherplatz reservieren oder freigeben muss (siehe auch Garbage Collection). Deklarationen für Datentypen sind optional und ein Lisp-Symbol kann als Variable für beliebige Arten von Objekten stehen. Viele dieser Eigenschaften sind im Laufe der Zeit in weitere Programmiersprachen übernommen worden. Anfang der 1960er waren sie jedoch ihrer Zeit weit voraus.

In den 1970er und 1980er Jahren wurden spezielle Lisp-Maschinen entwickelt und vertrieben. Diese ermöglichten das schnelle Ausführen von Lisp-Programmen, was auf damaligen allgemeinen Computern nur unter dem Verzicht auf Typüberprüfung und automatische Speicherbereinigung möglich war. Dies hat sich durch schnellere Computer jedoch geändert.

Programme in Lisp können interpretiert oder von einem Compiler in effizienten Code übersetzt werden. Typische Compiler sind Batch-Compiler oder inkrementelle Compiler. Inkrementelle Compiler können einzelne Ausdrücke übersetzen. Batch-Compiler übersetzen einzelne Lisp-Dateien oder ganze Lisp-Programme. Compiler übersetzen entweder in einen Bytecode für eine virtuelle Maschine, in andere Programmiersprachen (oft in C) für die weitere Übersetzung oder in Maschinencode für einen Prozessor.

Das Akronym LISP wird manchmal scherzhaft als „Lots of Irritating Superfluous Parentheses“ (eine Menge lästiger, überflüssiger Klammern) interpretiert.

Bedeutung

Historisch gesehen gehört Lisp zusammen mit Prolog zu den wichtigsten Programmiersprachen der künstlichen Intelligenz. Durch Lisp ist erstmals der Lambda-Kalkül zum Kern einer Programmiersprache gemacht worden. Dieser ist ein wesentliches Element der Semantik vieler moderner Programmiersprachen.

Im Unterschied zu Europa, wo Programmiersprachen wie Assembler, Fortran oder Pascal als klassische Vertreter der Familie der prozeduralen Programmiersprachen gelehrt wurden, war und ist zum Teil bis heute in den Vereinigten Staaten Lisp, bzw. einer seiner moderneren Dialekte wie Scheme, die erste gelehrte Programmiersprache. Das hatte einen großen Einfluss, da es sich bei den klassischen Vertretern der prozeduralen Sprachfamilien um Vertreter einer statischen Verarbeitungsweise von Daten handelt, während unter anderem Lisp ein strikt dynamisches Konzept vertritt.

Syntax

Lisp benutzt S-Expressions als externes Format, um sowohl Quelltext als auch Daten darzustellen. Funktions- und Makroaufrufe werden als Listen geschrieben, die als erstes Element den Namen der Funktion bzw. des Makros enthalten. Kommentare werden mit einem oder mehreren ; eingeleitet.

Beispiele in Common Lisp:

;; Addiere 2 und 3 und 4:
(+ 2 3 4)

;; Setze die Variable p auf den Wert 3,1415:
(setf p 3.1415)

;; Definiere eine Funktion, die ihr Argument quadriert:
(defun square (x)
  (* x x))

;; Quadriere die Zahl 3:
(square 3)

LISP-Hallo-Welt-Programm:

(princ "Hello, world!")
(terpri)

Mit (terpri) erfolgt ein Zeilenumbruch.

Minimaler Funktionsumfang für Lisp

Um ein minimales Lisp-System zu implementieren, sind nur sehr wenige Operatoren und ein allgemeiner Mechanismus zur Funktionsdefinition nötig. Die folgenden Funktionen sind im ursprünglichen Bericht von McCarthy enthalten:

• first (gibt das erste Element einer Liste zurück; hieß ursprünglich car (von Contents of Address Part of Register))
• rest (gibt die Restliste (ohne das erste Element) zurück; hieß ursprünglich cdr (von Contents of Decrement Part of Register))
• cons (Erzeugt aus zwei Zeigern ein CONS-Paar und gibt einen Zeiger auf dieses zurück. Kann zum Beispiel verwendet werden, um ein Element an den Anfang einer Liste anzufügen) (von CONStruct)
• quote (verhindert die Auswertung des nachfolgenden Objekts)
• eq (Test auf Identität zweier oder mehrerer Objekte)
• cond (bedingte Ausführung: Übernimmt eine beliebig lange Liste von Paaren, die jeweils aus einer Bedingung und einer Berechnungsvorschrift bestehen. Gibt das Auswertungsergebnis der ersten Berechnungsvorschrift zurück, deren zugehörige Bedingung wahr ist)
• Mechanismus zur Funktionsdefinition lambda

Bereits mit diesen Sprachmitteln kann ein bemerkenswerter Teil der Funktionen, die übliche Lisp-Systeme mitbringen, definiert werden.

Datentypen

In der Originalversion von Lisp gab es zwei grundsätzliche Arten Datentypen: Atomare Symbole und Listen. Atomare Symbole hießen so, weil sie nicht zerlegt werden konnten.

Listen waren Sequenzen von Elementen, wobei diese Elemente Atome oder Unterlisten sein konnten. Die Listen selbst wurden aus Cons-Zellen, einem Paar von Zeigern, gebildet, dessen erste Komponente auf das Element verweist, die zweite aber auf den Rest der Liste. Die leere Liste bzw. das Ende der Liste wird durch das Atom 'NIL' präsentiert. Die Zellen wurden in der Literatur wie rechts gezeigt visualisiert und dienten zusammengenommen als S-Ausdrücke auch zur Darstellung des LISP-Quelltexts selbst.

Ein Atom war entweder eine Zahl oder ein Symbol. Ein Symbol war eine alphanumerische Zeichenkette, die als Variablenname oder Datenelement beim symbolischen Rechnen verwendet wurde.

Intern wurde ein Symbol-Atom nur einmal in der Symboltabelle abgespeichert. Zwei Symbolatome, die gleich geschrieben wurden und an verschiedenen Stellen im Quelltext vorkamen, repräsentierten dasselbe Objekt.

Später wurden in den Lisp-Dialekten weitere Datentypen eingeführt, und das Konzept der Lisp-Atome verlor an Bedeutung.

Symbolische Ausdrücke

Symbolische Ausdrücke

${\displaystyle {\begin{array}{lrlll}Sexp&=&Atom&{\textrm {atom}}\\&\vert &(List)&{\textrm {list}}\\List&=&&{\textrm {nil}}\\&\vert &Sexp\,\,List&{\textrm {cons}}\\\end{array}}}$

Die Denotation der Lisp-Daten entsprechend der rechts gezeigten Grammatik eröffnet die Möglichkeit, diese Syntax selbst zu verwenden, um Lisp-Programme als Lisp-Daten (S-Ausdrücke, S-Expressions) niederzuschreiben.

Umgekehrt kann diese sehr einfache Grammatik verwendet werden, um sowohl Daten als auch Programme einzulesen und zu bearbeiten oder zu interpretieren.

John McCarthy beschreibt die Weise der Niederschrift von Programmen im Abschnitt 1.6 (A Universal LISP Function) des Lisp-Handbuchs, womit zugleich auch ein Lisp-Interpreter in Lisp selbst angegeben wird.

Diese enge Verzahnung der Repräsentation von Programmen und Daten stellt eine besondere Charakteristik der Lisp-Programmierung dar.

Zitate

Lisp-Dialekte

Literatur

• John McCarthy: LISP 1.5: Programmer's Manual. The MIT Press, Cambridge, Mass. 1962 (106 S.). 

• Anthony C. Hearn: Standard LISP. University, Stanford, Calif. 1969. 

• Walter Sonnenberg: Anwendung von Lisp zur Definition und Implementierung Algolähnlicher Programmiersprachen. Universität Karlsruhe, 1970.

• John McCarthy, Carolyn L. Talcott (Hrsg.): LISP: Programming and proving. Stanford University, Stanford 1978. 

• Herbert Stoyan: LISP-Programmierhandbuch: Eine Sprache für die nichtnumerische Informationsverarbeitung. Akademie-Verlag, Berlin 1978 (208 S.). 

• John Allen: Anatomy of Lisp. McGraw-Hill, 1978, ISBN 0-07-001115-X.

• Herbert Stoyan: LISP: Anwendungsgebiete, Grundbegriffe, Geschichte. Akademie-Verlag, Berlin 1980 (480 S.). 

• Herbert Stoyan, Günther Görz (Hrsg.): LISP: Eine Einführung in die Programmierung. Springer, Berlin 1984, ISBN 3-540-13158-2 (358 S.). 

• Patrick Henry Winston, Berthold Horn: Lisp. Addison-Wesley Verlag, 1987, ISBN 3-925118-61-6.
• Harold Abelson, Gerald Jay Sussman: Structure and Interpretation of Computer Programs (SICP). MIT Press, 1993, ISBN 978-0-262-01153-2.
• Christian Queinnec: Lisp in Small Pieces. Cambridge University Press, 2003, ISBN 0-521-54566-8.

Weblinks

• John McCarthy et al.: Lisp 1.5 Programmer’s Manual. (PDF; 4,5 MB; Abgerufen am 10. Februar 2025englisch). 
• John McCarthy: Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I. (PDF; 214 kB; Abgerufen am 10. Februar 2025englisch). 
• Paul Graham: The Roots of Lisp. (PostScript; 208 kB; Abgerufen am 10. Februar 2025englisch, eine konzise Einführung in Anlehnung an McCarthys Arbeit). 
• Paul McJones: History of LISP. Software Preservation Group am Computer History Museum; abgerufen am 10. Februar 2025 (englisch). 
• Paul Graham: The Roots of Lisp. (PDF; 141 kB; Abgerufen am 10. Februar 2025englisch). 
• Guy L. Steele Jr., Richard P. Gabriel: The Evolution of Lisp. (PDF; 996 kB; Abgerufen am 10. Februar 2025englisch). 
• Tim Pritlove, Hans Hübner: Lisp – Die Mutter aller Programmiersprachen. (Podcast; 01:35:28 h) CRE; abgerufen am 10. Februar 2025. 

Einzelnachweise

1. ↑ Foldoc Jargon File: Herkunft des Schlüsselworts terpri. Abgerufen am 2. Dezember 2010. 
2. ↑ Lisp is a Chameleon. paulgraham.com
3. ↑ Arc Forum, abgerufen am 6. November 2016.
4. ↑ About newLISP
5. ↑ (lisp (flavoured (erlang))). Abgerufen am 7. Juli 2019.