How we talk about algorithms

It's often the case that a programmer can quickly state the algorithm they want to use to solve a problem, but it takes significantly more time to cobble together the implementation. There are lots of good reasons why it has to be that way -- explaining something in English presumes an intelligent listener, but the computer you're programming to is not intelligent. But still, I'm wonder if part of the mental transformation that takes place is a conceptual restrucuring, that wouldn't be necessary if a computer language were structured differently.

A good way to look at this might be to examine some programs along with descriptions of their algorithms, and see if we can discern any structural differences, and propose new computer language structures that are closer to the human abstraction mechanisms.

So I want to take as a particular example the "BLACK" problem from this year's ICFP 2006 programming contest. After the end of the contest, participants discussed their solutions to some of the problems, and in some cases posted their code, in a public discussion list. As this was a problem I spent some time with (and didn't solve) I decided to look at the algorithms that other teams used.

Spoiler alert

The contest puzzle was an amazing construction that I'd highly recommend working on, even though the contest is over. I'll be giving away the problem description here (which is a good piece of work just to get to), and some solution algorithms.

The Problem

The problem is described here; basically you're doing a permutation of an ordered list, in steps, where each step can exchange pairs of adjacent items. When a step shifts any item to the right, there is a "plink" sound. There's no sound when shifting to the left. The task is to recreate the steps needed, given an ending permutation and the number of plinks each item would experience in tracing through the steps. So the first problem they provide looks like this:

* x -> (y,z)
* Means that if you drop a marble into pipe x, it comes out pipe y,
* and you hear z plinks
0 -> (3,4)
1 -> (2,3)
2 -> (0,1)
3 -> (1,1)

And one solution is this:

><||
|><|
><><
|><|
><><
><><

Where the ><'s represent swaps, and the |'s represent items that don't change in that step. The problem set started with this puzzle of width 4, and also included problems of width 10, 20, 30, 40, 50, 100, 200, 300, 400, and 500. Your score was based on submitting solutions; the code was not considered -- solving by hand was perfectly legal, if impractical for the larger problems.

Notation

I'll use this notation in the discussion below:

• In{st}[x]: the xth hole going into step {st} of the machine (numbering starting with 0)
  
• Out{st}[x]: the xth hole coming out of step {st}.
  
• Target{st}[x]: the desired destination of a marble placed at In{st}[x]
  
• Plinks{st}[x]: the plink count of a marble found at In{st}[x]
  
• Plinktarget{st}[x]: the desired plink count of a marble found at In{st}[x]
  
• Step{st}: The string of |'s, <'s, and >'s representing step #st of the machine
  

Solution Strategies

I studied the descriptions of solutions on the mailing list, and on the web pages of participants if they were linked from the list archive.

Divide and Conquer

The first insight that most solvers shared was a division into two sequential phases. As stated by Alain Frisch:

All the puzzles in the contest had a lot of plinks, [...] and it was indeed possible to first bubble sort the wires and then start from the identical permutation. That's what our team's solver does.

Jed Davis wrote:

Mine likewise -- it first does the usual selection sort, then figures
out what combination of maneuvers like that pictured above (moving a
ball N places to one side and then back) need to be placed after the
sort to reduce the remaining needed plinks to a form that can be handled
by appending only double-swaps.

Marcin Mucha wrote:

I guess you know that, be some puzzles do have solutions, but you can't decompose any solution as a sequence of a bubblesort and a solution starting from an identical permutation.

It's interesting that they all emphasize the sequentiality; the two phases can' t be done in parallel. Frisch says "to first xxxxxx and then yyyy"; Davis wrote "first xxxxxxx, then yyyyyy". Mucha uses the word "sequence". In your typical imperative language, simply listing two steps in order is sufficient to say "do one, then do the other"; this explicit statement of ordering suggests that sequentiality is not necessarily the default in English.

The Bubblesort

In two of the three quotes above, the posters mention bubblesort with the implied presumption that its application is obvious. Bubble sort is an apt description of an algorithm realizable by this type of machine, since every swap is done between adjacent elements. Here is the code Wikipedia gives for bubblesort:

function bubblesort (A : list[1..n]) {
 var int i, j;
 for i from n downto 1 {
     for j from 1 to i-1 {
         if (A[j] > A[j+1])
             swap(A[j], A[j+1])
     }
 }
}

A reasonably adept programmer should be able to read the description of the problem, and the vague advice to "apply a bubblesort", and implement it with some thought, but without any further clarification. They are making a conceptual mapping like this:

List parameter A

Mapping from exit hole# of current step to exit hole# of final step

n

The number of pipes in the machine

A[j] > A[j+1]

Pipe at j at this step is destined to a place further to the right of pipe at j+1

swap(A[j], A[j+1])

A pipe crossing is added

...so substituting the notation above, we have something like this:

function bubblesort (Dest{st}) {
 var int i, j;
 st = 0
 for i from n downto 1 {
     for j from 1 to i-1 {
         if (Target{st}[j] > Target{st}[j+1]) {
             Target{st+1}[j] := Target{st}[j+1]
             Target{st+1}[j+1] := Target{st}[j]
             st ++
         }
     }
 }
}

This is an interesting mapping because the paradigmatic bubblesort involves mutable storage, but this version builds a list of successively refined permutations. Wikipedia of course doesn't define bubblesort this way. Programmers can make this leap with some thought. Can the concept of "bubblesort" be defined such that something so fundamental is abstracted away? I'm still wrapping my brain around monads, but I think this is what they are good for.