summaryrefslogtreecommitdiff
path: root/provider/posts/beuteltier/1.lhs
diff options
context:
space:
mode:
Diffstat (limited to 'provider/posts/beuteltier/1.lhs')
-rw-r--r--provider/posts/beuteltier/1.lhs327
1 files changed, 327 insertions, 0 deletions
diff --git a/provider/posts/beuteltier/1.lhs b/provider/posts/beuteltier/1.lhs
new file mode 100644
index 0000000..7789f40
--- /dev/null
+++ b/provider/posts/beuteltier/1.lhs
@@ -0,0 +1,327 @@
1---
2title: On the Design of Overly Complicated Feedreaders
3published: 2015-08-04
4tags: Beuteltier
5---
6
7I like feedreaders.
8Thus, of course, I had to implement my own, because, as always, all existing software does
9not fullfill my exceedingly unrealistic expectations with respect to customizability and
10extendability.
11
12This post marks the start of a series describing and documenting the design of the current
13iteration of `Beuteltier` (`Beutel` kind of sounds like [Beuter](https://newsbeuter.org)
14and is german for bag, which is what we call our backstore since it is held at such an
15universal and unstructured level that the analogy is fitting. `Tier` is german for animal
16and taken to mean "Thing that does stuff". In conjunction `Beuteltier` means
17[Marsupial](https://en.wikipedia.org/wiki/Marsupial)).
18
19It should be noted that the library described here is not finished or ready for use in any
20sense of the word (at the time of writing a "trivial" implementation of a `Beutel` shipped
21with the library supports only `run`, `search`, and `delete`). Searching a way to
22procrastinate implementing the more arduous `insert` (it requires nubbing—deduplication in
23the backstore) I decided to, instead, start this series of posts and put the thought that
24went into the library so far in a form that I can read again for later reference.
25
26We begin, as is to be expected for a haskell project, with type definitions and, thus,
27design philosophy.
28
29This post in particular reproduces the file `beuteltier/Beuteltier/Types.hs` from the
30git repo with annotiations to provide some motivation.
31
32The `Beuteltier` library itself only provides primitives for (and a default implementation
33of) access to what we call a backstore. A backstore is, to us, an instance of the
34typeclass `Beutel` which contains the most primitive of primitives for storing, searching
35for and deleting representations of the objects we care about from the store.
36
37It is recommended that the reader not try to follow the rest of this post linearly but start
38at the end with the definition of the `Beutel` class and work their way backwards.
39
40> {-# LANGUAGE FlexibleInstances, StandaloneDeriving, KindSignatures, MultiParamTypeClasses, TypeFamilies #-}
41>
42> module Beuteltier.Types
43> ( -- * Types
44> Object
45> , ObjectGen(..)
46> , SubObject(..)
47> , MetaData(..)
48> , Thunk(..)
49> , ThunkState(..)
50> , ThunkResult(..)
51> , Tag
52> , Flag(..)
53> , SubObjectName
54> , ThunkName
55> , SearchQuery
56> , Predicate
57> , Beutel(..)
58> ) where
59
60`Flag` ends up being a [sum type](https://en.wikipedia.org/wiki/Sum_type) holding values
61such as `Seen`, `Old`, or `Hidden`.
62We define it externally.
63
64> import Beuteltier.Types.Flags
65
66The `Identity` functor serves as basis for many a Monadtransformer-stack.
67
68> import Data.Functor.Identity
69> import Data.Functor.Classes ()
70
71Binary contents are encoded as `ByteStrings`
72
73> import qualified Data.ByteString.Lazy as Lazy (ByteString)
74> import qualified Data.ByteString.Lazy as LBS
75
76Unicode text as `Text`
77
78> import Data.Text (Text)
79
80Long unicode text as lazy `Text`
81
82> import qualified Data.Text.Lazy as Lazy (Text)
83> import qualified Data.Text.Lazy as LT
84>
85> import Data.Set (Set)
86>
87> import Data.Map (Map)
88>
89> import Data.Time (UTCTime)
90>
91> import Data.Function (on)
92> import Data.Ord (comparing)
93> import Control.Applicative
94
95`Data.Default` provides some convenience when constructing extensive record structures.
96
97> import Data.Default
98
99The `boolexpr` package provides us with a structure for representing boolean expressions
100supporting functor operations and evaluation.
101
102> import Data.BoolExpr
103
104Previous iterations of Beuteltier acted on Objects that were kept completely in RAM during
105all operations.
106This proved to be unsustainable, not only because nubbing (deduplication in the store of
107all objects) tended to exceed all RAM constraints (>4GiB for a few hundred objects), but
108also because cheaper operations on objects, like presentation to the user, got painfully
109slow once large `SubObject`s (like videos) were introduced into the store.
110
111The straight forward solution was to enrich the `Object` structure with provisions for
112explicit lazyness and partial construction.
113
114> -- | We deal in, at runtime, partially retrieved Objects
115> data ObjectGen (f :: * -> *) = ObjectGen
116> { _oMeta :: f MetaData
117> -- ^ An undetermined set of Metainformation
118> , _oContent :: f (Map SubObjectName (f SubObject))
119> -- ^ A list of undetermined length of undetermined
120> -- 'SubObject's with guaranteed unique 'SubObjectName's
121> , _oThunks :: f [f Thunk]
122> -- ^ A list of undetermined length of undetermined Thunks.
123> -- There is such a thing as thunk colissions (i.e.: two
124> -- thunks promise or even create 'SubObject's with the
125> -- same name).
126> -- Precedence in such a case is to be as suggested by
127> -- the list structure (later thunks override earlier ones).
128> }
129>
130> instance Monad f => Default (ObjectGen f) where
131> def = ObjectGen { _oContent = return def
132> , _oThunks = return def
133> , _oMeta = return def
134> }
135
136It is straight forward to collapse the more advanced representation of `Object`s back to
137the old behaviour by parametrising over the Identity functor, which is simply a newtype
138wrapper over the contained structure.
139
140> -- | An entirely retrieved Object
141> type Object = ObjectGen Identity
142>
143> -- -- | The default 'Object' is empty except for metadata
144> -- instance Default Object where
145> -- def = ObjectGen { _oContent = return def
146> -- , _oThunks = return def
147> -- , _oMeta = return def
148> -- }
149>
150> -- | Equality simply gets deferred to all subcomponents
151> deriving instance Eq Object
152>
153> -- | 'Object's compare as their 'MetaData'
154> instance Ord Object where
155> compare = comparing _oMeta
156
157We would like to associate some set of meta information with all objects.
158Therefore, we do.
159
160> -- | Metadata associated with an Object
161> data MetaData = MetaData
162> { _mRetrieved :: UTCTime -- ^ Time of creation
163> , _mTags :: Set Tag -- ^ Tags such as the name of the author,
164> -- the title of the work represented in
165> -- the 'Object', ….
166> -- We use something like @show . _mTags@
167> -- to identify an 'Object' to the user
168> , _mFlags :: Set Flag -- ^ Flags such as \"Read\" or \"Spam\"
169> } deriving (Show, Ord)
170> -- | Tags are unicode text
171> type Tag = Text
172>
173> -- | 'MetaData' equates as the contained tags
174> instance Eq MetaData where
175> (==) = (==) `on` _mTags
176>
177> -- | The default MetaData has no tags, no flags, and an undefined timestamp
178> instance Default MetaData where
179> def = MetaData { _mFlags = def
180> , _mTags = def
181> , _mRetrieved = undefined -- There really is no such thing as a default time
182> }
183
184Objects are no fun if they don´t contain anything of interest in the end.
185
186Below we see a remnant of an older model of associating names to `SubObject`s. We switched
187to using a `Map` for reasons of deduplication. Inserting into a `Map` carries some
188guarantees that keys end up being unique.
189
190Note below: creation of a `SubObject` is an update. It is thus expected, that `SubObject`s
191created at the same time as the `Object` they are associated to encode an update
192time that matches the `Object`s creation time.
193
194> -- | Contents of an object
195> data SubObject = SubObject
196> -- { _sId :: SubObjectName
197> -- ^ We associate a name to every chunk of content to determine
198> -- how to present an object to the user
199> { _sContent :: Lazy.ByteString
200> , _sUpdates :: [UTCTime]
201> -- ^ Times of witnessed updates to this 'SubObject'
202> } deriving (Show)
203>
204> -- | No content, no witnessed updates
205> instance Default SubObject where
206> def = SubObject { _sContent = def
207> , _sUpdates = def
208> }
209>
210> -- | Extensionality for 'SubObject's:
211> --
212> -- > (==) = (==) `on` _sContent
213> instance Eq SubObject where
214> (==) = (==) `on` _sContent
215
216The distinguishing feature of Beuteltier is it´s support for `Thunk`s. They are, as the
217name suggests, loosly based on the concept of lazy evaluation. They are, however, less
218transparent and thus more explicit than implementations as they are used in, for example
219haskell.
220
221As far as Beuteltier is concerned `Thunk`s are executables that are expected to produce
222files in the directory they are executed in in a pure manner. That is to say they do not
223access external resources, where possible. A `Thunk` that downloads a video from the
224internet will, of course, access the internet and can thus fail. We expect it, however, to
225not to try and access the users home directory to look for e.g. credentials for
226authentication it intends to use to its primary job.
227
228When a `Thunk`s executable gets executed the files it creates (excluding itself) get
229translated to `SubObject`s with the filenames (directories stripped of course) as their
230`SubObjectName`s and the file contents as their… well, their contents. It is understood,
231that not all possible `SubObjectName`s can be created thus (we restrict ourselves to valid
232filenames on whatever system we happen to be on). We do not consider this to be a great
233loss.
234
235The advanced equality checks mentioned below are, in fact, implemented and will be explained
236in more detail in a later post concerned with the file `beuteltier/Beuteltier/Types/Util.hs`.
237
238> -- | Thunks are at runtime not yet known parts of an object
239> data Thunk = Thunk
240> { _tId :: ThunkName -- ^ For debugging
241> , _tScript :: Lazy.ByteString
242> -- ^ A Thunk is, in the end, a shell script that is expected to generate
243> -- 'SubObject's
244> , _tPromises :: Maybe [SubObjectName]
245> -- ^ Maybe we already know what our script is going to generate?
246> -- This would enable us to do some more advanced equality checks under
247> -- the assumption that scripts are pure
248> , _tState :: ThunkState
249> }
250> deriving (Show)
251>
252> -- | Empty id, empty script, promises nothing, and with default state
253> instance Default Thunk where
254> def = Thunk { _tId = def
255> , _tScript = def
256> , _tPromises = def
257> , _tState = def
258> }
259>
260> -- | Equality on 'Thunk's ignores '_tState' and '_tId'
261> instance Eq Thunk where
262> a == b = and $ [ (==) `on` _tScript
263> , (==) `on` _tPromises
264> ] <*> pure a <*> pure b
265>
266> -- | The states in which a 'Thunk' can be encountered.
267> data ThunkState = NotExecuted
268> | Executed [SubObjectName] ThunkResult
269> deriving (Show)
270>
271> -- | Return the default 'ThunkResult' upon forcing
272> instance Default ThunkState where
273> def = NotExecuted
274>
275> -- | Thunks generate some data during execution
276> data ThunkResult = ThunkResult
277> { _rOutErr, _rOutStd :: Lazy.Text
278> , _rExit :: Integer -- ^ Numerical exit code (0 usually means success)
279> }
280> deriving (Show)
281>
282> -- | Empty output, and with undefined exit code (no execution took place and we can´t
283> -- encode this in a numerical exit code)
284> instance Default ThunkResult where
285> def = ThunkResult { _rOutErr = LT.empty, _rOutStd = LT.empty
286> , _rExit = undefined
287> }
288>
289> -- | We expect identifiers for 'SubObject's to be short, thus 'String'
290> type SubObjectName = String
291> -- | We expect identifiers for 'Thunk's to be short, thus 'String'
292> type ThunkName = String
293>
294> -- | @LBS.empty@
295> instance Default (Lazy.ByteString) where
296> def = LBS.empty
297
298What good is a library for managing a backstore if it does not support search operations?
299We consider the answer to be "very little" and, thus, support searches.
300
301> type SearchQuery f = BoolExpr (Predicate f)
302> -- data Predicate f = Prim (ObjectGen f -> f Bool)
303> -- | Meta (MetaData -> Bool)
304> type Predicate f = ObjectGen f -> f Bool
305
306The heart of the `Beuteltier` library is the typeclass reproduced below. We expect
307implementations of backstores to be `Monad`s so that we may be able to construct
308complicated actions that act on the backstore in question.
309Once we have constructed such an action using the three primitives `search`, `insert`, and
310`delete` we additionally require a way to execute that action from within the `IO`
311`Monad`.
312
313Additional primitives, such as those for "forcing" and resetting thunks, are provided in
314additional libraries and, thus, later posts.
315
316> -- | We have the user supply the functions we use to interact with whatever backstore
317> -- she uses
318> class Monad functor => Beutel (functor :: * -> *) where
319> data Config :: *
320> run :: Config -> functor a -> IO a
321> -- ^ Actually run whatever action we constructed against the backstore
322> search :: SearchQuery functor -> functor [ObjectGen functor]
323> -- ^ Perform a search
324> insert :: Object -> functor ()
325> -- ^ Insert an object
326> delete :: SearchQuery functor -> functor ()
327> -- ^ Delete the results of a search
generated by cgit v1.2.3 (git 2.25.1) at 2024-05-06 11:04:20 +0000