Deklarative Programmierung - Mündliche PDF

Preview

Summary

Das war meine Zusammenfassung für die mündliche Nachholklausur. Hier sind die wichtigsten Fragen und Antworten aufgelistet, was mich gut auf die Prüfung vorbereitet hat....

Description

Allgemein: Unterschied zwischen funktionaler (Scheme) und logischer (Prolog) Programmierung: Funktionale Programmierung (Scheme)  orientiert am mathematischen Funktionsbegriff  Programme sind (Systeme von) Funktionsdefinitionen  Berechnung: Reduktion von Funktionsanwendungen auf Normalform Die Aufgabenstellung und die bekannten Prämissen werden hier als funktionaler Ausdruck formuliert. Das selbstständige Anwenden von Funktionsersetzung und Auswertung seitens des Interpreters oder Compilers lösen dann die Aufgabenstellung. Das Programm kann als Abbildung der Eingabe auf die Ausgabe aufgefasst werden. Logische Programmierung (Prolog)  orientiert am Begriff der logischen Konsequenz  Programme sind (Systeme von) elementaren und bedingten Aussagen (log. Datenbanken) 

Berechnung: Auswertung von Anfragen an diese Datenbank Die Aufgabenstellung und ihre Prämissen werden als logische Aussagen (Regeln) formuliert (vgl. funktionale Programmierung, s. o.). Der Interpreter versucht dann, die gewünschte Lösungsaussage herzuleiten. Bei anderen regelbasierten Sprachen wie Prolog werden Regeln gegen eine Datenmenge auf ihre Instanziierbarkeit geprüft. Aus allen Regelinstanziierungen wird eine (mehrere, alle) ausgewählt und die zur Regel gehörenden Anweisungen werden ausgeführt.

Was ist Deklarative Programmierung (im Gegensatz zu Prozeduraler) Deklarative Programmierung  Im Gegensatz zu imperativen Programmierparadigmen, bei denen das Wie im Vordergrund steht, fragt man in der deklarativen Programmierung nach dem Was, das berechnet werden soll. Es wird also nicht mehr der Lösungsweg programmiert, sondern nur noch angegeben, welches Ergebnis gewünscht ist. Zu diesem Zweck beruhen deklarative Paradigmen auf mathematischen, rechnerunabhängigen Theorien.  Während ein prozedurales Programm den Weg beschreibt, auf dem das gewünschte Ziel (=Ergebnis) erreicht werden kann, ist ein deklaratives Programm die genaue Beschreibung (Spezifikation) eben dieses Ergebnisses.  Dazu gehören: Funktionale Sprachen (Scheme) und logische Sprachen (Prolog) Prozedurale Programmierung  Den Ansatz, Programme in kleinere Teilaufgaben aufzuspalten, bezeichnet man als prozedurale Programmierung. Die entstehenden Teilprogramme werden Prozeduren genannt. Praktisch alle aktuellen imperativen Programmiersprachen beinhalten den prozeduralen Ansatz.  Bei der imperativen Programmierung besteht ein Quellcode aus einer Folge von Befehlen, die vorgeben, in welcher Reihenfolge was vom Computer getan werden soll

Was ist Deklarative Programierung (im Gegensatz zu Imperativer) 



Imperative Programmierung: Es geht darum, der "Maschine" einen genauen Ablauf zu vermitteln, mit dem ein gewünschtes Ergebnis erreicht werden soll. Außerdem: Speicherzuweisung und Veränderung des Selben Deklarative Programmierung: Hier geht es darum, der "Maschine" zu vermitteln, was man erreichen möchte, und den Computer herausfinden zu lassen, wie das im einzelnen am besten zu bewerkstelligen ist.

Wie unterscheiden sich Variablen bei Prozeduraler Programmierung von Variablen bei deklarativer Programmierung?  

Deklarative Programmierung: Eher mathematisches Verständnis. Eine Variable x = 1 und kann nicht mehr geändert werden. Variablen sind (wie in der Mathematik) Namen von Objekten und haben keinen veränderlichen (zuweisbaren) Wert Prozedurale Programmierung: Einer Variable kann jederzeit ein neuer Wert zugewiesen werden. Sie kann also manipuliert werden.

Was ist Restrekursion? Welche Vorteile hat sie? 

