11 Quote und Unquote
Listen spielen in funktionalen Sprachen eine wichtige Rolle, insbesondere in der Familie von Sprachen, die von LISP abstammen (wie Racket und BSL).
Wenn man viel mit Listen arbeitet, ist es wichtig, eine effiziente Notation dafür zu haben. Sie haben bereits die list Funktion kennengelernt, mit der man einfache Listen kompakt notieren kann.
Allerdings gibt es in BSL/ISL (und vielen anderen Sprachen) einen noch viel mächtigeren Mechanismus, nämlich quote und unquote. Diesen Mechanismus gibt es seit den 1950er Jahren in LISP, und noch heute eifern beispielsweise Template Sprachen wie Java Server Pages oder PHP diesem Vorbild nach.
Um mit quote und unquote zu arbeiten, ändern Sie bitte den Sprachlevel auf "Anfänger mit Listenabkürzungen" beziehungsweise "Beginning Student with List Abbreviations".
11.1 Quote
Das quote Konstrukt dient als kompakte Notation für große und verschachtelte Listen. Beispielsweise können wir mit der Notation (quote (1 2 3)) die Liste (cons 1 (cons 2 (cons 3 empty))) erzeugen. Dies ist noch nicht besonders eindrucksvoll, denn der Effekt ist der gleiche wie
> (list 1 2 3) (1 2 3)
Zunächst mal gibt es eine Abkürzung für das Schlüsselwort quote, nämlich das Hochkomma, ’.
> '(1 2 3) (1 2 3)
> '("a" "b" "c") ("a" "b" "c")
> '(5 "xx") (5 "xx")
Bis jetzt sieht quote damit wie eine minimale Verbesserung der list Funktion aus. Dies ändert sich, wenn wir damit verschachtelte Listen, also Bäume, erzeugen.
> '(("a" 1) ("b" 2) ("c" 3)) (("a" 1) ("b" 2) ("c" 3))
Wir können also mit quote auch sehr einfach verschachtelte Listen erzeugen, und zwar mit minimalem syntaktischen Aufwand.
Die Bedeutung von quote ist über eine rekursive syntaktische Transformation definiert.
'(e-1 ... e-n) wird transformiert zu (list 'e-1 ... 'e-n). Die Transformation wird rekursiv auf die erzeugten Unterausdrücke 'e-1 usw. angewendet.
Wenn l ein Literal (eine Zahl, ein String, ein WahrheitswertWenn Sie boolsche Literale quoten wollen, müssen Sie die Syntax #true und #false für die Wahrheitswerte verwenden; bei true und false erhalten Sie ein Symbol., oder ein Bild) ist, dann wird 'l transformiert zu l.
Wenn n ein Name/Bezeichner ist, dann wird 'n transformiert zum Symbol 'n.
Ignorieren Sie eine Sekunde die dritte Regel und betrachten wir den Ausdruck '(1 (2 3)). Gemäß der ersten Regel wird dieser Ausdruck im ersten Schritt transformiert zu (list '1 '(2 3)). Gemäß der zweiten Regel wird der Unterausdruck '1 zu 1 und gemäß der Anwendung der ersten Regel wird aus dem Unterausdruck '(2 3) im nächsten Schritt (list '2 '3). Gemäß der zweiten Regel wird dieser Ausdruck wiederum transformiert zu (list 2 3). Insgesamt erhalten wir also das Ergebnis (list 1 (list 2 3)).
Sie sehen, dass man mit quote sehr effizient verschachtelte Listen (eine Form von Bäumen) erzeugen kann. Vielleicht fragen Sie sich, wieso wir nicht gleich von Anfang an quote verwendet haben. Der Grund dafür ist, dass diese bequemen Wege, Listen zu erzeugen, verbergen, welche Struktur Listen haben. Insbesondere sollten Sie beim Entwurf von Programmen (und der Anwendung des Entwurfsrezepts) stehts vor Augen haben, dass Listen aus cons und empty zusammengesetzt sind.
11.2 Symbole
Symbole sind eine Art von Werten die Sie bisher noch nicht kennen. Symbole dienen zur Repräsentation symbolischer Daten. Symbole sind verwandt mit Strings; statt durch Anführungszeichen vorne und hinten wie bei einem String, "Dies ist ein String", werden Symbole durch ein einfaches Hochkomma gekennzeichnet: 'dies-ist-ein-Symbol. Symbole haben die gleiche Syntax wie Namen/Bezeichner, daher sind beispielsweise Leerzeichen nicht erlaubt.
Im Unterschied zu Strings sind Symbole nicht dazu gedacht, Texte zu repräsentieren. Man kann beispielsweise nicht (direkt) Symbole konkatenieren. Es gibt nur eine wichtige Operation für Symbole, nämlich der Vergleich von Symbolen mittels symbol=?.
> (symbol=? 'x 'x) #true
> (symbol=? 'x 'y) #false
Symbole sind dafür gedacht, "symbolische Daten" zu repräsentieren. Das sind Daten, die "in der Realität" eine wichtige Bedeutung haben, aber die wir im Programm nur mit einem Symbol darstellen wollen. Ein Beispiel dafür sind Farben: 'red, 'green, 'blue. Es macht keinen Sinn, die Namen von Farben als Text zu betrachten. Wir wollen lediglich ein Symbol für jede Farbe und vergleichen können, ob eine Farbe beispielsweise 'red ist (mit Hilfe von symbol=?).
11.3 Quasiquote und Unquote
Der quote Mechanismus birgt noch eine weitere Überraschung. Betrachten Sie das folgende Programm:
(define x 3) (define y '(1 2 x 4))
Welchen Wert hat y nach Auswertung dieses Programms? Wenn Sie die Regeln oben anwenden, sehen Sie, dass nicht etwa (list 1 2 3 4) sondern (list 1 2 'x 4) herauskommt. Aus dem Bezeichner x wird also das Symbol 'x.
Betrachten wir noch ein weiteres Beispiel:
> '(1 2 (+ 3 4)) (1 2 (+ 3 4))
Wer das Ergebnis (list 1 2 7) erwartet hat, wird enttäuscht. Die Anwendung der Transformationsregeln ergibt das Ergebnis: (list 1 2 (list '+ 3 4)). Aus dem Bezeichner + wird das Symbol '+. Das Symbol '+ hat keine direkte Beziehung zur Additionsfunktion, genau wie das Symbol 'x in dem Beispiel oben keine direkte Beziehung zum Konstantennamen x hat.
Was ist aber, wenn Sie Teile der (verschachtelten) Liste doch berechnen wollen?
Betrachten wir als Beispiel die folgende Funktion:
; Number -> (List-of Number) ; given n, generates the list ((1 2) (m 4)) where m is n+1 (check-expect (some-list 2) (list (list 1 2) (list 3 4))) (check-expect (some-list 11) (list (list 1 2) (list 12 4))) (define (some-list n) ...)
Eine naive Implementation wäre:
(define (some-list n) '((1 2) ((+ n 1) 4)))
Aber natürlich funktioniert diese Funktion nicht wie gewünscht:
> (some-list 2) ((1 2) ((+ n 1) 4))
Für solche Fälle bietet sich quasiquote an. Das quasiquote Konstrukt verhält sich zunächst mal wie quote, außer dass es statt mit einem geraden Hochkomma mit einem schrägen Hochkomma abgekürzt wird:
> `(1 2 3) (1 2 3)
> `(a ("b" 5) 77) (a ("b" 5) 77)
Das besondere an quasiquote ist, dass man damit innerhalb eines gequoteten Bereichs zurückspringen kann in die Programmiersprache. Diese Möglichkeit nennt sich "unquote" und wird durch das unquote Konstrukt unterstützt. Auch unquote hat eine Abkürzung, nämlich das Komma-Zeichen.
> `(1 2 ,(+ 3 4)) (1 2 7)
Mit Hilfe von quasiquote können wir nun auch unser Beispiel von oben korrekt implementieren.
> (some-list-v2 2) ((1 2) (3 4))
Die Regeln zur Transformation von quasiquote sind genau wie die von quote mit einem zusätzlichen Fall: Wenn quasiquote auf ein unquote trifft, neutralisieren sich beide. Ein Ausdruck wie `,e wird also transformiert zu e.
11.4 S-Expressions
Betrachten Sie die person-has-ancestor Funktion aus Programmieren mit rekursiven Datentypen. Eine ähnliche Funktion lässt sich auch für viele andere baumartig organisierte Datentypen definieren, beispielsweise solche zur Repräsentation von Ordnerhierarchien in Dateisystemen oder zur Repräsentation der Hierarchie innerhalb einer Firma.
Natürlich könnten wir neben person-has-ancestor nun auch noch file-has-enclosing-directory und employee-has-manager implementieren, aber diese hätten eine sehr ähnliche Struktur wie person-has-ancestor. Wir würden also gegen das DRY-Prinzip verstoßen.
Es gibt eine ganze Reihe von Funktionen, die sich auf vielen baumartigen Datentypen definieren liessen: Die Tiefe eines Baumes berechnen, nach Vorkommen eines Strings suchen, alle "Knoten" des Baums finden, die ein Prädikat erfüllen, und so weiter.
Um solche Funktionen generisch (also einmal für alle Datentypen) definieren zu können, brauchen wir die Möglichkeit, über die genaue Struktur von Datentypen abstrahieren zu können. Dies funktioniert mit den "getypten" Datentypen, die wir bisher betrachtet haben, nicht.
Eine der großen Innovationen der Programmiersprache LISP war die Idee eines universellen Datenformats: Ein Format, mit dem beliebige strukturierte Daten repräsentiert werden können, und zwar in solch einer Weise, dass das Datenformat Teil der Daten ist und dementsprechend darüber abstrahiert werden kann. Diese Idee wird typischerweise alle paar Jahre wieder einmal neu erfunden; zur Zeit sind beispielsweise XML und JSON beliebte universelle Datenformate.
Der Mechanismus, den es dazu in LISP seit Ende der 1950er Jahre gibt, heißt S-Expressions. Was sind S-Expressions? Hier ist eine Datendefinition, die dies genau beschreibt:
; An S-Expression is one of: ; – a Number ; - a String ; - a Symbol ; - a Boolean ; - an Image ; – empty ; - a (list-of S-Expression)
Beispiele für S-Expressions sind: (list 1 (list 'two 'three) "four"), "Hi". Dies sind keine S-Expressions: (make-posn 1 2), (list (make-student "a" "b" 1)).
S-Expressions können als universelles Datenformat verwendet werden, indem die Strukturierung der Daten zum Teil der Daten gemacht wird. Statt (make-posn 1 2) kann man auch die S-Expression '(posn 1 2) oder '(posn (x 1) (y 2)) verwenden; statt (make-person "Heinz" (make-person "Horst" false false) (make-person "Hilde" false false)) kann man auch die S-Expression '(person "Heinz" (person "Horst" #false #false) (person "Hilde" #false #false)) oder '(person "Heinz" (father (person "Horst" (father #false) (mother #false)) (mother (person "Hilde" (father #false) (mother #f))))) verwenden.
Der Vorteil der zweiten Variante ist, dass man beliebige strukturierte Daten auf diese Weise uniform ausdrücken kann und die Struktur selber Teil der Daten ist. Damit wird es möglich, sehr generische Funktionen zu definieren, die auf beliebigen strukturierten Daten funktionieren. Der Nachteil ist der, dass man Sicherheit und Typisierung verliert. Es ist schwierig, zu sagen, dass eine Funktion beispielsweise nur S-Expressions als Eingabe verarbeiten kann, die einen Stammbaum repräsentieren.
Der Quote-Operator hat die Eigenschaft, dass er stets S-Expressions erzeugt. Sie können sogar beliebige Definitionen oder Ausdrücke in BSL nehmen, einen Quote-Operator drumherumschreiben, und Sie erhalten eine S-Expression, die dieses Programm repräsentiert.
> (first '(define-struct student (firstname lastname matnr))) define-struct
Diese Eigenschaft, die manchmal Homoikonizität genannt wird, macht es besonders leicht, Programme als Daten zu repräsentieren und Programme zu schreiben, die die Repräsentation eines Programms als Eingabe bekommen oder als Ausgabe produzieren. In Scheme und (vollem) Racket gibt es sogar eine Funktion eval, die eine Repräsentation eines Ausdrucks als S-Expression als Eingabe bekommt und die diesen Ausdruck dann interpretiert und das Ergebnis zurückliefert. Beispielsweise würde (eval '(+ 1 1)) Ergebnis 2 liefern. Damit wird es möglich, Programme zur Laufzeit zu berechnen und dann direkt auszuführen - eine sehr mächtige aber auch sehr gefährliche Möglichkeit.
11.5 Anwendungsbeispiel: Dynamische Webseiten
Da S-Expressions ein universelles Datenformat sind, ist es einfach, andere Datenformate darin zu kodieren, zum Beispiel HTML (die Sprache in der die meisten Webseiten definiert werden).
Zusammen mit Quasiquote und Unquote können S-Expressions dadurch leicht zur Erstellung von dynamischen Webseiten, bei denen die festen Teile als Template definiert werden, genutzt werden. Beispielsweise könnte eine einfache Funktion zur Erzeugung einer dynamischen Webseite wie folgt aussehen:
; String String -> S-Expression ; produce a (representation of) a web page with given author and title (define (my-first-web-page author title) `(html (head (title ,title) (meta ((http-equiv "content-type") (content "text-html")))) (body (h1 ,title) (p "I, " ,author ", made this page."))))
Die Funktion erzeugt die Repräsentation einer HTML-Seite, bei der die übergebenen Parameter an der gewünschten Stelle eingebaut werden. S-Expressions und Quasi-/Unquote führen zu einer besseren Lesbarkeit im Vergleich zur Variante der Funktion, die die Datenstruktur mit cons und empty oder list zusammenbaut. Die erzeugte S-Expression ist zwar noch kein HTML, aber sie kann leicht zu HTML umgewandelt werden. In Racket gibt es zu diesem Zweck beispielsweise die xexpr->string und xexpr->xml Funktion der XML Bibliothek.
> (require xml)
> (xexpr->string (my-first-web-page "Klaus Ostermann" "Meine Homepage")) "<html><head><title>Meine Homepage</title><meta http-equiv=\"content-type\" content=\"text-html\"/></head><body><h1>Meine Homepage</h1><p>I, Klaus Ostermann, made this page.</p></body></html>"
Der durch xexpr->string erzeugte String ist gültiges HTML und könnte nun an einen Browser geschickt und dargestellt werden.