Let-insertion for template haskell

When using Template Haskell to generate programs it's very easy to end up with a lot of duplication as splices are naively spliced in place.

For example

foo x = [|| $$x + $$x ||]

Will generate a program which completely duplicates its argument. In this case I can manually remove the duplicate by inserting a let.

foo x = [|| let x' = $$x in x' + x' ||]

Not too bad but a bit annoying to have to do manually.

When constructing bigger programs however this process becomes tedious or impossible to do correctly by hand.

foo :: (Q (TExp (Bool)) -> Q (TExp Int)) -> Q (TExp Int) 
foo xf = [|| (let x = True in $$(xf [|| x ||])) + (let x = False in $$(xf [|| x ||]) ||]

Now if I pass a constant function to foo, the resulting code won't mention x so it could be floated out. However, there's not way I can tell that without running xf so I can't perform the same transformation as I did for the earlier program and manually insert a let. In the case of splicing in fully static data you really want it to float to the top-level and turn into a CAF.

The proposal of this ticket is to implement something like the mechanism for let-insertion in metaocaml.

http://okmij.org/ftp/meta-programming/#let-insert

We add two new primitives:

genlet :: Q (TExp a) -> Q (TExp a)
let_locus :: Q (TExp a) -> Q (TExp a)

genlet marks a code value that we want to float. let_locus marks places where we want to insert a let. When we evaluate the code fragment and encounter a genlet call, whatever the argument evaluates to is floated as far upwards as possible and inserted at the position of one of the loci.

For example,

sqr :: Code Int -> Code Int
sqr c = [|| $$c + $$c ||]

sqr_let :: Code Int -> Code Int
sqr_let c = let_locus (sqr (genlet c))

Splicing sqr [|| 1 ||] will result in 1 + 1 but sqr_let [|| c ||] will equal let x = 1 in x + x ||].

It's important to do this earlier rather than later as a lot of duplication can take place which the simplifier does not like.

Trac metadata

Trac field	Value
Version	8.6.3
Type	FeatureRequest
TypeOfFailure	OtherFailure
Priority	normal
Resolution	Unresolved
Component	Template Haskell
Test case
Differential revisions
BlockedBy
Related
Blocking
CC
Operating system
Architecture

changed weight to 5

added Tfeature request TemplateHaskell Trac import + 1 deleted label

mentioned in issue #16177 (closed)

Now if I pass a constant function to foo, the resulting code won't mention x so it could be floated out.

Is this really a common case?

Perhaps it is not common but it can become increasingly cumbersome to manually insert lets as your program gets more complicated. Another example is if your program generates a small list statically in many different places you just want this to float outwards. Manually let binding it requires adding additional arguments which makes the program more difficult to understand.

I think a proposal such as this would benefit from more eyes. Would you consider a ghc-proposal?

A note about the metaocaml implementation. That works by trying to insert the expression at each locus and choosing the most outermost scope where it is possible to insert the expression. This check is performed by attempting to run the splice and then catching an exception if it leads to a variable being out of scope.

A paper about let insertion and how it works in MetaOcaml.

https://www.cl.cam.ac.uk/~jdy22/papers/generating-mutually-recursive-definitions-short-paper.pdf

added typed TemplateHaskell label

added Pnormal label