MapLink

From OpenCog
Jump to: navigation, search

The MapLink a link type analogous to the `map` function commonly found in functional programming languages, such as the scheme SRFI-1 `map`, or `map` in haskell.

MapLink generalizes of the map concept in several ways. First, the MapLink can be applied to either SetLinks or ListLinks. Secondly, MapLink performs type-checking on its inputs, so that mismatched inputs are discarded; thus, it is a kind of FilterLink.

In many ways, MapLink is similar to BindLink, except that MapLink does not search the entire atomspace for matching patterns; rather, it only examines the given input list/set, and applies the map to that.

In many ways, MapLink is the opposite of PutLink, in that it un-does a beta reduction, by extracting values from a matching pattern. Thus, MapLink could have been named UnPutLink, CoPutLink or ExtractLink or UnBetaReduceLink. See the page Atom relationships for more about opposites.

These ideas are illustrated in the examples shown in /examples/guile/map.scm. The first 4 examples illustrate the extraction of values for a single variable; this is, of un-beta-reducing a single composition. This includes a demonstration of type checking, which can be used to implement filtering. The next few examples show how multi-variable extraction works, as a straight-forward extension of the single-variable case. The final examples illustrate actual "mapping", that is, graph re-writing or graph transformation as a result of applying a mapping function.

Summary

Please see /examples/guile/map.scm for fully-documented examples of how to use MapLink.

The MapLink has two basic forms. The first form looks like this, and behaves as a filter:

MapLink
   ScopeLink
       variable declarations (e.g. VariableList)
       pattern body (containing above variables)
   SetLink
       collection of items to which the above pattern is applied to.

This behaves like a filter, because the pattern body is applied to each of the items in the SetLink. If there is a match, then values for the variables can be fished out of the item. So, in this form, MapLink behaves like a pattern-matching filter, or, conceptually like an UnPutLink or a CoPutLink, categorically "opposite" to PutLink.

The second form is

MapLink
   ImplicationScopeLink
       variable declarations (e.g. VariableList)
       antecedent pattern body (containing above variables)
       consequent pattern body (containing above variables)
   SetLink
       collection of items to which the above pattern is applied to.

In short-hand, one might write P(x,y)->Q(x,y) where x,y are the variables, P(x,y) is the antecedent, and Q(x,y) is the consequent. The arrow is the implication.

In this form, the MapLink behaves both as a filter, and as a rewrite rule. This is closer to the scheme srfi-1 map, or the haskell map, but not the same. In scheme/haskell, the antecedent is always trivial, and accepts any pattern. When this means that scheme and haskell cannot extract variable groundings from complex patterns. Or rather, that scheme/haskell cannot extract variable groundings without jumping through a lot of extra hoops, writing a lot of extra code. Whether or not this is a design advantage can be further debated. Since OpenCog desired to be a kind of relational database with pattern matching as a core primitive, there seem to be important advantages to merging mapping with filtering (i.e. implementing re-writing as a basic primitive). In the end, we are shooting for speed, usability and mathematical beauty.

Motivation; Performance considerations

MapLink was originally motivated by the idea that it might possibly be a "performance-enhanced" version of BindLink. The imagined "performance advantage" was that it would not have to search "the entire atomspace", and that, instead, it only applied to some "small set".

The performance advantage is somewhat illusory. First, the BindLink does not have to actually search the "entire atomspace"; the current implementation employs a number of effective algos to limit the search to the smallest possible subset of the atomspace. BindLink doesn't splurge, and isn't wasteful.

Usability considerations

The SetLink has several usability issues, some of which are severely negative, and these are inherited by MapLink. The usability issues are discussed in detail, on the SetLink page. The primary one affecting MapLink is this:

  • All Links are immutable, and so are SetLinks. Thus, once created, they cannot be altered; they can only be created and destroyed. That means that elements can neither be added to, nor removed from an existing SetLink.

Thus, using SetLinks for declarative knowledge is problematic. It does work OK for procedural usages, where the SetLinks are generated on-the-fly, out of thin air, as some procedural evaluation plods along. Fortunately, the MapLink is intended to be a procedural atom, so the SetLink-based interface is acceptable. See the page "atom relationships" for a general review of procedural vs. declarative usage in the AtomSpace.