I’ve know for a long time that you could convert any iterative function to be recursive and vice versa, but up until recently, I only knew how to go from iterative to recursive in a mostly formulaic way.
I recently saw a cool presentation where he shows a refactoring to deterministically (at least AFAICT) go from a recursive function to an iterative one. It took me a bit of rewatching and fiddling as to how to apply it, but now having done a few exercises, I have a good feel for it, and I thought perhaps using a slightly more involved example might help explain it to others.
I had written about doing simple functional quicksort in java and I thought, since I work in typescript a lot these days, I could work through it on the blog to show how it would work.
So let’s start with the origin source. To do this the simple way in a browser console, you’ll need an HTML file to load, while looking at the browser console. For our cases it can be stupid simple. It can be simpler than this, but this keeps the browser console from being annoyed and logging warnings.
<!DOCTYPE html>
<html>
<head>
<meta charset="utf-8" />
<script src="defunc.js"></script>
</head>
</html>
In a terminal window, run this to get things compiling automatically as you make edits. VSCode probably has something to do this, but I only thought of that as I was writing this. BTW: this assumes you have tsc installed somewhere.
touch defunc.ts
tsc -w --inlineSourceMap defunc.ts
Now with that out of the way, the simple recursive typescript port of the quick implementation I posted for java is
const arr = [15, 2, 7, 9, 20, 23, 1, 5, 28, 3];
function quicksort(input: number[]) {
if (input.length <= 1) {
return input;
}
const pivot = input[0];
const rest = input.slice(1);
const lt = rest.filter(v => v < pivot);
const gteq = rest.filter(v => v >= pivot);
const left = quicksort(lt);
const right = quicksort(gteq);
return left.concat(pivot, ...right);
}
console.log('sorted', quicksort(arr));
Load your HTML file, look in the console, and voila, it does what you’d think.
Continuation Passing Style
If you’re not familiar with CPS, first, go read up on it now. Ok, now that
you’re back, for our purposes, any time we might call quicksort recursively,
we’ll manually pass in a continuation to receive the return value of the
quicksort call, rather than having it return the normal way. And rather
than calling return to return a value, you call the continuation with the
return value instead.
function quicksort(input: number[], kont: (n: number[]) => void) {
if (input.length <= 1) {
kont(input);
} else {
const pivot = input[0];
const rest = input.slice(1);
const lt = rest.filter(v => v < pivot);
const gteq = rest.filter(v => v >= pivot);
quicksort(lt, left => {
quicksort(gteq, right => {
kont(left.concat(pivot, ...right));
});
});
}
}
quicksort(arr, res => console.log('sorted', res));
So here, where we’d return input, we call the continuation with input as
the argument instead. We had to reorder the bottom parts a bit. Here we
quicksort the stuff to the left, then quicksort the stuff to the right,
then call the continuation with everything glued all together.
Also, you’ll notice that to print the result, we have to pass a continuation
function to quicksort that then logs the result, rather than returning it.
Defunctionalization
This is the magical bit. If you watch the aforementioned video, the trick here is to take every place where we call the continuation and externalize it into a structure we can pass, so as to disentangle it from the runtime stack. Keep in mind this doesn’t yet get us to the iterative solution just yet.
So in the case of the nested quicksort calls, we start from the inside out.
We start with this:
quicksort(lt, left => {
quicksort(gteq, right => {
kont(left.concat(pivot, ...right));
});
});
Then defunctionalize the inner kont call:
quicksort(lt, left => {
quicksort(gteq, {action = 'JOINIT', left: res, pivot: kont.pivot, next: kont.next});
});
Here for the continuation, we just make sure that the continuation contains all the the values we need for it to be able to compute what it does.
Then defunctionalize the inner quicksort call
quicksort(lt, {action: 'RECUR', gteq, pivot, next: kont});
pulling what they would do into the doit function which takes these new externalized
continuation objects and the result that is going to go to them.
The reason for kont.next in lieu of plain kont is that this stack frame
should just return its value to its parent, it won’t build up any “stack”
context of its own.
Anyway after defunctionalization, you wind up with this:
interface Continuation {
action: string;
gteq?: number[];
left?: number[];
pivot?: number;
next: Continuation;
}
function doit(kont: Continuation, res: number[]) {
if (kont.action == 'JOINIT') {
doit(kont.next, kont.left.concat(kont.pivot, ...res));
} else if (kont.action == 'RECUR') {
quicksort(kont.gteq, {action: 'JOINIT', left: res, pivot: kont.pivot, next: kont.next});
} else if (kont.action == 'DONE') {
console.log('sorted', res);
}
}
function quicksort(input: number[], kont: Continuation) {
if (input.length <= 1) {
doit(kont, input);
} else {
const pivot = input[0];
const rest = input.slice(1);
const lt = rest.filter(v => v < pivot);
const gteq = rest.filter(v => v >= pivot);
quicksort(lt, {action: 'RECUR', gteq, pivot, next: kont});
}
}
quicksort(arr, {action: 'DONE', next: null});
Inlining
Now that we have that done, we’ll inline the call to doit.
function quicksort(input: number[], kont: Continuation) {
if (input.length <= 1) {
//doit(kont, input)
if (kont.action == 'JOINIT') {
/// Hmmm what do we do here?
doit(kont.next, kont.left.concat(kont.pivot, ...res));
} else if (kont.action == 'RECUR') {
quicksort(kont.gteq, {action: 'JOINIT', left: res, pivot: kont.pivot, next: kont.next});
} else if (kont.action == 'DONE') {
console.log('sorted', res);
}
} else {
const pivot = input[0];
const rest = input.slice(1);
const lt = rest.filter(v => v < pivot);
const gteq = rest.filter(v => v >= pivot);
quicksort(lt, {action: 'RECUR', gteq, pivot, next: kont});
}
}
But doit itself is recursive, what do we do? It turns out that with some tail
recursion elimination we can take care of it as the call to doit is in the
tail position.
function quicksort(input: number[], kont: Continuation) {
if (input.length <= 1) {
while (true) {
// TCE on doit
let res = input; // to replace the arg that was in doit
if (kont.action == 'JOINIT') {
// doit(kont.next.next, kont.left.concat(kont.pivot, ...res));
input = kont.left.concat(kont.pivot, ...res);
kont = kont.next;
continue;
} else if (kont.action == 'RECUR') {
quicksort(kont.gteq, {action: 'JOINIT', left: res, pivot: kont.pivot, next: kont.next});
} else if (kont.action == 'DONE') {
console.log('sorted', res);
}
break;
}
} else {
const pivot = input[0];
const rest = input.slice(1);
const lt = rest.filter(v => v < pivot);
const gteq = rest.filter(v => v >= pivot);
quicksort(lt, {action: 'RECUR', gteq, pivot, next: kont});
}
}
From there we can do TCE on calls to quicksort itself, and you get:
function quicksort(input: number[], kont: Continuation) {
while (true) {
if (input.length <= 1) {
while (true) {
let res = input;
if (kont.action == 'JOINIT') {
input = kont.left.concat(kont.pivot, ...res);
kont = kont.next;
continue;
} else if (kont.action == 'RECUR') {
input = kont.gteq;
kont = {action: 'JOINIT', left: res, pivot: kont.pivot, next: kont.next};
break;
} else if (kont.action == 'DONE') {
console.log('sorted', res);
return;
}
}
} else {
const pivot = input[0];
const rest = input.slice(1);
const lt = rest.filter(v => v < pivot);
const gteq = rest.filter(v => v >= pivot);
input = lt;
kont = {action: 'RECUR', gteq, pivot, next: kont};
}
}
}
quicksort(arr, {action: 'DONE', next: null});
From there, we do some refactoring, and some renaming to clean a few things up, and you have a brand spanking shiny new iterative quicksort!
interface Continuation {
action: string;
greaterEqual?: number[];
lessThan?: number[];
pivot?: number;
next: Continuation;
}
function quicksort(input: number[]) {
let kont: Continuation = {action: 'DONE', next: null};
while (true) {
if (input.length > 1) {
const pivot = input[0];
const rest = input.slice(1);
const lessThan = rest.filter(v => v < pivot);
const greaterEqual = rest.filter(v => v >= pivot);
input = lessThan;
kont = {action: 'DORIGHT', greaterEqual, pivot, next: kont};
continue;
}
while (true) {
if (kont.action == 'DONE') {
return input;
}
if (kont.action == 'JOINIT') {
input = kont.lessThan.concat(kont.pivot, ...input);
kont = kont.next.next;
continue;
}
if (kont.action == 'DORIGHT') {
kont = {action: 'JOINIT', lessThan: input, pivot: kont.pivot, next: kont};
input = kont.next.greaterEqual;
break;
}
}
}
}
console.log('sorted', quicksort(arr));
I could also make it a bit less scrutable by removing action from
Continuation as which value of action can be determined by the presence of
other attributes in the Continuation but I’ll leave that as an exercise for
the reader; I’ve done enough for you, do it yourself :)
Summary
Ok, this is kinda cool, but why do it? Clearly the output code isn’t nearly as pretty as what we started with. There are occasions where this could be extremely useful. If you were sorting large lists and doing something with a UI thread that needed attention, you could have quicksort run for some number of iterations, and return a continuation to restart it when you came back to it. You could use this to implement a simple for of coroutines. Or if you’re working in a single-threaded event loop, this can give you a way to suspend the computation. Lastly, if you’re on a machine without a whole lot of stack to play with, this can definitely make it work.
So do you need it often? Nope. It it really cool? Oh yeah! I have a feeling that this may be the kind of thing you don’t know you need until you know it exists. Not nearly to the extent like lambdas, but still.