Merging chunk maps into a single map via `Data.Typeable`

[balacij]

Background

Presently, ChunkDBs are built as an enumeration of "chunk" maps;

Drasil/code/drasil-database/lib/Database/Drasil/ChunkDB.hs

Lines 165 to 183 in 10f9f9e

	-- | Our chunk databases. \Must contain all maps needed in an example.\
	-- In turn, these maps must contain every chunk definition or concept
	-- used in its respective example, else an error is thrown.
	data ChunkDB = CDB { symbolTable :: SymbolMap
	, termTable :: TermMap
	, defTable :: ConceptMap
	, _unitTable :: UnitMap
	, _traceTable :: TraceMap
	, _refbyTable :: RefbyMap
	, _dataDefnTable :: DatadefnMap
	, _insmodelTable :: InsModelMap
	, _gendefTable :: GendefMap
	, _theoryModelTable :: TheoryModelMap
	, _conceptinsTable :: ConceptInstanceMap
	, _sectionTable :: SectionMap
	, _labelledcontentTable :: LabelledContentMap
	, _refTable :: ReferenceMap
	} -- TODO: Expand and add more databases
	makeLenses ''ChunkDB

Problem

i. We are unable to add (almost) arbitrary data into the ChunkDBs for various different systems.
ii. We manually track chunks in lists (by a single type, for later further processing) in SystemInformation when we already have them registered in the ChunkDB.

Drasil/code/drasil-database/lib/Database/Drasil/SystemInformation.hs

Lines 45 to 53 in 10f9f9e

	, _quants :: [e]
	, _concepts :: [f]
	, _instModels :: [InstanceModel]
	, _datadefs :: [DataDefinition]
	, _configFiles :: [String]
	, _inputs :: [h]
	, _outputs :: [i]
	, _defSequence :: [Block SimpleQDef]
	, _constraints :: [j] --TODO: Add SymbolMap OR enough info to gen SymbolMap

iii. Adding arbitrary data to a ChunkDB is impossible without editing core drasil-database files, and difficult when editing core drasil-database files because it affects compilation of other examples.
iv. Working with similar maps requires redundant manual recreation (swhs and nopcm has a bit of this).
v. We have occurrences of conflicting UIDs because they are registered in different maps.

Potential Solution : Merging Maps into a single one

I think we can solve these 5 or so problems by merging our maps into a single Map, and using more of the core Data.Map functionality.

We will need to hide type information to create a homogeneous Chunk type, and then merge our maps into a single Chunk Map.

The solution would, approximately, be as follows:
(1) Assume we have the following UID type, and typeclasses:

type UID = String

-- | An interface to get the UID of a chunk.
class HasUID a where
    uid :: a -> UID

-- | Dump data to Strings for debugging-purposes.
class DrasilDumpable a where
    dump :: a -> String

(2) We build a Chunk type intended to carry arbitrary data in our final ChunkDB:

import Data.Typeable -- this is an important design decision (as opposed to Type.Reflection) for simplicity
...
data Chunk where  -- Personally, I find GADTs to be more readable, but this can be done without them via ExistentialQuantification
    CHUNK :: (HasUID t, DrasilDumpable t, Typeable t) => t -> Chunk

instance HasUID         Chunk where uid  (CHUNK t) = uid t
instance DrasilDumpable Chunk where dump (CHUNK t) = dump t
...

Here, we build a commonality between all chunks registered in Drasil (e.g., they ALL must have a UID [a design decision], they all must be Typeable [Thanks to GHC 8.2+, this is the new 'normal'], and they all must be DrasilDumpable [not really required, but I think this would help in debugging -- this could also be something that we mass-dump into a single JSON file for our stable examples to show all raw knowledge we use to build up softifacts]). Additionally, we discard the real type information because the Typeable allows us to retrieve it later, and it will be helpful in creating a homogeneous map type.

(3) Thanks to capturing all of our chunks in a single Chunk type, we can construct a single homogeneous ChunkDB type:

