Mon May 10 15:54:54 EDT 2010

Lifting and combinators

Summary remarks from previous posts:

  - Implementing loops is necessarily a syntax-oriented approach
    (i.e. working on the Procedure or Term data types), since there is
    no way to do this purely from semantics : the high-level
    combinator structure gets lost through code duplication, and just
    the atomic data dependencies are left over.

  - What should be possible is to write these combinators in such a
    way that they can be lifted to the original function space to
    apply them to the opaque functions, i.e. there's a functor that
    maps from combinators on syntax to combinators on functions.

Now, can we turn this around by defining functions to operate on
abstract representations of containers and using loop fusion to derive

Currently (for the music DSP app) I'm only interested in 2 kinds of
combinators: parallel vector map i->o lifted to [i]->[o], and
sequential state machine execution (s,i)->(s,o) lifted to

The former is simple to do (see Feldspar [1]).  The latter requires
some way to define the unit delay 'Z' on abstract containers, probably
a modification of the fusion law in [1].

Conclusion: find a way to represent fusion.

The abstract container type should be guided by the implementation of
'Z'.  I.e. whenever Z occurs in a term, it has to be a sequence type,
or a type associated with a past?

So, let's start with defining Indexed as a functor with:

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

import Ai

data Indexed a = Indexed (Int -> a)

instance Functor Indexed where
    fmap f (Indexed ixf) = Indexed (f . ixf)

instance Show a => Show (Indexed a) where
    show (Indexed ixf) = show $ map ixf [0..10]

i0 :: Indexed Float
i0 = Indexed (\n -> [0..] !! n)
i1 = fmap sin i0

t0 :: Indexed (Term Float)
t0 = Indexed (\n -> var ("a[" ++ show n ++ "]"))
t1 = fmap sin t0

*Main List> t1
[(sin a[0]),(sin a[1]),(sin a[2]),(sin a[3])]

The fusion law is the main trick to abstract vectors into element
references.  The insight that Indexed doesn't really need to be a
function from Int but an abstract rep is the main bridge to AST

Next: how to define Z on Indexed?  Looks like Z needs to be a property
of the data type - much deeper than simply feeding "-1" into the index

[1] entry://20100316-115313