Deforestation pass

[ordinarymath]

CakeML currently does not have a deforestation pass. We would probably improve on benchmarks once this is implemented.

[ordinarymath]

For implementation I'm considering

1. Add primrec combinators as a primitive operation.
2. Add a pass which detects primrec functions and rewrites them to use the combinators.
3. Implement a simplication pass that merges combinators.
4. Implement a pass that removes the combinators. This is essentially shortcut deforestation + warm fusion. https://dl.acm.org/doi/pdf/10.1145/224164.224223 This would remove the difficulty with doing higher order inlining.

[oskarabrahamsson]

The language in the paper is lazy and pure. Will these rewrites hold in a strict language with side effects?

[ordinarymath]

I don't think the algorithm would work out of the box and need to be changed.

[oskarabrahamsson]

I think you should consider targeting purecake with this sort of thing, and not CakeML. The reason is that I suspect that these sort of rewrites enable things like

map f o map g = map (f o g)

To get something like this in CakeML, you first have to establish that f, g, and map are pure and total. It seems like a hassle to implement an analysis that does this well.