type ChunkDB = M.Map UID Chunk

(4) We build a few functions to help with registering chunks into the ChunkDB:

-- Registering a list of like-typed chunks
chunksToChunkDB :: (HasUID t, Typeable t, DrasilDumpable t) => [t] -> ChunkDB
chunksToChunkDB = M.fromList . map (\x -> (uid x, CHUNK x))

-- Registering
registerChunk :: (HasUID t, Typeable t, DrasilDumpable t) => t -> ChunkDB -> ChunkDB
registerChunk c = M.insert (uid c) (CHUNK c)

-- Retrieval (I prefer using `Maybe` for prototyping instead of forced errors, but this would likely be a strict value or an error in practice)
retrieveChunk :: Typeable a => ChunkDB -> UID -> Maybe a
retrieveChunk cdb u = do
    (CHUNK r) <- M.lookup u cdb
    cast r

(5) When we want to pull arbitrary lists of chunks from the db by their TypeReps, we can via casting:

retrieveChunksByType :: (HasUID t, DrasilDumpable t, Typeable t) => ChunkDB -> TypeRep -> [t]
retrieveChunksByType cdb tr = relevantChunks
    where
        allChunks = M.toList cdb
        relevantChunks = mapMaybe (\(_, CHUNK c) -> if typeOf c == tr then cast c else Nothing) allChunks

NOTE: There is one problem here (which I go into small discussion into in my prototype), but it's not too important here. Essentially, the if typeOf c == tr then cast c else Nothing seems to be too strict of a requirement, and we might want to lessen to just a cast c (in which case, we can get rid of the then redundant TypeRep parameter), but I'm not entirely certain yet (I will have to do more research on this).

Of course, whenever we want to do this, it will be rather inefficient, so we can create a cache:
(6) A Map of ChunkDBs by their TypeReps:

type ChunksByTypeRep = M.Map TypeRep ChunkDB

dumpChunkDBToTypeRepMap :: ChunkDB -> ChunksByTypeRep
dumpChunkDBToTypeRepMap cdb = allRegistered
    where
        -- gather a list of registered types
        knownChunkTypes :: [TypeRep]
        knownChunkTypes = nub . map (typeOf . snd) $ M.toList cdb

        -- gather types with a list of all registered chunks that are of that type
        chunksWithTypes :: [(TypeRep, [Chunk])]
        chunksWithTypes = map (\x -> (,) x $ retrieveChunksByTypeInChunkBox cdb x) knownChunkTypes

        -- reconcile everything found, into a single ChunksByTypeRep map
        allRegistered :: ChunksByTypeRep
        allRegistered = M.fromList $ map (second chunksToChunkDB) chunksWithTypes

This still might not be the right solution for us because it constructs the ChunksByTypeRepMap after having fully constructed a single ChunkDB, but we can easily create an alternative solution which registers chunks in both maps when registering them.

type ChunkDB' = (ChunkDB, ChunksByTypeRep)

-- There is one small problem here w.r.t uniqueness of UIDs and ensuring that the TypeRepMap is an accurate `view` of the `ChunkDB`
-- To fix it, we would just need to add an extra lookup to the initial chunkDB, removing it from the TypeRepMap manually before re-adding it to both maps (not a large problem, but I noticed it while typing up this ticket)
registerChunk' :: (HasUID t, Typeable t, DrasilDumpable t) => t -> ChunkDB' -> ChunkDB'
registerChunk' c (cdb, trcdb) = (cdb', trcdb')
    where
        u      = uid c
        chk    = CHUNK c
        cdb'   = M.insert u chk cdb
        trcdb' = M.alter
                    (maybe
                        (Just $ M.singleton u chk)
                        (Just . M.insert u chk))
                    (typeOf c)
                    trcdb

retrieveChunk' :: Typeable a => ChunkDB' -> UID -> Maybe a
retrieveChunk' (cdb, _) u = do
    (CHUNK r) <- M.lookup u cdb
    cast r

