3.1 Grundprinzipien und Ideen der Funktionalen Programmierung
Wir werten Funktionen aus, dabei kommen wir
in den Berechnungen ohne Variablen aus.
Hierfür verwendet man symbolische Ausdrücke, die mit anderen Daten in Listenstrukturen
abgelegt werden.
Funktionen können kombiniert werden, um zusammengesetzte
komplexere Funktionen zu erzeugen.
Mittel zur Abstraktion: Benennung der zusammengesetzten
Elemente und dessen Handling.
Elementare Ausdrücke sind enfachste Einheiten der Sprache.
Objekte, Zustände und Nebeneffekte bleiben
aus.
Die Auswertung (Evaluation) ist die Berechnung
des Werts eines Ausdrucks.
Die Auswertung ist rekursiv, wenn auf einen ihrer Schritte die Regel
selbst angewendet wird.
Schachtelung mit Klammern z.B. ( ( ) ).
Eine Kombination ist in Klammern z.B. ( a
b c).
Generalisierte Variablen sind Werte von Selektoren (z.b. car) oder
Werte von Zugriffsfunktionen.
Substituierbarkeit
Eine Variable durch ihre Definition in einem
Ausdruck ersetzen. Dieses Abstraktionsmittel setzt wir ein,
um Eigenschaften bestimmter Funktionen nachzuweisen. Damit
können wir eine sehr einfache Spezifikationen
in eine effiziente Implementierung
transformieren.
Das Substitutionsmodell verwendet eine lokale Umgebung mit formalen
Parametern.
Kombinationen werden zuerst nach ihren Teilausdrücken
ausgewertet.
3.2 Vergleich funktionaler Programmiersprachen
| HASKELL: |
beherrscht die "verzörgerte Auswertung" (= Lazy Evaluation), die der normalen
Auswertung entspricht, .dh. jeder (Teil-)Ausdruck
wird erst berechnet wenn sein Wert zum Gesamtergebnis
benötigt wird.
|
| ML: |
starke und polymorphe Typsysteme, Funktionsdefinition
über pattern matching.
|
| SCHEME: |
wertet applikativ aus und hat statische Gültigkeitsbereiche.
Daten, Prozeduren und Programmcode werden
gleich behandelt (Äquivalenz), weil sie den selben
Namensraum haben und auf der selben Art und
Weise angesprochen werden (referenziert).
Die Typisierung erfolgt dynamisch.
call-by-value Parameterübergabe (gegensätzlich zur verzörgerten Auswertung
in Haskell)
Jeder Ausdruck hat einen Wert. Es gibt nur
zwei Arten von Ausdrücken: Atome und Listen.
Auswertung: Zuerst werden die Argumente ausgewertet,
dann die Funktionen.
Hinweis: Scheme verfügt nicht über "pattern
matching"!
|
| Kellerspeicher (Stapel) |
Implementierung |
|
|
| Datum auf dem Keller "oben" speichern:
|
(push datum keller) |
| Liefert und entfernt oberstes Datum: |
(pop keller) |
| Abfrage: ist der Keller leer? |
(empty? keller) |
| oberstes Datum wählen, Keller bleibt unverändert: |
(top keller) |
| liefert die Anzahl der Elemente im Keller: |
(size keller) |
| zeigt alle Elemente nacheinander an: |
(print keller) |
| Warteschlange (Queue) |
Implementierung |
|
|
| fügt das Datum am Ende der Warteschlange
an: |
(enqueue! datum queue) |
| liefert und entfernt das erste Element: |
(dequeue! queue) |
| testet ob die Schlange leer ist: |
(empty? queue) |
| wählt das Element am Kopfende der Schlange
aus: |
(front queue) |
| liefert die Anzahl der Elemente in der Schlange: |
(size queue) |
| zeigt alle Elemente der Schlange nacheinander
an: |
(print queue) |
Implementierungstipps zu den Warteschlangen:
Üblicherweise verwendet man lineare Listen.
Werden die Warteschlangen aber lang, so ist
es ratsam, neben
dem Zeiger auf den Kopf der Liste noch einen
zweiten Zeiger auf das Schwanzende zu benutzen.
3.3 Auswertung von Kombinationen
Erzeugung Name-Objekt-Zuordnung in aufeinanderfolgender Interaktion:
(define Variable < zugewiesener
Wert der
Variable := Objekt > )
- Teilausdrücke auswerten
- von links nach rechts Argumente auswerten. Operatoren sind selbst
zusammengesetzte Ausrücke.
Kombinationen als Baum darstellen
- Eine einzige Kombination entspricht einem
Knoten
- die Blätter sind die Operanden und die
Operationen
- Auswertung vom Endknoten ausgehen und dann
auf einer höhere Ebene im Baum kombinieren
- Baumakkumulation
3.4 Wichtige Funktionen und Kommandos in
Scheme
(u.a. auch Lisp)
Hinweis: In den Beispielen steht das
Symbol
"<" für den Prompt (die
Eingabezeile)
| Symbolname |
Aufgabe |
Beispiel |
let |
definiert lokale (Hilfs-)Variablen und öffnet einen eigenen Gültigkeitsbereich.
praktisch bei mehfacher Verwendung eine Wertes.Sein
ganzer Rumpf wird ausgewert und der letzte
Ausdruck wird zurückgegeben.
Es sind keine Bedingungen auf
Ausdrücken
sichtbar, die an Variablen gebunden
werden
können.
|
(let ((x (+ a b)))
hier: der Wert der Summe x=a+b |
| let* |
die sequentielle Variante von let
nur die Bindungen "darüber"
sind
sichbar |
|
| letrc |
Hilfsprozeduren lassen sich lokal definieren,
weil alle Bindungen auf der rechten Seiten
sichtbar sind. |
|
| print |
druckt sein Argument (unter Nebenwirkungen)
aus und gibt es anschliessend zurück |
|
| quote |
Quote gibt sein Argument zurück.
Die Kurznotation für (quote <ausdruck>)
ist '<ausdruck>
|
> (quote x)
> 'x
x |
| set! |
weist einer Variablen einen Wert zu
|
(set! a (read))
a bekommt den Wert der Eingabe |
| setf |
ändert den Wert der Variablen (oder Teile
davon) |
|
| setq |
weist einem Symbol ein Wert zu
Beispiel ein binärer Baum als
geschachtelte
Liste
(setq *binbaum* 7 (9 (5 ( ( ) ( ) ) (22 (
) ( ) ) (4 (18 ( ) ( ) ) ( ) ))), wobei "(
)" leere Unterbäume sind.
|
|
3.5 Datentypen
Symbole
Ein Symbol evaluiert zu seinem Wert und es kann in Ausdrücken vorkommen. Steht
das Symbol an erster Stelle im Ausdruck,
dann könnte es als Funktionsnamen interpretiert
werden.
Liste
Die Elemente einer Liste sind beliebige Lisp-Objekte
Die Leere Liste ( ) wird mit NIL bezeichnet.
Sie evaluiert zu sich selbst.
| Symbolname |
Aufgabe |
Beispiele |
| car |
Content of Adressregister |
|
| cdr |
entspricht dem Zeiger links. Er zeigt nur
auf einzelne ElementeContent of Deviceregister |
|
| cons |
fügt vorne in die bestehende Liste ein Element
ein.
- benötigt eine neue Speicherzelle
(im Heap). |
> cons(l atom)
(l . atom)
> cons(l NIL)
|
| first |
gibt das erste Listenelement zurück |
|
| rest |
gibt die ganze Liste |
|
*Diese Schlüsselwörter kommen in Common Lisp
vor (aber nicht in Scheme).
Wir können auch car und cdr zu einem
Befehl
zusammenfassen:
car(cdr <ausdruck>) = cadr<ausdruck>
cdr(cdr <ausdruck>) = cddr<ausdruck>
Achtung: "cons( 5 '( ) )" ist nicht
das selbe wie "cons( '( ) 5)"
Besonderheiten in der Listenverarbeitung
| kopierend |
destruktiv |
mutierend |
Argumente bleiben unverändert
append: hängt zwei Listen aneinander
und
legt eine neue Liste an.
Aufwand: Zeit und Platz: Länge
der ersten
Liste. |
Argumente werden zerstört
set-cdr!
|
Objekte werden (absichtlich) geändert
setf |
3.6 Definiton von Funktionen und Prozeduren
Mit defun wird eine Funktion in Common LISP definiert.
Dahinter folgt der Name der Funktion, die
Parameterliste und schliesslich der Rumpf
der Fuktion, in dem die Ausdrücke stehen.
Anschaulich:
| (defun |
<name> |
<parameterliste> |
<ausdruck>* ) |
Funktions-
definiton |
kennzeichnet die Funktionaliät durch eine
eindeutige Namensgebung.
Beispiel: (defun quadrat (x)), "quadrat"
steht hier für eine quadratische Funktion |
legt die Paramter fest |
Beim Aufruf wird der Rumpf der Funktion ausgeführt.
Der Wert des letzten Ausdrucks wird zurückgegeben.
Die Ausdrücke dürfen die Parameter
verwenden. |
Die Präfixnotation für Funktionen verhindert Mehrdeutigkeiten
und eine Verschachtelung der Kombinationen.
#'funcall: syntaktische Funktionshervorhebung, der
Datentyp ist eine Fuktion.
exact: integer, ration und komplexe
Zahlen
inexact: floats und komplexe Zahlen
mit Gleitkomma
bignum: lange Zahlen
fixnum: Festkommazahl (feste Länge)
ratio: zwei automatisch verkürzte Integerwerte
(rational)
Eine annonyme Funktion erzeugen:
(lambda (x) (* x x)) ;; Eine Funktion die
ihr Argument quadratiert.
Mit define wird eine Prozedur definiert (in Scheme
auch eine Funktion). Diese Definition erzeugt
während dem Auswerten eine zusammengesetzte Prozedur. Die Prozedur wird mit ihrem Namen verknüpft.
Anschaulich:
| (define |
<Prozedurname> |
<formale
Parameter> |
<Prozedurrumpf = ausdruck>* ) |
| Defintion |
Der Name ist ein Symbol |
- benutze Namen innerhalb des Rumpfes
- werden durch aktuelle Argumente
beim Aufruf
ersetzt |
Der Rumpf wird ausgewertet nachdem jeder
formale Parameter durch das entsprechende
Argument ersetzt wurde. |
Wie kann man sich die Abstraktionstechnik von zuammengesetzten
Prozeduren vorstellen ?
| (define |
(quadrat |
x) |
(* |
x |
x)) |
| Zum |
quadrieren |
von etwas, |
multipliziere |
es |
mit sich selbst |
3.7 "Gleich" - nicht immer das
selbe?
| equal? |
eqv? (für Elementartypen) |
eq? (für zusammengesetzte Typen) |
gleichaussehend
von der selben Struktur
Aufwand: Zeit:
Atomzahl der Argumente |
identisch
selbes Objekt (=in der selben Speicherzelle)
Pointergleichheit
(eqv? (cons 1 2) (cons 1 2)) liefert false, weil
cons zwei verschiedene Zellen anlegt. |
nackte Pointergleichheit
|
3.8 Kontrollstrukturen
Bedingungen werden von links bis zum wahren Ausdruck bei OR und bis zum falschen Ausdruck bei AND ausgewertet. Es wird der wahre Ausdruck zurückgegeben (sonst NIL) oder der letzte Ausdruck bei der ersten falschen Bedinung unter AND
(sonst NIL).
| cond |
if |
cond (Bedingung) (Anweisung)* )
Anweisung des ersten erfüllten Zweigs ausführen
und anschliessend zurückgeben. |
IF(Bedingung)(then-Zweig)[(else-Zweig)] |
4.1 Rekursion
Kennzeichen für die Rekursion in Scheme:
- Kette von verzörgerten Operation
sammeln
sich im Stack
- Interpreter merkt sich die Operation,
um
sie später ausführen zu können.
Beispiel: Cons-Operationen werden aufbewahrt
bis die Rekursion terminiert.
Allgemeines zur Rekursion in funktionalen
Sprachen:
Man muss unterscheiden zwischen "rekursiven Prozeduren" und "rekursiven Prozessen".
Rekursive Prozeduren sind Teile eines
Programms,
geschrieben in einer bestimmten
Programmiersprache, die sich selbst
direkt
oder indirekt aufrufen. Die Betrachtung
erfolgt
dabei statisch (zur "Compile-Zeit").
Rekursive Prozesse sind die durch ein
Programm
bzw. einen Programmteil beschriebenen
Operationen auf einer abstrakten Maschine (ohne Beschränkung durch Speicherplatz oder
Zeit).
Die Betrachtung erfolgt dabei zur Laufzeit.
Welcher Prozess sich aus einer Prozedur
ergibt,
hängt eventuell vom Compiler bzw. Interpreter
ab.
Bei rekursive Prozeduren kann man unterscheiden
zwischen:
direkte und indirekte Rekursion
- Bei "direkter Rekursion" ruft eine Prozedur sich selbst auf
und wird nur durch sich selbst aufgerufen.
- Bei "indirekter Rekursion" ruft eine Prozedur a eine Prozedur
b auf, die wiederum
(eventüll indirekt) Prozedur a aufruft.
lineare, nicht-lineare und geschachtelte
Rekursion
- Bei "linearer Rekursion" ruft
die Prozedur bei jedem denkbaren Durchlauf
(Abarbeitungsweg)
maximal eine linear rekursive Prozedur
auf
(und keine nicht linear rekursiven
Prozeduren).
Hinweis: Es können durchaus mehrere
rekursive
Aufrufe vorhanden sein, wenn diese
in
unterschiedlichen Zweigen einer Fallunterscheidung
stehen.
- Bei "nicht-linearer Rekursion"
(auch "Baumrekursion" oder "kaskadenartige Rekursion" genannt)
gibt es in einem denkbaren Durchlauf
mehrere
Aufrufe einer oder mehrerer rekursiver
Prozeduren.
Wenn dabei ein rekursiver Aufruf
das Argument
eines anderen rekursiven Aufrufs
ist, spricht
man
von "geschachtelter Rekursion".
Endaufruf und Endrekursion
- Als "Endaufruf" wird ein Prozeduraufuf
bezeichnet, bei dem eine Prozedur das Ergebnis einer anderen
Prozedur ohne weitere Verarbeitung zurückliefert, die aufgerufene Prozedur
also die letzte
Anweisung der aufrufenden Prozedur darstellt.
Eine linear rekursive Prozedur, bei der alle rekursiven
Aufrufe Endaufrufe sind, wird als "endrekursive Prozedur" (tail recursive procedure)
bezeichnet.
Diese Begriffe übertragen sich auf
Prozesse,
indem der konkrete Abauf betrachtet
wird.
Dabei ist es
nicht immer einfach, anhand der Prozedur
zu entscheiden, was für eine Art
von Prozess
erzeugt wird.
Beispiel:
(define (dec x)
(- x 1))
(define (g x)
(cond ((zero? x) 1)
((test? x) (h x x))
(else (g (dec x))) ))
(define (h u v)
(+ (g (dec u)) (g (dec v))) )
Wenn die Prozedur test? immer den
Wert #f
liefert, handelt es sich beim Prozess
der
Prozedur g um
einen (linearen) endrekursiven Prozess.
Wenn
test? mindestens einmal den Wert
#t liefert,
handelt es
sich um einen indirekten nicht-linear
rekursiven
Prozess.
Nicht jedem endrekursiven Prozess liegt also
eine endrekursiven Prozedur zugrunde.
Andererseits
führt
aber jede endrekursive Prozedur zu einem
endrekursiven Prozess.
iterative Prozeduren (oder Programmabschnitte)
- Bei diesen wird ihr Zustand durch eine
feste, von der Eingabe unabhängige Anzahl
von Zustandsvariablen
beschrieben (konstanter Platzbedarf).
Die
Schleifenkonstrukte (z.B. "do" in Scheme oder "while"
in Java)
erzeugen solche Programmabschnitte.
- Entsprechend gibt es auch iterative Prozesse.
Scheme realisiert Endaufrufe grundsätzlich
durch eine
iterative Abarbeitung (technisch
gesprochen:
die Ausführung der aufgerufenen Prozedur
wird durch
einen Sprung fortgesetzt, ohne dass
dabei
auf dem Stack ein neuer Frame erzeugt
wird),
wodurch
endrekursive Prozeduren als iterative
Prozesse
besonders effizient abgearbeitet
werden.
Achtung: Das ein Prozess linear rekursiv
ist, bedeutet nicht, dass seine Zeitkomplexität
linear ist.
Es ist noch nicht einmal sicher gestellt,
dass der Prozess überhaupt terminiert.
Es gilt jedoch: Die Speicher-Komplexität
linear rekursiver, nicht iterativer
Prozesse
ist linear.
Zufammenfassung:
| linear rekursiv |
linear iterativ |
endrekursiv |
- Kette verzörgerter Operationen nimmt linear
zu
- Informationen müssen mitgeführt werden
|
- beschreibar mit fester Zustandszahl/-variablen
- Anzahl der Rechenschritte nimmt
linear
mit n zu
-konstanter Speicherbedarf
|
- ein iterativer Prozeß der durch eine rekursive
Prozeudur beschieben |
|
VZ | © 2005 Mathlab.de | Impressum