AB3 Imperative Programme

Implementieren Sie die folgenden Funktionen nur unter Verwendung der bereits importierten Funktionen. Folgende Sprachkonstrukte dürfen nicht verwendet werden:

🎦 Spuren-basierte Programmierung (klicken, um Video anzuschauen) 🎦

Bei der spuren-basierten Programmierung wird ein Programm schrittweise aus Ausführungsspuren konstruiert. Zuerst wird der zu implementierende Algorithmus per Hand ausgeführt. Diese Ausführung wird dann in eine Tabelle übersetzt, bei welcher die Spalten mit den Variablen des Programms beschriftet sind und jede Zeile einem Ausführungsschritt entspricht. Anschließend müssen Operationen angegeben werden, welche die Veränderung der Werte in jeder Zeile beschreiben. Daraus kann dann der Kontrollflussgraph des Programms abgeleitet werden. Zum Schluss muss für jede Operation ein Entscheidungsbaum angegeben werden, der beschreibt, mit welcher Operation das Programm als nächstes fortfahren soll. Die Struktur von Programmen, welche mithilfe dieser Methode entwickelt werden, entspricht dem Aufbau von sp-Programmen.

Ab Teil 2 geht es darum, gegebene sp-Programme zu vervollständigen. Gewisse Informationen, wie z.B. Ausführungsspuren in Form von Tabellen, sind dabei schon gegeben. Sie können Teile der Methode anwenden, um die Lücken entsprechend auszufüllen.

Teil 1: Kontrollstrukturen

type Operation a = (a -> a)
type Predicate a = (a -> Bool)
Der Zustand eines Programms ist gegeben durch die Werte der Variablen, welche in dem Programm vorkommen. Dieser Zustand wird durch die Typvariable a repräsentiert.
Eine Operation verändert den Zustand des Programms. Ein Beispiel für eine Operation ist eine Zuweisung (Wert einer Variable wird neu festgelegt).
Ein Prädikat gibt an, ob der Zustand des Programms eine gewisse Eigenschaft aufweist, z.B. ob eine Variable größer als 0 ist. Prädikate kommen in Kontrollstrukturen vor, um den Kontrollfluss des Programms zu steuern.
Ein Programm kann als eine große Operation gesehen werden, welche durch Kombinieren von Operationen mithilfe von Kontrollstrukturen und Prädikaten entsteht. 
if2     :: (Predicate a) -> (Operation a) -> (Operation a)
while   :: (Predicate a) -> (Operation a) -> (Operation a) 
repeat  :: Int -> (Operation a) -> (Operation a)
foreach :: [b] -> (Operation (a,b)) -> (Operation a)
Die Funktion if2 bekommt ein Prädikat arg1 und eine Operation arg2 als Parameter und soll folgende Operation zurückgeben. Falls arg1 wahr ist, dann wird arg2 ausgeführt, ansonsten bleibt der Zustand des Programms unverändert.
Die Funktion while soll folgende Operation zurückgeben. Solange das Prädikat arg1 wahr ist, wird die Operation arg2 wiederholt ausgeführt. Wenn das Prädikat arg1 nicht wahr ist, dann wird der Zustand des Programms zurückgegeben.
Die Funktion repeat soll folgende Operation zurückgeben. Es wird arg1-mal arg2 ausgeführt (arg1 ≥ 0).
Die Funktion foreach soll folgende Operation zurückgeben. Für jedes Element der Liste arg1 soll die Operation arg2 ausgeführt werden. Die Operation arg2 bekommt zusätzlich zum Programmzustand auch das Element der Liste übergeben. Die Liste wird in ihrer natürlichen Reihenfolge durchlaufen. 
tailRecursion :: (Operation a) -> (Operation a) -> (Predicate a) -> (Operation a)
Eine Funktion \(f \colon a \rightarrow a \) lässt sich als einfache Endrekursion ausdrücken, falls es Funktionen \(g,h \colon a \rightarrow a\) und \(p \colon a \rightarrow \{0,1\} \) gibt, sodass gilt $$ f(x) = \begin{cases} g(x) & \text{, falls } p(x) = 0 \\ f(h(x)) & \text{, falls } p(x) = 1 \end{cases} $$ Definieren Sie die Funktion tailRecursion nur mithilfe der Funktionen while und (.) (Komposition (f . g) x = f(g(x))). Es soll gelten arg1 \(=g\), arg2 \(=h\) und arg3 \(=p\). 
primitiveSort lst = (while (not.isEmpty.?) ?) lst
Definieren Sie die Funktion primitiveSort indem Sie die '?' in obigem Code-Snippet entsprechend ersetzen. 
bubbleSort :: (Ord a) => (Operation [a])
swapPred   :: (Ord a) => (Predicate ([a],Int))
swapOp     :: (Ord a) => (Operation ([a],Int))
Mithilfe der obigen Kontrollstrukturen soll BubbleSort implementiert werden. Dabei wird eine Liste mit \(n\) Elementen sortiert, indem folgendes \(n-1\) Mal wiederholt wird. Man durchläuft jedes benachbarte Paar der Liste und falls das linke Element größer ist als das rechte, dann werden die beiden vertauscht. Achten Sie darauf, dass die Funktion auch für leere Listen funktioniert.
Die '?' in folgendem Code-Snippet müssen entsprechend ersetzt und die Funktionen swapPred und swapOp entsprechend definiert werden. 
bubbleSort lst = program ?
  where
    n = length lst
    program = 
        (repeat ?
          (foreach ?
            (if2 ? ?)      
          )
        )