retrieveChunksByType' :: Typeable a => ChunkDB' -> TypeRep -> [a]
retrieveChunksByType' (_, trcdb) tr = maybe [] (mapMaybe ((\(CHUNK c) -> cast c) . snd) . M.toList) (M.lookup tr trcdb)

Does it solve all noted problems?

i. We are unable to add (almost) arbitrary data into the ChunkDBs for various different systems.
Yes, so as long all all relevant data is typeable, has a UID, and (optionally) can be dumped to a String (DrasilDumpable).

ii. We manually track chunks in lists (by a single type, for later further processing) in SystemInformation when we already have them in nicely placed maps.
Yes, we would have additional functionality for grabbing all chunks in a chunkdb by a particular TypeRep. However, we lose out on the ability of polymorphic types with type constraint restrictions, but it seems that we stick to a small group of types anyway, so this ability may not be needed.

iii. Adding allowed datatypes to a ChunkDB is impossible without editing core drasil-database files, and difficult when editing core drasil-database files because it affects compilation of other examples.
Yes, we will be solving both problems here because the data registerable is nearly arbitrary. Through this, ChunkDB should become mostly stable and unchanging.

iv. Working with similar maps requires redundant manual recreation (swhs and nopcm has a bit of this).
Yes, since ChunkDB is now a single type, we will be able to use Data.Map's abilities to allow for easier merging of ChunkDBs and such.

v. We have occurrences of conflicting UIDs because they are registered in different maps.
Yes. By merging in a single map, we ensure uniqueness is upheld in UIDs.

In general, I think this would decrease LOC while allowing us to generally get more out of our ChunkDBs.

Notable issues

I can only think of 2 issues, but I'm unsure of how impactful they are.

1. We're using Data.Typeable. It appears that this library is largely unstable pre-GHC-8.2, and previously was designed differently. Additionally, since we are discarding type information and later re-gaining it, we will have some amount of runtime impact, but I'm unsure of how much.
2. Retrieving chunks en masse by a single TypeRep is tricky, but I think we can sufficiently manage it. In (5), I briefly mentioned this. However, with a bit of hard work, we can mitigate the overhead -- we should be able to create functions similar to makeLenses which hides the difficulty associated with creating TypeReps and casting chunks/lists of chunks.

I'm posting this ticket earlier rather than later because I think it's a good proof of concept, but it still has problems. I don't think the problems are too 'breaking', but it would be best to discuss the base before I spend more time on this design.

Prototype

I've made, and, lightly, tested this in my mini-development repo: https://github.com/balacij/ExprTests/blob/f7321d55611e7721a339188c79b66a3c6258ee8c/src/Lang/ChunkDB.hs

If you'd like to open up this code locally, I've currently setup stack run to run through a few small tests with this ChunkDB prototype.

[balacij]

I should also mention that the above code is just a prototype, I think we can refine it a bit more. In particular, I think we should be using newtypes for the ChunkDBs, and creating errors (either as an Either X String, or an actual plain error) where appropriate.

[JacquesCarette]

I think the technical ideas on the database side are sound. I'm going to want to work on the names of the functions provided by this, but that's not too hard. I am fine with the use of TypeRep and Typeable.

The thing that I am most curious about is how this will change (or enable change) in user code, as well as in data-drasil. My feeling is that if we adopt a monadic style (specifically: using a State monad with a ChunkDB state) for 'registering', the resulting code will likely be fine. This 'registration' would be what replaces the explicit gathering into lists that we currently have. This is an important "second half" of doing this!

[balacij]

I think the technical ideas on the database side are sound. I'm going to want to work on the names of the functions provided by this, but that's not too hard. I am fine with the use of TypeRep and Typeable.

This sounds great!

