ChunkDB: Conflicting UIDs -- How do we fix them?

[balacij]

Context: #2873

A "conflicting UID" is a UID that appears in more than one of Drasil's chunk database tables. To see which ones currently exist at any time, you can run make debug and peek into the build/X/.drasil/problematic_seeds.json files.

At time of writing, the categories are as follows:

• Terms (IdeaDicts) and Symbols (QuantityDicts) -- e.g., in dblpend
• Terms, Symbols, Concepts (ConceptChunks) -- e.g., in gamephysics, glassbr
• Terms, Instance Models, Concepts -- e.g., in gamephysics
• Terms, General Definitions -- e.g., in gamephysics
• Terms and Concepts -- e.g., in glassbr
• Terms and Units (UnitDefns) -- e.g., in hghc
• Terms and Data Definitions -- e.g., in sglpend
• Terms and Theory Models -- e.g., in ssp

We don't want any conflicting UIDs because when the upgraded ChunkDB prototype is merged, chunks will be overwritten by one another. We need to change the UIDs of things, reorganizing the chunks if necessary.

[balacij]

As @JacquesCarette mentioned in our meeting yesterday (#4087), we're reaching a point where we need to address the elephant in the room: the fundamentally different view on how chunks are formed.

As per the wiki, in the past, chunks were formed in a Matryoshka style, where data was "attached" to smaller nuggets gradually by continuously wrapping around a chunk, with each one sharing the same UID. In fact, they would often nest the entire smaller chunk and all data about the 'smaller thing' would be 'inherited' by the larger thing. Two examples: QuantityDict and DefinedQuantityDict.

With #2873, we are completely diverging from this. Each thing registered in the ChunkDB is a unique chunk now. Previously, a UID could refer to many different chunks.

[JacquesCarette]

Right. Matryoshka style made sense when we started out, and then we discovered that it was a bad idea. So we're going to slowly undo that design towards having more things have their own 'identity'.

[balacij]

Strictly speaking, for the conflicting UIDs issue to "not be an issue" for #2873, we only need to address the above, but the greater issue of "our chunks share UIDs when they aren't supposed to" will most likely continue past #2873 as we move to registering all chunks in Drasil.

[balacij]

IdeaDict

The most prominent issue is IdeaDict (i.e., paired terms [NP -- noun phrases] and abbreviations [Maybe String]) and $X$ (where $X$ is any of our other chunk types). This issue is particularly widespread (and necessary) because of how Sentence works (see #4123).

Additional context: #4039

How do these happen? nw (largely)!

nw forms duplicate IdeaDicts:

Drasil/code/drasil-lang/lib/Language/Drasil/Chunk/NamedIdea.hs

Lines 76 to 82 in 3c832e5

	-- | Historical name: nw comes from 'named wrapped' from when
	-- 'NamedIdea' exported 'getA' (now in 'Idea'). But there are
	-- no more wrappers, instead we have explicit dictionaries. Unwraps
	-- an 'Idea' and places its 'UID' and 'NP' into an 'IdeaDict' with
	-- 'Nothing' for an abbreviation.
	nw :: Idea c => c -> IdeaDict
	nw c = IdeaDict (c ^. uid) (c ^. term) (getA c)

nw works on any chunk that 'are named ideas' and 'are ideas':

Drasil/code/drasil-lang/lib/Language/Drasil/Chunk/NamedIdea.hs

Lines 18 to 31 in 3c832e5

	-- TODO: Why does a NamedIdea need a UID? It might need a UID to be registered in the chunk map.
	-- | A NamedIdea is a 'term' that we've identified (has a 'UID') as
	-- being worthy of naming.
	class HasUID c => NamedIdea c where
	-- | Lens to the term (a noun phrase).
	term :: Lens' c NP
	-- | An 'Idea' is the combination of a 'NamedIdea' and a 'CommonIdea'.
	-- In other words, it /may/ have an acronym/abbreviation.
	class NamedIdea c => Idea c where
	-- | Gets the acronym/abbreviation.
	getA :: c -> Maybe String
	--Get Abbreviation/Acronym? These might need to be separated
	--depending on contexts, but for now I don't see a problem with it.

For example, SSP's ChunkDB:

Drasil/code/drasil-example/ssp/lib/Drasil/SSP/Body.hs

Lines 153 to 163 in 3c832e5

	-- SYMBOL MAP HELPERS --
	symbMap :: ChunkDB
	symbMap = cdb (map (^. output) SSP.iMods ++ map qw symbols) (map nw symbols
	++ map nw acronyms ++ map nw doccon ++ map nw prodtcon ++ map nw generalDefinitions ++ map nw SSP.iMods
	++ map nw defs ++ map nw defs' ++ map nw softwarecon ++ map nw physicCon
	++ map nw physicsTMs
	++ map nw mathcon ++ map nw mathcon' ++ map nw solidcon ++ map nw physicalcon
	++ map nw doccon' ++ map nw derived ++ map nw fundamentals ++ map nw educon
	++ map nw compcon ++ [nw algorithm, nw ssp] ++ map nw units)
	(map cw SSP.iMods ++ map cw symbols ++ srsDomains) units SSP.dataDefs SSP.iMods
	generalDefinitions tMods concIns labCon allRefs citations

The majority of the nw use represents a duplicate UID conflict being created. If we remove them, we'll be greeted with errors of the form:

$caseStudy$: Term: $uid$ not found in TermMap

Ok, how does that happen?

Sentence

When various 'named ideas' are referred to in Sentences, we don't eagerly take the 'name's and place them in Sentences. Rather, we place them in Ch (a constructor of Sentence) that only captures the form UID of the 'named idea' as well as information about the form the name should be rendered:

Drasil/code/drasil-lang/lib/Language/Drasil/Sentence.hs

Lines 52 to 55 in 3c832e5

	data Sentence where
	-- | Ch looks up the term for a given 'UID' and displays the term with a given 'SentenceStyle' and 'CapitalizationRule'.
	-- This allows Sentences to hold plural forms of 'NounPhrase's and 'NamedIdea's.
	Ch :: SentenceStyle -> TermCapitalization -> UID -> Sentence

When they eventually need to be rendered in the final artifacts, they are looked up in the database and placed in the correct form (i.e., singular, plural, acronym):

Drasil/code/drasil-printers/lib/Language/Drasil/Printing/Import/Helpers.hs

Lines 61 to 72 in 3c832e5

	-- | Look up a term given a chunk database and a 'UID' associated with the term. Also specifies capitalization
	lookupT :: ChunkDB -> UID -> TermCapitalization -> Sentence
	lookupT sm c tCap = resolveCapT tCap $ termResolve sm c ^. term
	-- | Look up the acronym/abbreviation of a term. Otherwise returns the singular form of a term. Takes a chunk database and a 'UID' associated with the term.
	lookupS :: ChunkDB -> UID -> TermCapitalization -> Sentence
	lookupS sm c sCap = maybe (resolveCapT sCap $ l ^. term) S $ getA l >>= capHelper sCap
	where l = termResolve sm c
	-- | Look up the plural form of a term given a chunk database and a 'UID' associated with the term.
	lookupP :: ChunkDB -> UID -> TermCapitalization -> Sentence
	lookupP sm c pCap = resolveCapP pCap $ termResolve sm c ^. term

termResolve is the key thing here that creates the error:

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

Lines 131 to 133 in 3c832e5

	-- | Looks up a 'UID' in the term table from the 'ChunkDB'. If nothing is found, an error is thrown.
	termResolve :: ChunkDB -> UID -> IdeaDict
	termResolve m x = uMapLookup "Term" "TermMap" x $ termTable m

Solution?

Now the question is: What do we do to resolve this?

One solution is to "demote" IdeaDict to "not a chunk" (at least temporarily) and think of the IdeaDict table as merely caching the "names"/"terms" of the data the chunks capture -- #4039 .

[JacquesCarette]

I think the first thing to do is probably to remove the meaningless Ch from Sentence and replace it with a number of other, more meaningful holders of information. Because of how Ch works, we're probably stuffing things into a Chunk's 'term' that don't belong there at all. But we need to figure out what a meaningful replacements should be.

We have to remember (and this is a more recent realization) that Chunk is not meaningful; it is a device for making information have a unique key and be re-usable.

So I guess the next step in the investigation is to figure out what functions map to Ch (since we don't use it directly, only indirectly), and then figure out who uses those functions.

[JacquesCarette]

Also, I'd say that IdeaDict is the most prominent symptom of a deeper problem. IdeaDict isn't a problem per se. I do agree that nw itself is much closer to itself being a problem -- because it embodies an incorrect assumption.

The code

Drasil/code/drasil-example/ssp/lib/Drasil/SSP/Body.hs

Lines 153 to 163 in 3c832e5

	-- SYMBOL MAP HELPERS --
	symbMap :: ChunkDB
	symbMap = cdb (map (^. output) SSP.iMods ++ map qw symbols) (map nw symbols
	++ map nw acronyms ++ map nw doccon ++ map nw prodtcon ++ map nw generalDefinitions ++ map nw SSP.iMods
	++ map nw defs ++ map nw defs' ++ map nw softwarecon ++ map nw physicCon
	++ map nw physicsTMs
	++ map nw mathcon ++ map nw mathcon' ++ map nw solidcon ++ map nw physicalcon
	++ map nw doccon' ++ map nw derived ++ map nw fundamentals ++ map nw educon
	++ map nw compcon ++ [nw algorithm, nw ssp] ++ map nw units)
	(map cw SSP.iMods ++ map cw symbols ++ srsDomains) units SSP.dataDefs SSP.iMods
	generalDefinitions tMods concIns labCon allRefs citations

is trying to do something reasonable: take a bunch of information present in an example, and insert all the vocabulary used in the database. That's good!

Except that some of those things being treated as 'vocabulary' are not. And the symptom is the need to 'cast' them. That, I think, is where our real problem lies. Everything in that line should be looked at to see if it is 'vocabulary' or if it is something else. And why, when it is 'something else', we need to treat it as vocabulary for the example to work. We are making a "semantic mistake" which shows up by our need to treat things that are not vocabulary as vocabulary.

[balacij]

I think the first thing to do is probably to remove the meaningless Ch from Sentence and replace it with a number of other, more meaningful holders of information. Because of how Ch works, we're probably stuffing things into a Chunk's 'term' that don't belong there at all. But we need to figure out what a meaningful replacements should be.

We have to remember (and this is a more recent realization) that Chunk is not meaningful; it is a device for making information have a unique key and be re-usable.

So I guess the next step in the investigation is to figure out what functions map to Ch (since we don't use it directly, only indirectly), and then figure out who uses those functions.

All of our chunk tables are dumped to disk with make debug, so I'll give it a proper look tomorrow, but from a quick skim, I don't see anything that screams "abuse."

Or are you saying that Ch should be replaced with, say, NameOfDD, NameOfTM, NameOfQuantity, etc. (though with better names)? This would amount to also telling which chunk type map termResolve should look into. Typed UID references could be the solution to this. With the current database, this might involve a lot of monotonous work (if we were to add a TUID type with information about which chunk table to look up the table from), but, ironically, with #2873, this is fairly straightforward to implement -- https://github.com/balacij/ProtoChunkDB/blob/efd0a24723f8528688b5089cb7467d5d249120a5/src/TypedUIDRef.hs#L14-L25 .

One alternative, hacky solution could be to create fake IdeaDicts on the fly whenever a UID misses the termTable but hits for one of the other tables:

-- | Looks up a 'UID' in the term table from the 'ChunkDB'. If nothing is found, an error is thrown.
termResolve :: ChunkDB -> UID -> IdeaDict
termResolve m x -- = uMapLookup "Term" "TermMap" x $ termTable m
  | (Just (t, _)) <- Map.lookup x (termTable m) = t
  -- SUPER HACK: The below are hacks to allow any 'DataDefinition' or 'QuantityDict' or ... to have their terms auto-extracted and used. Generates a fake `IdeaDict`.
  | (Just (t, _)) <- Map.lookup x (symbolTable m) = nw t
  | (Just (t, _)) <- Map.lookup x (conceptChunkTable m) = nw t
  | (Just (t, _)) <- Map.lookup x (_unitTable m) = nw t
  | (Just (t, _)) <- Map.lookup x (_dataDefnTable m) = nw t
  | (Just (t, _)) <- Map.lookup x (_insmodelTable m) = nw t
  | (Just (t, _)) <- Map.lookup x (_gendefTable m) = nw t
  | (Just (t, _)) <- Map.lookup x (_theoryModelTable m) = nw t
  | (Just (t, _)) <- Map.lookup x (_conceptinsTable m) = nw t
  | otherwise = error $ "Term: " ++ show x ++ " not found in TermMap"

This code should be easy to remove once we have typed UIDs. Though, I'm not sure if it returning an entire IdeaDict is the right move regardless.

Now, a question is: What's our end goal with this?

Consider the following sentence:

purp :: Sentence
purp = foldlSent_ [S "predict the", phrase motion `S.ofA` S "single", phrase pendulum]

Currently, phrase inserts a Ch Sentence constructor in place with the UID of motion and pendulum, respectively:

purp = foldlSent_ [S "predict the", Ch TermStyle NoCap (motion ^. uid) `S.ofA` S "single", Ch TermStyle NoCap (pendulum ^. uid)]

Ideally, what should it be saying? Instead of motion ^. uid, should it be something more similar to TermOf motion which would be processed approximately as resolveIdeaDict $ motion ^. ideaDict when rendering? If I'm understanding your second comment correctly, this question should be in line with it.

[balacij]

• GlassBR contains an IdeaDict {uid = "refBy", term = "referenced by", abbreviation = Just "RefBy" }. It also has this term duplicated for UIDs: refBy and refByDom.
• HGHC has IdeaDict {uid = "fp", term = "FP", abbreviation = Nothing}.
• Each case study seems to have IdeaDicts that contain the NFR/FR types, assumptions, goals, etc. I'm not sure if this is desirable because, for example, A is not a common abbreviation for assumption, but it is the prefix label we use for the group of assumptions -- Re-design of prependAbrv #3626 .
• SWHS has a few oddities that conflate symbols with abbreviations (similar, but different):

[JacquesCarette]

Yes, my thought was along the lines of NameOfDD, etc, with better names. Typed UIDs would be a good addition that would let us embed things into Sentence with less fear and no need for tons of new constructors.

Your termResolve prototype is worth investigating; but it should return a NounPhrase, no? It's called termResolve because, at the end of the day, that's the only thing it is after.

I do think that termOf motion would be better (lower-case, to allow termOf to do some processing before generating a TermOf). In fact, we might want to rename, and call it term, and rename our current lens to something else. And yes, you seem to be understanding properly.

Your investigation seems to have turned up some oddities that probably need fixing. Does feel like an incorrect use of IdeaDict.

[balacij]

The majority of the "IdeaDicts and $x$" issues are resolved. The remainder of the issues stem from things imported from drasil-data, but I think @jackwyand's work is clearing through a lot of those -- at least from what I've seen across the last few notes.

The vast majority of the remaining issues are now on a similar wavelength to our IdeaDicts issue, ConceptChunk and $X$:

    "t_0": [
        "symbols",
        "concepts"
    ],
    "theory:accj": [
        "instanceModels",
        "concepts"
    ],

[balacij]

Now, recall that there are also many IdeaDict and ConceptChunk UID conflicts that we're suppressing right now by just not registering the IdeaDicts. A similar kind of solution should be possible for ConceptChunk, but I'm not sure if it's conceptually the right idea. Why?

First, recall a bit of key ConceptChunk components:

-- | Concepts are 'Idea's with definitions and domains.
type Concept c = (Idea c, Definition c, ConceptDomain c)

...

-- | For projecting out to the 'ConceptChunk' data-type.
cw :: Concept c => c -> ConceptChunk
cw c = ConDict (nw c) (c ^. defn) (cdom c)

...

-- | The ConceptChunk datatype records a concept that contains an idea ('IdeaDict'),
-- a definition ('Sentence'), and an associated domain of knowledge (['UID']).
--
-- Ex. The concept of "Accuracy" may be defined as the quality or state of being correct or precise.
data ConceptChunk = ConDict { _idea :: IdeaDict -- ^ Contains the idea of the concept.
                            , _defn' :: Sentence -- ^ The definition of the concept.
                            , cdom' :: [UID] -- ^ Domain of the concept.
                            }
makeLenses ''ConceptChunk

We seem to have a clear idea of what ConceptChunks are for: they establish English definitions for our vocabulary (an English definition for a word) for a list of applicable domains. So, applying the same solution would mean that we have multiple chunks that provide definitions for terms.

So, why is a solution similar to that of IdeaDicts questionable? Several reasons:

1. A ConceptChunk establishes a definition. What if we wanted to declare alternative definitions for a word? We would have two ConceptChunks to the same IdeaDict (i.e., same UID for both the ConceptChunks and shared with the IdeaDict). There should be 3 unique UIDs here. This is inadequately captured. Additionally, the relationship between a chunk that implements Concept and ConceptChunk is unclear. What does that relationship mean?
2. A QuantityDict isn't an instance of a Concept -- this solution wouldn't work. It has no definition:

-- | QuantityDict is a combination of an 'IdeaDict' with a quantity.
-- Contains an 'IdeaDict', 'Space', a function from 
-- 'Stage' -> 'Symbol', and 'Maybe' a 'UnitDefn'.
--
-- Ex. A pendulum arm does not necessarily have to be defined as a concept before
-- we assign a space (Real numbers), a symbol (l), or units (cm, m, etc.).
data QuantityDict = QD { _id' :: IdeaDict
                     , _typ' :: Space
                     , _symb' :: Stage -> Symbol
                     , _unit' :: Maybe UnitDefn
                     }
makeLenses ''QuantityDict

In fact, there are no Sentences around it! However, we seem to not use QuantityDicts as often as I thought. For example, when rendering the table of symbols (via TSymb' -- #4216), we use DefinedQuantityDicts (or one of its extension chunks) and then project out the QuantityDicts for registration in the ChunkDB. Recall DefinedQuantityDict:

A DefinedQuantityDict (and its ConstrConcept and UnitalChunk extensions) are Concepts, however:

-- | DefinedQuantityDict is the combination of a 'Concept' and a 'Quantity'.
-- Contains a 'ConceptChunk', a 'Symbol' dependent on 'Stage', a 'Space', and maybe a 'UnitDefn'.
-- Used when we want to assign a quantity to a concept. Includes the space, symbol, and units for that quantity.
--
-- Ex. A pendulum arm can be defined as a concept with a symbol (l), space (Real numbers), and units (cm, m, etc.).
data DefinedQuantityDict = DQD { _con :: ConceptChunk
                             , _symb :: Stage -> Symbol
                             , _spa :: Space
                             , _unit' :: Maybe UnitDefn
                             }

makeLenses ''DefinedQuantityDict

They are Concepts, and the ChunkDB contains two projections from our DefinedQuantityDicts: the QuantityDict and the ConceptChunk.

To give a concrete example of this in practice:

-- Data.Drasil.Concepts.Physics
iPos :: ConceptChunk
iPos = dccWDS "iPos" (cn "initial position") (S "The" +:+ phrase position +:+ S "at the body's initial point")
-- ^ contained in a list: `physicsCon`

-- Data.Drasil.Quantities.Physics
iPos :: UnitalChunk
iPos = uc CP.iPos (sup lP initial) Real metre
-- ^ contained in a list: `physicscon`

Two of our case studies import both:

>  rg "physic(C|sc)on[^\']" -ths
drasil-example/dblpend/lib/Drasil/DblPend/Body.hs
25:import Data.Drasil.Concepts.Physics (gravity, physicCon, physicCon', pendulum, twoD, motion)
28:import Data.Drasil.Quantities.Physics (physicscon)
152:  map nw [algorithm, len, mass, errMsg, program] ++ map nw physicCon ++ map nw mathcon ++ map nw physicalcon ++

drasil-example/projectile/lib/Drasil/Projectile/Lesson/Body.hs
17:import Data.Drasil.Quantities.Physics (physicscon)
18:import Data.Drasil.Concepts.Physics (physicCon)
67:symbMap = cdb (map qw physicscon ++ symbols) (nw projectileMotion : map nw doccon ++ 
68:  map nw doccon' ++ map nw physicCon ++ concepts ++ map nw mathcon) 

The remainder of our case studies seem to only import physicCon. Regardless, this is a huge grey area that needs further investigation. Specifically, we need to investigate if the QuantityDict shared UIDs with ConceptChunks is also relevant to the code generator. #4201 seems to indicate that it is relevant.
3. I can't quite tell if we're conflating descriptions with definitions when it comes to our use of ConceptChunks. This needs to be investigated further.

[JacquesCarette]

There are two chunks with UID "t_0" !?!? That's horrible! There should be none with such an untraceable UID.

"theory:accj" conflict seems like a straight bug from the old days, where an instance model would be seen as "the same thing" as its underlying concept. That should be an easy fix, by having instance models refer to concepts instead of taking on their identity.

I'm surprised no analysis of these conflicts came up with those conclusions?

[JacquesCarette]

For ConceptChunk vs IdeaDict, I think the "solution" is simple: don't nest. Then we get two possibilities for the "new" ConceptChunk:

1. have a piece of vocabulary that comes with a definition all the time.
2. have a piece of vocabulary (IdeaDict) that has multiple definitions (so a new data-structure that adds a definition to an IdeaDict that it refers to.

So that means getting rid of the current implementation of ConceptChunk completely, and replacing it with 2 different ones. My guess is that most of our current ConceptChunks will fall into the first kind, and so we can keep the name as is, to minimize churn.

[I have not had the time to think through the projections problem, I'll have to come back to that part.]

[JacquesCarette]

QuantityDict also (now) has a clear definition: it is supposed to represent a variable (thus the symbol) representing a quantity (thus the name) of the type/unit given, 'of' the thing pointed to by the IdeaDict. So a 'quantity' should be an entity separate from the underlying piece of vocabulary. So that suggests that QuantityDicts should get their own UID, separate from the thing it's denoting a quantity of.

Going up one level, to your "concrete example of this in practice", I think the same layering could happen here. Little would change in the code, except that the UnitalChunk would get it own UID, everything else could stay as is.

So the next lot of duplicate UIDs should be fixed by having more things "be their own thing" and thus have their own UID.

[balacij]

This was completed with #4465 being our latest PR needed to fixing up the conflicting UIDs.