TMRM Exegesis: Primitive Navigation

Now that we know how proxies form atomic blocks to build maps, we can start to navigate through a given map. Since the structure is so minimalistic we can expect that there are only a few ways to get around a map.

Let us first assume that we have a single proxy in our hand:

FDE78CC := { shoesize => 42,
              beard => white,
              beard => long }

4 Corners of the Compass

One thing we could be interested in is to find all it keys of that proxy. Now, for this operation TMRM has already defined a function, unsurprisingly called keys. In the above case it returns 3 proxies:

FDE78CC \ = [ shoesize, beard, beard ]

We use \ as ASCII replacement for the vertical down-arrow TMRM is using. Annex C cleverly contains a list of symbols and how they can be emulated in ASCII (kudos Patrick).

You will note that the result of the \ navigator is not a set, rather a multiset since a particular key may appear any number of times within a proxy. We definitely do not want to lose that information.

Another thing we might be interested in is to learn which values are behind a particular key for a given proxy. If we tried this with our proxy and the key beard, then we expect to see the multiset

FDE78CC -> beard = [ white, long ]

Another axis of interest could be to learn whether and where our proxy is actually used somewhere else. Now somewhere else can only be in another proxy, say,

FDE78AA := { person => FDE78CC,
             person => DFEA89C }

and there it can only be a key or a value. If we wanted to know where the proxy FDE78CC is used as value, then we will expect

[ ...., FDE78AA, ... ]

The ...'s symbolize that the remaining results depend on the map we are operating in. This is in contrast to the navigators \ and -> above which are only dependent on a proxy. Here we also need to take into account a map.

To find all proxies in which a particular proxy is the value for a particular key, TMRM defines the <- navigator:

FDE78CC <- person = [ ..., FDE78AA, .... ]

Again, this is only defined in the context of a map.

Finally, to find all keys where the proxy is the value for it, there is the / navigator:

FDE78CC / = [ ..., person, ... ]

Also that one depends on a contextual map.

That would be basically it, except for some minor twists:

Subtyping Keys

When we above used FDE78CC -> beard to retrieve all values for a key, then the TMRM processor has not any leeway: If the proxy contained a

goatee => grey

key/value pair then our query would not catch that, even if goatee were a subtype of beard.

To honor subtyping for keys TMRM has generalized the -> navigator. In the starred variant we also would get the goatee property:

FDE78CC -> beard * = [ white, long, grey ]

This key-subtyping is also defined for <- in an analoguous way.

Navigating from Values

The second twist is also a generalization. As it stands, we can apply our navigation operators only to proxies. But it is equally justified to start navigating from primitive values, not that we always can expect a non-empty result.

But for 42 <- shoesize we can definitely expect to see

42 <- shoesize = [ ..., FDE78CC, .... ]

The advantage of this generalization is that the navigation operators can now be chained:

42 <- shoesize * -> beard *

Bare Bones Query Language

If you had implemented TMRM, then \, /, ->* and <-* would give you already a primitive navigation language, one which you could theoretically use to query any TMRM map.

Clearly, this is not overly comfortable, well unless you find micro-assembler programming comfortable. What the TMRM editors have chosen to do is to use this primitive path language to define a high-level one. That is formalized in Annex A. It looks impressive at first sight, with all the maths winding up for TMQL. But once you have seen a few examples how it operates on tables (actually sequences of tuples) these high-level path expressions quickly lose their cryptic nature.

But before we go there, we will look again at the navigation axes, but this time at those for TMDM. It allows us to investigate how these can be used for virtualizing maps.

Work supported by the Austrian Research Centers.

Posted In