The key step to the IKAT algorithm is the IKAT function call which allows the renderer to leap dynamically around the set of template files, guided by a form of "argument matching process" which locates the most "suitable" of a set of tags sharing the same ID, to be used to render the component which it currently has in its hands.

If you have got here via the link from the IKAT algorithm, then you will know that at this point the IKAT algorithm is in the "extended state", having in its hands a "current container", a particular child of this container which is also a container (called the PSC), and is at an index in the template file holding a tag (the "forking tag") whose prefix agrees with the prefix of the PSC. The "current container" is peering with a tag called the "scoping tag", which will be the nearest ancestor of the "forking tag" which mentions an rsf:id.

If you got here by some other means, you will probably not want to read on much further.

IKAT Function Call Resolution in detail#

At this point IKAT assembles the resolution set for the function call, which consists of all tags throughout the current set of template files which share the prefix of the PSC. It then scans through all of these, assigning them a priority based on their quality of match to the PSC container.

This procedure can be seen as one of "argument matching", and it procedes based on the IDs of the children of the PSC (yes, that is, drawn from the grandchild components of the "current container"). The IDs of these children (called the set {I_P}) represent the "producer demand" on the template system, and can be seen as the "actual arguments" of the function call. These IDs are matched against the child tag IDs of the putative tags in the resolution set (which, you remember, share the prefix of the PSC). These IDs may be seen as the "formal parameters" of the function call, called the set {I_T}.

For each tag T in the resolution set, IKAT computes a numeric priority, which essentially encodes a lexicographic ordering on three sorts of desirability. This logic is implemented in the evalDeficit function in highest level of desirability is attached to there being NO MISSING MEMBERS from {I_T} that were demanded in {I_P}. IKAT adds a penalty of 1,000,000 for each missing child tag of this sort, assessed solely by prefix.

The second level of desirability is assesed by bringing the suffices of {I_P} into consideration. For each tag in {I_P} that does not have an exact match, both in prefix and suffix in {I_T}, IKAT adds a penalty of 1000.

Penultimately, IKAT adds a penalty of 1 for each "unficit" - an extra tag in {I_T} that does not appear in {I_P}.

IKAT will then select the target tag with the lowest overall priority, breaking ties with the following scheme[1]:

  1. FIRST priority to tags in the "current scope" (i.e. nested in the "scoping tag") where the tag ID is an EXACT MATCH for the current template ID.
  2. SECOND priority to tags in the current scope where only the tag prefix is a match for the current template ID.
  3. THIRD priority to non-local tags where the tag ID is an exact match of the current template ID.
  4. FOURTH priority to non-local tags where only the tag prefix is a match for the current template ID.
Finally, IKAT adds a "tie-break" penalty of 1 for "locality" of the target tag. If the target tag is NOT a child of the "current container".

If after all of these rules have been followed, there are still multiple tags with the same priority (could happen quite easily where the tags have no children), IKAT will pick the first such tag in the document.

Despite appearances, this algorithm runs really quite quickly (a few microseconds), and could no doubt be accelerated even further by some form of caching, since the template is expected to change very infrequently and will probably face only a small variety of distinct function call demands from producers during its lifetime.

[#1] NB, these following rules could also be implemented by appending them to the low-order bits of the penalty, I have not got around to doing this since to be honest this level of fine-tuning is so subtle I suspect noone is likely to devise a template that relies on it. This of course being said at the moment of there being exactly 3 IKAT templates in the world....
[#2] However, there does need to be a further "tweak" to the "tie-break" rules that will cause IKAT to cycle in sequence through all local tags which are equally good matches to the PSC, to allow rendering hacks like the "every second table row a different colour" type thing. So, together with the "bit-ised" version of [1], this results in using up the 3 low-order bits of the penalty scalar, multiplying all the above penalties by 8...

Add new attachment

Only authorized users are allowed to upload new attachments.
« This page (revision-) was last changed on 19-Jul-2006 09:36 by UnknownAuthor