Restrekursiv: Ist quasi iterativ, da nichts gespeichert werden muss. Alle relevanten Informationen werden direkt weitergegeben. Bei der restrekursiven Funktion ruft sich die Funktion mit einem veränderten Parameter auf.



Nicht-Restrekursiv: Hier müssen Werte gespeichert werden. Erst, wenn der letzte Durchlauf der Schleife durch ist, können die Werte addiert werden und so das Endergebnis berechnet werden. Die Schleife läuft also quasi noch einmal rückwärts.

Allgemein: Lineare Rekursion

Bei der linearen Rekursion wird der übergebene Parameter mit dem Rekursionsergebnis verrechnet.

Baumrekursi on

Die baumartige Rekursion kommt zum Einsatz, wenn man das Ergebnis aus zwei verschiedenen Rekursionsaufrufen berechnet. Bei der geschachtelten Rekursion ist das Ergebnis des Rekursionsaufrufes Parameter eines Rekursionsaufrufes. Ist quasi iterativ, da nichts gespeichert werden muss. Alle relevanten Informationen werden direkt weitergegeben. Bei der endrekursiven Funktion ruft sich die Funktion mit einem veränderten Parameter auf.

Kaskadieren de Rekursion Iteration/ Endrekursio n

Scheme: Worauf basiert Scheme?    

Dialekt von LISP 1958: LISP by John McCarthy (= Idee der funktionalen Programmierung) 1975: SCHEME (= rationale Rekonstruktion, Steele & Sussman) 1991: IEEE Standard SCHEME

Wie funktioniert die Funktionale Programmierung? Wie arbeitet der Compiler?  math. Definitionen werden eingegeben, die Anfrage ist ein Ausdruck, der durch Funktionen aufgebaut ist  Diese werden durch Vorgegebene ersetzt bis keine Funktionen mehr vorhanden sind, die ersetzt werden könnten Funktionale Programmierung: wie sieht ein Programm aus, welches Format hat ein Befehl?  ::= ( )  Prozedur-Aufruf: (prozedur-name arg1 arg2 arg3)  Sogar (* (- 5 3) (+ 1 9)) ist ein Prozedur. Es wird von innen nach außen ausgewertet.  If-Statement: (if Condition-check-procedure Then-procedure Else-procedure ) 

Lambda erstellt eine Funktion, define benennt die Funktion: (define square (lambda (x) (* x x))) (define (square x) (* x x))





Code und Daten: alles hat die gleiche Strukture --> Sind Listen mit Items! (+ 1 2) ist eine Liste! Ich kann auch quoten ‘(1 2 3) würde genau das ausgeben, aber ohne Quote würde (1 2 3) einen Fehler werfen, da versucht wird, die 1 als Prozedur zu interpretieren, obwohl sie keine ist. Symbole: (aa bb cc), wobei aa, bb oder cc Symbole sind

Wie ist die Arbeitsweise vom Interpreter bei Scheme? 1. Start des Systems 2. System signalisiert Bereitschaft (Bereitzeichen) 3. Benutzer schreibt einen Ausdruck („Term"),  abgeschlossen durch Zeilenwechsel (return) 4. System analysiert die Eingabe und  wertet die Eingabe aus und druckt Ergebnis ...  oder meldet Fehler 5. zurück nach Schritt 2 („read-eval-print loop")

Wie ist in Scheme ein Term aufgebaut und wie werden Terme ausgewertet?  Term: o Term als zentrales Sprachelement (Funktor A1 … An)  komplexe Terme durch o 

Verschachtelung Programme als Daten

