Lambda the Ultimate

Starting from the beginning of CLRS, we have sorts of various kinds. The pseudo-code expresses sorts with loops and arrays. So, when the text says here's the general expression of a bubble sort, what is really shown is an imperative algorithm that uses mutable cells. Nothing wrong with this technique, as the algorithms are highly optimized. But there are other data structures that can be sorted. And the algorithm that works great for arrays, isn't necessarily good when applied to lists. The expression of the algorithm in recursive form can be informative. And there is not really a need to resort to state in all cases (hence, monads need not be applicable). Sorts can be expressed in both functional and imperative languages without need of state.

The pseudo-code language that is used in CLRS is strictly an imperative language. Fortunately, the analysis techniques extend beyond imperative algorithms and can be applied to algorithms in the more general sense. Because the pseudo-code is biased toward imperative languages, I would say that their language does not really capture the fundamental nature of the underlying algorithms. So the goal of avoiding any particular language is somewhat negated because it assumes a PL of a particular type.

What I'd like is to find an algorithms text which expresses a fairly wide swath of algorithms in declarative, functional, imperative, etc... styles. Texts like CTM and SICP come closer, but I don't know that they can be described as exposition on algorithms.

Because the pseudo-code is biased toward imperative languages, I would say that their language does not really capture the fundamental nature of the underlying algorithms.

Can an algorithm be separated from its computational model? Offhand I would say no, in which case it's not clear to me that algorithms even have a "fundamental nature" in the sense your quote suggests.

Since we are dealing with algorithms, I figure what better way than to pick an example - let's run with MergeSort. Here's the MergeSort as defined in the pseudo code of CLRS:

% MergeSort in CLRS
Merge(A, p, q, r)
   n1 ← q - p + 1
   n2 ← r - q
   create arrays L[1..n1 + 1] and R[1..n2 + 1]
   for i ← 1 to n1
      do L[i] ← A[p + i - 1]
   for j ← 1 to n2
      do R[j] ← A[q + j]
   L[n1 + 1] ← ∞
   L[n2 + 1] ← ∞
   i ← 1
   j ← 1
   for k ≤ p to r
      do if L[i] ≤ R[j]
         then A[k] ← L[i]
              i ← i + 1
         else A[k] ← R[j]
              j ← j + 1

MergeSort(A, p, r)
   if p < r
      then q ← ⌊(p + r)/2⌋
           MergeSort(A, p, q)
           MergeSort(A, q + 1, r)
           Merge(A, p, q, r)

So, I took that and implemented it in fairly literal form in Oz:

% MergeSort in CLRS ported to Oz
Infinity = 999999999

proc {Merge A P Q R}
   N1 = Q - P + 1
   N2 = R - Q
   Lx = {NewArray 1 N1+1 _}
   Rx = {NewArray 1 N2+1 _}
in
   for I in 1..N1 do
      Lx.I := A.(P+I-1)
   end
   for J in 1..N2 do
      Rx.J := A.(Q+J)
   end
   Lx.(N1+1) := Infinity
   Rx.(N2+1) := Infinity
   local
      I = {NewCell 1}
      J = {NewCell 1}
   in
      for K in P..R do
         if Lx.@I =< Rx.@J then
            A.K := Lx.@I
            I := @I + 1
         else
            A.K := Rx.@J
            J := @J + 1
         end
      end
   end
end

proc {MergeSort A P R}
   if P < R then
      local
         Q = (P + R) div 2
      in
         {MergeSort A P Q}
         {MergeSort A Q+1 R}
         {Merge A P Q R}
      end
   end
end

Lifting code from CTM, I see a merge sort for lists that does not require state:

% MergeSort in CTM
fun {Merge Xs Ys}
   case Xs # Ys
   of nil # Ys then Ys
   [] Xs # nil then Xs
   [] (X|Xr) # (Y|Yr) then
      if X<Y then X|{Merge Xr Ys}
      else Y|{Merge Xs Yr}
      end
   end
end

proc {Split Xs ?Ys ?Zs}
   case Xs
   of nil then Ys=nil Zs=nil
   [] [X] then Ys=[X] Zs=nil
   [] X1|X2|Xr then Yr Zr in
      Ys=X1|Yr
      Zs=X2|Zr
      {Split Xr Yr Zr}
   end
end

fun {MergeSort Xs}
   case Xs
   of nil then nil
   [] [X] then [X]
   else Ys Zs in
      {Split Xs Ys Zs}
      {Merge {MergeSort Ys} {MergeSort Zs}}
   end
end

What I am saying is that we have two different implementations of MergeSort. One that utilizes arrays and mutable cells, and another that uses lists and single assignment variables. The fundamental algorithm of merge sort should be able to be somewhat independent of the data structure (hence the drive to generics in PLs) and be capable of telling us the common methodology that is used in the two specific instances of MergeSort. Abstract Data Types and operations on those ADTs is the name of the game. Generic operations that apply to any number of ADTs is the push in the functional PLs. CLRS makes no attempt to define MergeSort in a functional style. Indeed, mutable cells are used in practically every algorithm defined in pseudo code.