I like feedreaders. Thus, of course, I had to implement my own, because, as always, all existing software does not fullfill my exceedingly unrealistic expectations with respect to customizability and extendability.
This post marks the start of a series describing and documenting the design of the current iteration of Beuteltier (Beutel kind of sounds like Beuter and is german for bag, which is what we call our backstore since it is held at such an universal and unstructured level that the analogy is fitting. Tier is german for animal and taken to mean “Thing that does stuff”. In conjunction Beuteltier means Marsupial).
It should be noted that the library described here is not finished or ready for use in any sense of the word (at the time of writing a “trivial” implementation of a Beutel shipped with the library supports only run, search, and delete). Searching a way to procrastinate implementing the more arduous insert (it requires nubbing—deduplication in the backstore) I decided to, instead, start this series of posts and put the thought that went into the library so far in a form that I can read again for later reference.
We begin, as is to be expected for a haskell project, with type definitions and, thus, design philosophy.
This post in particular reproduces the file beuteltier/Beuteltier/Types.hs from the git repo with annotiations to provide some motivation.
The Beuteltier library itself only provides primitives for (and a default implementation of) access to what we call a backstore. A backstore is, to us, an instance of the typeclass Beutel which contains the most primitive of primitives for storing, searching for and deleting representations of the objects we care about from the store.
It is recommended that the reader not try to follow the rest of this post linearly but start at the end with the definition of the Beutel class and work their way backwards.
> {-# LANGUAGE FlexibleInstances, StandaloneDeriving, KindSignatures, MultiParamTypeClasses, TypeFamilies #-}
>
> module Beuteltier.Types
> ( -- * Types
> Object
> , ObjectGen(..)
> , SubObject(..)
> , MetaData(..)
> , Thunk(..)
> , ThunkState(..)
> , ThunkResult(..)
> , Tag
> , Flag(..)
> , SubObjectName
> , ThunkName
> , SearchQuery
> , Predicate
> , Beutel(..)
> ) whereFlag ends up being a sum type holding values such as Seen, Old, or Hidden. We define it externally.
> import Beuteltier.Types.FlagsThe Identity functor serves as basis for many a Monadtransformer-stack.
> import Data.Functor.Identity
> import Data.Functor.Classes ()Binary contents are encoded as ByteStrings
> import qualified Data.ByteString.Lazy as Lazy (ByteString)
> import qualified Data.ByteString.Lazy as LBSUnicode text as Text
> import Data.Text (Text)Long unicode text as lazy Text
> import qualified Data.Text.Lazy as Lazy (Text)
> import qualified Data.Text.Lazy as LT
>
> import Data.Set (Set)
>
> import Data.Map (Map)
>
> import Data.Time (UTCTime)
>
> import Data.Function (on)
> import Data.Ord (comparing)
> import Control.ApplicativeData.Default provides some convenience when constructing extensive record structures.
> import Data.DefaultThe boolexpr package provides us with a structure for representing boolean expressions supporting functor operations and evaluation.
> import Data.BoolExprPrevious iterations of Beuteltier acted on Objects that were kept completely in RAM during all operations. This proved to be unsustainable, not only because nubbing (deduplication in the store of all objects) tended to exceed all RAM constraints (>4GiB for a few hundred objects), but also because cheaper operations on objects, like presentation to the user, got painfully slow once large SubObjects (like videos) were introduced into the store.
The straight forward solution was to enrich the Object structure with provisions for explicit lazyness and partial construction.
> -- | We deal in, at runtime, partially retrieved Objects
> data ObjectGen (f :: * -> *) = ObjectGen
> { _oMeta :: f MetaData
> -- ^ An undetermined set of Metainformation
> , _oContent :: f (Map SubObjectName (f SubObject))
> -- ^ A list of undetermined length of undetermined
> -- 'SubObject's with guaranteed unique 'SubObjectName's
> , _oThunks :: f [f Thunk]
> -- ^ A list of undetermined length of undetermined Thunks.
> -- There is such a thing as thunk colissions (i.e.: two
> -- thunks promise or even create 'SubObject's with the
> -- same name).
> -- Precedence in such a case is to be as suggested by
> -- the list structure (later thunks override earlier ones).
> }
>
> instance Monad f => Default (ObjectGen f) where
> def = ObjectGen { _oContent = return def
> , _oThunks = return def
> , _oMeta = return def
> }It is straight forward to collapse the more advanced representation of Objects back to the old behaviour by parametrising over the Identity functor, which is simply a newtype wrapper over the contained structure.
> -- | An entirely retrieved Object
> type Object = ObjectGen Identity
>
> -- -- | The default 'Object' is empty except for metadata
> -- instance Default Object where
> -- def = ObjectGen { _oContent = return def
> -- , _oThunks = return def
> -- , _oMeta = return def
> -- }
>
> -- | Equality simply gets deferred to all subcomponents
> deriving instance Eq Object
>
> -- | 'Object's compare as their 'MetaData'
> instance Ord Object where
> compare = comparing _oMetaWe would like to associate some set of meta information with all objects. Therefore, we do.
> -- | Metadata associated with an Object
> data MetaData = MetaData
> { _mRetrieved :: UTCTime -- ^ Time of creation
> , _mTags :: Set Tag -- ^ Tags such as the name of the author,
> -- the title of the work represented in
> -- the 'Object', ….
> -- We use something like @show . _mTags@
> -- to identify an 'Object' to the user
> , _mFlags :: Set Flag -- ^ Flags such as \"Read\" or \"Spam\"
> } deriving (Show, Ord)
> -- | Tags are unicode text
> type Tag = Text
>
> -- | 'MetaData' equates as the contained tags
> instance Eq MetaData where
> (==) = (==) `on` _mTags
>
> -- | The default MetaData has no tags, no flags, and an undefined timestamp
> instance Default MetaData where
> def = MetaData { _mFlags = def
> , _mTags = def
> , _mRetrieved = undefined -- There really is no such thing as a default time
> }Objects are no fun if they don´t contain anything of interest in the end.
Below we see a remnant of an older model of associating names to SubObjects. We switched to using a Map for reasons of deduplication. Inserting into a Map carries some guarantees that keys end up being unique.
Note below: creation of a SubObject is an update. It is thus expected, that SubObjects created at the same time as the Object they are associated to encode an update time that matches the Objects creation time.
> -- | Contents of an object
> data SubObject = SubObject
> -- { _sId :: SubObjectName
> -- ^ We associate a name to every chunk of content to determine
> -- how to present an object to the user
> { _sContent :: Lazy.ByteString
> , _sUpdates :: [UTCTime]
> -- ^ Times of witnessed updates to this 'SubObject'
> } deriving (Show)
>
> -- | No content, no witnessed updates
> instance Default SubObject where
> def = SubObject { _sContent = def
> , _sUpdates = def
> }
>
> -- | Extensionality for 'SubObject's:
> --
> -- > (==) = (==) `on` _sContent
> instance Eq SubObject where
> (==) = (==) `on` _sContentThe distinguishing feature of Beuteltier is it´s support for Thunks. They are, as the name suggests, loosly based on the concept of lazy evaluation. They are, however, less transparent and thus more explicit than implementations as they are used in, for example haskell.
As far as Beuteltier is concerned Thunks are executables that are expected to produce files in the directory they are executed in in a pure manner. That is to say they do not access external resources, where possible. A Thunk that downloads a video from the internet will, of course, access the internet and can thus fail. We expect it, however, to not to try and access the users home directory to look for e.g. credentials for authentication it intends to use to its primary job.
When a Thunks executable gets executed the files it creates (excluding itself) get translated to SubObjects with the filenames (directories stripped of course) as their SubObjectNames and the file contents as their… well, their contents. It is understood, that not all possible SubObjectNames can be created thus (we restrict ourselves to valid filenames on whatever system we happen to be on). We do not consider this to be a great loss.
The advanced equality checks mentioned below are, in fact, implemented and will be explained in more detail in a later post concerned with the file beuteltier/Beuteltier/Types/Util.hs.
> -- | Thunks are at runtime not yet known parts of an object
> data Thunk = Thunk
> { _tId :: ThunkName -- ^ For debugging
> , _tScript :: Lazy.ByteString
> -- ^ A Thunk is, in the end, a shell script that is expected to generate
> -- 'SubObject's
> , _tPromises :: Maybe [SubObjectName]
> -- ^ Maybe we already know what our script is going to generate?
> -- This would enable us to do some more advanced equality checks under
> -- the assumption that scripts are pure
> , _tState :: ThunkState
> }
> deriving (Show)
>
> -- | Empty id, empty script, promises nothing, and with default state
> instance Default Thunk where
> def = Thunk { _tId = def
> , _tScript = def
> , _tPromises = def
> , _tState = def
> }
>
> -- | Equality on 'Thunk's ignores '_tState' and '_tId'
> instance Eq Thunk where
> a == b = and $ [ (==) `on` _tScript
> , (==) `on` _tPromises
> ] <*> pure a <*> pure b
>
> -- | The states in which a 'Thunk' can be encountered.
> data ThunkState = NotExecuted
> | Executed [SubObjectName] ThunkResult
> deriving (Show)
>
> -- | Return the default 'ThunkResult' upon forcing
> instance Default ThunkState where
> def = NotExecuted
>
> -- | Thunks generate some data during execution
> data ThunkResult = ThunkResult
> { _rOutErr, _rOutStd :: Lazy.Text
> , _rExit :: Integer -- ^ Numerical exit code (0 usually means success)
> }
> deriving (Show)
>
> -- | Empty output, and with undefined exit code (no execution took place and we can´t
> -- encode this in a numerical exit code)
> instance Default ThunkResult where
> def = ThunkResult { _rOutErr = LT.empty, _rOutStd = LT.empty
> , _rExit = undefined
> }
>
> -- | We expect identifiers for 'SubObject's to be short, thus 'String'
> type SubObjectName = String
> -- | We expect identifiers for 'Thunk's to be short, thus 'String'
> type ThunkName = String
>
> -- | @LBS.empty@
> instance Default (Lazy.ByteString) where
> def = LBS.emptyWhat good is a library for managing a backstore if it does not support search operations? We consider the answer to be “very little” and, thus, support searches.
> type SearchQuery f = BoolExpr (Predicate f)
> -- data Predicate f = Prim (ObjectGen f -> f Bool)
> -- | Meta (MetaData -> Bool)
> type Predicate f = ObjectGen f -> f BoolThe heart of the Beuteltier library is the typeclass reproduced below. We expect implementations of backstores to be Monads so that we may be able to construct complicated actions that act on the backstore in question. Once we have constructed such an action using the three primitives search, insert, and delete we additionally require a way to execute that action from within the IO Monad.
Additional primitives, such as those for “forcing” and resetting thunks, are provided in additional libraries and, thus, later posts.
> -- | We have the user supply the functions we use to interact with whatever backstore
> -- she uses
> class Monad functor => Beutel (functor :: * -> *) where
> data Config :: *
> run :: Config -> functor a -> IO a
> -- ^ Actually run whatever action we constructed against the backstore
> search :: SearchQuery functor -> functor [ObjectGen functor]
> -- ^ Perform a search
> insert :: Object -> functor ()
> -- ^ Insert an object
> delete :: SearchQuery functor -> functor ()
> -- ^ Delete the results of a search