Using CPS for semi-automatic fusion

Usually when I find myself writing a pipeline like this:

|> fun that produces intermediate data
|> same
|> ...

where the data isn’t lazy, I resort to either converting it to a lazy form (via an external library like iter if it’s already pulled), specifically designed to let the compiler fuse it, or rewrite the pipeline, manually “fusing” it, to just one big recursive function.

One day early on my learning journey I’d come across a blog post that suggested a third option: CPS. The changes to the functions were minimal, if they were changed at all (my current understanding of CPS suggests they need to be changed to pass the thunks across computations, but maybe the blogger did something smarter). The transformation was more-or-less purely mechanical. It was used to compose the functions replacing the reverse-apply operator (as opposed to creating a common data structure).
At the time this transformation was way over my head, and I made the terrible mistake of not bothering to bookmark the blog post. Now, though, I feel like I understand CPS better – at least the basics, so I set on to hunting for that post and learning what it has to offer. The code examples were written in OCaml too!
So far, unfortunately, no dice. Have you good folk come across it?

1 Like

I’m not sure if this is the exact blog post you ask for (probably not), but I guess it is close enough because it uses delimited continuation (coroutines) for generators (lazy streams that can fusion), and it has an OCaml implementation (however, it seems this implementation only uses OCaml’s exception mechanism).

There might be other posts about similar subjects at Oleg Kiselyov’s website.

1 Like

It’s not the one, but an interesting read nonetheless!

Gagallium : Generators, iterators, control and continuations ?

That’s not the one either… It’s where I first learned about defunctionalization though!