Opened 8 months ago

Last modified 7 months ago

#16176 new feature request

Let-insertion for template haskell

Reported by: mpickering Owned by:
Priority: normal Milestone:
Component: Template Haskell Version: 8.6.3
Keywords: TypedTemplateHaskell Cc:
Operating System: Unknown/Multiple Architecture: Unknown/Multiple
Type of failure: None/Unknown Test Case:
Blocked By: Blocking:
Related Tickets: Differential Rev(s):
Wiki Page:

Description

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.

Change History (5)

comment:1 Changed 8 months ago by simonpj

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?

comment:2 Changed 8 months ago by mpickering

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.

comment:3 Changed 8 months ago by goldfire

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

comment:4 Changed 8 months ago by mpickering

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.

comment:5 Changed 7 months ago by mpickering

Note: See TracTickets for help on using tickets.