Description
Continuation Passing Style (CPS) is a form of programming in which functions do not return values. Instead, when a function is called, it is given another function, called its continuation. When the function produces a value, it calls its continuation with the value, instead of returning it. In this way, the same function can produce no values (by never calling its continuation), one value (by calling its continuation once), two values (by calling its continuation twice), etc. It can even produce n values, where n is a number not known in advance, by calling its continuation n times. In this computer laboratory, you will write a CPS function that produces all permutations of a list.
1. Theory.
Suppose that l is a finite list of zero or more distinct elements (so there are no duplicates). Then a permutation of l is either l itself, or else a list made by rearranging the elements of l. For example, the OCaml list [0; 1; 2] has six possible permutations, shown below.
[0; 1; 2]
[0; 2; 1]
[1; 0; 2]
[1; 2; 0]
[2; 0; 1]
[2; 1; 0]
If l has n distinct elements, then it has n! permutations. This is because there are n possible choices for the first element of a permutation, n−1 choices for the second element, n−2 choices for the third element, etc., until finally there is only one choice left for the last element. As a result, the total number of permutations is:
n! = n × (n−1) × (n−2) ⋯ × 2 × 1
As a result, the number of permutations rises very rapidly as the length of the list l increases. For example, a list of length with ten elements has 10! = 3628800 possible permutations.
Suppose we want to generate all possible permutations of a list; perhaps we want to know if one of them has an interesting property. Since there are so many permutations, it would take too much memory to generate them all, and store them in another list. It would be better to generate them one at a time, so we need only the memory for a single permutation. This can be done in OCaml using CPS.
Here’s a sketch of an OCaml function called permuting that generates permutations in this way. It takes three arguments: a continuation called etc, a list of distinct things that have been permuted called permutedThings, and a list of distinct things that have not yet been permuted called unpermutedThings. We do not care what the things are: they might be characters, numbers, strings, etc.
-
If unpermutedThings is empty, then call etc on permutedThings, then stop.
-
If unpermutedThings is not empty, then choose a thing from unpermutedThings somehow. Make a new list of permutedThings, by adding the chosen thing to the front of permutedThings. Make a new list of unpermutedThings, by removing the chosen thing from unpermutedThings. Call permuting recursively with etc, the new permutedThings, and the new unpermutedThings.
-
Go back to step 2, but choose a different thing from unpermutedThings this time. Continue until all the things have been chosen once, then stop.
Note that each time we call permuting, the list unpermutedThings is smaller. That means it will eventually become empty, so permuting will terminate at step 1. Also note that permuting is a CPS function: it never returns a permutation! Instead, every time it generates a permutation, it calls its continuation etc.
At this point, you may wonder how we get the permutations, since they are generated, but never returned. The answer is that the continuation etc contains code that processes each permutation—in other words, it continues the computation for each permutation.
2. Implementation.
For this laboratory assignment, you must write the following OCaml functions. Of course you may write more helper functions if you need them. Your functions must not use loops, mutable objects, or variables.
- choose etc things
Call the continuation etc on each member of the list things.
- allbut things thing
Return a list that is like things, but in which the first appearance of thing is removed.
- permute etc things
Assume things is a list of distinct elements. Generate all possible permutations of things, one at a time. Each permutation is a list with the same elements as things, all but one of which has its elements in a different order. Call etc on each permutation.
Here are some hints.
-
The function choose is a CPS function, so it does not return a useful value. If you write it in the obvious way, then it will return (). It may need to use the OCaml semicolon operator ‘;’.
-
The function allbut is not a CPS function: it returns a list. You wrote a function very much like allbut in the first laboratory assignment for this course.
-
The function permute is a CPS function, so it does not return a useful value. If you write it in the obvious way, then it will return (). It must use something like permuting (described in the previous section) as a helper. It must also use choose and allbut as helpers.
3. Deliverables.
The file tests4.ml contains some tests, worth 30 points. It also contains a definition of an OCaml function called printThings that prints lists. Insert your code into this file, then run it with OCaml. When you think your code is correct, then submit the file with your code in it, and the results of the tests in a comment at the end. The lab TA’s will tell you how and where to turn in your work. It must be submitted by 11:55 PM on Tuesday, October 12, 2021.
