Nachdem im vorherigen Teil die Basiselemente der Scheme-Programmierung vorgestellt wurden, soll in diesem Artikel ein essentieller Vorteil von Scheme die Hauptrolle spielen, nämlich die funktionale Programmierung.

Ein großer Vorteil LISP-ähnlicher Sprachen ist die Existenz von Funktionen höherer Ordnung. Das sind Funktionen, die entweder wiederum Funktionen als Parameter akzeptieren, in denen Funktionen Rückgabewert sein können, oder aber für die beides zutrifft. Diese Möglichkeit ist in Beispielen wie den folgenden besonders nützlich.

Funktionen als Parameter

Um zu zeigen, wie nützlich Funktionen als Parameter sind, sollen die Funktionen double-all und add-two als Beispiel dienen. Die erste Funktion verdoppelt alle Elemente einer Liste während die zweite zu jedem Element zwei addiert (Listing 1).

Die Ähnlichkeit der beiden Funktionen ist so frappierend, dass sich die Frage aufdrängt, ob man hier nicht etwas verallgemeinern kann. Mankann zumindest in Scheme. Der Unterschied besteht nur in der jeweiligen Operation auf dem jeweils ersten Element der Restliste. Nach der Bearbeitung wird das Ergebnis in die Rückgabeliste aufgenommen. Mit einer Funktion als Parameter lassen sich die beiden Beispiele vereinfachen. Dazu behalten wir die Implementierung bei und parametrisieren die Unterschiede durch einen Parameter (hier op ).

(define (apply-to-all op a-list)
  (if (null? a-list) 
      '()
      (cons (op (first a-list))
   (apply-to-all op (cdr a-list)))))
Op  sieht  in double-all  so aus: 

 (* 2 x), was man
direkt in Scheme übersetzen kann: 

 (define (double x) (* 2 x))

Wenden wir double-all sowie apply-to-all zusammen mit double einmal an:

