Nicht-numerische Daten
Einführung in die Programmierung

• Symbole sind eine einfache Möglichkeit für die Repräsentation nicht-numerischer Daten.
• Symbole sind aufgebaut wie Variablennamen; damit sie nicht als solche interpretiert werden, ist ein Hochkomma voranzustellen.

• Beispiele:

  'symbol 'KarlMarx 'Dies-ist-auch-ein-Symbol 'x1
  

• Symbole dürfen Buchstaben, Ziffern und ein paar Sonderzeichen (keine Leerzeichen!) enthalten.
• Symbole sind – wie Zahlen – atomare Daten.
• Symbole werden – wie Zahlen – zu sich selbst ausgewertet.

• Einzige Operation auf symbolischen Atomen ist die Prüfung auf Gleichheit: equal? erwartet zwei Symbole als Argumente und liefert #true dann und nur dann, wenn sie identisch sind:

    (equal? 'Hallo 'Hallo) ;;=> #true 
    (equal? 'Karl 'Rosa)   ;;=> #false
    (equal? 'Hallo hallo)  ;;=> #true, wenn hallo für 'Hallo steht
  

• Symbolische Ausdrücke (kurz: S-Ausdrücke) wurden erfunden von McCarthy für LISP.
• Definition: (vorläufig)
  Ein S-Ausdruck ist
  • ein Atom, z.B. 27, ’Karl, ’ist

  • eine Folge von S-Ausdrücken, eingeschlossen in (), z.B.

    • ’(Karl ist 27),
    • ’((Dies ist) (eine Liste) (mit 3 Elementen))

    Solche S-Ausdrücke heißen Listen. (Man beachte die Rekursivität dieser Definition!)

• Atome sind entweder numerisch, boolesch oder symbolisch

• Für einen Gebrauchtwagenhändler repräsentieren wir die Menge der im Angebot befindlichen Automarken in einer Liste von Symbolen, z.B. so:

  (’VW ’Opel ’Toyota)
  

• Listen können beliebig lang werden (vgl. Definition des S-Ausdrucks). Eine Liste-von-Symbolen (lvs) kann als Datenstruktur wie folgt rekursiv definiert werden:
  • Eine Liste-von-Symbolen ist entweder
    1. die leere Liste: empty oder
    2. (cons s lvs) , wobei s ein Symbol und lvs eine Liste-von-Symbolen ist
• Bei Listen handelt es sich also um gemischte Daten:
  • Die leere Liste empty kann mit dem Prädikat empty? , die nicht-leere Liste mit dem Prädikat cons? erkannt werden.

• Es soll geprüft werden können, ob in der Liste mit den Automarken ’BMW vorkommt.

• Gemäß unserer bisherigen Regeln schreiben wir die Zweckbestimmung und einen passenden Funktionskopf auf:

     ;; ermittelt, ob das Symbol 'BMW in der liste-von-symbolen auftritt
     (define enthaelt-bmw?
       (lambda [lvs] ...))
  

Regel 10: Von nun an schreiben wir vor jeden Funktionskopf einen Vertrag als Kommentar.

• Der Vertrag beschreibt, welche Arten von Daten (Datentypen) die Funktion als Argumente erwartet und welche Datenart die Funktion als Resultat liefert:

  <Typ von Argument 1> ... <Typ von Argument n> -> <Typ des Resultats>
  

• Für unser Beispiel enthaelt-bmw? lautet der Vertrag

  ;; enthaelt-bmw? : (list-of symbol) -> boolean
  

• Den Vertrag fügen wir hinter die Zweckbestimmung ein:

     ;; ermittelt, ob das Symbol 'BMW in der liste-von-symbolen auftritt
     ;; enthaelt-bmw? : (list-of symbol) -> boolean 
     (define enthaelt-bmw?
       (lambda [lvs] ...))
  

• Nun definieren wir eine Funktionsschablone gemäß Regel 9 (für die Verarbeitung gemischter Daten), die der Struktur der Datendefinition Liste-von-Symbolen folgt.

• Da diese zwei Fälle, die leere und die nicht-leere Liste, unterscheidet, ergibt sich folgende Schablone:

         (define f
            (lambda [lvs]
               (cond [(empty? lvs) ...]
                     [(cons? lvs)  ...])))
  

• Eine nicht-leere Liste ist eine aus zwei Komponenten zusammengesetzte Datenstruktur:

  1. dem ersten Element
  2. der Restliste (ohne das erste Element)
     

  Dem Prinzip von Regel 8 (für strukturverarbeitende Funktionen) folgend ergänzen wir die Schablone nun um die Aufrufe der Selektionsfunktionen für diese beiden Komponenten.

• Aus diesen Überlegungen ergibt sich folgende Schablone:

     (define f
       (lambda [lvs]
         (cond 
           [(empty? lvs) ...]
           [(cons? lvs)  ... (first lvs) 
                         ... (rest lvs) ...])))
  

• Die Auslassungszeichen sind dann entsprechend der Zweckbestimmung auszufüllen, d. h. die Lösung muss aus den Zugriffen auf das erste Element und die Restliste geeignet kombiniert werden.
• Kehren wir dazu zu unserem Beispiel zurück.

• Die Schablone angewendet auf enthaelt-bmw?, wobei die Lösung für den Fall der leeren Liste bereits eingetragen ist:

     (define enthaelt-bmw?
            ;;;;;;;;;;;;;;
       (lambda [lvs]
         (cond 
           [(empty? lvs) #false]
                         ;;;;;;
           [(cons? lvs) ... (first lvs) 
                        ... (rest lvs) ...])))
  

• Nun betrachten wir die Komponenten der nicht-leeren Liste. Falls das erste Element das gesuchte ist, muss die Funktion #true liefern:

     (define enthaelt-bmw?
       (lambda [lvs]
         (cond 
           [(empty? lvs) #false]
           [(cons? lvs) 
              (cond [(equal? (first lvs) 'BMW) #true]
                     ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
                    [else ... (rest lvs) ...])])))
  

• Falls das gesuchte Symbol nicht das erste in der Liste ist, hängt das Ergebnis der Funktion davon ab, ob es in der Restliste gefunden wird. Da die Restliste ja selbst wieder eine Liste-von-Symbolen ist, ist auf sie die Funktion enthaelt-bmw? anwendbar:

     (define enthaelt-bmw?
       (lambda [lvs]
         (cond 
           [(empty? lvs) #false]
           [(cons? lvs) 
                   (cond [(equal? (first lvs) 'BMW) #true]
                         [else (enthaelt-bmw? (rest lvs))])])))
  

• Damit ist die Funktion vollständig. (Zu finden unter enthaelt-bmw.rkt in moodle)

• Die Funktion enthaelt-bmw? wurde unter Verwendung der Regeln 8 und 9 (ergänzt um Regel 10) entwickelt.
• Falls man in der Analyse der zu verarbeitenden Daten feststellt, dass die Benutzung einer Liste (mit beliebig vielen Elementen) angemessen ist, wird diese zunächst präzise als rekursive Datenstruktur definiert.
• Die Definition einer rekursiven Datenstruktur erfolgt durch Aufschreiben von mindestens zwei Sätzen, wobei mindestens einer einen Rückbezug auf die Definition und mindestens einer keinen Rückbezug auf die Definition aufweist.

• Betrachten wir dazu noch einmal die Definition der Liste von Symbolen:

• Der Pfeil verdeutlicht den Selbstbezug der Definition.

• Die Funktionsschablone wird als bedingte Funktion aufgeschrieben, die für jeden Satz der Definition der rekursiven Datenstruktur eine Frage-Antwort-Kombination enthält.
• Dabei könnte für jede Frage, die eine dem Parameter der Funktion gleichartige Datenstruktur selektiert, ein Pfeil auf den Funktionsnamen gezeichnet werden.
• Man erhält dann eine Funktionsschablone, die zur rekursiven Definition der Datenstruktur so zu sagen isomorph ist:

Anmerkung: Der bisher verwendete Aufruf (cons? lvs) ist hier (und im Folgenden) durch else ersetzt.

• Dieser Rückwärtspfeil wird durch eine rekursive Anwendung der Funktion ersetzt.

• Damit ergibt sich für das Beispiel der Verarbeitung beliebig langer Listen von Symbolen die folgende Funktionsschablone:

     (define listen-funktion
       (lambda [lvs]
         (cond 
           [(empty? lvs) ...]
           [else ... (first lvs) ... 
                 ... (listen-funktion (rest lvs)) ...])))
                      ;;;;;;;;;;;;;;;    
  

• Wir sprechen hier von natürlicher Rekursion.

• Die Entwicklung des Funktionsrumpfs beginnt mit den Frage-Antwort-Kombinationen, die keine rekursiven Aufrufe enthalten.
  • Die Antwort ist in der Regel einfach.
  • Sie sollte in den Tests bereits vorkommen.
• Für die rekursiven Fälle ist zunächst vorauszusetzen, dass die rekursive Anwendung der Funktion auf die Restliste bereits das gewünschte Ergebnis liefert.
• Dieses ist mit dem Ergebnis für das erste Element der Liste geeignet (problemabhängig) zu kombinieren.
  • Dieser Schritt besteht in dem Beispiel enthaelt-BMW? in einer weiteren Fallunterscheidung.

Regel 11:

Schreibe eine präzise Datendefinition für die zu verarbeitende rekursive Datenstruktur auf. Folge dabei dem im Abschnitt Datendefinition angegebenen Muster.

Regel 12:

Formuliere mindestens einen Test für den Fall, dass die rekursive Datenstruktur

• keine Elemente,
• genau ein Element,
• mehr als ein Element

enthält!

Regel 13 (Funktionsschablone)

• Entwickele eine Funktionsschablone, die der rekursiven Struktur der Daten folgt.
• Dazu
  • Schreibe das Skelett eines cond-Ausdrucks auf mit je einer Frage-Antwort-Klausel für jeden nicht-rekursiven und jeden rekursiven Fall!
  • Notiere dabei für die rekursiven Fälle die passenden Selektionsausdrücke ((first ...), (rest ...)).
  • Dabei ist zu beachten, dass auf den Ausdruck (rest ...) die zu entwickelnde Funktion rekursiv anzuwenden ist.

• Anwendung der Regeln für die Entwicklung rekursiver Funktionen auf Funktionen, die eine Liste als Resultat liefern.
• Dem Gebrauchtwagenhändler soll eine Funktion zur Verfügung gestellt werden, mit dem er ein Modell aus seiner Angebotspalette entfernen kann.

• Anhand eines weiteren Beispiels soll die Anwendung der Regeln für die Entwicklung rekursiver Funktionen demonstriert werden.
• Während des Entwurfsprozesses kann es sich als zweckmäßig erweisen, für die Lösung bestimmter Teilprobleme eigene Funktionen (Hilfsfunktionen) vorzusehen.
• Dabei ist es hilfreich, diese Hilfsfunktionen als bereits existent vorauszusetzen, um zunächst mit ihrer Hilfe die Lösung des Hauptproblems formulieren zu können.

• Diese Vorgehensweise wird

  • Top-down-Entwurf oder auch
  • schrittweise Verfeinerung

  bezeichnet.

Fall 1

Die bekannten Regeln (insbesondere was die Funktionsschablone anbelangt) können wie bisher angewendet, weil das zweite Argument nicht zerlegt werden muss. Beispiel: append (concatenate)

Fall 2

Da beide Listen gleich lang sind, genügt es eine von beiden auf Leersein zu prüfen. Für die Ermittlung des Resultats ist aber der Zugriff auf das erste Element und die Restliste von beiden Argumentlisten notwendig. Das führt zur folgenden angepassten Funktionsschablone: