Hi
I'm about to start implementing matchers that are type aware in guile-log. The status now is that I have a quite advanced and good indexing mechanism in my matchers that will mean that I easilly can parse out the matching line in a very fast way. I do this by employing classical techniqes taken from n classic AI book and add to that a hefty use of bitsets.
Of cause it can be better, faster etc. But I like what I got. But it can be better.
One of the difficulties matching Types is type inheritance. And especially the multple version. It Turns out that your hierarky will be an acyclic directed graph. Knowing that this is a useful datastructure and pattern I decided to try getting this effective like scalable quite fast etc.
So how to I code the inheritance.
A very fun algorithm to construct is to take a set of atoms (x1, ...., xn), a set of arrows ((i,j),...) and try generating a ordering e.g. xi -> j, so that this defined order does not missmatch with the partial order defined through the acycllic graph. For bonus point generate a uniform random sample if such a linear order on them. How do you do this? .....
Well you find out about the set of sources and the set pointing to those sources, P. You start to
enumerate the sources and then find the parents in P who just points to sources, add the next numbers to them, add them to the sources and remake P agaion finding the parents who only points to sources and iterate. Voila you will have created the linear order. make sure to codify the generations of an order i as gen(i) pointing to the first order in the next generation
For the next step let element with order i map to bit(i) the number with bit i a one and zero else.
Then map each i to a inheritance set i -> ih(i). when j -> i you take ih(j) = ih(i) | ih(j) if we employ the bitwice C or operator. When this process are finished you will have ih pointing to the set of elements classes that i is depending on. Then finally let iih(i) be the bitvector with all bits above the bit(gen(i)) as one.
Now you can create a binary tree T(x1,,,,,xn) so for a pair t=(t1,t2), there are ihh's
ihh(t1), ihh(t2), then ihh(t) = ihh(t1) | ihh(t2) this is a well defined coding and now you use it as
follows
if you want to match a class s or it's subclass at position with the tree T, let ih = ih(s) , then
if ih & ihh(Tree) == ih there might find a match in the tree. Now visit the branches whose ih & ihh == ih and continue down a tree. if you find a leaf with ihh & ih == ih you take the value of the that. It will be a bitvector representing the available matches and | them all together. This means that in the end we will have a bitset representing all the valid matches for this position and this can be used as input in the indexer.
The constructioning of the tree is crucial. first of all a class system is forest of acyclic graphs.
list them. For each acyclic graph take out one parent set who does not have any parents themselves list them first, then list the new forest of acyclic graphs and continue recursivele intill you have a tree of classes, linearize that tree and use that order to construct a binary search tree as explained above.
Hmm maybe you can do better, but you get the gist of it, it's quite fun. It all boils down to create a tree that act as a search tree and not as a list. I will have such a compilation of the indexer at the first lookup in the matcher and doo all this lazilly. I will maintain this tree as a balanced functional tree and will allow it to dynamically add new classes. The tree will then update functionally in order
to be able to restore an old state, it will then perhaps result in an non optinal search tree but one may trigger a reindexing of the tree programatically to yeild a better one.
This is probably way too advanced for the small type class structures that are out there, but I want something to scale, I do think it's a really interesting feature to have cause the great utility of acyclic graphs or partial orders.
A final little optimisation, the application may have a huge system of classes. encoding them as bitvectors are a bit heavy if you have 10000 of them, 1000 is kind of ok, but still a bit heavy. I do plan to maintain subsets in the actual matcher which make sense in type applications because a generalized fiunction does usually just touch a fraction of the overall functional tree. Also there is quite a lot of tricks you can do in a compilation step to avoid over creating large numbers and keep the gc calm e.g. using mutating aperators like X |= p or even (serbit X k) etc.
Happy hacking.
Stefan