(define a-list '(1 2 3))
(double-all a-list) -> '(2 4 6)
(apply-to-all double a-list) -> '(2 4 6)

Der angedeutete Pfeil -> steht für “ergibt” oder “evaluiert zu”. Die beiden Funktionen liefern das gleiche Ergebnis, jedoch ist die zweite Version universeller einsetzbar.

Was hier so bemerkenswert einfach geht, ist in manchen Sprachen gar nicht oder nur mit hohem Aufwand nachzubilden. Die sich aus Funktionen höherer Ordnung ergebenden Möglichkeiten, dürften selbst bei diesem Beispiel schon so offensichtlich sein, dass man sich fragt, warum nicht alle Sprachen solche Möglichkeiten bieten. Um nicht jeder noch so kleinen Funktion einen eigenen Namen geben zu müssen, kann man in Scheme auch anonyme Funktionen einsetzen. Somit kann apply-to-all folgendermaßen vereinfacht werden:

(apply-to-all (lambda (n) (* 2 n)) a-list)

Das Ergebnis wäre wieder \'(2 4 6). Dieses lambda ist in Scheme ein wichtiges Basiselement der Programmierung und die Grundlage weiterer Elemente, auch wenn diese Elemente auf den ersten Blick keine Gemeinsamkeiten mit dem unscheinbaren lambda besitzen.

Apply-to-all kann man durch die Scheme Standardfunktion ( map) ersetzen. Mit dieser sähe unsere Lösung so aus:

(map(lambda (n) (* 2 n)) a-list)

Selbstverständlich kann man double-all mit Hilfe von map reimplementieren.

(define (double-all al)
    (map (lambda (n) (* 2 n)) al))

Eine weitere nützliche Funktion ( filter) dient zum Aussortieren von Elementen, die bestimmten Bedingungen genügen. Man kann filter wie in Listing 2 implementieren:

Möchten Sie nun aus einer Liste alle positiven Elemente herausfiltern, können Sie folgende Scheme-Funktion nutzen:

(filter positive? a-list)

Map und filter sind beliebig kombinierbar. Mit

(filter positive? (map double a-list))

verdoppelt man beispielsweise alle Elemente und sortiert dann die Positiven aus. In diesem Fall wäre

(map double (filter positive? a-list))

äquivalent und aus Effizienzgründen vorzuziehen. Wer mag, kann sich mal Gedanken darüber machen, warum das so ist.

(define (double-all a-list)
  (if (null? a-list) 
          '()
          (cons (* 2 (first a-list)) 
                  (double-all (rest a-list)))))

(define (add-two a-list)
  (if (null? a-list)
          '()
          (cons (+ 2 (first a-list)) 
                  (add-two (rest a-list)))))

(define (filter pred? a-list)
  (cond

    ((null? a-list) '())
    ((pred? (first a-list)) (cons (first a-list)
                                  (filter pred? (rest a-list))))
    (else
     (filter pred? (rest a-list)))))

Funktionen als Rückgabewerte

In Scheme sind Funktionen und Daten gleichberechtigt. Funktionen sind an allen Stellen erlaubt, wo auch “normale” Variablen vorkommen können. Innerhalb anderer Methoden, als Parameter und auch als Rückgabewerte. Sie sind in Fachterminologie ausgedrückt Objekte erster Klasse (first-class objects). Hier ein Beispiel:

(define (make-adder n)   (lambda (m)     (+ n m))) (define add-5 (make-adder 5))

Bei add-5 handelt es sich um eine Funktion, die 5 zu ihrem Argument addiert, Steele stellt in [6], S. 145, Kapitel 2.3.2 ein interessantes Beispiel vor.

Lokale Variablen

Wie in anderen Sprachen kann man auch in Scheme lokale Variablen deklarieren und nutzen. Im Gegensatz zu den meisten anderen Sprachen ist es unerheblich, ob es sich bei den Werten der lokalen Variablen um Daten oder Funktionen handelt. Lokale Variablen werden in einem mit let oder let* eingeleiteten Block deklariert und initialisiert. Der Unterschied zwischen let und let* besteht darin, dass man sich in let* auf vorher auftretende Deklarationen beziehen kann. Bemerkenswert an den beiden lets ist, dass sie nur Makros um das schon bekannte lambda sind. Im Prinzip sind die beiden folgenden Zeilen äquivalent:

(let ((i 1)) (display i) (newline))
((lambda (i) (display i) (newline)) 1)

Die erste Art ist meiner Meinung nach besser lesbar und verständlicher. Beachten Sie aber bitte, dass Sie nicht das “named-let” aus dem ersten Teil mit dieser lokalen Variablendeklaration vertauschen. Die hier gültige Form lautet: (let ((variable init)) . Auf die Initialisierung kann in Scheme nicht verzichtet werden.

Am folgenden Beispiel erkennen Sie, dass man in Scheme auch Funktionen an lokale Variablen binden kann.

(let ((d (lambda (n) (* n 2))))
    (display (d 1)) (newline))

Let kann man nicht nur innerhalb anderer Funktionen oder weiterer let-Blöcken finden, sondern auch auf dem Top-Level. In jedem Fall sind die deklarierten Variablen nur bis zum Ende des Blockes sichtbar, in dem sie definiert wurden.

Die Verschachtelung gilt nicht nur für lets, sondern auch für Kombinationen von let und define. Ob Sie also (let ((i 1) (j 10)) (+ i j)) benutzen oder (let ((i 1)) (let ((j 10)) (+ i j))), richtet sich nach der Situation oder Ihren Vorstellungen. Scheme legt Ihnen auch keine Restriktionen bezüglich der Position von weiteren Funktionen oder der Einführung von lokalen Variablen auf.

Lexikalische Bindung

Scheme spielte in diesem Bereich eine Vorreiterrolle in der Lisp-Familie. Die lexikalische Bindung veranschaulicht wiederum ein Beispiel am besten.

(define counter 50)
(define (inc-counter)
  (set! counter (+ 1 counter))
  counter)
(let ((counter 100))
  (display (inc-counter)) (newline)
  (display (inc-counter)) (newline))

Da in Scheme die lexikalische Bindung gilt, erhalten Sie als Ausgabe 51 52. Zwar überlagert der counter im let-Block die globale Variable mit dem gleichen Namen, jedoch nicht in der Funktion inc-counter. Als diese Funktion definiert wurde, war nur die globale Variable bekannt, und nur auf diese hat inc-counter Zugriff. Innerhalb des Blockes definierte Funktionen oder Variablen hätten hingegen nur Zugriff auf die überlagerte Variable.

Eine andere Art der Bindung wird dynamische genannt, sie war Standard in den ersten Lisps Versionen, bei Emacs Lisp handelt es sich noch um ein Lisp mit dynamischer Bindung. Dr. Scheme stellt diese Bindung mit fluid-let zur Verfügung:

(fluid-let ((counter 100))
  (display (inc-counter) (newline))
  (display (inc-counter) (newline)))

Ausgabe hier: 100 101. Da das Verhalten sich bei der lexikalischen und dynamischen Bindung unterscheidet, sollten Sie sich der jeweils gültigen Bindung bewusst sein. Scheme unterstützt normalerweise nur die lexikalische Bindung, Common Lisp bietet beide Arten und Emacs Lisp standardmäßig die dynamische Bindung (mit Möglichkeiten, die lexikalische Bindung zu emulieren).

Datenkapselung in Scheme

Der kontrollierte Zugriff auf Daten ist in Scheme eines der interessanten Anwendungsgebiet für eine Kombination aus lexikalischen Bindung und dem Gebrauch von Funktionen höherer Ordnung.

In Listing 3 erkennt man im Methodenkopf folgende Neuerung : . args. Dieser durch Punkt abgetrennte Parameter steht für eine Liste in der weitere optionale Elemente zusammengefasst werden, vergleichbar der Ellipsis (den drei Punkten) in C.

Die Initialisierung der ersten Variablen balance erfolgt durch (if (not (null? args)) (car args) 1000)). Falls die args-Liste existiert, wird das erste Element der Liste als Anfangsbestand aufgefasst, andernfalls setzt man ihn auf 1000. Ähnlich wird auch der Zinssatz mit einem Wert initialisiert. Auf lokale Variablen hat man von außen keine Zugriffsmöglichkeit, man kann sie aber wie folgt “exportieren”:

(lambda (message)
      (case message
        ((name) (lambda () name))
        ((balance) (lambda () 
                     balance))
        ...

Es handelt sich um eine anonyme Funktion mit einem Parameter, die gleichzeitig Rückgabewert der Methode wird. Mit dem Parameter wird auf eine in der Fallunterscheidung definierte Methode zugegriffen. Lautet message beispielsweise \’name, dann wird folgende Funktion zurückgegeben: (lambda () name))). Da es sich um eine Funktion handelt, muss man sie aufrufen, um das eigentlich interessierende Ergebnis zu erhalten. Der Aufruf kann dabei auf verschiedene Weise erfolgen, entweder durch eine objektorientierte oder eine funktionale Vorgehensweise. Auf OOP-Art könnte das so aussehen:

(define (send fun message . args)
           (apply (fun message) args))

Die Funktion apply erwartet eine Funktion und eine Liste von Elementen, auf die diese Funktion angewandt wird. Wenn Sie etwa eine Addition ausführen wollen, können Sie entweder (+ 1 2 3) benutzen oder aber (apply + \'(1 2 3)). Senden wir die Nachricht \’name an account, erhalten wir die oben erwähnte parameterlose Funktion. Gehen wir von folgender Definition aus: (define acc1 (account “someone”)), lautet die Ersetzung für den Aufruf (send acc1 \’name); (apply (acc1 \’name) \'()). Bevorzugen Sie die funktionale Art des Aufrufs benutzen Sie: ((acc1 \’name)) (Bitte beachten Sie die Klammerung!)

Diese Art der Vorgehensweise kann die Basis für ein OO-System bilden. Wenn dieses System den Vorstellungen von objektorientierter Programmierung entsprechen soll, sind Makros, ein weiteres Scheme-Programmierwerkzeug sicher hilfreich.

(define (account name . args)
  (let ((name name)
        (balance (if (not (null? args)) (car args) 1000))
        (interest-rate 
         (if (and
              (not (null? args))
              (not (null? (cdr args)))) 
             (cadr args) 
             0.06)))
    (lambda (message)
      (case message
        ((name) (lambda () name))
        ((balance) (lambda () 
                     balance))
        ((deposit) (lambda (amount) 
                     (set! balance (+ balance amount))
                     balance))
        ((withdraw) (lambda (amount)
                      (set! balance (- balance amount))
                      balance))
        ((interest-rate) (lambda () 
                           interest-rate))
        ((add-interest) (lambda () 
                          (set! balance 
                               (* balance 
                                  (+ 1 interest-rate)))
                          balance))
        (else (lambda () "Method unknown"))))))
(define (send fun message . args)
  (apply (fun message) args))

Makros

Alle Lisps bieten Möglichkeiten, neue Daten- und Kontrollstrukturen (wie eine neue Fallunterscheidung, eine neue Schleife) zu definieren. In den meisten Schemes gibt es verschiedene Wege, Makros zu definieren. Sie werden hier die “alte” und die “R5RS” Art genannt. Im Beispiel handelt es sich um eine einseitige Fallunterscheidung.

Die “alte” Art

my-when Makro
(define-macro my-when
  (lambda (test . body)
  `(if ,test (begin ,@body))))

Sie sehen, wie einfach solche Erweiterungen in Scheme vorzunehmen sind. Makros werden mit define-macro eingeleitet, erhalten einen Namen ( my-when), erwarten Parameter (hier test . body und eine “passende ” Ersetzung ( `(if …) ). Betrachten wir die Ersetzung genauer:

Vor der Klammer des if befindet sich ein “Backtick” (umgekehrtes einfaches Hochkomma). Diesen Backtick kann man mit dem doppelten Hochkomma ( “ ) in der Shell-Programmierung vergleichen. Das schon bekannte einfache Hochkomma ( \’ ) hat hingegen bei Lisp eine ähnliche Funktion wie bei Shells. Während im ersten Fall bestimmte Zeichen eine Bedeutung erhalten (in Scheme sind das , und ,@, , bei der Shell das Dollarzeichen), ist im zweiten Fall diese Sonderbedeutung aufgehoben. (vgl. Backtick vs. normales Hochkomma)

Nach diesen Erklärungen ist es sicher Interessant, unser neu definiertes Kontrollflusselement in Aktion zu sehen:

(my-when 1 0) -> 0
(define foo 2) (my-when (< foo 3) 
                  "foo ist kleiner als 3")  
                        -> "foo ist kleiner als 3"

Unser Makro expandiert anscheinend wie gewünscht. Was man auch überprüfen kann. Sie müssen dazu aber mzscheme auf der Kommandozeile aufrufen, da diese Auswertung in der Scheme- Entwicklungsumgebung nicht funktioniert. Hier die Expandierung unseres my-when-Makros:

> (expand-defmacro '(my-when (< 1 2)"True"))  
     ->  (#%if (< 1 2) (#%begin "True"))

Die Integration von neuen und alten Elementen ist nahtlos. Es ergeben sich dadurch attraktive Anwendungsgebiete, wie z.B. Konfigurationsmöglichkeiten für Ihre Software, die Sie mit einer in Scheme eingebetteten Sprache konfigurierbar machen, ohne dabei auf die Vorteile einer vollständigen Programmiersprache verzichten zu müssen. Diese Vorteile sind bei Lisp inhärent, daher sollte einen der Erfolg des Emacs mit seinem Emacs-Lisp nicht wundern oder die Entscheidung der FSF, in allen ihren Anwendungen Guile, eine Scheme- Implementierung, als Skriptsprache einzusetzen.

(define al '(1 ,(+ 1 2) 3)) 
     -> (1 ,(+ 1 2) 3))
     (define a2 `(1 ,(+ 1 2) 3)) 
      -> (1 3 3)

Die “R5RS”-Art

Wenn Sie define-syntax mit Bekanntem vergleichen, können Sie vielleicht eine Analogie zur Fallunterscheidung feststellen. Mit define-syntax my-when-new wird dem Makro ein Name gegeben ( my-when-new ).

my-when-new Makro
(define-syntax my-when-new
  (syntax-rules ()
    ((my-when-new test body ... ) 
     (if test (begin body ...)))))

Nach syntax-rules folgt eine Reihe von Mustern, in denen das Makro auftreten kann. In unserem Fall besteht nur eine Möglichkeit: (my-when …) . Dieses Muster verlangt zunächst den Namen des Makros, dann einen Test test und anschließend etwas wie body … . Die … stehen für beliebig viele weitere Ausdrücke.

Sollte nun ein my-when-new in der geforderten Form gefunden werden, wird die nachfolgende Transformation ( (if test (… vorgenommen, in der Ersetzung werden keine speziellen Expandierungszeichen benötigt. Die Namen der in der Schablone auftauchenden Variablen, werden “automatisch” zugeordnet.

Wie die Schablonen aussehen müssen, entnehmen Sie bitte dem R5RS-Report, den Sie in DrScheme unter den Manuals finden können. Gehen Sie dazu auf den Menüpunkt Help Helpdesk und wählen dort Help Desk Manuals Revised(5) … aus. Hier ein weiteres Beispiel (aus dem Report):

my-and Makro
(define-syntax my-and
  (syntax-rules ()
    ((my-and) #t)
    ((my-and test) test)
    ((my-and test1 test2 ...) 
        (if test1 (my-and test2 ...) #f))))

Das ist doch ziemlich beeindruckend. Sie haben ein wie in C arbeitendes and in nur sechs Zeilen Scheme implementiert. Interessant ist hauptsächlich das letzte Muster, in dem mehrere Tests an my-and übergeben werden. Es handelt sich dabei um eine rekursive Makroexpansion, d.h. dieses Makro wird solange expandiert, bis es kein weiteres Makro mehr enthält. Sobald sich bei der expandierten Form ein Wahrheitswert von “falsch” ergibt wird #f zurückgegeben.

Ein umfangreicheres Beispiel

Es soll nun ansatzweise gezeigt werden, wie man in Scheme Strukturen definieren könnte. Dabei soll der Zugriff nur über Zugriffsfunktionen erfolgen. Der Gebrauch wird so aussehen: (define-my-record name Felder) . Es wird dann eine Erzeugungsmethode make-name angelegt, sowie Methoden um auf die verschiedenen Felder lesend und schreibend zuzugreifen. Die Methoden zum Lesen werden dabei mit get- eingeleitet, die zum Schreiben mit set- .

Betrachten wir dazu unser Beispiel über die Datenkapselung in Scheme. Mit den geplanten Erweiterungen ergibt sich eine Teilautomatisierung.

(define-my-record account (name balance interest-rate))
     (let (( me (make-account ("Friedrich" 1000 0.06))))
       ((me 'get-name)) -> "Friedrich"
       (send me 'get-balance) -> 1000
       ((me 'set-balance 2000))) -> 2000

Für diese Erweiterungen kombiniert man Makros mit Funktionen. Als Beispiel die Methode für die Generierung der lesenden Zugriffe

(define (create-getter-clauses slots)
  (define (create-getter slot)
    `((,(prepend-string "get-" slot))
      (lambda () ,slot)))
  (map create-getter slots))

Sie sehen, wie die verschiedenen Scheme-Elemente zusammengefügt werden. Es wird eine interne Funktion definiert, diese in einer g). Die Ausgabe des Aufrufs der create-getter-clauses entspricht genau der im case benötigten Form. Die Zugriffsmethode wird abhängig vom Namen generiert. Wenn Sie also name in define-my-record benutzen, wird mit prepend-string “get-“name das Symbol get-name generiert. Da dies für alle Feldnamen erfolgen soll, wenden Sie die innere Methode auf alle übergebenen Elemente an ( map ). Durch den Aufruf der Funktion haben Sie dynamisch Scheme Code erzeugt!

“Eingebaut” wird dieser Code in folgendes Makro:

(define-macro define-my-record
 (lambda (name slots)
  `(define (,(make-new-record-name name)
              ,@slots)
       (lambda (message)
         (case message
        ,@(create-getter-clauses slots)
        ,@(create-setter-clauses slots)
    (else (error "Method unknown")))))))

Das Makro define-my-record erwartet einen Namen, eine Liste von Elementen ( slots ), generiert eine Erzeugungsmethode aus dem ersten Parameter, sowie aus allen Namen Elementen in slots , jeweils eine “get-” und “set-” Methode.

Im Beispiel können alle Elemente abgefragt und verändert werden. Mit etwas mehr Programmieraufwand können Sie Variablen nur zum Lesen, Typ-tests, weitere Methoden und sogar Vererbung (vergl. [7], Kapitel 11.3, S. 266) hinzufügen.

Zusammenfassung

Dieser Teil zeigte, wie wichtig Funktionen in Scheme sind und wie einfach sie eingesetzt werden können. Dies baut einerseits die Scheu ab, Funktionen als Parameter zu gebrauchen oder als Rückgabewert zu nutzen. Andererseits müssen Sie die in anderen Sprachen gewohnte Trennung von Datenstrukturen und Funktionen als hinfällig betrachten, um Lisps vorteilhaft einsetzen zu können. Diese Umstellung kann nur durch längere Beschäftigung mit funktionalen Sprachen erfolgen.

Bemerkenswert an Scheme ist sicher auch die Generierung von Code durch Makros. Es zeigt, wie eine minimalistische Sprache mit (Achtung: Modewort-Alarm) orthogonalen Programmierelementen, eine enorme Flexibilität ermöglicht.

Ausblick

Im nächsten Artikel werde ich auf Standard-Scheme sowie nützliche Bibliotheken eingehen, sowie einige “Spezialitäten” der verschiedenen Schemes vorstellen.

Wie immer würde ich mich über Kommentare, Anregungen, Kritik freuen. Sie können mich unter frido@q-software-solutions.com erreichen. Oder Sie besuchen einfach mal die Scheme/Lisp- Newsgruppen. (uwo)

Copyright © 2002 Linux New Media AG