Symantic.ObserveSharing

Class Referenceable

class Referenceable letName repr where

This class is not for end-users like usual symantic operators, though it will have to be defined on end-users' interpreters.

Minimal complete definition

Nothing

Methods

ref :: Bool -> letName -> repr a

(ref isRec letName) is a reference to (letName). It is introduced by observeSharing. (isRec) is True iif. this reference is recursive, ie. appears within its definition.

TODO: index letName with a to enable dependent-map

default ref :: FromDerived (Referenceable letName) repr => Bool -> letName -> repr a

Instances

(Referenceable letName repr, Eq letName, Hashable letName, Show letName) => Referenceable letName (FinalizeSharing letName repr)

Defined in Symantic.ObserveSharing

Methods

ref :: Bool -> letName -> FinalizeSharing letName repr a

Referenceable letName (ObserveSharing letName repr)

Defined in Symantic.ObserveSharing

Methods

ref :: Bool -> letName -> ObserveSharing letName repr a

Class Definable

class Definable letName repr where

This class is not for end-users like usual symantic operators. There should be not need to use it outside this module, because used definitions are gathered in Letsable.

Minimal complete definition

Nothing

Methods

def :: letName -> repr a -> repr a

(def letName sub) let-binds (letName) to be equal to (sub). This is a temporary node either replaced by ref and an entry in lets's LetBindings, or removed when no reference is made to it.

default def :: FromDerived1 (Definable letName) repr => letName -> repr a -> repr a

Instances

(Referenceable letName repr, Eq letName, Hashable letName, Show letName) => Definable letName (FinalizeSharing letName repr)

Defined in Symantic.ObserveSharing

Methods

def :: letName -> FinalizeSharing letName repr a -> FinalizeSharing letName repr a

Definable letName (ObserveSharing letName repr)

Defined in Symantic.ObserveSharing

Methods

def :: letName -> ObserveSharing letName repr a -> ObserveSharing letName repr a

Class MakeLetName

class MakeLetName letName where

Methods

makeLetName :: SharingName -> IO letName

Type SharingName

data SharingName

Note that the observable sharing enabled by StableName is not perfect as it will not observe all the sharing explicitely done.

Note also that the observed sharing could be different between ghc and ghci.

Constructors

forall a. SharingName (StableName a)

Instances

Eq SharingName

Defined in Symantic.ObserveSharing

Methods

(==) :: SharingName -> SharingName -> Bool

(/=) :: SharingName -> SharingName -> Bool

Hashable SharingName

Defined in Symantic.ObserveSharing

Methods

hashWithSalt :: Int -> SharingName -> Int

hash :: SharingName -> Int

makeSharingName :: a -> SharingName

(makeSharingName x) is like (makeStableName x) but it also forces evaluation of (x) to ensure that the StableName is correct first time, which avoids to produce a tree bigger than needed.

Note that this function uses unsafePerformIO instead of returning in IO, this is apparently required to avoid infinite loops due to unstable StableName in compiled code, and sometimes also in ghci.

Note that maybe pseq should be used here.

Type ObserveSharing

newtype ObserveSharing letName repr a

Constructors

ObserveSharing

Fields

• unObserveSharing :: ReaderT (HashSet SharingName) (State (ObserveSharingState letName)) (FinalizeSharing letName repr a)

Instances

Letsable letName (ObserveSharing letName repr)

Defined in Symantic.ObserveSharing

Methods

lets :: LetBindings letName (ObserveSharing letName repr) -> ObserveSharing letName repr a -> ObserveSharing letName repr a

Definable letName (ObserveSharing letName repr)

Defined in Symantic.ObserveSharing

Methods

def :: letName -> ObserveSharing letName repr a -> ObserveSharing letName repr a

Referenceable letName (ObserveSharing letName repr)

Defined in Symantic.ObserveSharing

Methods

ref :: Bool -> letName -> ObserveSharing letName repr a

(Referenceable letName repr, MakeLetName letName, Eq letName, Hashable letName, Show letName) => LiftDerived4 (ObserveSharing letName repr)

Defined in Symantic.ObserveSharing

