syntactic-1.0: Generic abstract syntax, and utilities for embedded languages

Safe HaskellNone



This module is similar to Language.Syntactic.Sharing.Reify, but operates on AST (HODomain dom p) rather than a general AST. The reason for having this module is that when using HODomain, it is important to do simultaneous sharing analysis and HOLambda reification. Obviously we cannot do sharing analysis first (using reifyGraph from Language.Syntactic.Sharing.Reify), since it needs to be able to look inside HOLambda. On the other hand, if we did HOLambda reification first (using reify), we would destroy the sharing.

This module is based on the paper Type-Safe Observable Sharing in Haskell (Andy Gill, 2009,



reifyGraphTop :: (forall a. ASTF (HODomain dom p) a -> Bool) -> ASTF (HODomain dom p) a -> IO (ASG ((Lambda :+: (Variable :+: dom)) :|| p) a, VarId)Source

Convert a syntax tree to a sharing-preserving graph



:: Syntactic a (HODomain dom p) 
=> (forall a. ASTF (HODomain dom p) a -> Bool)

A function that decides whether a given node can be shared

-> a 
-> IO (ASG ((Lambda :+: (Variable :+: dom)) :|| p) (Internal a), VarId) 

Reifying an n-ary syntactic function to a sharing-preserving graph

This function is not referentially transparent (hence the IO). However, it is well-behaved in the sense that the worst thing that could happen is that sharing is lost. It is not possible to get false sharing.