SignatureLink

A SignatureLink is a type constructor -- it is used to declare a pattern type signature. A signature consists of type declarations, and is used to declare an algebraic data type. It can be used wherever a TypeNode can be used: for example, with the TypedVariableLink (which is used inside of VariableList, LambdaLink and BindLink) to specify complex variable types. It can also be used with the TypedAtomLink to indicate the type of some given atom. Signatures are used by type checking to enforce type restrictions.

Function type declarations can be created with the ArrowLink, which is a function type constructor.

The FilterLink proposal uses the SignatureLink to filter a set of atoms.

The deep types page discusses a similar idea.

The FuzzyLink is a link type, similar to a SignatureLink, but not requiring an exact match, but allowing only an approximate match. This can be used to perform fuzzy searching.

Examples

This is best illustrated by means of examples. Thus, for example, the following link:

ListLink
   ConceptNode "some"
   ConceptNode "thing"

has the signature

SignatureLink
   ListLink
      TypeNode "ConceptNode"
      TypeNode "ConceptNode"

Conversely, the above signature only matches the structure of ListLinks that have exactly two members in their outgoing set, both of which are ConceptNodes.

A more complex example is the prototypical EvaluationLink, having the form

EvaluationLink
   PredicateNode "Some property"
   ListLink
       ConceptNode "thing A"
       ConceptNode "thing B"

This has the signature:

SignatureLink
   EvaluationLink
      TypeNode "PredicateNode"
      ListLink
         TypeNode "ConceptNode"
         TypeNode "ConceptNode"

Type constants

Signatures can include constants. In that sense, they resemble the patterns searched for by the pattern matcher. Thus,

EvaluationLink
   PredicateNode "Some property"
   ListLink
       ConceptNode "thing A"
       ConceptNode "thing B"

also has the signature

SignatureLink
   EvaluationLink
      TypeNode "PredicateNode"
      ListLink
          ConceptNode "thing A"
          TypeNode "ConceptNode"

as well as the signature

SignatureLink
   EvaluationLink
      PredicateNode "Some property" 
      ListLink
         TypeNode "ConceptNode"
         ConceptNode "thing B"

These signatures are narrower, in that they specify types that are more restrictive. Thus, the first signature above will match any EvaluationLink, with any PredicateNode, but it must explicitly have ConceptNode "thing A" within it. The second signature only matches those EvaluationLink's whose PredicateNode is "Some property". When a specific non-type atom appears in a SignatureLink, it can be thought of as a "type constant"; it is fixed, not variable. Thus PredicateNode "Some property" is a type constant in the last example.

Polymorphism

The TypeChoice link can be used to define polymorphic signatures. Thus, for example,

SignatureLink
   EvaluationLink
      TypeChoice
         TypeNode "PredicateNode"
         TypeNode "GroundedPredicateNode"
      ListLink
         TypeNode "ConceptNode"
         TypeNode "ConceptNode"

is the combinanation of two signatures, one for the ordinary EvaluationLink, using an ordinary PredicateNode, and one using a GroundedPredicateNode. That is, it combines this signature:

SignatureLink
   EvaluationLink
      TypeNode "PredicateNode"
      ListLink
         TypeNode "ConceptNode"
         TypeNode "ConceptNode"

with this signature:

SignatureLink
   EvaluationLink
      TypeNode "GroundedPredicateNode"
      ListLink
         TypeNode "ConceptNode"
         TypeNode "ConceptNode"

Type checking

The pattern matcher can be used to perform type query and type checking. The current type-checker is fairly simple: it is implemented as the "value_is_type()" function; see /opencog/atomutils/TypeUtils.h At this time, it does not have a scheme wrapper, but it could.

To perform a type query, once simply search the entire atomspace for a given signature by employing the BindLink. Thus, for example, all atoms of the following signature

SignatureLink
   EvaluationLink
      TypeNode "PredicateNode"
      ListLink
         TypeNode "ConceptNode"
         TypeNode "ConceptNode"

can be obtained by performing the search

GetLink
   TypedVariableLink
       VariableNode "$x"
       SignatureLink
           ... etc as above...
   VariableNode "$x"

The above query works today, although it is not optimized, and might run slow on a large atomspace. Its not hard to optimize, just no one has needed this yet.

You could do the same thing without using a SignatureLink, but it would much more verbose (although, currently, it would probably run faster). As follows:

GetLink
   VariableList
       TypedVariableLink
          VariableNode "$any-pred"
          TypeNode "PredicateNode"
       TypedVariableLink
          VariableNode "$any-concept"
          TypeNode "ConceptNode"
       TypedVariableLink
          VariableNode "$any-other-concept"
          TypeNode "ConceptNode"
    EvaluationLink
       VariableNode "$any-pred"
       ListLink
          VariableNode "$any-concept"
          VariableNode "$any-other-concept"

Note that the GetLink is more verbose than the SignatureLink variant

Note that using the pattern matcher is overkill for basic type checking, such as that given above. That is because basic type checking is guaranteed to terminate in finite time: you just walk to the bottom of the tree.

Type equations

The pattern matcher becomes useful only if type equations are needed, for example:

SignatureLink
   EvaluationLink
      TypeNode "PredicateNode"
      ListLink
         TypeVar "$some-type"
         TypeVar "$some-type"

Here, the "TypeVar $some-type" implies that the two slots of the ListLink must be of the same type, whatever type that may be. Solving this kind of type equation would require the pattern matcher, and could not easily be done with basic tree code. (In other words, type equations are currently not supported).

Unit test

The /tests/query/DeepTypeUTest.cxxtest implements a unit test for this function. The /examples/pattern-matcher/type-signature.scm provides a demo.

OpenCog