> His trick is to ask the audience to give a non-recursive version of Quicksort, and of course everyone starts trying to remove the recursion, for example by making the stack explicit or looking for invertible functions in calls. But his point is that recursion is not at all fundamental in Quicksort.
I'm not completely sure what distinction Meyer is trying to draw between the implementation he discusses, and "making the stack explicit". He ends up with a "set" of intervals that he pushes onto and pops from, which might as well have been a stack of arguments.
Is the point that the order you pull things out of the set doesn't matter, so demanding that it behave as a stack is overly prescriptive?
Watching the source lecture[0], it's not about how the code is written so much as how the function is specified. It's easier to describe quicksort as a few set equations without invoking the concept of recursion, but since we don't write code like that people can't get to it easily.
The nuts-and-bolts difference is in fact that it's a set and not a stack, but the underlying question is, why do we all treat the set implementation as the derived version?
> since we don't write code like that people can't get to it easily.
I've lately been trying to write code with no recursion - as in able to be implemented with each function having a variable indicating where to return to, no implicit stack in sight. (Statically-determinable stack size, to put it another way.)
It took me a bit to get the hang of, but I'd argue that it ends up being easier in the long run. Far easier to change the priority operator on your queue than trying to reason what behavior different orders of recursion get you, for example.
Ditto with graph search algorithms. It's enlightening to teach graph search algorithms as a single algorithm with a queue, where changing the priority gives you Dijkstra's algorithm (least cost first), DFS (LIFO), BFS (FIFO), A* (current cost + underestimating huristic of cost left), or whatever. Also easy to show that A* degenerates into Dijkstra's algorithm when you use a null heuristic (i.e. a heuristic that returns a constant) if you teach them as variants of the same algorithm.
> but since we don't write code like that people can't get to it easily
which likely sums up what Lamport is trying to get across - express your work equationally, determine properties and generally understand what you're dealing with and then later, you can 'compile your equations' down to a particular implementation.
from my own practice, i've found that it is much easier to reason about equations and reflect it down into code than to try and reason about the code
Yes, that's the principal idea, I think -- separating out the implementation details from the actual conditions that are necessary for correctness. IIRC, I've seen another presentation of this where the author used that freedom to implement a work-stealing quicksort across multiple threads.
Is the point that the order you pull things out of the
set doesn't matter, so demanding that it behave as a
stack is overly prescriptive?
Right. In fact, there are several parts of the algorithm that are not really fundamental; one is how you pick the pivot, and another is how you perform the partitioning (ensuring that all elements before the pivot are less and all elements after are greater).
Lamport's point is that if you look at the fundamentals of the quicksort algorithm, which are that you must pick a pivot, partition such that smaller values come before and larger values come after, and then at some point later apply the same two steps to the two intervals [start, pivot) and (pivot, end].
Any algorithm that follows that specification will correctly sort the array, and then you can tweak exactly how you do that depending on your constraints. You could do it recursively, you could do it iteratively, you could divide it up into separate threads until you have one thread per processor each of which does the recursive or iterative algorithm on a private work list, you could do a worker pool in which each worker takes intervals from the set of remaining intervals to sort, etc. And likewise, you can tweak how you pick the pivot (picking the first element in the array is usually a bad idea, as it gives worst case behavior for already sorted arrays), and tweak how you perform the partitioning.
Anyhow, he didn't go into this kind of detail, he just pointed out that thinking about the fundamental specification can help get you away from the details of a particular implementation.
Of course, you can make the same point about many other algorithms - graph search, for example.
The nice thing about showing that arbitrary orderings still work is that you can, for example, do parallel sorting with work-stealing, where each thread tries to grab the smallest interval from its working set at each iteration (to minimize space requirements and to improve cache locality), but other threads try to grab the largest interval possible (to reduce the amount of locking as much as possible).
I'm not completely sure what distinction Meyer is trying to draw between the implementation he discusses, and "making the stack explicit". He ends up with a "set" of intervals that he pushes onto and pops from, which might as well have been a stack of arguments.
Is the point that the order you pull things out of the set doesn't matter, so demanding that it behave as a stack is overly prescriptive?