ideas for compiler project

[Bjorn Lisper]

Simon:
>Lots of people have observed that Haskell might be a good "scripting
>language" for numerical computation.  In complicated numerical
>applications, the program may spend most of its time in (say) matrix
>multiply, which constitutes a tiny fraction of the code for the
>application. So write the bulk of the application in Haskell (where the
>logic is complex but the performance doesn't matter) and then link to a
>C or Fortran library to do the small part that is really compute
>intensive.

>More concretly, suppose you built an FFI interface to BLAS or some
>readily available numerical library, and then demonstrated the utility
>of the resulting beast by writing some non-trivial numerical application
>in it.  

This is an interesting idea that I think can be made to work to some
extent. One issue will be to find the right tradeoff between stateful and
purely functional, i.e., allowing nice matrix-algebra based expressions
while ensuring that memory can be reused to the extent necessary. If all
matrix operations are wrapped up in some state monad, then you lose the nice
matrix algebra style. If, on the other hand, you have no way to express
updating, then you lose memory reuse (unless you have a *really* smart
compiler...).

The best tradeoff is probably to mimic a small imperative language with
clean, side effect-free matrix operations, where updates are effectuated by
explicit matrix assignments. Of course, this is possible only if the BLAS
routines are side effect-free themselves our can be wrapped up as such.

It is interesting to note that MATLAB started out exactly as a convenient
scripting language for a Fortran matrix library. MATLAB is a system for
matrix computing that contains nice graphical possibilities and a matrix
programming language. It is very popular in engineering, and is widely used
for applications like signal processing, automatic control, and PDE solving,
in particular in the early prototyping phase. Its popularity does not stem
from its speed, since it's quite slow, but rather from:
- nice graphics capabilities (plottings, etc)
- convenient matrix language (to some extent, I would add), and
- above all, lots of "toolboxes", i.e., MATLAB software wrapped up for
  various applications (simulation of control systems/signal processing,
  etc.) There is a big third-party market for this kind of software.

I think MATLAB's matrix language provides about the right level of
abstraction for a high-level matrix language. You can for instance write
things like

Y = inv(A)*B

to assign to Y the solution of Ax = B. To some extent this is what you'd
like to have, On the other hand, a closer look at the language will reveal
that it has many strange and ugly semantical corners, where the
imperativeness shines through in nasty ways. This is a hindrance to
optimizing compilation, since good optimization of matrix code requires
extensive reordering transformations. Also, MATLAB is very ill-suited to
expressing block-recursive matrix algorithms, which are becoming
increasingly important in numerical computing. And, of course, there is no
decent type system, no higher order functions, etc...

So, I think it could be interesting to embed a purified version of MATLAB's
matrix language in Haskell. This would be interesting as a demonstration of
what a good matrix language could look like, but don't expect to be able to
sell it to the world since the competitors are far ahead in all other
aspects.

>You'd need to find a "real" application though. 

There are plenty. Signal processing, automatic control, PDE solvers,...

>The classical "kernels"
>(matrix multiply, inversion etc) are precisely the things you may not
>want to do in Haskell.

With the current compiler technology for Haskell, one would add. I don't
think it would be impossible to compile such Haskell programs into efficient
code. Functional languages for matrix/array computing was a quite active
research area 10-15 years ago, with efforts like Sisal and Id. These
languages were strict and first order, but you can write such programs in
Haskell. I think it would be possible to have a Haskell compiler that could
manage a subset of Haskell matrix programs quite well. (Christoph Herrmann
did some interesting work in this direction: Christoph, you're reading this
list aren't you?) Whether it would be worth the (big) effort is another
matter.

Björn Lisper