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. You'd need to find a "real" application though. The classical "kernels" (matrix multiply, inversion etc) are precisely the things you may not want to do in Haskell. Simon | -----Original Message----- | From: Hal Daume III [mailto:hdaume@ISI.EDU] | Sent: 22 January 2002 22:00 | To: Haskell Mailing List | Subject: ideas for compiler project | | | Hi All, | | I'm currently taking a class in compiler optimization for | high performance computing (i.e., parallel architectures, | including VLIW, FPGA, multimedia extension architectures, | systems-on-a-chip, etc). It's the second of two graduate | level compiler courses, and it purely project based. And the | project is of our choosing. | | The professor has made some suggested projects, which I could | do, but none of them are really FP specific. I'm curious if | anyone has any ideas of a project I could do. I'm looking | for something that's open, yet | constrained, etc (standard semester-long-project-course | stuff), hopefully having to do with optimizations | specifically for FPLs, or at least ones that would benefit them. | | I'm open to all ideas... | | - Hal | | -- | Hal Daume III | | "Computer science is no more about computers | hdaume@isi.edu | than astronomy is about telescopes." -Dijkstra | www.isi.edu/~hdaume | | | _______________________________________________ | Haskell mailing list | Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell |
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
On Thu, Jan 24, 2002 at 03:38:59PM +0100, Bjorn Lisper wrote:
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. ...
Just a comment on a long post... I am personally found of MetaFont's approach, where you write Ax = B to find the solution to Ax = B. When working with transformations and such, being able to write all your equations "forwards" makes it much easier to keep everything straight; plus, if you have several equations for a variable, you don't have to figure out how to gather them together. Can anyone see a way to implement something like this in Haskell? Or is it better to make a small interpreted language? Best, Dylan Thurston
On Sat, 16 Feb 2002, Dylan Thurston wrote:
On Thu, Jan 24, 2002 at 03:38:59PM +0100, Bjorn Lisper wrote:
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. ...
Just a comment on a long post... I am personally found of MetaFont's approach, where you write
Ax = B
to find the solution to Ax = B. When working with transformations and such, being able to write all your equations "forwards" makes it much easier to keep everything straight; plus, if you have several equations for a variable, you don't have to figure out how to gather them together. Can anyone see a way to implement something like this in Haskell? Or is it better to make a small interpreted language?
Best, Dylan Thurston
why not write some software that does something like let y = ((Matrix A) :*: (Vector X)) := (Matrix B)) data MatrixExp = ... data Sym = A | B | C ... data Unknown = X | Y ... solve :: MatrixExp -> Maybe (Vector Sym) ... ? Jay Cox
Simon Peyton-Jones:
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. ... You'd need to find a "real" application though. The classical "kernels" (matrix multiply, inversion etc) are precisely the things you may not want to do in Haskell.
That's it. With one "grain of salt". It happened to me that I wanted to write some structurally trivial routines for matrix inversion, iterators for ODEs, etc., but I wanted them *polymorphic*. (And, sometimes, lazy: manipulators of power series, asymptotic expansions, some automatic dif- ferentiation stuff, etc.) Then Haskell was a decent tool, and - as Björn Lisper remarks, the hindrance was the lack of integrated tools. Writing a triple loop to invert a matrix instead of having something like `recip` defined within the field of square matrices, and implemented with some efficiency considerations in mind, is a bit clumsy. Björn quotes and comments:
The classical "kernels" [...] 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.
Steven Bevan wrote interesting numeric routines a long time ago. Thorsten Zoerner wrote a Clean package Class with several Lin. Algebra and some "slicing" utilities, which emulated the "vectorized" approach of Matlab. This can be in its greater part translated into Haskell. --- But, please, some criticisms of Matlab are weakly justified. BL says:
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...
Block recursive Schemes in Matlab are easier than in C++. Implementing pyramid algorithms is not difficult. Slicing, reshaping, cloning, etc. of matrices are very powerful tools, but they are so imperative, that it is not easy to see how to replace them with something "functionally purified". The Matlab type system is dynamic and "indecent", but you have objects and inheritance, and you *HAVE* higher-order functions as well. All the Matlab GUI tools, very powerful and reconfigurable are based on objects, which accept callbacks as parameters. This is not so clean as we would like to have, but pragmatically OK. What bothers me a bit in our Haskell world is the fact that the efforts are atomized. People work on GUIs, and don't care about drawing/painting routines. Those who care, are often far away from the numerical world. The numerically-oriented folk often disregard with a lot of desinvolture the attempts to put the Haskell numerical classes in an abstract algebraic framework (really useful from the point of view of code reusing), etc. I have the impression that this is changing, but slowly, while the scientific computation/visualization world is marching very fast, not only in the direction of very-fast-even-more-dirty routines, but also in the direction of new conceptualization/representation models (like, e.g., "actors" in VTK). Jerzy Karczmarczuk Caen, France
Jerzy Karczmarczuk writes:
Steven Bevan wrote interesting numeric routines a long time ago.
Actually I did little more than transliterate the algorithm descriptions I found in a book on numerical analysis. I know next to nothing about numerical analysis so I have no idea if they are interesting or useful. Implementing them was a pleasant diversion from what I was supposed to be doing at the time :-)
participants (6)
-
Bjorn Lisper -
Dylan Thurston -
Jay Cox -
Jerzy Karczmarczuk -
Simon Peyton-Jones -
Stephen J Bevan