Givens

abs :: a -> Acc a
rep :: Acc a -> a

   -- To simplify talking about transformations in these notes:
dimensions = constant (Z :. width :. height)

(With some type restrictions on abs. See the "Notes on types in Accelerate" for more information on these restrictions).

Transformation

Top-level

generateImage (toRGBF f) w h
  =>
genRGBF (interpretResult (run (generate dimensions (indexing2 (abs f)))))
        w h

General Transformations

abs (rep x) => x

abs (if b then t else f)
  =>
rep (cond (abs b) (abs t) (abs f))

x >= y   =>   rep (abs x >=* abs y)

x + y    =>   rep (abs x + abs y)

Recursion

Idea

Start by turning the recursive function into something that does one step of the recursion. In the general case, something like a CPS transformation will be necessary to turn everything into tail calls (and then lambdas would need to be eliminated somehow), but for the time being we will assume that we only have tail recursion (which is the case in the mandelbrot example).

Concretely,

go k (n, x, y)
  | n >= maxIters  = (0, 0, 1)
  | x*x + y*y >= 4 = (n/maxIters, 0, 0)
  | otherwise      = go (n+1, (x*x + y*y + scaledX), (2*x*y + scaledY))

becomes

go' k (n, x, y)
  | n >= maxIters  = (0, 0, 1)
  | x*x + y*y >= 4 = (n/maxIters, 0, 0)
  | otherwise      = k (n+1, (x*x + y*y + scaledX), (2*x*y + scaledY))

go      = fix go'
oneStep = abs . go' id . rep -- Note: We might want to write this in a pointful
                             -- style to avoid dealing with (.) unnecessarily.

(Note: I haven't type checked the definition of oneStep yet. The abs and rep could be in the wrong spot.)

Incidentally, HERMIT already has a command (fix-intro) which will perform this sort of transformation to fix automatically.

This seems very similar to the worker/wrapper transformations.

We can avoid potentially complicated matching-up of base conditions to base cases by running an extra step (this will be shown at the end of the section).

Now, we find all of the conditional branches in the original go where go is not free (since these cannot be recursive if go is not free in them). We can, for the time being, say that these are ultimately "remembered" as a function:

notCond = \(n, x, y) -> (n >= maxIters) || (x*x + y*y >= 4)

I suspect this will be the trickiest part.

Now we should be able to express this at each go call site

... (go initialValue) ...

using the Accelerate while like this

... (oneStep (while (not . notCond)
                    oneStep
                    initialValue)) ...

Here, the outer oneStep application calculates the value for the appropriate base case.

If nothing else applies...

abs f => abs (... {inlined f} ...)

Then try to continue with the transformation. If nothing applies again and nothing is of the form abs f where f is an identifier, then terminate. If f cannot be inlined, also terminate.