Alternative Methods for Retaining Explicit and Finding Implicit Sharing in Embedded DSLs

Detection of sharing is a known challenge for implementers of embedded domain specific languages (DSLs). There are many solutions, each with their advantages and drawbacks. Many solutions are based on observable sharing, that requires either a monadic interface or use of unsafe referencing, e.g., Data.Reify. Monadic interfaces are considered unsuitable for domain experts, and the use of unsafe referencing leads to fragile software.Kiselyov’s methods for implicit and explicit sharing detection for finally tagless style DSLs is an elegant solution without having to resort to unsafe observable sharing. However these methods are not applicable to all types of DSLs (including those generating hypergraphs). We will present alternative methods which handle these cases. The main difference comes from the use of a trie to perform hash-consing. Our method for implicit sharing essentially trades worst-case exponential growth in computation for increased memory footprint. To mitigate this issue, our method for explicit sharing reduces the memory footprint.