[raphlinus]

Thanks for the reference, it's definitely relevant. I took a pass over the paper somewhere between skimming and reading, and, while it's definitely in the ballpark of deriving parallel programs from sequential, it's also pretty clear their source language can't express the stack monoid problem because it lacks a "cons" operation; basically it seems to be for various fancy reduction problems where it consumes a sequence and spits out a scalar. On a quick read, I have no idea whether that's a fundamental limitation or something that could be extended.

I think examples like generating mergesort from insertion sort are maybe trying to be too clever. I mostly just want something that lets you slice up the problem into chunks, process each chunk in parallel, then combine them back in ways that don't kill performance on modern GPU hardware.