Galois Connections submitted an entry to the ICFP programming competition.
Here are some notes about our entry.
* Completeness
- It provided a solution to the Tier 3 requirements.
* Language
- It was written completely in Haskell98, compiling in Hugs and GHC-4.08.
- It was around 2000 lines of new Haskell and around 500 of library code
(the Parsec parsing library).
* Optimizations
- We use various algorithmic optimizations, including bounding boxes.
- We obtained respectable speeds by also doing Haskell specific
optimizations.
We first profiled to identify bottlenecks, and then
- used inlining pragmas (these are inside comments, so are ignored
by Hugs).
- used strict fields in our key structures.
- used the -funbox-strict-fields
The final C code for matrix multiplication did no boxing/unboxing,
but was straight-line multiply and adds.
* Speed
- We ran the sample inputs in a few seconds per picture.
For example, fib.gml ran in less than 7 seconds on my 650 Mz laptop.
* Correctness
- We used Quickcheck to test some optimized matrix implementations.
- We used strong typing to catch the differences between Points,
Matrixes and Vectors, as well as in many other places.
- We also wrote (in Haskell) a ppmdiff command, that
let us compare our output with the published output.
* Evaluator
- We used our evaluator with three different monads.
(1) Top Level - This uses the IO monad, and can call render.
(2) Callback (surfaces) - This uses a monad called Pure, that can only
call pure functions. Attempts to call render give an error.
(3) Symbolic Evaluation - We also have an Abs monad, that runs with
abstract symbols, which are run for a finite time to see if a
surface function will return constant values.
- We added an extra command 'trace' (in our local copy), that helped
us debug our GML, especially callback usage.
- The evaluation had lazy semantics :-)
* Extras
- We implemented anti-aliasing but did not turn it on by default,
because the judges were doing binary diffs.
We plan to make available our source code at some point in the future.
Hope this answers your questions,
Andy Gill
Galois Connections
