Language.Syntactic.Functional.Sharing

Simple code motion transformation performing common sub-expression elimination and variable hoisting. Note that the implementation is very inefficient.

The code is based on an implementation by Gergely Dévai.

Interface

data InjDict sym a b

Interface for injecting binding constructs

Constructors

InjDict

Fields

• injVariable :: Name -> sym (Full a)

  Inject a variable

• injLambda :: Name -> sym (b :-> Full (a -> b))

  Inject a lambda

• injLet :: sym (a :-> ((a -> b) :-> Full b))

  Inject a "let" symbol

data CodeMotionInterface sym

Code motion interface

Constructors

Interface

Fields

• mkInjDict :: forall a b. ASTF sym a -> ASTF sym b -> Maybe (InjDict sym a b)

  Try to construct an InjDict. The first argument is the expression to be shared, and the second argument the expression in which it will be shared. This function can be used to transfer information (e.g. from static analysis) from the shared expression to the introduced variable.

• castExprCM :: forall a b. ASTF sym a -> ASTF sym b -> Maybe (ASTF sym b)

  Try to type cast an expression. The first argument is the expression to cast. The second argument can be used to construct a witness to support the casting. The resulting expression (if any) should be equal to the first argument.

• hoistOver :: forall c. ASTF sym c -> Bool

  Whether a sub-expression can be hoisted over the given expression

defaultInterface

Arguments

:: (binding :<: sym, Let :<: sym, symT ~ Typed sym)

=> (forall a. Typeable a => Name -> binding (Full a))

Variable constructor (e.g. Var or VarT)

-> (forall a b. Typeable a => Name -> binding (b :-> Full (a -> b)))

Lambda constructor (e.g. Lam or LamT)

-> (forall a b. ASTF symT a -> ASTF symT b -> Bool)

Can the expression represented by the first argument be shared in the second argument?

-> (forall a. ASTF symT a -> Bool)

Can we hoist over this expression?

-> CodeMotionInterface symT

Default CodeMotionInterface for domains of the form Typed (... :+: Binding :+: ...).

defaultInterfaceDecor

Arguments

:: (binding :<: sym, Let :<: sym, symI ~ (sym :&: info))

=> (forall a b. info a -> info b -> Maybe (Dict (a ~ b)))

Construct a type equality witness

-> (forall a b. info a -> info b -> info (a -> b))

Construct info for a function, given info for the argument and the result

-> (forall a. info a -> Name -> binding (Full a))

Variable constructor

-> (forall a b. info a -> info b -> Name -> binding (b :-> Full (a -> b)))

Lambda constructor

-> (forall a b. ASTF symI a -> ASTF symI b -> Bool)

Can the expression represented by the first argument be shared in the second argument?

-> (forall a. ASTF symI a -> Bool)

Can we hoist over this expression?

-> CodeMotionInterface symI

Default CodeMotionInterface for domains of the form (... :&: info), where info can be used to witness type casting

Code motion

codeMotion :: forall sym m a. (Equality sym, BindingDomain sym) => CodeMotionInterface sym -> ASTF sym a -> ASTF sym a

Perform common sub-expression elimination and variable hoisting