[Haskell-cafe] Functional programming for processing of large raster images

[ajb at spamcop.net]

G'day all.

Quoting oleg at pobox.com:

> Recently Vo Minh Thu wondered if Haskell (or, I generalize, functional
> programming) can be of much use for computer graphics programming.

As others have pointed out, it's Haskell (and its laziness) that he
perceived to be the problem.

However, I'd like to take the discussion up one more level.

I hope that Thu doesn't mind me saying this, but off-list, I got a
better idea of the program that he was trying to write.  He's not
interested writing an image processing system.  In that sense, raster
images are actually not a central data structure.

The scenario is quite typical:

    - A decent, ambitious idea about a program or suite of programs
      that someone would like to write.

    - A good idea about how to write something simple to start with,
      at least as a proof of concept, possibly to be refactored into
      something more sophisticated later.

    - Some thinking, exploratory code or back-of-the-envelope playing
      around reveals some data structure to be extremely important to
      get right for the simple system, even though it's likely to
      play a small, non-central role in the "real" system.  There's no
      obvious, clean, efficient way to implement this data structure in
      Haskell.

I think that a lot of people here have been in precisely this position.
Often there's a good substitute (e.g. I'll wager that a lot of GHC had
already been written before FastPackedString became necessary; String
turns out to be fine to start things off), but sometimes there isn't.

I have a suspicion that this is related to an old complaint, namely
that programmers are trained to think about algorithms and data
structures and not so much about APIs.

An efficient algorithm or data structure is indeed a fine thing.  But
for 99.9% of cases, for overall program efficiency, nothing beats a
well-designed API.  If your program has an efficiency problem, you
simply remove the offending code and put in new code which conforms to
the same API.  As if by magic, everything works much as it did, only
more efficiently.

This advice is triply important for a data structure or algorithm which
may not play a central role in the final program.

Now I don't know if there are any decent references on API design.
This gives the general idea, though:

    http://lcsd05.cs.tamu.edu/slides/keynote.pdf

With my agile programming hat on, however, I'd argue that if you're
writing an application (as opposed to an ISO standard), the most
important thing is to write something, anything, that WORKS and put
it behind a very thin API layer to start with, even if it's a quick
and dirty choice of implementation.  Both the implementation and the
API can be changted as it needs to, and simply having the API there
(even if it's bad) will encourage you to modify said API instead of
digging into the innards of what you're trying to protect.

Eventually, you'll find the true set of operations that you need.

(If you are writing an ISO standard, of course, then you need to take
more care.  The "rule of threes" states that a) you need to examine at
least three systems to find out what you need in the API, and b) you
need to use the API at least three times to ensure that it's reusable.
Nobody claimed this stuff was easy.)

> In this project, functional programming does what it is probably best
> suited: to develop a `compiler' -- a compiler from a filter
> specification to quite efficient code.

Or, in even more generality:

    http://c2.com/cgi/wiki?AlternateHardAndSoftLayers

Functional programming is great for implementing the "soft" layers where
the smart and flexible bits lie.  It may not be as great for implementing
the "hard" layers where the dirty bit hackery and tight loops lie (though
it might be okay for prototyping that part).  Over time, anything in the
soft layer which turns out to have efficiency issues can migrate to the
hard layer as required.

As Henry James famously pointed out, "all writing is rewriting".  That's
especially true of software.

Cheers,
Andrew Bromage