The thing that I am most curious about is how this will change (or enable change) in user code, as well as in data-drasil. My feeling is that if we adopt a monadic style (specifically: using a State monad with a ChunkDB state) for 'registering', the resulting code will likely be fine. This 'registration' would be what replaces the explicit gathering into lists that we currently have. This is an important "second half" of doing this!

I like the idea of using State for 'registering'. I will need to spend a bit of time on this.

I also briefly considered how this would impact explicit need for gathering chunks into lists and then 'registering' them, but I was left a bit confused.

My first thought on how this "should be done" is: we wouldn't have any "collection" of chunks from within the modules they're defined. Instead, in the main executable program, we would perform some sort of reflection on known modules from the lib folders and packages, and gather all ones in their scopes.

In Java, I would likely either use Java's Instrumentation API (Agents) to find the related modules at the "class loading time" (I'm not too sure what to call this; pre-runtime-loading?), or I would use Java's reflection lib (in the early stage of my programs runtime) to search for '@' Annotated definitions with a specific annotation class, and annotations that ensures the definition is kept for runtime usage & analysis (@Retention(RetentionPolicy.RUNTIME), and @Target(ElementType.TYPE)).

I suppose the equivalent for the Instrumentation API could be a GHC plugin. Haskell has it's own reflection (and template haskell), which, I think would have (at least) the same functionality as Java's.

Do you have any thoughts on how this second half should be done?

With the first method, we might end up with less "boilerplate annotation" code placed in each "data" module.

[JacquesCarette]

We really don't want to do reflection in Haskell. A lot of this stuff in Java is really meta-linguistic (i.e. outside the actual language). I want to stay within Haskell as much as possible, and within well-understood Haskell too.

So we need to think about the process of registration. Doing inspection on an SRS to find used stuff is good. But we also need to "declare" which things from the standard databases (i.e. data-drasil) we're going to use. I don't want that part to be done via deep black magic.

[balacij]

We really don't want to do reflection in Haskell. A lot of this stuff in Java is really meta-linguistic (i.e. outside the actual language). I want to stay within Haskell as much as possible, and within well-understood Haskell too.
So we need to think about the process of registration. Doing inspection on an SRS to find used stuff is good. But we also need to "declare" which things from the standard databases (i.e. data-drasil) we're going to use. I don't want that part to be done via deep black magic.

Ah, ok. With your example, this makes a lot more sense to me now, thank you. I was thinking of a completely different direction!

Doing inspection on an SRS to find used stuff is good.

This sounds good to me.

But we also need to "declare" which things from the standard databases (i.e. data-drasil) we're going to use. I don't want that part to be done via deep black magic.

I wonder if we could be placing ChunkDBs inside ChunkDBs to indicate an imported "bundle of knowledge". Though, since UIDs for various chunks would be local to the ChunkDB they're placed in, we would need a new mechanism for UID generation/assignment. Manually written strings wouldn't quite cut it anymore because those strings would be local to the specific ChunkDBs they're intended to be placed in. I'm not quite sure how to resolve this yet (vaguely, it seems like we need to give ChunkDB context to chunk definitions when creating them). The sound of placing ChunkDBs within ChunkDBs sounds like a neat way of importing knowledge bundles however!