Methods

liftDerived4 :: (Derived (ObserveSharing letName repr) a -> Derived (ObserveSharing letName repr) b -> Derived (ObserveSharing letName repr) c -> Derived (ObserveSharing letName repr) d -> Derived (ObserveSharing letName repr) e) -> ObserveSharing letName repr a -> ObserveSharing letName repr b -> ObserveSharing letName repr c -> ObserveSharing letName repr d -> ObserveSharing letName repr e

(Referenceable letName repr, MakeLetName letName, Eq letName, Hashable letName, Show letName) => LiftDerived3 (ObserveSharing letName repr)

Defined in Symantic.ObserveSharing

Methods

liftDerived3 :: (Derived (ObserveSharing letName repr) a -> Derived (ObserveSharing letName repr) b -> Derived (ObserveSharing letName repr) c -> Derived (ObserveSharing letName repr) d) -> ObserveSharing letName repr a -> ObserveSharing letName repr b -> ObserveSharing letName repr c -> ObserveSharing letName repr d

(Referenceable letName repr, MakeLetName letName, Eq letName, Hashable letName, Show letName) => LiftDerived2 (ObserveSharing letName repr)

Defined in Symantic.ObserveSharing

Methods

liftDerived2 :: (Derived (ObserveSharing letName repr) a -> Derived (ObserveSharing letName repr) b -> Derived (ObserveSharing letName repr) c) -> ObserveSharing letName repr a -> ObserveSharing letName repr b -> ObserveSharing letName repr c

(Referenceable letName repr, MakeLetName letName, Eq letName, Hashable letName, Show letName) => LiftDerived1 (ObserveSharing letName repr)

Defined in Symantic.ObserveSharing

Methods

liftDerived1 :: (Derived (ObserveSharing letName repr) a -> Derived (ObserveSharing letName repr) b) -> ObserveSharing letName repr a -> ObserveSharing letName repr b

(Referenceable letName repr, MakeLetName letName, Eq letName, Hashable letName, Show letName) => LiftDerived (ObserveSharing letName repr)

Defined in Symantic.ObserveSharing

Methods

liftDerived :: Derived (ObserveSharing letName repr) a -> ObserveSharing letName repr a

type Derived (ObserveSharing letName repr)

Defined in Symantic.ObserveSharing

type Derived (ObserveSharing letName repr) = FinalizeSharing letName repr

observeSharing :: Eq letName => Hashable letName => Show letName => ObserveSharing letName repr a -> WithSharing letName repr a

Interpreter detecting some (Haskell embedded) let definitions used at least once and/or recursively, in order to replace them with the lets and ref combinators. See Type-safe observable sharing in Haskell

Beware not to apply observeSharing more than once on the same term otherwise some def introduced by the first call would be removed by the second call.

Type WithSharing

type WithSharing letName repr a = (repr a, HashMap letName (SomeLet repr))

Type ObserveSharingState

data ObserveSharingState letName

Constructors

ObserveSharingState

Fields

• oss_refs :: HashMap SharingName (letName, Int)
• oss_recs :: HashSet SharingName

observeSharingNode :: Eq letName => Hashable letName => Show letName => Referenceable letName repr => MakeLetName letName => ObserveSharing letName repr a -> ObserveSharing letName repr a

Type FinalizeSharing

newtype FinalizeSharing letName repr a

Remove def when non-recursive or unused or replace it by ref, moving defs to the top.

Constructors

FinalizeSharing

Fields

• unFinalizeSharing :: ReaderT (HashSet letName) (Writer (LetBindings letName repr)) (repr a)

Instances

(Referenceable letName repr, Eq letName, Hashable letName, Show letName) => Definable letName (FinalizeSharing letName repr)

Defined in Symantic.ObserveSharing

Methods

def :: letName -> FinalizeSharing letName repr a -> FinalizeSharing letName repr a

(Referenceable letName repr, Eq letName, Hashable letName, Show letName) => Referenceable letName (FinalizeSharing letName repr)

Defined in Symantic.ObserveSharing

Methods

ref :: Bool -> letName -> FinalizeSharing letName repr a

