Implement automatic sharing for the surface language code

[Mikolaj]

That would happen whenever a Tensor class code is instantiated to the Ast instance, in the same step that vectorization happens (I'm not sure how these two would interleave). This would transform any code written by the user from scratch, as well as any code we pretty-print, loosing sharing, and the user copy-pastes and feeds to GHC (perhaps in the same repl session, so any impurity needs to be re-entrant).

I think this is really hard, but fortunately Tom says others did it already:

This is interesting. I'd like it to work without tlet in horde-ad as well. How does Accelerate do it?

Stable names to get global sharing, then the typed sharing recovery algorithm to convert to local sharing. Accelerate literature calls this whole procedure "sharing recovery" instead of just the second half.

[Mikolaj]

@tomsmeding notes:

• The Accelerate paper that described this sharing recovery approach is https://dl.acm.org/doi/10.1145/2500365.2500595 (PDF attached). Relevant is section 3.
• Note the link to https://github.com/mchakravarty/hoas-conv , which is an implementation of the algorithm on the simply-typed lambda calculus, represented as a well-typed well-scoped De Bruijn AST.
• If you don't care about a well-typed (GADT-based) AST representation, it seems that reference [14] in the attached paper, which refers to https://ku-fpg.github.io/files/Gill-09-TypeSafeReification.pdf , provides an untyped algorithm for doing the same thing.
• As an addendum, it seems that the mentioned [14] reference, Gill '09, is this library on Hackage: https://hackage.haskell.org/package/data-reify

[tomsmeding]

The data-reify package implements what we have taken to calling "global sharing". I believe Gill '09 does not discuss conversion from global sharing to local sharing, which hoas-conv implements in its Convert.hs. (It does the global sharing detection in Sharing.hs.) If anyone wants the Accelerate paper but doesn't have access, feel free to send me an email.