What is Expressiveness in a Computer Language

[Greg Buchholz]

George Neuner wrote:
> That was interesting, but the authors' method still involves runtime
> checking of the array bounds.  IMO, all they really succeeded in doing
> was turning the original recursion into CPS and making the code a
> little bit clearer.

    Hmm.  There is a comparison in both the DML and Haskell code, but
that's just there to make the binary search terminate correctly.  The
point of the exercise is the line in the DML code "val m = (hi + lo)
div 2", or the "bmiddle" function in the Haskell code.  If you change
that line to something like "val m = (hi + lo)" you'll get a compiler
error complaining about an unsolved constraint.  The point of the
Haskell code is to use the type system to ensure that array indices
have a know provenance.  They're derived from and statically associated
with each individual array, so you can't use an index from one array
with a different array.  You'll probably also enjoy the paper...

    "Eliminating Array Bound Checking Through Dependent Types"
    http://citeseer.ist.psu.edu/xi98eliminating.html

...and DML itself...

    http://www.cs.bu.edu/~hwxi/DML/DML.html

Greg Buchholz