I am designing a DSL (in clojure, specifically; though this question is more general than that) in which 'entities' are tracked as immutable hashes/maps, and where the 'concept' membership of an entity is dynamically determined by the keys and values of the maps. A toy example of how this would appear:
(defconcept AnnotatedEntity :contains [annotations meta-data])
(defconcept PointCloud :contains vertices)
(defconcept Polygon :contains [vertices edges])
(defconcept Triangle
:isa Polygon
:condition (= (count vertices) 3))
(defconcept Rectangle
:isa Polygon
:condition (= (count vertices) 4))
(concepts {:vertices [[0 0], [0 1], [1 0]] :edges [[0 1] [1 2] [2 0]]})
#{PointCloud Polygon Triangle}
(concepts {:vertices [[0 0] [0 1] [1 1] [1 0]]
:annotations {:name "unit-rectangle point-cloud"}
:meta-data {}})
#{PointCloud AnnotatedEntity}
Since the :condition of a concept is just a function that gets run on the map, we can ignore this part of the test (and thus any requirements on the values) for now; my interest is in efficiently identifying all of the possible concepts in which a given map might hold membership based on its keys. I.e., let's simplify the above to just this:
(defconcept AnnotatedEntity :contains [annotations meta-data])
(defconcept PointCloud :contains [vertices])
(defconcept Polygon :contains [vertices edges])
(defconcept Triangle :contains [vertices edges])
(defconcept Rectangle :contains [vertices edges])
(possible-concepts {:vertices [[0 0], [0 1], [1 0]]
:edges [[0 1] [1 2] [2 0]]})
#{PointCloud Polygon Triangle Rectangle}
(possible-concepts {:vertices [[0 0] [0 1] [1 1] [1 0]]
:annotations {:name "unit-rectangle point-cloud"}
:meta-data {}})
#{PointCloud AnnotatedEntity}
Currently, I perform this by brute force, which is plenty efficient for toy examples, but which is not efficient enough for a core piece of a library that will sometimes be called many many times per millisecond with arbitrarily large maps and arbitrarily many concepts.
One simple example of an optimization that improves this process is to keep track of a map of all keys included in any concept such that the values are sets of concepts containing the key; for the above example:
(def concepts-of-keys {:annotations #{AnnotatedEntity}
:meta-data #{AnnotatedEntity}
:vertices #{PointCloud Polygon Triangle Rectangle}
:edges #{Polygon Triangle Rectangle}})
(defn possible-concepts [ent]
(set (filter #(every? (partial contains? ent) (.getKeys %))
(apply clojure.set/union (map concepts-of-keys (keys ent))))))
This is quite a bit better than simply testing against every possible concept, but only if concepts have fairly unique keys. If every concept depends on a single key like :meta-data or :id or something very common (or all concepts inherit from a single base concept) then this is basically as inefficient as checking every concept.
Accordingly I don't believe that either of these are the best solution. For example, one might imagine building a decision tree (which would, in practice, be wrapped in a ref or atom and updated as concepts are defined):
(def concept-decision-tree
"
Each element of the decision tree is [test-keys if-every if-not-every] where
test-keys is a key or set of keys that should be tested for membership in a
given entity; if the entity contains all these keys, descend along the
if-every element and along the if-not-every otherwise. These values are sets
if the membership of the entity has been deduced by the most recent
decision.
"
[#{:annotations :meta-data} ;; if the entity has all of these elements...
;; descend into this subtree
[:vertices [:edges #{AnnotatedEntity PointCloud Polygon Triangle Rectangle}
#{AnnotatedEntity PointCloud}]
#{AnnotatedEntity}]
;; otherwise, descend into this subtree...
[:vertices [:edges #{PointCloud Polygon Triangle Rectangle}
#{PointCloud}]
#{}]])
(defn possible-concepts [ent]
(loop [[test-keys if-every if-not-every] concept-decision-tree]
(if (every? (partial contains? ent)
(if (set? test-keys) test-keys [test-keys]))
(if (set? if-every) if-every (recur if-every))
(if (set? if-not-every) if-not-every (recur if-not-every)))))
This is better yet, assuming we can maintain the decision tree; what I'm wondering is what is the best way to do that, or, alternately, what is an alternative that is equally/more efficient? It is not obvious to me how one would balance such a decision tree as concepts were added.
My intuition is that this problem has a theory that is is widely understood and that I just don't know the formal name for the problem; for that matter I should mention that I'm intellectually interested in the most optimal answer and not in the answer that can be written fastest or that a project manager would most approve of.
In other words, what I'm looking for in an answer:
- A solution to the decision-tree updating problem, either conceptually with enough details to implement, or a simple example implementation
- An alternative solution to this problem that is equally/similarly/more efficient
- A pointer to a the computer science literature on this topic
- A formal/standard name for this problem
- Examples of libraries or languages that implement this form of typing dynamically
What I'm not looking for in an answer:
- a brute-force solution (I already have one!)
- "<something something> premature optimization is the root of all evil, <something something> so just brute force it."
One other thing I should mention: though I've written these examples using standard maps, I'm not opposed to a solution that involves a special subclass of the persistent map class that tracks its keys and annotates newly created maps with their types as they are created. E.g., a special type that imiates maps but knows that when it encounters (dissoc ent-map :vertices) the new map should have concepts like PointCloud, Polygon, etc. removed from its concept list.
Thanks in advance!