o Syntax für die externe Repräsentation der Daten Auswertung von Termen: Ein Term wird ausgewertet, indem  1. Alle Elemente des Terms ausgewertet werden (R5RS: keine feste Reihenfolge, d.h.: implementations-abhängig!) und  2. der Wert des ersten Elements, der ein Prozedurobjekt sein muss, auf die Werte der restlichen Elemente („Argumente") angewandt wird  Rekursive Termstrukturen führen zu einer rekursiven Verarbeitungsregel Fundamentale Reihenfolgeregel: Auswertung von INNEN nach AUSSEN Faustregel: keine Reihenfolge für Terme auf gleicher Ebene festgelegt; also agiere als ob Auswertung parallel Define: Wir sagen: Ein Name (Identifikator) identifiziert eine „Variable", deren Wert ein Objekt ist: „Symbol". Der Operator zur Benennung von Objekten (= Variablendeklaration samt evtl. Werteassoziation) heißt define Auswertung von Define: o

  





o o

1. Erstes und drittes Element ausgewertet 2. Wert v. Dritten wird dem zweiten Element (=Identifikator) in aktueller Umgebung

o

zugeordnet 3. Wert der Operation ist unspezifiziert (keine Ausgabe, nur „Zuweisung/Benennung“)

o

 Namen v. Spezialformen: syntaktische Schlüsselwörter (-> direkt codiert, nicht in

globaler Umgebung) Prozeduren als Bausteine zur Definition anderer Prozeduren (define (square x) (* x x)) (define (sum-of-squares x y) (+ (square x) (square y)) )



(define (f a) (sum-of-squares (+ a 1) (* a 2)) ) (f 5) Substitutionsmodell:

Prolog: Was ist Prolog?  

Prolog ist eine logische und deklarative Programmiersprache Prolog-Programme bestehen quasi aus einer Wissensdatenbank, deren Einträge in Fakten und Regeln aufgeteilt sind. Der Prolog-Interpreter benutzt die Fakten und Regeln, um systematisch eine Antwort zu finden. Ein positives Resultat bedeutet, dass die Anfrage logisch ableitbar ist. Das Ausführen eines Prolog-Programms bedeutet immer das Stellen einer Anfrage.

mann(adam). mann(tobias). mann(frank). ?- mann(tobias). yes. ?- mann(X). X=adam X=tobias X=frank



Eine Anfrage mit einer Variablen liefert als Antwort zusätzlich Belegungen, mit denen die Anfrage wahr wird. Man nennt eine solche Variablenbelegung Unifikation und sagt, die Variable wird mit diesem Wert unifiziert. Variablen sind in Prolog Token, die mit einem Großbuchstaben beginnen:

Worauf basiert Prolog?  

1970er: Alain Colmerauer (aufbauend auf Forschung zu automatisierten Beweisen) Wurzeln in maschineller Sprachverarbeitung (Parsing)



Logische Programmierung (z.B. in Prolog) basiert auf Klausellogik und dem StandardInferenzmechanismus der Resolution

Benennung:  Atom: nicht teilbarer Term, kleingeschrieben  Regel: umgedrehte Implikation. Regelzeichen : Prädikat: auto ist Prädikat bei auto(blau). auto(rot). 

Unifikation: Bezeichnet das Gleichsetzen zweier Terme durch konsistente Ersetzung von Variablen durch andere geeignete Terme. Wenn eine Variable durch einen Term substituiert wurde, ist sie gebunden. Zwei ungebundene Variablen unifizieren immer. Zwei Atome unifizieren nur, wenn sie identisch sind. Die Unifikation zweier Terme scheitert, wenn sie syntaktisch nicht gleich sind oder wenn die Argumentwerte in den gleichen Argumentpositionen beider Terme nicht unifizieren. Beispiel: die Terme schwester(anna, petra) und schwester(anna, X) können unifiziert werden, indem X durch petra ersetzt wird

Wie ist ein Prolog-Programm aufgebaut? Wie wird eine einzelne Anfrage ausgewertet? Was sind Fakten/Regeln? 

  

Terme: Ein Term ist entweder o ein Konstantensymbol, o ein Variablensymbol, o ein Funktionssymbol angewendet auf ein Tupel (geordnete Anordnung) von Termen. Formeln (Fakten, Regeln, Anfragen) Der Regeloperator :- ist dabei wie ein umgedrehter Implikationspfeil zu lesen. Der Operator , in dieser Regel definiert eine Konjunktion und wird und gesprochen.

Wie funktioniert logische Programmierung?  es wird nach einer logischen Konsequenz gesucht  vorgegeben ist Datenbank mit Fakten und Regeln (Prädikate)  eingegebene Anfrage ist ein Ausdruck der ?wahr? oder ?falsch? sein kann  es wird nach Prädikaten gesucht, die mit der Anfrage unifiziert werden können, die Anfrage wird dann mit dem Rumpf des gefundenen Prädikats ersetzt, so lange, bis ein leeres Ziel entsteht, dann ist das Ergebnis ?wahr?  oder kein leeres Ziel, dann ?Endlosschleife? irgendwann evtl. Stackoverflow Unifikation am Beispiel "is", Auswertungsablauf, bei Anfrage mit mehreren Teilzielen (-? x is 1, x is 2.)

Wie ist die Arbeitsweise des Interpreters?

Trace der Abarbeitung: 1. Initiales Ziel: dark(X), big(X). 2. Scannen des Programms von „oben nach unten“ nach einer Klausel, deren Kopf sich mit dem ersten Teilziel dark(X) unifizieren läßt. Gefunden wird Klausel (7). (X=Z1) Ersetzen des ersten Teilziels mit dem instantiierten Körper der Klausel (7). Damit neues Ziel: black(Z1), big(Z1). 3. Scannen des Programms um eine Klausel zu finden, die sich mit black(Z1) unifizieren läßt. Gefunden wird Klausel 5: black(cat). Diese Klausel hat einen leeren Körper. Damit verkleinert sich das Ziel auf big(cat). (Z1=cat) 4. Scannen des Programms, um big(cat) zu bearbeiten. Keine Klausel findet sich. Backtracking auslösen zu Schritt 3. Rückgängigmachen der Substitution Z1=cat und Wiederherstellen des „alten“ Ziels: black(Z1), big(Z1). Weiterscannen des Programms ab Klausel 5. Keine Klausel findet sich. Backtracking zu Schritt 2 and weiterscannen unterhalb Klausel 7. Klausel (8) kann zur Unifikation herangezogen werden: dark(Z) :- brown(Z). (X=Z2) Ersetzen des ersten Teilziels durch brown(Z2) ergibt neues Ziel brown(Z2), big(Z2). 5. Scannen des Programms, um brown(Z2) zu unifizieren. Finden der Klausel (4). Diese Klausel hat keinen Körper. Das Ziel schrumpft zu big(bear). (Z2=bear) 6. Scannen des Programms. Finden der Klausel (1). Diese Klausel hat keinen Körper. Ziel schrumpft zum leeren Ziel. Erfolgreiche Terminierung. Liefere korrespondierende Variablenbindung X=Z2=bear.

Programme Kleines Programm schreiben: Summe der Elemente einer Liste (Scheme und Prolog). SCHEME Nicht-restrekursiv: (define (sum1 liste) (if (null? liste) 0 (+ (car liste) (sum1 (cdr liste))) ) ) (sum1 '(1 2 3 4))

SCHEME Restrekursiv/Iterativ: (define (sum2 liste n) (if (null? liste) n (sum2 (cdr liste) (+ (car liste) n)) ) ) (sum2 '(1 2 3 4) 0)

PROLOG summe([],0). summe([X|Rest],Sum) :- summe(Rest,Sum0), Sum is Sum0+X. ?- summe([10,20,30], Sum)

Kleines Programm schreiben: Produkt einer Liste (Scheme und Prolog). SCHEME Nicht-restrekursiv: (define (prod1 liste) (if (null? liste) 1 (* (car liste) (prod1 (cdr liste))) ) ) (prod1 '(1 2 3 4))

SCHEME Restrekursiv/Iterativ: (define (prod2 liste n) (if (null? liste) n (prod2 (cdr liste) (* (car liste) n)) ) ) (prod2 '(1 2 3) 1)

PROLOG product_list([],1). product_list([X|Rest], Prod) :- product_list(Rest, Prod0), Prod is Prod0*X. ?- product_list([20,30,40], Prod) Kleines Programm schreiben: Länge einer Liste (Scheme und Prolog). (Bei Prolog: Was bedeutet :- und , und was ist der Unterschied zwischen L = L0+1 und L is L0+1) SCHEME Nicht-restrekursiv: SCHEME Restrekursiv/Iterativ: (define (len2 liste n) (define (len1 liste) (if (null? liste) (if (null? liste) n 0 (len2 (cdr liste) (+ n 1)) (+ 1 (len1 (cdr liste))) ) ) ) ) (len2 '(1 2 3 5 0) 0) (len1 '(1 2 3 5 0)) PROLOG length_list([],0). length_list([X|R], L) :- length_list(R, L0), L is L0+1. ?- length_list([1,0,5,3,2], L)...