EDIT:
With ChunkDBs placed inside ChunkDBs, we might only need to collect chunks into their databases once, and then when referencing chunks from other ChunkDBs, we would import the whole ChunkDB they originated from (in the system's ChunkDB), and then the chunk (from whatever chunk that relies on it). However, I would hope that references wouldn't require us to also manually note from which ChunkDB the chunk originates from. Through 'tree shaking' (haha), we can also get rid of all unused chunks from the imported ChunkDBs so that they don't impact SRS documents and code too much.

ASIDE: Would we also want to create an idea of "foreground" vs "background" knowledge within a system? This could likely be used by printers to know whether a piece of knowledge is relevant enough to be printed in it's printing context.

[balacij]

I think this ticket is also loosely relevant to #2195, specifically in understanding the role of SystemInformation.

[JacquesCarette]

I don't necessarily want to put databases inside databases, but I think that creating a "current database for this example" from a collection of other databases, that's definitely a good idea. Which is roughly what you arrived at in your EDIT.

As far as UIDs are concerned, we can learn from URIs there, and use "qualified" names as a means to indicate provenance.

On foreground vs background: yes, but. What I mean is that I really want creators of an artifact to have to think about what they want in their artifact, then make an active choice. Now, when some sets of choice emerge as common, we can definitely create short-hands that automate it. [In many ways, a lot of doc-lang arose from such a process.]

And yes, that other ticket is relevant. The point is that we need to better understand the development process that we want for using Drasil. Because we've been so deep in prototype mode, we were mostly just doing things. Now is a good time to do more design. This is in part what the white paper is a prelude for.

The big question that underlies #2195 is just that: what's the end-to-end development process of a Drasil example? I mean, the process that we envision people should be using, when Drasil is able to support it.

[balacij]

I don't necessarily want to put databases inside databases, but I think that creating a "current database for this example" from a collection of other databases, that's definitely a good idea. Which is roughly what you arrived at in your EDIT.
As far as UIDs are concerned, we can learn from URIs there, and use "qualified" names as a means to indicate provenance.

The main thing that I like about putting databases inside databases is that we get unique UIDs for cheap/free. However, it's quite complex in practice (duplicate and cyclical dependencies, & renaming UIDs from 'import's to be adjusted to it's new parent database), I haven't been able to come up with a design yet, and we'd likely need to be as careful as, if not more, general programming languages (the ones with support for modules & packages) in handling 'imports'. However, I might be thinking about this differently. Out of curiosity, do you think this is the main problem with databases in databases, or do you see a greater problem (or just other problems, I might just not be understanding how to design this at the moment)?

I think using qualified UIDs will mostly simplify the development. However, if we have conflicting UIDs for whatever reason, we might even see some Lens 'setter' usage to import specific modules with different UIDs to not cause breakage. Though, this might cause breakage in references from other imported chunks which depend on a re-UIDd chunk. I'm sure this will very rarely, if ever, occur, but, to mitigate it, it might be good for us to first build out the "concept domain" system you mentioned (to both analyze where breakage would occur, and fix it).

On foreground vs background: yes, but. What I mean is that I really want creators of an artifact to have to think about what they want in their artifact, then make an active choice. Now, when some sets of choice emerge as common, we can definitely create short-hands that automate it. [In many ways, a lot of doc-lang arose from such a process.]

Yes, I agree. I initially thought of coupling this kind of information with CHUNKs, but I quickly realized that it would be too specific to a specific definition of background and foreground (which might be different in each printer!). Thank you.

And yes, that other ticket is relevant. The point is that we need to better understand the development process that we want for using Drasil. Because we've been so deep in prototype mode, we were mostly just doing things. Now is a good time to do more design. This is in part what the white paper is a prelude for.
The big question that underlies #2195 is just that: what's the end-to-end development process of a Drasil example? I mean, the process that we envision people should be using, when Drasil is able to support it.

I see. I'll need to think about this for a while. Thank you 😄

[balacij]

I've just now realized that I completely neglected to mention why I looked into this. I've been looking into this because I need to be able to place arbitrarily parameterized types inside ChunkDBs and, potentially, SystemInformations. I will need to keep prototyping to see the extents of what will be possible, and how. However, I am quite happy with this progress for now. I still need to figure out how the State will work, but the rest mostly seems to make sense at least.

[balacij]

The thing that I am most curious about is how this will change (or enable change) in user code, as well as in data-drasil. My feeling is that if we adopt a monadic style (specifically: using a State monad with a ChunkDB state) for 'registering', the resulting code will likely be fine. This 'registration' would be what replaces the explicit gathering into lists that we currently have. This is an important "second half" of doing this!

I don't think I fully understand how/why we wouldn't need to gather into explicit lists anymore. Do you happen to have any examples of this?