Open Source im professionellen Einsatz
Linux-Magazin 01/2001

Weiterführende Elemente der Scheme-Programmierung

Funktioneller gehts nicht

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.

655

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 ).

apply-to-all

(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.

Listing 1: Zwei
sehr ähnliche Funktionen (double-all, all-two)

(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)))))

Listing 2:
Implementierung von filter

(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.

Linux-Magazin kaufen

Einzelne Ausgabe
 
Abonnements
 
TABLET & SMARTPHONE APPS
Bald erhältlich
Get it on Google Play

Deutschland

Ähnliche Artikel

  • Standards? Standards!

    Der Scheme-Standard hat einen recht kleinen Umfang, also greifen Programmierer für größere Projekte zwangsläufig auf Erweiterungen zurück. Im Zentrum dieses Artikels stehen daher Standard-Scheme und seine Erweiterungen.

  • Wir können auch anders

    Bisher vorgestellte Programme waren in funktionaler Weise implementiert. Schemes Stärken liegen zwar hauptsächlich in diesem Bereich, jedoch gibt es auch die Möglichkeit, objektorientiert vorzugehen.

  • Wechsel auf der Brücke

    Scripting funktioniert nicht nur bei den üblichen Verdächtigen wie Bash, Korn-Shell und Python, sondern auch mit Scheme. Im Zentrum des Artikels stehen darum die Shell-Programmierung mit Scheme sowie die Programmierung fürs Internet.

  • Web-Wunder

    Mit Scheme setzt das freie Web-Framework Hop eine ziemlich esoterische Programmiersprache ein. Seine Architektur und Flexibilität machen es jedoch zu einer spannenden Alternative zu Django & Co.

  • Groß in Mode

    Die Anpassung an spezielle Dateiformate führt beim Editor-Urgestein Emacs über so genannten Major Modes in der Programmiersprache Elisp. Dieser Workshop demonstriert die Technik am Beispiel eines Mode zum Schreiben von Manuskripten für das Linux-Magazin.

comments powered by Disqus

Stellenmarkt

Artikelserien und interessante Workshops aus dem Magazin können Sie hier als Bundle erwerben.