Teil 2: BubbleSort

Die vorherige Version von BubbleSort kann mithilfe folgender zwei Beobachtungen erweitert werden, sodass der Algorithmus in bestimmten Fällen nach weniger Schritten terminiert.

Wenn während einer Iteration keine zwei Elemente vertauscht werden, dann ist die Liste sortiert.

Nach der ersten Iteration ist das größte Element auf dem letzten Platz. Nach der zweiten Iteration ist das zweitgrößte Element auf dem vorletztem Platz, usw. Das heißt, nach der ersten Iteration braucht das letzte Element der Liste nicht mehr betrachtet zu werden, nach der zweiten Iteration brauchen die letzten zwei Elemente der Liste nicht mehr betrachtet werden, usw.

Implementieren Sie den erweiterten Algorithmus indem Sie die '?' in der Datei AB3_2/bubbleSort.sp entsprechend ersetzen. Die Traces, welche beim Aufruf der Funktion main erzeugt werden, müssen identisch sein zu denen in AB3_2/reference (dies wird beim Aufruf von main getestet).

Teil 3: Ägyptische Multiplikation

Bei der ägyptischen Multiplikation (auch bekannt als russische Bauernmultiplikation) werden zwei natürliche Zahlen \(a\) und \(b\) multipliziert indem die Zahl \(a\) wiederholt verdoppelt und addiert wird. Beispiele (leere Zelle bedeutet der Wert bleibt unverändert):
\(a\)=5, \(b\)=16
\(i\)\(c\)\(r\)
1650
810
420
240
18080
\(a\)=7, \(b\)=11
\(i\)\(c\)\(r\)
1177
51421
228
15677

Die Zahl \(c\) wird auf \(r\) addiert, falls \(i\) ungerade ist. Die Sequenz der Werte, welche \(i\) annimmt, beschreiben die Binärdarstellung von \(b\) (gerade=0, ungerade=1).

Implementieren Sie den obigen Algorithmus indem Sie die '?' in der Datei AB3_3/egyptMult.sp entsprechend ersetzen. Die Traces, welche beim Aufruf der Funktion main erzeugt werden, müssen identisch sein zu denen in AB3_3/reference (dies wird beim Aufruf von main getestet). Sie können davon ausgehen, dass \(a, b \geq 0\).

Tipp Der Kontrollfluss (der #FLOW-Abschnitt in der sp-Datei) kann aus den Prädikatsequenzen der Referenz-Traces zum Teil rekonstruiert werden. Eine solche Sequenz entspricht dabei einem Pfad durch den binären Entscheidungsbaum.

Teil 4: Confidential String Matching

Beim Confidential String Matching Problem sind zwei Listen von Strings a und b gegeben und es soll geprüft werden, ob concat a == concat b. Zum Beispiel gilt das für a = ["ab","cde"] und b = ["a","bc","de"], da beide "abcde" ergeben. Allerdings sind die Strings in a und b vertraulich. Deshalb kann nur indirekt auf die beiden Listen zugegriffen werden: 
coa  :: CSMInstance -> Int
cob  :: CSMInstance -> Int
lena :: CSMInstance -> Int -> Int
lenb :: CSMInstance -> Int -> Int
ssc  :: CSMInstance -> Int -> Int -> Int -> Int -> Int -> Bool
Die Funktion coa (= cardinality of a) gibt die Anzahl der Strings in a zurück (analog dazu cob für b).
Die Funktion lena (= length of element of a) gibt die Länge des (arg1+1)-ten Strings in a zurück (analog dazu lenb für b).
Die Funktion ssc (= substring call) ist wahr gdw. wenn zwei Teilstrings aus a und b gleich sind. Genauer gesagt: ssc (CSMInstance a b) ca cb oa ob l ist wahr gdw. die ersten l Zeichen der Teilstrings a' und b' gleich sind, wobei a' der Teilstring vom (ca+1)-ten String aus a ist, welcher ab dem (oa+1)-tem Zeichen anfängt (analog dazu b' für cb).
Implementieren Sie den durch das obige Bild beschriebenen Algorithmus, indem Sie die '?' in der Datei AB3_4/csmAlg.sp entsprechend ersetzen. Die Traces, welche beim Aufruf der Funktion main erzeugt werden, müssen identisch sein zu denen in AB3_4/reference (dies wird beim Aufruf von main getestet). Außerdem müssen Sie Funktionen in der Datei AB3_4.hs implementieren, mit welchen Sie die Prädikate p_eqlen und p_empty ausdrücken können.

Teil 5: Josephus-Problem

Das Josephus-Problem ist wie folgt definiert (siehe auch Numberphile (Video)). Es stehen \(n\) Personen im Kreis, welche von \(1\) bis \(n\) nummeriert sind. Am Anfang entfernt Person \(1\) ihren Nachbarn (Person \(2\)) aus dem Kreis. Danach entfernt der neue Nachbar von \(1\) (Person \(3\)) seinen Nachbarn (Person \(4\)) aus dem Kreis. Die nächste Person, die jemanden entfernt, ist dann \(5\). Dies wird solange wiederholt, bis nur noch eine Person übrig ist. Wie lautet die Nummer dieser Person?

Implementieren Sie den obigen Algorithmus indem Sie die '?' in der Datei AB3_5/josephus.sp entsprechend ersetzen. Die Traces, welche beim Aufruf der Funktion main erzeugt werden, müssen identisch sein zu denen in AB3_5/reference (dies wird beim Aufruf von main getestet).