The Pattern Matcher
In the last lesson we added Atoms to the Atomspace using the scheme shell. We also used a function named cog-execute! to use the Atoms to add two numbers. In this lesson, we will look at some other functions to interact with Atomspace.
What is the Pattern Matcher(PM)?
The pattern matcher is the query engine that is used to find Atoms in Atomspace that fit into a certain template or pattern. The PM can be used from c++, scheme or python. Here we will use it from scheme. A pattern here means a hypergraph consisting of Nodes and Links of several types. One type of Node is the VariableNode. VariableNodes are used to indicate "blank spots" in the pattern, with the pattern matcher then finding all graphs that can "fill in the blanks". This process is called 'grounding' a pattern.
Patterns are specified in three ways, using either GetLink, BindLink or DualLink. For the first two, one creates the pattern-template that one wishes to search for. The pattern is just a graph, which can be specified as a collection of trees making up the graph, the trees containing the VariableNodes. During the search, all matching graphs are found, and the groundings, the subgraphs that "fit" into the "blanks" indicated by the variables, are noted. By running the GetLink, a list is returned of all of these groundings (these matches). The BindLink is used for graph-rewriting: the grounding are then pasted into a second pattern, to create a new graph. The DualLink performs an "inverted" search: given an "answer" graph, it will return a list of all "questions" which are answered by it. That is, the DualLink allows you to search for queries. This is commonly required for building chatbots, to find pattern templates that match what was said by the human speaker.
The best and most current version of the tutorial is in the github examples directory. It is recommended that you go through them in order. These examples are more complete, extensive and accurate than those given below. But if you're in hurry, the below might do.
A Background in Scheme
Scheme is a dialect of Lisp; the scheme shell allows scheme code to manipulate the contents of an OpenCog AtomSpace.
- If you don't have a background in Scheme, it might be worth going through the Scheme documentation.
We need to add some Atoms in the Atomspace so that we can apply the above mentioned functions. We make a file helloPM.scm:
note you can't create or edit files within the scheme commandline, open another terminal or exit to bash
This script will just add some Atoms to the Atomspace and exit. Add the following script to the helloPM.scm file:
1;Boilerplate code for loading the opencog modules 2;You should skip these if you have already put these in ~/.guile 3 4(use-modules (ice-9 readline)) 5(activate-readline) 6(add-to-load-path ".") 7(use-modules (opencog)) 8(use-modules (opencog exec)) 9;END Boilerplate code 10 11(display "-----------------------------------------------------------------------") 12(newline)(newline) 13 14;Some relationships 15(Inheritance (Concept "Blue") (Concept "Color")) 16(Inheritance (Concept "Green") (Concept "Color")) 17(Inheritance (Concept "Red") (Concept "Color")) 18 19(Inheritance (Concept "fish") (Concept "Animal")) 20(Inheritance (Concept "dog") (Concept "Animal")) 21(Inheritance (Concept "cat") (Concept "Animal"))
Run the script on the bash shell:
$ guile helloPM.scm
Or within the scheme commandline:
$ (load "helloPM.scm")
Now we can start with the Pattern Matcher (PM) functions.
As said earlier, patterns can be grounded if they have VariableNodes - we use the cog-execute! function to ground patterns. So, we will first specify a pattern and then ground it using the cog-execute! function.
Specify a pattern: Suppose we want to find out what colors there are in the Atomspace. For this we can specify a pattern as follows (all of these snippets are to be appended to the end of helloPM.scm.)
;Define a pattern that is satisfiable by colors (define get-colors (Get ;Declare varibales [optional] (Variable "$color") ;The pattern that the variable must satisfy (Inheritance (Variable "$color") (Concept "Color") ) ) )
Ground the pattern: Now, we can look for all Atoms in the Atomspace that can be substituted in place of (VariableNode "$color") in the pattern above. All such atoms must be linked to the (ConceptNode "Color") via an InheritanceLink to be valid matches. Lets find such atoms.
Ground the pattern using cog-execute!:
(display (cog-execute! get-colors))(newline)
The result of running cog-execute! will be a SetLink, that is connecting all Atoms that matched the pattern. This will be printed to the screen as:
(SetLink (ConceptNode "Blue") (ConceptNode "Green") (ConceptNode "Red") )
Sometimes, one is interested only knowing if there is any solution at all, rather than knowing what that solution might be. In this case, use SatisfactionLink when specifying the pattern. The pattern is effectively the same as before:
;Define a pattern that is satisfiable by colors (define have-any-colors? (SatisfactionLink ;Declare varibales [optional] (VariableNode "$color") ;The pattern that the variable must satisfy (InheritanceLink (VariableNode "$color") (ConceptNode "Color") ) ) )
The result of running cog-execute! is a TruthValue. It is printed to the screen as (stv 1 1). This corresponds to "true, with full confidence" -- the first number is the truth-strength (zero to one), and the second number is the confidence (zero to one).
BindLinks are used to perform graph re-writing. They combine a search with a plug-in-0the-values step. Let us look at an example.
What we are doing here is defining a graph-rewrite called make-pets The query looks for notes of type Animal, and then label these nodes as pets. Code:
(define make-pets (Bind ;Declare the variables [optional] (Variable "$denizen") ;Declare the pattern used to ground the variables (Inheritance (Variable "$denizen") (Concept "Animal")) ;If a match is found for the pattern then we want ;to add the following hypergraph ot the Atomspace (Inheritance (Variable "$denizen") (Concept "Pet"))))
Now we execute the graph-rewrite query using cog-execute!. Code:
(display (cog-execute! make-pets))
The output of this query will be:
(SetLink (InheritanceLink (ConceptNode "fish") (ConceptNode "Pet") ) (InheritanceLink (ConceptNode "dog") (ConceptNode "Pet") ) (InheritanceLink (ConceptNode "cat") (ConceptNode "Pet") ) )
We can now use GetLink to find the pets in the Atomspace.
79;Get the list of pets in the Atomspace 80(define have-pets? 81 (Satisfaction 82 ;Declare variables 83 ;This is how you specify that the VariableNode "$animal" 84 ;should only be grounded by a ConceptNode. We are constraining 85 ;the type of the VariableNode to a ConceptNode. 86 (TypedVariable 87 (Variable "$animal") 88 (Type "ConceptNode") 89 ) 90 ;The pattern that the variable must satisfy 91 (Inheritance 92 (Variable "$animal") 93 (Concept "Pet") 94 ) 95 ) 96) 97(display ">>> SatisfactionLink results:")(newline) 98(display (cog-evaluate! have-pets?)) 99 100;GetLink is just like the SatisfactionLink, except that it returns the pets 101(define get-pets 102 (GetLink 103 ;Declare varibales [optional] 104 (TypedVariableLink 105 (VariableNode "$animal") 106 (TypeNode "ConceptNode") 107 ) 108 ;The pattern that the variable must satisfy 109 (InheritanceLink 110 (VariableNode "$animal") 111 (ConceptNode "Pet") 112 ) 113 ) 114) 115(display ">>> GetLink results:")(newline) 116(display (cog-execute! get-pets))
PutLink provides just the "pasting" part of a graph rewrite search-n-paste operation. Combined with a GetLink, its more-or-less equivalent to performing a BindLink for the graph rewrite. First we will look at how PutLink can be used to write hypergraphs into Atomspace and then we will see how we can combine it with GetLink. (In mathematical logic or lambda calculus, a PutLink is known as a "beta redex").
Writing new nodes using PutLink: We specify a pattern in the PutLink that is to be written to Atomspace, and we also provide a list of VariableNodes that will be substituted into.
120;Paste with PutLink 121(define beta-redex 122 (PutLink 123 ;The pattern to write into Atomspace 124 (InheritanceLink 125 (VariableNode "$x") 126 (ConceptNode "PrimaryColor") 127 ) 128 ;The Atoms to paste into the pattern 129 (SetLink 130 (ConceptNode "Red") 131 (ConceptNode "Green") 132 (ConceptNode "Blue") 133 ) 134 ) 135) 136 137; Perform the "beta reduction" of the redex: 138(display (cog-execute! beta-redex)) 139 140;Check that the Atoms were created 141(define get-colors 142 (GetLink 143 (TypedVariableLink 144 (VariableNode "$color") 145 (TypeNode "ConceptNode") 146 ) 147 ;The pattern that the variable must satisfy 148 (InheritanceLink 149 (VariableNode "$color") 150 (ConceptNode "PrimaryColor") 151 ) 152 ) 153) 154(display (cog-execute! get-colors))
You would see the following output, meaning that the primary color was created in the Atomspace.
(SetLink (ConceptNode "Blue") (ConceptNode "Red") (ConceptNode "Green") )
Combining with GetLink: Now we use GetLink to get the Atoms that are to be used to ground the pattern in PutLink from the Atomspace. Used this way, the result is equivalent to the rewrite provided by BindLink.
153;Combining PutLink and GetLink together 154(define re-write 155 (PutLink 156 ;The pattern to be created in the Atomspace 157 (InheritanceLink 158 (VariableNode "$x") 159 (ConceptNode "PrimaryColor") 160 ) 161 ;The GetLink to search the Atomspace for grounding atoms 162 (GetLink 163 ;Variable declaration 164 (TypedVariableLink 165 (VariableNode "$color") 166 (TypeNode "ConceptNode") 167 ) 168 ;Pattern 169 (InheritanceLink 170 (VariableNode "$color") 171 (ConceptNode "Color") 172 ) 173 ) 174 ) 175) 176(display (cog-execute! re-write)) 177 178;Check that the node was written 179(define get-primarycolors 180 (GetLink 181 (TypedVariableLink 182 (VariableNode "$color") 183 (TypeNode "ConceptNode") 184 ) 185 ;The pattern that the variable must satisfy 186 (InheritanceLink 187 (VariableNode "$color") 188 (ConceptNode "PrimaryColor") 189 ) 190 ) 191) 192(display (cog-execute! get-primarycolors))
You should now see the output:
(SetLink (ConceptNode "Blue") (ConceptNode "Red") (ConceptNode "Green") )
The Type System
The pattern matcher has a complete type system which can be used to constrain Variables and otherwise specify signatures, functions and type constructors. For quick flavor of how the type system can be used, the below illustrates the use of TypeNode and TypeChoice to constraint variable matching, as well as the use of ChoiceLink to specify serveral differrent graph structures.
193;Find all nodes that are either primarycolors or colors 194(define get-all-colors 195 (GetLink 196 ;Variable declaraions 197 (TypedVariableLink 198 (VariableNode "$obj") 199 ;The TypeChoice link can be used to constrain the 200 ;type of a node to two or more types. 201 (TypeChoice 202 (TypeNode "VariableNode") 203 (TypeNode "ConceptNode") 204 ) 205 ) 206 ;Pattern: Nodes satisfying any of the choices of patterns 207 ;will be returned 208 (ChoiceLink 209 ;Choice1 210 (InheritanceLink 211 (VariableNode "$obj") 212 (ConceptNode "Color") 213 ) 214 ;Choice2 215 (InheritanceLink 216 (VariableNode "$obj") 217 (ConceptNode "PrimaryColor") 218 ) 219 ) 220 ) 221) 222(display ">>> All colors:\n") 223(display (cog-execute! get-all-colors))
Note that the term "choice" here is used in the sense of a restaurant menu or vending machine: you can pick one item from the menu. This is distinct from the logical OrLink, which is reserved for combining TruthValues (along with AndLink and NotLink).
The links below provide detailed descriptions of all topics in this chapter. This tutorial has been severely restricted selection from these pages. One should explore these links to gain a deeper understanding of the topics introduced here.
- Examples with ChoiceLink
Linus is the Pattern Matcher Master!