(Eq letName, Hashable letName) => LiftDerived4 (FinalizeSharing letName repr)

Defined in Symantic.ObserveSharing

Methods

liftDerived4 :: (Derived (FinalizeSharing letName repr) a -> Derived (FinalizeSharing letName repr) b -> Derived (FinalizeSharing letName repr) c -> Derived (FinalizeSharing letName repr) d -> Derived (FinalizeSharing letName repr) e) -> FinalizeSharing letName repr a -> FinalizeSharing letName repr b -> FinalizeSharing letName repr c -> FinalizeSharing letName repr d -> FinalizeSharing letName repr e

(Eq letName, Hashable letName) => LiftDerived3 (FinalizeSharing letName repr)

Defined in Symantic.ObserveSharing

Methods

liftDerived3 :: (Derived (FinalizeSharing letName repr) a -> Derived (FinalizeSharing letName repr) b -> Derived (FinalizeSharing letName repr) c -> Derived (FinalizeSharing letName repr) d) -> FinalizeSharing letName repr a -> FinalizeSharing letName repr b -> FinalizeSharing letName repr c -> FinalizeSharing letName repr d

(Eq letName, Hashable letName) => LiftDerived2 (FinalizeSharing letName repr)

Defined in Symantic.ObserveSharing

Methods

liftDerived2 :: (Derived (FinalizeSharing letName repr) a -> Derived (FinalizeSharing letName repr) b -> Derived (FinalizeSharing letName repr) c) -> FinalizeSharing letName repr a -> FinalizeSharing letName repr b -> FinalizeSharing letName repr c

(Eq letName, Hashable letName) => LiftDerived1 (FinalizeSharing letName repr)

Defined in Symantic.ObserveSharing

Methods

liftDerived1 :: (Derived (FinalizeSharing letName repr) a -> Derived (FinalizeSharing letName repr) b) -> FinalizeSharing letName repr a -> FinalizeSharing letName repr b

(Eq letName, Hashable letName) => LiftDerived (FinalizeSharing letName repr)

Defined in Symantic.ObserveSharing

Methods

liftDerived :: Derived (FinalizeSharing letName repr) a -> FinalizeSharing letName repr a

type Derived (FinalizeSharing _letName repr)

Defined in Symantic.ObserveSharing

type Derived (FinalizeSharing _letName repr) = repr

Class Letsable

class Letsable letName repr where

Minimal complete definition

Nothing

Methods

lets :: LetBindings letName repr -> repr a -> repr a

(lets defs x) let-binds (defs) in (x).

default lets :: Derivable repr => FromDerived1 (Letsable letName) repr => LetBindings letName repr -> repr a -> repr a

Instances

Letsable letName (ObserveSharing letName repr)

Defined in Symantic.ObserveSharing

Methods

lets :: LetBindings letName (ObserveSharing letName repr) -> ObserveSharing letName repr a -> ObserveSharing letName repr a

Type SomeLet

data SomeLet repr

Constructors

forall a. SomeLet (repr a)

Type LetBindings

type LetBindings letName repr = HashMap letName (SomeLet repr)

Type OpenRecs

type OpenRecs letName a = LetRecs letName (OpenRec letName a)

Mutually recursive terms, in open recursion style.

type OpenRec letName a = LetRecs letName a -> a

Mutually recursive term, in open recursion style. The term is given a final (aka. self) map of other terms it can refer to (including itself).

type LetRecs letName = HashMap letName

Recursive let bindings.

fix :: (a -> a) -> a

Least fixpoint combinator.

mutualFix :: forall recs a. Functor recs => recs (recs a -> a) -> recs a

Lest fixpoint combinator of mutually recursive terms. (mutualFix opens) takes a container of terms in the open recursion style (opens), and return that container of terms with their knots tied-up.

Used to express mutual recursion and to transparently introduce memoization, between observed sharing (defLet, call, jump) and also between join points (defJoin, refJoin).

Here all mutually dependent functions are restricted to the same polymorphic type (a). See http://okmij.org/ftp/Computation/fixed-point-combinators.html#Poly-variadic