]> Git — Sourcephile - haskell/symantic-base.git/blob - src/Symantic/ObserveSharing.hs
iface: change `(==)` to curryed form
[haskell/symantic-base.git] / src / Symantic / ObserveSharing.hs
1 {-# LANGUAGE AllowAmbiguousTypes #-} -- For ShowLetName
2 {-# LANGUAGE BangPatterns #-} -- For makeSharingName
3 {-# LANGUAGE DataKinds #-} -- For ShowLetName
4 {-# LANGUAGE ExistentialQuantification #-} -- For SharingName
5 -- {-# LANGUAGE MagicHash #-} -- For unsafeCoerce#
6 module Symantic.ObserveSharing where
7
8 import Control.Applicative (Applicative(..))
9 import Control.Monad (Monad(..))
10 import Data.Bool
11 import Data.Eq (Eq(..))
12 import Data.Function (($), (.))
13 import Data.Functor (Functor, (<$>))
14 import Data.Functor.Compose (Compose(..))
15 import Data.HashMap.Strict (HashMap)
16 import Data.HashSet (HashSet)
17 import Data.Hashable (Hashable, hashWithSalt, hash)
18 import Data.Int (Int)
19 import Data.Maybe (Maybe(..), isNothing)
20 import Data.Monoid (Monoid(..))
21 import Data.Ord (Ord(..))
22 -- import GHC.Exts (Int(..))
23 -- import GHC.Prim (unsafeCoerce#)
24 import GHC.StableName (StableName(..), makeStableName, hashStableName, eqStableName)
25 -- import Numeric (showHex)
26 import Prelude ((+), error)
27 import System.IO (IO)
28 import System.IO.Unsafe (unsafePerformIO)
29 import Text.Show (Show(..))
30 import qualified Control.Monad.Trans.Class as MT
31 import qualified Control.Monad.Trans.Reader as MT
32 import qualified Control.Monad.Trans.State as MT
33 import qualified Control.Monad.Trans.Writer as MT
34 import qualified Data.HashMap.Strict as HM
35 import qualified Data.HashSet as HS
36
37 import Symantic.Derive
38
39 -- * Class 'Referenceable'
40 -- | This class is not for end-users like usual symantic operators,
41 -- though it will have to be defined on end-users' interpreters.
42 class Referenceable letName repr where
43 -- | @('ref' isRec letName)@ is a reference to @(letName)@.
44 -- It is introduced by 'observeSharing'.
45 -- @(isRec)@ is 'True' iif. this 'ref'erence is recursive,
46 -- ie. appears within its 'define'.
47 --
48 -- TODO: index 'letName' with 'a' to enable dependent-map
49 ref :: Bool -> letName -> repr a
50 ref isRec name = liftDerived (ref isRec name)
51 default ref ::
52 FromDerived (Referenceable letName) repr =>
53 Bool -> letName -> repr a
54
55 -- * Class 'Definable'
56 -- | This class is not for end-users like usual symantic operators.
57 -- There should be not need to use it outside this module,
58 -- because used 'define's are gathered in 'Letsable'.
59 class Definable letName repr where
60 -- | @('define' letName sub)@ let-binds @(letName)@ to be equal to @(sub)@.
61 -- This is a temporary node either replaced
62 -- by 'ref' and an entry in 'lets''s 'LetBindings',
63 -- or removed when no 'ref'erence is made to it.
64 define :: letName -> repr a -> repr a
65 define name = liftDerived1 (define name)
66 default define ::
67 FromDerived1 (Definable letName) repr =>
68 letName -> repr a -> repr a
69
70 -- * Class 'MakeLetName'
71 class MakeLetName letName where
72 makeLetName :: SharingName -> IO letName
73
74 -- * Type 'SharingName'
75 -- | Note that the observable sharing enabled by 'StableName'
76 -- is not perfect as it will not observe all the sharing explicitely done.
77 --
78 -- Note also that the observed sharing could be different between ghc and ghci.
79 data SharingName = forall a. SharingName (StableName a)
80 -- | @('makeSharingName' x)@ is like @('makeStableName' x)@ but it also forces
81 -- evaluation of @(x)@ to ensure that the 'StableName' is correct first time,
82 -- which avoids to produce a tree bigger than needed.
83 --
84 -- Note that this function uses 'unsafePerformIO' instead of returning in 'IO',
85 -- this is apparently required to avoid infinite loops due to unstable 'StableName'
86 -- in compiled code, and sometimes also in ghci.
87 --
88 -- Note that maybe [pseq should be used here](https://gitlab.haskell.org/ghc/ghc/-/issues/2916).
89 makeSharingName :: a -> SharingName
90 makeSharingName !x = SharingName $ unsafePerformIO $ makeStableName x
91
92 instance Eq SharingName where
93 SharingName x == SharingName y = eqStableName x y
94 instance Hashable SharingName where
95 hash (SharingName n) = hashStableName n
96 hashWithSalt salt (SharingName n) = hashWithSalt salt n
97 {-
98 instance Show SharingName where
99 showsPrec _ (SharingName n) = showHex (I# (unsafeCoerce# n))
100 -}
101
102 -- * Type 'ObserveSharing'
103 newtype ObserveSharing letName repr a = ObserveSharing { unObserveSharing ::
104 MT.ReaderT (HashSet SharingName)
105 (MT.State (ObserveSharingState letName))
106 (FinalizeSharing letName repr a) }
107
108 -- | Interpreter detecting some (Haskell embedded) @let@ definitions used at
109 -- least once and/or recursively, in order to replace them
110 -- with the 'lets' and 'ref' combinators.
111 -- See [Type-safe observable sharing in Haskell](https://doi.org/10.1145/1596638.1596653)
112 --
113 -- Beware not to apply 'observeSharing' more than once on the same term
114 -- otherwise some 'define' introduced by the first call
115 -- would be removed by the second call.
116 observeSharing ::
117 Eq letName =>
118 Hashable letName =>
119 Show letName =>
120 ObserveSharing letName repr a ->
121 WithSharing letName repr a
122 observeSharing (ObserveSharing m) =
123 let (fs, st) = MT.runReaderT m mempty `MT.runState`
124 ObserveSharingState
125 { oss_refs = HM.empty
126 , oss_recs = HS.empty
127 } in
128 let refs = HS.fromList
129 [ letName
130 | (letName, refCount) <- HM.elems (oss_refs st)
131 , refCount > 0
132 ] in
133 --trace (show refs) $
134 MT.runWriter $
135 (`MT.runReaderT` refs) $
136 unFinalizeSharing fs
137
138 -- ** Type 'WithSharing'
139 type WithSharing letName repr a =
140 (repr a, HM.HashMap letName (SomeLet repr))
141 {-
142 -- * Type 'WithSharing'
143 data WithSharing letName repr a = WithSharing
144 { lets :: HM.HashMap letName (SomeLet repr)
145 , body :: repr a
146 }
147 mapWithSharing ::
148 (forall v. repr v -> repr v) ->
149 WithSharing letName repr a ->
150 WithSharing letName repr a
151 mapWithSharing f ws = WithSharing
152 { lets = (\(SomeLet repr) -> SomeLet (f repr)) <$> lets ws
153 , body = f (body ws)
154 }
155 -}
156
157 -- ** Type 'ObserveSharingState'
158 data ObserveSharingState letName = ObserveSharingState
159 { oss_refs :: HashMap SharingName (letName, Int)
160 , oss_recs :: HashSet SharingName
161 }
162
163 observeSharingNode ::
164 Eq letName =>
165 Hashable letName =>
166 Show letName =>
167 Referenceable letName repr =>
168 MakeLetName letName =>
169 ObserveSharing letName repr a ->
170 ObserveSharing letName repr a
171 observeSharingNode (ObserveSharing m) = ObserveSharing $ do
172 let nodeName = makeSharingName m
173 st <- MT.lift MT.get
174 ((letName, seenBefore), seen) <- getCompose $ HM.alterF (\seenBefore ->
175 -- Compose is used to return (letName, seenBefore) along seen
176 -- in the same HashMap lookup.
177 Compose $ return $ case seenBefore of
178 Nothing ->
179 ((letName, seenBefore), Just (letName, 0))
180 where letName = unsafePerformIO $ makeLetName nodeName
181 Just (letName, refCount) ->
182 ((letName, seenBefore), Just (letName, refCount + 1))
183 ) nodeName (oss_refs st)
184 parentNames <- MT.ask
185 if nodeName `HS.member` parentNames
186 then do -- recursive reference to nodeName:
187 -- update seen references
188 -- and mark nodeName as recursive
189 MT.lift $ MT.put st
190 { oss_refs = seen
191 , oss_recs = HS.insert nodeName (oss_recs st)
192 }
193 return $ ref True letName
194 else do -- non-recursive reference to nodeName
195 -- update seen references
196 -- and recurse if the nodeName hasn't been seen before
197 -- (would be in a preceding sibling branch, not in parentNames).
198 MT.lift $ MT.put st{ oss_refs = seen }
199 if isNothing seenBefore
200 then MT.local (HS.insert nodeName) (define letName <$> m)
201 else return $ ref False letName
202
203 type instance Derived (ObserveSharing letName repr) = FinalizeSharing letName repr
204 instance
205 ( Referenceable letName repr
206 , MakeLetName letName
207 , Eq letName
208 , Hashable letName
209 , Show letName
210 ) => LiftDerived (ObserveSharing letName repr) where
211 liftDerived = observeSharingNode . ObserveSharing . return
212 instance
213 ( Referenceable letName repr
214 , MakeLetName letName
215 , Eq letName
216 , Hashable letName
217 , Show letName
218 ) => LiftDerived1 (ObserveSharing letName repr) where
219 liftDerived1 f a = observeSharingNode $ ObserveSharing $
220 f <$> unObserveSharing a
221 instance
222 ( Referenceable letName repr
223 , MakeLetName letName
224 , Eq letName
225 , Hashable letName
226 , Show letName
227 ) => LiftDerived2 (ObserveSharing letName repr) where
228 liftDerived2 f a b = observeSharingNode $ ObserveSharing $
229 f <$> unObserveSharing a
230 <*> unObserveSharing b
231 instance
232 ( Referenceable letName repr
233 , MakeLetName letName
234 , Eq letName
235 , Hashable letName
236 , Show letName
237 ) => LiftDerived3 (ObserveSharing letName repr) where
238 liftDerived3 f a b c = observeSharingNode $ ObserveSharing $
239 f <$> unObserveSharing a
240 <*> unObserveSharing b
241 <*> unObserveSharing c
242 instance
243 ( Referenceable letName repr
244 , MakeLetName letName
245 , Eq letName
246 , Hashable letName
247 , Show letName
248 ) => LiftDerived4 (ObserveSharing letName repr) where
249 liftDerived4 f a b c d = observeSharingNode $ ObserveSharing $
250 f <$> unObserveSharing a
251 <*> unObserveSharing b
252 <*> unObserveSharing c
253 <*> unObserveSharing d
254 instance Referenceable letName (ObserveSharing letName repr) where
255 ref = error "[BUG]: observeSharing MUST NOT be applied twice"
256 instance Definable letName (ObserveSharing letName repr) where
257 define = error "[BUG]: observeSharing MUST NOT be applied twice"
258 instance Letsable letName (ObserveSharing letName repr) where
259 lets = error "[BUG]: observeSharing MUST NOT be applied twice"
260
261 -- * Type 'FinalizeSharing'
262 -- | Remove 'define' when non-recursive or unused
263 -- or replace it by 'ref', moving 'define's to the top.
264 newtype FinalizeSharing letName repr a = FinalizeSharing { unFinalizeSharing ::
265 MT.ReaderT (HS.HashSet letName)
266 (MT.Writer (LetBindings letName repr))
267 (repr a) }
268
269 type instance Derived (FinalizeSharing _letName repr) = repr
270 instance (Eq letName, Hashable letName) =>
271 LiftDerived (FinalizeSharing letName repr) where
272 liftDerived = FinalizeSharing . pure
273 instance (Eq letName, Hashable letName) =>
274 LiftDerived1 (FinalizeSharing letName repr) where
275 liftDerived1 f a = FinalizeSharing $ f <$> unFinalizeSharing a
276 instance (Eq letName, Hashable letName) =>
277 LiftDerived2 (FinalizeSharing letName repr) where
278 liftDerived2 f a b = FinalizeSharing $
279 f <$> unFinalizeSharing a
280 <*> unFinalizeSharing b
281 instance (Eq letName, Hashable letName) =>
282 LiftDerived3 (FinalizeSharing letName repr) where
283 liftDerived3 f a b c = FinalizeSharing $
284 f <$> unFinalizeSharing a
285 <*> unFinalizeSharing b
286 <*> unFinalizeSharing c
287 instance (Eq letName, Hashable letName) =>
288 LiftDerived4 (FinalizeSharing letName repr) where
289 liftDerived4 f a b c d = FinalizeSharing $
290 f <$> unFinalizeSharing a
291 <*> unFinalizeSharing b
292 <*> unFinalizeSharing c
293 <*> unFinalizeSharing d
294 instance
295 ( Referenceable letName repr
296 , Eq letName
297 , Hashable letName
298 , Show letName
299 ) => Referenceable letName (FinalizeSharing letName repr) where
300 ref isRec = liftDerived . ref isRec
301 instance
302 ( Referenceable letName repr
303 , Eq letName
304 , Hashable letName
305 , Show letName
306 ) => Definable letName (FinalizeSharing letName repr) where
307 define name body = FinalizeSharing $ do
308 refs <- MT.ask
309 let (repr, defs) =
310 MT.runWriter $ MT.runReaderT (unFinalizeSharing body) refs
311 if name `HS.member` refs
312 then do
313 -- This 'define' is 'ref'erenced: move it into the result,
314 -- to put it in scope even when some 'ref' to it exists outside of 'body'
315 -- (which can happen when a body-expression is shared),
316 -- and replace it by a 'ref'.
317 MT.lift $ MT.tell $ HM.insert name (SomeLet repr) defs
318 return $ ref False name
319 else
320 -- Remove this unreferenced 'define' node.
321 unFinalizeSharing body
322
323 -- * Class 'Letsable'
324 class Letsable letName repr where
325 -- | @('lets' defs x)@ let-binds @(defs)@ in @(x)@.
326 lets :: LetBindings letName repr -> repr a -> repr a
327 lets defs = liftDerived1 (lets ((\(SomeLet val) -> SomeLet (derive val)) <$> defs))
328 default lets ::
329 Derivable repr =>
330 FromDerived1 (Letsable letName) repr =>
331 LetBindings letName repr -> repr a -> repr a
332
333 -- ** Type 'SomeLet'
334 data SomeLet repr = forall a. SomeLet (repr a)
335
336 -- ** Type 'LetBindings'
337 type LetBindings letName repr = HM.HashMap letName (SomeLet repr)
338
339 {-
340 -- | Not used but can be written nonetheless.
341 instance
342 ( Letsable letName repr
343 , Eq letName
344 , Hashable letName
345 , Show letName
346 ) => Letsable letName (FinalizeSharing letName repr) where
347 lets defs x = FinalizeSharing $ do
348 ds <- traverse (\(SomeLet v) -> do
349 r <- unFinalizeSharing v
350 return (SomeLet r)
351 ) defs
352 MT.lift $ MT.tell ds
353 unFinalizeSharing x
354 -}
355
356 -- ** Type 'OpenRecs'
357 -- | Mutually recursive terms, in open recursion style.
358 type OpenRecs letName a = LetRecs letName (OpenRec letName a)
359 -- | Mutually recursive term, in open recursion style.
360 -- The term is given a @final@ (aka. @self@) map
361 -- of other terms it can refer to (including itself).
362 type OpenRec letName a = LetRecs letName a -> a
363 -- | Recursive let bindings.
364 type LetRecs letName = HM.HashMap letName
365
366 -- | Least fixpoint combinator.
367 fix :: (a -> a) -> a
368 fix f = final where final = f final
369
370 -- | Lest fixpoint combinator of mutually recursive terms.
371 -- @('mutualFix' opens)@ takes a container of terms
372 -- in the open recursion style @(opens)@,
373 -- and return that container of terms with their knots tied-up.
374 --
375 -- Used to express mutual recursion and to transparently introduce memoization,
376 -- between observed sharing ('defLet', 'call', 'jump')
377 -- and also between join points ('defJoin', 'refJoin').
378 --
379 -- Here all mutually dependent functions are restricted to the same polymorphic type @(a)@.
380 -- See http://okmij.org/ftp/Computation/fixed-point-combinators.html#Poly-variadic
381 mutualFix :: forall recs a. Functor recs => recs ({-finals-}recs a -> a) -> recs a
382 mutualFix opens = fix f
383 where
384 f :: recs a -> recs a
385 f recs = ($ recs) <$> opens