Tue Mar 16 11:53:13 CET 2010


Feldspar[1] looks like an interesting project to follow.  Very close
to things I've been trying lately.  In [2] it is said they follow a
``deep embedding'' which means that the result of evaluation in the
host language is a syntax tree instead of a computation.  For Feldspar
this is then compiled further, or interpreted.

Fusion works by "Representing vectors by their index function".  It
takes the following form for the definition of map:

    map f (Indexed 1 ixf) = Indexed 1 (f . ixf)

I.e. the function f is moved inside the loop.  [2] : "... map
... results in a new vector ... with a different index function.  The
new index function is simply the composition of f and the previous
index function ixf.

Aside from fusion, Feldspar generates non-optimized imperative code
that is postprocessed.

They target TMS320C64xx.

The paper also mentions SPIRAL and Silage as related work.

The main conclusion I draw here is that it doesn't seem to be so
difficult to map functional descriptions to imperative programs for
well-structured programs.  However, the devil is in the details: how
to direct the compiler to generate efficient code.  That part of
compilation is really complex.

[1] http://dsl4dsp.inf.elte.hu/
[2] http://dsl4dsp.inf.elte.hu/Feldspar-ODES8.pdf