An illustration of the Eureka phenomenon is described in
Barasch and Page, "Parallel computation, functional programming, and
Fortran 8x", Hypercube Multiprocessors 1986 (Michael T. Heath, ed.)
SIAM, 1986, 57-69
In this case, it amounted to a reversal in the order of nested loops
that wasn't spotted in the original code.
The following paper discusses the transformational approach and gives
an example of generating a clean and simple presentation of the
computation that John mentions in his note (35,000 Fortran code,
rethought from scratch and expressed in a 9000-line, literate
Miranda code), with plans (never carried out) to convert back to
vector Fortran.
Moe and Page, Experience with a large scientific application in a
functional language, Proc 1993 Conference on Functional Programming
Languages and Computer Architecture, Copenhagen, Denmark (June 1993)
On the negative side, my experience was that it's a real struggle to
get the people in charge of scientific computing (physicists,
chemical engineers, etc.) to believe there might be some value in
changing programming languages. The Sisal people will confirm this,
I think.
I concluded that effort invested in making functional languages
more accessible (good tools, GUI support, education and training,
sneaking in the side door like Pizza, ...) would contribute more
towards increasing the use of functional languages than attacking
the high performance area.
Rex Page
__________________________________________________________________
On Fri, 16 Oct 1998, John O'Donnell wrote:
>
> There's another way to look at the role of Haskell in scientific computing.
> All the discussion so far is assuming that (1) you write your program in
> Haskell, (2) you run it through a compiler, (3) you compare the speed with
> Fortran, (4) you sigh and give up...
>
> In this picture, Haskell is being used to express the algorithm at just one
> level of abstraction. Now, Fortran is a very limited language, and it's only
> capable of expressing one level of abstraction. But Haskell does *not*
> have that limitation!
>
> So there is another way to use functional languages: they can help you to
> express your algorithm cleanly and simply, and they can also help you in
> deriving a more efficient low-level version via program transformation. If
> you like, it's possible to transform the program all the way down to C or
> Fortran, and at that point you don't need a Haskell compiler or graph
> reduction at all - you just use the Fortran or C compiler.
>
> Naturally, this transformational approach doesn't help if you start out
> thinking of the algorithm in a low level, first order style with lots of
> imperative iterations over arrays. In such cases one might as well just write
> the program in Fortran to start with.
>
> However, there are some algorithms that are very difficult to write in Fortran
> or C, but which can be expressed much more clearly and simply in a functional
> style. (A good example of this is the hierarchical radiosit algorithm.) You
> can write a high level executable specification, using Haskell and ghc; if the
> performance is inadequate, then you can transform the program to a lower
> level. The crucial point here is that the transformations are not aimed at
> getting rid of inefficiencies caused by graph reduction or the like; the
> transformations are aimed at making the algorithm fit better onto the
> underlying architecture.
>
> One apparent problem with the transformational approach is that it's a lot of
> work. Isn't it easier just to write your program once, in a language that
> supports only one level of abstraction, and compile it? I think this is a
> valid criticism (after all, *I* am the one raising it!) but there are two
> counterarguments:
>
> -- some of the transformation steps required are straightforward and
> boring, but there may be the possibility of automating these. After
> all, even the ghc compiler is a transformational system `under
> the hood'. Full transformational automation has not been achieved
> yet, but work is underway.
>
> -- For some algorithms, insight is needed to transform down to a
> low level efficient implementation: "Eureka steps". It is
> unrealistic to expect a compiler to find Eureka steps, but the
> transformational approach may make it possible to automate the
> boring steps while allowing the programmer to insert clever
> insights. You can't do this with compilers, and you can't do
> it with languages that can express algorithms only at one level
> of abstraction.
>
> John O'Donnell
>
>
