The Pattern Matcher

From OpenCog
(Redirected from Term rewriting)


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.

See also:


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.

Initial setup

We need to add some Atoms in the Atomspace so that we can apply the above mentioned functions. We make a file helloPM.scm:

vim 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
 4(use-modules (ice-9 readline)) 
 6(add-to-load-path ".")
 7(use-modules (opencog))
 8(use-modules (opencog exec))
 9;END Boilerplate code
11(display "-----------------------------------------------------------------------")
14;Some relationships
15(Inheritance (Concept "Blue") (Concept "Color"))
16(Inheritance (Concept "Green") (Concept "Color"))
17(Inheritance (Concept "Red") (Concept "Color"))
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 
		;Declare varibales [optional]
		(Variable "$color")
		;The pattern that the variable must satisfy
 			(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:

   (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?
		;Declare varibales [optional]
		(VariableNode "$color")
		;The pattern that the variable must satisfy
			(VariableNode "$color")
			(ConceptNode "Color")

Here, we search for satisfaction using cog-execute!, which returns a TruthValue, instead of some atoms: (display (cog-execute! have-any-colors?))(newline)

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
		;Declare the variables [optional]
		(Variable "$denizen")
		;Declare the pattern used to ground the variables
 			(Variable "$denizen")
			(Concept "Animal"))

		;If a match is found for the pattern then we want
		;to add the following hypergraph ot the Atomspace
 			(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:

      (ConceptNode "fish")
      (ConceptNode "Pet")
      (ConceptNode "dog")
      (ConceptNode "Pet")
      (ConceptNode "cat")
      (ConceptNode "Pet")

GetLink, again

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	)
 97(display ">>> SatisfactionLink results:")(newline)
 98(display (cog-evaluate! have-pets?))
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	)
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	)
137; Perform the "beta reduction" of the redex:
138(display (cog-execute! beta-redex))
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	)
154(display (cog-execute! get-colors))

You would see the following output, meaning that the primary color was created in the Atomspace.

   (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	)
176(display (cog-execute! re-write))
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	)
192(display (cog-execute! get-primarycolors))

You should now see the output:

   (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	)
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).


1 What is the Pattern Matcher?

an interface to ground variables.
the query engine that is used to find Atoms in Atomspace that fit into a certain template or pattern.
within the atomspace, it's system for finding graphs.
the graphical analog, in Atomese, of a database query engine.
a system that is to graphs what regex (regular expressions) are to strings.

2 In the context of the Atomese Pattern Matcher, what is a pattern?

A template used for finding graphs of a particular shape
a tree decomposition of a graph; that is, a set of trees having shared Atoms that together specify a graph.
a lambda expression containing bound variables
the graphical analog, in Atomese, that resembles SQL SELECT WHERE and HAVING clauses.
a collection of ungrounded terms, in the sense of term-theory.

3 Grounding a pattern requires?

understanding the principles of intuitionistic logic.
the successful matching of pattern variables to Atoms in the AtomSpace.
an understanding of Kripke Frames.
filling the blanks in a pattern by looking for similar patterns in atomspace.
obtaining an atomic formula all of whose terms are ground terms.

4 cog-execute!...

is used to execute any executable link types
can be used to invoke code that runs Atomese
can used to look for possible groundings of a pattern
can be used to ground patterns specified inside GetLinks
returns Atoms
returns Hypergraphs

5 cog-evaluate!...

returns TruthValues
is used to look for the existence of a grounding of a pattern
can be used to evaluate logical expressions
is used to determine the truth of an expression

6 Based on the examples above, how can the expression (stv 1 1) be understood?

certain truth
logical true
certain falsehood

Further Reading

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.


Linus is the Pattern Matcher Master!