Systematic Programming Summer Semester 2020
Dr. Maurice Chandoo Leibniz Universität Hannover

AB3 Imperative Programs

Implement the following functions using only the already imported functions. Additionally, the following language constructs are not permitted:

• if ... then ... else ... (use if' instead if imported)
• Guards
• List Comprehensions: [(i,j) | i <- [1,2], j <- [3,4]]

🎦 Trace-Based Programming (click to watch video) 🎦

In trace-based programming a program is constructed stepwise from execution traces. The first step is to execute the algorithm to be implemented by hand. This execution is then translated into a table where the columns correspond to the variables of the program and each row describes an execution step. After that, one has to find operations which describe the changes of the values in each row. From that, the control-flow graph of the program can be derived. Finally, one has to come up with a binary decision tree for each operation which describes with what operation the program should continue after executing a particular operation. The structure of programs which are developed using this method coincides with sp-programs.

Starting from part 2, the task is to complete partial sp-programs. Certain information such as execution traces in the form of tables is given. Parts of the method can be applied to fill in the gaps.

Part 1: Control Structures

The state of a program is described by the values of the variables which occur in it. This state is represented by the type variable a.
An operation changes the state of a program. An example of an operation is an assignment (value of a variable is changed).
A predicate tells us whether the state of a program satisfies a certain property. For example, whether a certain variable is larger than 0. Predicates are used in control structures to guide the control flow of the program.
A program can be regarded as a single big operation which results from combining smaller ones using control structures and predicates. The function if2 gets a predicate arg1 and an operation arg2 as input parameters and should return the following operation. If arg1 is true then arg2 should be executed. Otherwise, the state of the program should remain unchanged.
The function while should return the following operation. As long as the predicate arg1 holds, the operation arg2 is executed repeatedly. As soon as the predicate arg1 does not hold anymore, the state of the program is returned.
The function repeat should return the following operation. The operation arg2 is executed arg1 ≥ 0 times.
The function foreach should return the following operation. For every element in the list arg1 the operation arg2 should be executed. In addition to the program state the operation arg2 also gets the element of the list. The list should be traversed in its natural order. A function \(f \colon a \rightarrow a \) can be expressed as tail recursion if there exists functions \(g,h \colon a \rightarrow a\) and \(p \colon a \rightarrow \{0,1\} \) such that: $$ f(x) = \begin{cases} g(x) & \text{, if } p(x) = 0 \\ f(h(x)) & \text{, if } p(x) = 1 \end{cases} $$ Define the function tailRecursion using only the functions while and (.) (composition (f . g) x = f(g(x))). Assume that arg1 \(=g\), arg2 \(=h\) and arg3 \(=p\). Define the function primitiveSort by replacing '?' in the above code. Implement BubbleSort using the above control structures. In BubbleSort a list with \(n\) elements is sorted by repeating the following \(n-1\) times. Traverse each neighboring pair in the list and if the left element is larger than the right then swap them. Keep in mind that the function should also work for the empty list.
The '?' in the following code must be replaced and the function swapPred and swapOp have to be defined adequately.

Part 2: BubbleSort

The previous version of BubbleSort can be extended such that the algorithm terminates sooner in certain cases. The following two observations can be used to achieve this.

If no two elements are swapped during an iteration then the list is sorted.

After the first iteration the largest element becomes the last element of the list. After the second iteration the second-largest element becomes the second-last element of the list and so on. This means after the first iteration one does not have to consider the last element of the list anymore and after the second iteration one does not have to consider the two last elements of the list and so on.

Implement this extension of BubbleSort by replacing the '?' in the file AB3_2/bubbleSort.sp. The traces produced when calling main must be identical to the ones in AB3_2/reference (this is tested when main is called).

Part 3: Egyptian Multiplication

In Egyptian multiplication (also known as Russian peasant multiplication) two natural numbers \(a\) and \(b\) are multiplied by repeatedly doubling and adding. Examples (empty cell means the value remains unchanged):

The number \(c\) is added to \(r\) if \(i\) is odd. The sequence of values assumed by \(i\) describe the binary representation of \(b\) (even=0, odd=1).

Implement the above algorithm by replacing the '?' in the file AB3_3/egyptMult.sp. The traces produced when calling main must be identical to the ones in AB3_3/reference (this is tested when main is called). You may assume that \(a, b \geq 0\).

Hint

The control flow (the #FLOW part in the sp-file) can be partially reconstructed from the predicate sequences in the reference traces. Such a predicate sequence corresponds to a path through the binary decision tree.

Part 4: Confidential String Matching

For the confidential string matching problem two lists of strings a and b are given and it should be decided whether concat a == concat b. For example, this holds for a = ["ab","cde"] and b = ["a","bc","de"] because both equal "abcde" when concatenated. However, the strings in a and b are confidential. Therefore one can only access them indirectly: The function coa (= cardinality of a) returns the number of strings in a (resp. cob for b).
The function lena (= length of element of a) returns the length of the (arg1+1)-th string in a (resp. lenb for b).
The function ssc (= substring call) returns true iff two substrings from a and b are equal. More specifically, ssc (CSMInstance a b) ca cb oa ob l returns true iff the first l characters from the substring a' and b' are equal with a' being the substring of the (ca+1)-th string in a which starts from the (oa+1)-th character (resp. b' for cb and ob).
Implement the algorithm described by the above picture. Replace the '?' in the file AB3_4/csmAlg.sp. The traces produced when calling main must be identical to the ones in AB3_4/reference (this is tested when main is called). Additionally, you have to implement functions in the file AB3_4.hs which allow you to express the predicates p_eqlen and p_empty.

Part 5: Josephus Problem

The Josephus problem is defined as follows (see also Numberphile (Video)). There are \(n\) people standing in a circle who are labeled \(1\) to \(n\). In the beginning, person \(1\) removes person \(2\) from the circle. Then the new neighbor of \(1\) (person \(3\)) removes their next neighbor (person \(4\)) from the circle. The next person to remove their neighbor is person \(5\). This is repeated until only one person remains. What is the number of this person?

Implement this algorithm by replacing the '?' in the file AB3_5/josephus.sp. The traces produced when calling main must be identical to the ones in AB3_5/reference (this is tested when main is called).