opencog/ure

Unified Rule Engine. Graph rewriting system for the AtomSpace. Used as reasoning engine for OpenCog.

Unified Rule Engine

opencog	singnet

The Unified Rule Engine, URE for short, is a term rewriting engine for OpenCog. It can be used to implement any logic. As of today it is used for PLN, the Pattern Miner and Relex2Logic.

The strengths of the URE are

• Reads/writes knowledge directly from/to the AtomSpace.
• It is generic, can be used to implement any logic, even higher order logics with some limitations.
• Comes with a powerful control mechanism to speed up reasoning.

The weaknesses of the URE are:

IT IS NO LONGER MAINTAINED

The lead developer walked away. Some unit tests pass. It's slowly bit-rotting.

Building and Installing

Prerequisites

To build the URE you need to first build and install:

• The AtomSpace
• The term unifier

See Building-and-installing-the-AtomSpace for more information.

Building URE

Be sure to install the pre-requisites first! Perform the following steps at the shell prompt:

    cd ure
    mkdir build
    cd build
    cmake ..
    make -j

Libraries will be built into subdirectories within build, mirroring the structure of the source directory root.

Unit tests

To build and run the unit tests, from the ./build directory enter (after building opencog as above):

    make -j test

Tests can be run in parallel as well:

    make -j test ARGS=-j4

Install

After building, you must install the URE.

    sudo make install

Examples

Examples can be found in this repository under

URE examples

And

PLN examples

for PLN in particular.

More info

The primary documentation for the URE is here:

• URE wiki
• URE README.md

ure's Issues

Add BackwardChainerGetLink

Proposal

To slightly ease the usage of the URE and make it appear more as an extension of the pattern matcher, it would be nice to introduce

BackwardChainerGetLink

which would be a scope link that can be executed by the atomese interpreter and yield a similar output to GetLink.

Example

For example, executing the following

(cog-execute!
  (BackwardChainerGet
    (TypedVariable
      (Variable "$X")
      (Type "ConceptNode"))
    (Inheritance
      (Concept "A"))
      (Variable "$X")
    <rule-base-with-deduction-rule>))

on the KB described in issue opencog/atomspace#2472 would yield the following

(Set
  (Concept "B")
  (Concept "C")
  (Concept "D")
  (Concept "F"))

URE compilation fails: warning: control reaches end of non-void function

URE compilation fails:

[  4%] Building CXX object opencog/unify/CMakeFiles/unify.dir/Unify.cc.o
Scanning dependencies of target COPY_TO_LOAD_PATH_IN_BUILD_DIR_FROM__ws_ure_opencog_scm
[  4%] Built target COPY_TO_LOAD_PATH_IN_BUILD_DIR_FROM__ws_ure_opencog_scm
/ws/ure/opencog/unify/Unify.cc: In member function ‘opencog::Unify::SolutionSet opencog::Unify::unify(const opencog::Handle&, const opencog::Handle&, opencog::Context, opencog::Context) const’:
/ws/ure/opencog/unify/Unify.cc:631:10: error: ‘using element_type = class opencog::Atom {aka class opencog::Atom}’ has no member named ‘is_unordered_link’
  if (rh->is_unordered_link())
          ^~~~~~~~~~~~~~~~~
/ws/ure/opencog/unify/Unify.cc:635:1: warning: control reaches end of non-void function [-Wreturn-type]
 }

Full log here:
https://circleci.com/gh/opencog/atomspace/4626?utm_campaign=vcs-integration-link&utm_medium=referral&utm_source=github-checks-link

Fix replacement example inference tree expansion

Problem

Some BC inference tree expansion fails. The problem can be reproduced by running

https://github.com/opencog/ure/tree/master/examples/ure/replacement

As one can see from the log, in iteration 3, where the case (synonymous (Predicate "believe") (Variable "$B")) is considered as unification, the subsequent inference tree expansion fails. The unification is correct, so the problem comes from the expansion itself.

Tasks

• Create unit test based on that example in BITUTest.cxxtest, named test_expand_4 or such.
• Fix BIT expansion to pass the unit test.

Merge the forward and backward chainer into a mixed chainer

Here are some vague guidelines for implementing the mixed chainer. Should be refined as we'll progress into the task.

1. Forward and backward chaining often need to occur over the same inference tree in order to construct the desire inference tree.
2. Providing a target may not always mean that the best chaining strategy should be backward, likewise providing sources may not always mean that best chaining strategy should be forward, these decisions should not be hardwired, and instead be delegated to control policies (possibly handwritten by default).
3. The mixed chainer should be able to take input intermediary sources/targets, not just end sources/targets.
4. It is expected as well that different parts of an inference tree could be evolved independently then stick together (using unification, just like a rule is stuck to an inference tree).

Possible bug in AndBIT::expand()

The pull req #93 works around something that smells like a bug in AndBIT::expand(). I can't really tell, so I am opening this issue to track the question. If it's not actually a bug, then just close this :-) See #93 for details of what seems to be wrong.

Memoize unification to speed up URE

One source of computational overhead in the URE is the unification between rule conclusions and targets when going backward, or rule premises and sources when going forward.

Often the same unification operation is carried over. Add to that, unification is stateless. Thus is a perfect candidate for memoization.

Rule::unify_source method execution takes about 30% of ForwardChainer execution time

I profiled ForwardChainer to find out how performance can be improved and found that it spends significant amount of time in the Rule::unify_source method. It depends on rules complexity. The more complex rules are used the bigger this amount of time is. The following benchmark demonstrates this: opencog/benchmark#27

The problem is that unify_source does almost nothing. First part converts rule's BindLink into another one with random variable naming (RewriteLink::alpha_convert). And second one constructs new BindLink with some variables grounded.

Proper fix probably should be raised to opencog/atomspace, but I am raising the issue here as main concern is URE performance.

Flame graph of the code benchmarked (better opening in web-browser):
perf.svg.gz

Following steps require getting perf and FlameGraph tool (https://github.com/brendangregg/FlameGraph). Intel CPU with support of Intel Processor Trace is required as well.

Steps to reproduce:
Run benchmark in the background:

./micro/benchmark --benchmark_filter=ForwardChainer_Basic --benchmark_min_time=600 &

Collect profile using Intel Processor Trace. You need only 1 second of profile it will be too large otherwise:

perf record -e intel_pt//u -p `pidof benchmark` sleep 1

Build flame graph of the do_step call (it can take a lot of time):

perf script --itrace=i100nsg | ./FlameGraph/stackcollapse-perf.pl | fgrep 'benchmark;BM_ForwardChainer_Basic;opencog::ForwardChainer::do_chain;opencog::ForwardChainer::do_step_rec;opencog::ForwardChainer::do_step;' | ./FlameGraph/flamegraph.pl > perf.svg

Create an incremental unifier

Unification is inherently costly (NP in the worst case, I think, don't quote me on that). However queries are often similar, or their complexity incrementally builds up due to how the URE evolves inference trees.

So this would be a generalization of memoizing unification, see issue https://github.com/opencog/atomspace/issues/1913 but is much more advanced, it's pretty much a research project, might already have some literature on the subject, TBD.

Using GlobNode in Backward Chainer

My aim is to write a rule for URE that deals with variable number of arguments in a link.

As an example I try to take the latest atom in a Product link and put it on top.
This works fine if I use GlobNode just in BindLink (sample [1]).
When I try to use the same BindLink with URE the result is nothing (sample[2]).
If I change GlobNode to VariableNode URE works fine (sample [3]).

[1] Using Glob node with BindLink:

(use-modules (opencog) (opencog exec) (opencog query))

;;;;;;;;;;;;;;;;;;;;;
;;; Knowledge base ;;
;;;;;;;;;;;;;;;;;;;;;

(Product (stv 1 1) ; a non-zero truth value is needed!
 (ConceptNode "A")
 (ConceptNode "B"))

;;;;;;;;;;;;;;;;;
;; Rule  base  ;;
;;;;;;;;;;;;;;;;;

(define (on-top h)
 (display "on-top input:\n")
 (display h)
 (cog-set-tv! h (cog-new-stv 0.75 0.42))
 h)

(define on-top-rule
 (BindLink
  (VariableList
   (GlobNode "$X1")
   (TypedVariable (Variable "$X2") (Type "ConceptNode"))
  )
  (Product
   (GlobNode "$X1")
   (Variable "$X2")
  )
  (ExecutionOutputLink
   (GroundedSchemaNode "scm: on-top")
   (ListLink
    (Product
     (Variable "$X2")
     (GlobNode "$X1")
    )))))

(display (cog-execute! on-top-rule))

Output:

on-top input:
(ProductLink
   (ConceptNode "B")
   (ConceptNode "A")
)
(SetLink
   (ProductLink (stv 0.75 0.42)
      (ConceptNode "B")
      (ConceptNode "A")
   )
)

[2] Using GlobNode with URE:

(use-modules (opencog) (opencog query) (opencog exec) (opencog rule-engine))

;;;;;;;;;;;;;;;;;;;;;
;;; Knowledge base ;;
;;;;;;;;;;;;;;;;;;;;;

(Product (stv 1 1) ; a non-zero truth value is needed!
 (ConceptNode "A")
 (ConceptNode "B"))

;;;;;;;;;;;;;;;;;
;; Rule  base  ;;
;;;;;;;;;;;;;;;;;

(define (on-top-formula h)
 (display "on-top input:\n")
 (display h)
 (cog-set-tv! h (cog-new-stv 0.75 0.42))
 h)

(define on-top-rule
 (BindLink
  (VariableList
   (GlobNode "$X1")
   (TypedVariable (Variable "$X2") (Type "ConceptNode"))
  )
  (Product
   (GlobNode "$X1")
   (Variable "$X2")
  )
  (ExecutionOutputLink
   (GroundedSchemaNode "scm: on-top-formula")
   (List
    (Product
     (Variable "$X2")
     (GlobNode "$X1")
    )))))


(define on-top-rule-name
 (DefinedSchema "on-top-rule"))

(Define on-top-rule-name
 on-top-rule)

;;;;;;;;;;
;; URE  ;;
;;;;;;;;;;

(define ci-rbs (Concept "ci-rbs"))

;; Add rules to ci-rbs
(ure-add-rules ci-rbs
 (list
  (cons on-top-rule-name (stv 1.0 1.0))))

;; Set URE parameters
(ure-set-maximum-iterations ci-rbs 20)

;; Attention allocation (set the TV strength to 0 to disable it, 1 to
;; enable it)
(EvaluationLink (stv 0 1)
 (PredicateNode "URE:attention-allocation")
 ci-rbs
)

;;;;;;;;;;;;;;;;;;;;;;
;; Backward Chainer ;;
;;;;;;;;;;;;;;;;;;;;;;

(display
 (cog-bc
  ci-rbs
  (Product (VariableNode "$X") (Concept "A"))
  #:vardecl (TypedVariable (VariableNode "$X") (TypeNode "ConceptNode")))
)

Output:

(SetLink
)

[3] Using VariableNode with URE:

(use-modules (opencog) (opencog query) (opencog exec) (opencog rule-engine))

;;;;;;;;;;;;;;;;;;;;;
;;; Knowledge base ;;
;;;;;;;;;;;;;;;;;;;;;

(Product (stv 1 1) ; a non-zero truth value is needed!
 (ConceptNode "A")
 (ConceptNode "B"))

;;;;;;;;;;;;;;;;;
;; Rule  base  ;;
;;;;;;;;;;;;;;;;;

(define (on-top-formula h)
 (display "on-top input:\n")
 (display h)
 (cog-set-tv! h (cog-new-stv 0.75 0.42))
 h)

(define on-top-rule
 (BindLink
  (VariableList
   (TypedVariable (Variable "$X1") (Type "ConceptNode"))
   (TypedVariable (Variable "$X2") (Type "ConceptNode"))
  )
  (Product
   (Variable "$X1")
   (Variable "$X2")
  )
  (ExecutionOutputLink
   (GroundedSchemaNode "scm: on-top-formula")
   (List
    (Product
     (Variable "$X2")
     (Variable "$X1")
    )))))


(define on-top-rule-name
 (DefinedSchema "on-top-rule"))

(Define on-top-rule-name
 on-top-rule)

;;;;;;;;;;
;; URE  ;;
;;;;;;;;;;

(define ci-rbs (Concept "ci-rbs"))

;; Add rules to ci-rbs
(ure-add-rules ci-rbs
 (list
  (cons on-top-rule-name (stv 1.0 1.0))))

;; Set URE parameters
(ure-set-maximum-iterations ci-rbs 20)

;; Attention allocation (set the TV strength to 0 to disable it, 1 to
;; enable it)
(EvaluationLink (stv 0 1)
 (PredicateNode "URE:attention-allocation")
 ci-rbs
)

;;;;;;;;;;;;;;;;;;;;;;
;; Backward Chainer ;;
;;;;;;;;;;;;;;;;;;;;;;

(display
 (cog-bc
  ci-rbs
  (Product (VariableNode "$X") (Concept "A"))
  #:vardecl (TypedVariable (VariableNode "$X") (TypeNode "ConceptNode")))
)

Output:

on-top input:
(ProductLink
   (ConceptNode "B")
   (ConceptNode "A")
)
(SetLink
   (ProductLink (stv 0.75 0.42)
      (ConceptNode "B")
      (ConceptNode "A")
   )
)

forward chainer finds that Tweety is a green frog in examples/ure/frog

If in examples/ure/frog (Forward Chainer (using the frog rule base)) replace source with (Evaluation (stv 1.0 1.0) (Predicate "eats_flies") (Concept "Tweety")) then forward chainer infer that Tweety is green frog.

you should run it from examples/ure/frog

(use-modules (opencog exec))
(use-modules (opencog ure))
(load "frog-rule-base.scm")
(define source  (Evaluation (stv 1.0 1.0) (Predicate "eats_flies") (Concept "Tweety")))
(cog-fc frog-rb source)

It infers that Tweety is a green frog

Have the URE fully support formula premises wrapped in SetLink

Problem

When a rule formula has a set of unordered premises they can be wrapped in a SetLink. For instance a conjunction rule can be expressed as follows

Bind
  And
    X
    Y
  ExecutionOutput
    GroundedPredicate "conjunction-formula"
    And
      X
      Y
    Set
      X
      Y

Wrapping X and Y in a SetLink allows the URE to not create multiple versions of inference trees with different permutations of X and Y. For instance without SetLink, when unifying this rule with some target And Z W it would create 2 inference trees

Bind
  And
    Z
    W
  ExecutionOutput
    GroundedPredicate "conjunction-formula"
    And
      Z
      W
    Z
    W

and

Bind
  And
    Z
    W
  ExecutionOutput
    GroundedPredicate "conjunction-formula"
    And
      Z
      W
    ;; Z and W have been swapped
    W
    Z

Motivation

Wrapping unordered formula premises in SetLink avoids over-representing semantically equivalent inference trees, which ultimately speeds up reasoning.

Task

Currently the URE only supports wrapping all formula premises in SetLink, but in some case only a subset of premises are unordered. So the task here would be to have the URE support wrapping a subset of formula premises in a SetLink.

URE performance

The current URE design has a performance bottleneck.that may be constraining system performance. This is a feature-enhancement request to maybe fix that. It's low-priority; I wanted to note it here so that it doesn't get lost.

To provide isolation for the application of rules to the focus set, the current URE creates a brand-new, stand-alone atomspace, copies the focus-set into it, and copies the rules into it. This is done every time the forward chainer is run. (and also the backward chainer, I presume)

The problem is that creating atoms and adding them to the atomspace is slow: currently, one can add about 100K atoms/second to the atomspace. The current PLN ruleset has more than 2K atoms, thus requires approx 20 milliseconds to set up the atomspace. This limits PLN performance to no more than 50 invocations of PLN per second, and probably less.

The Relex2logic ruleset currently consists of about 1.5K atoms: 750 nodes and 800 links approx.

A single parsed sentence, from relex, has 500 atoms in it, typical. Since these are the focus set, they must also be copied into the atomspace - I assume r2l generates a similar number of atoms, that have to be passed into PLN. Thus, atomspace creation in the URE limits performance to no more than:

-- 5+115 = 20 millisecs for R2L
-- 20+5 = 25 millisecs for PLN
-- 20+25 = 55 millisecs for single sentence and one run of R2L, one run of PLN.

This is a hefty overhead. I don't think it's impacting any current work, but it will eventually cause problems...

The hyperlink to the term unifier in the README leads nowhere.

In the README, the link to the term unifier (which is said to be a dependency) leads nowhere.

Here is the broken link:

https://wiki.opencog.org/w/Unify

It is hard to build URE without proper information locating the term unifier dependency.

Backward chainer takes super long in this case

The Backward Chainer takes over 4 seconds in this scenarios with only 10 waypoints. This time increases only marginally with 100 or 200 waypoints.

To run this, you need to create a 9-fold fuzzy and in the pln/opencog/pln/rules/propositional/fuzzy-conjunction-introduction.scm file and adjust the path to the file in the script.

#!/usr/bin/env python
import time

from opencog.type_constructors import *
from opencog.bindlink import execute_atom, evaluate_atom
from opencog.ure import BackwardChainer, ForwardChainer
from opencog.utilities import initialize_opencog
from opencog.atomspace import AtomSpace, types, TruthValue, create_child_atomspace
from opencog.logger import create_logger, Logger,log
from opencog.scheme_wrapper import scheme_eval

TRUE = TruthValue(1.0, 1.0)

def identical_formula(A, B):
    # rospy.loginfo("identical_formula({},{})".format(A,B))
    link = IdenticalLink(A,B)
    # out = A.get_out()
    if A == B:
        link.tv = TruthValue(1, 1)
    else:
        link.tv = TruthValue(0, 1)
    return link


def build_deduction_rulebase():
    rbs = ConceptNode("deduction-rule-base")
    execute_code = \
    '''
    (use-modules (opencog))
    (use-modules (opencog logger) (opencog ure) (opencog exec))
    (load-from-path "/home/rasberry/git/pln/opencog/pln/rules/propositional/fuzzy-conjunction-introduction.scm")
    (define rbs (Concept "deduction-rule-base"))
    (ure-set-complexity-penalty rbs 0.1)
    '''
    scheme_eval(atomspace, execute_code)

    MemberLink(DefinedSchemaNode("fuzzy-conjunction-introduction-9ary-rule"), rbs)

    return rbs


def print_results(query,results):
    print("Query:\n{:}\n\nResults:\n{:}\n\nDetails:\n--------".format(query, results))
    if query.type_name == "GetLink":
        for setlink in results.get_out():
            for result in setlink.get_out():
                print("Result Truth: {:}".format(result.tv))
                print("Result:\n{:}".format(result))
                print("------------------------\n")
    elif query.type_name == "AndLink":
        for result in results.get_out():
            print("Result Truth: {:}".format(result.tv))
            print("Result:\n{:}".format(result))
            for condition in result.get_out():
                print("------------------------")
                print("Condition:{:}".format(condition))
                print("Condition Truth: {:}".format(condition.tv))
                if condition.type_name == "NotLink":
                    subcondition = condition.get_out()[0]
                    print("    Subcondition: {:}".format(subcondition))
                    print("    Subcondition Truth: {:}".format(subcondition.tv))
            print("-----------------------------------------------------")
    else:
        for result in results.get_out():
            print("Result Truth: {:}".format(result.tv))
            print("Result:\n{:}".format(result))
            print("------------------------\n")


if __name__ == '__main__':
    atomspace = AtomSpace()

    initialize_opencog(atomspace)
    rbs = build_deduction_rulebase()



    for index in range(1,10,1):
        odd = "wp_{:d}".format(index)
        even = "wp_{:d}".format(index+1)
        o = ConceptNode(odd).truth_value(1.0, 1.0)
        e = ConceptNode(even).truth_value(1.0, 1.0)
        # print("creating link {}<->{}".format(o,e))
        EvaluationLink(PredicateNode("leads_to"), ListLink(o, e)).truth_value(1.0, 1.0)
        EvaluationLink(PredicateNode("leads_to"), ListLink(e, o)).truth_value(1.0, 1.0)

    wp5 = ConceptNode("wp_5")
    wp6 = ConceptNode("wp_6")

    true = ConceptNode("true").truth_value(1.0, 1.0)
    false = ConceptNode("false").truth_value(1.0, 1.0)
    seen_picking = ConceptNode("seen_picking").truth_value(1.0, 1.0)
    called_robot = ConceptNode("called_robot").truth_value(1.0, 1.0)
    approaching = ConceptNode("approaching").truth_value(1.0, 1.0)
    movement = ConceptNode("movement").truth_value(1.0, 1.0)

    human = ConceptNode("human").truth_value(1.0, 1.0)
    alice = ConceptNode("alice").truth_value(1.0, 1.0)
    InheritanceLink(alice, human).truth_value(1.0, 1.0)
    StateLink(alice, wp5).truth_value(1.0, 1.0)
    StateLink(ListLink(alice, seen_picking), false).truth_value(1.0, 1.0)
    StateLink(ListLink(alice, called_robot), false).truth_value(1.0, 1.0)
    StateLink(ListLink(alice, movement), approaching)

    robot = ConceptNode("bob").truth_value(1.0, 1.0)
    StateLink(robot, wp6).truth_value(1.0, 1.0)

    variables = VariableList(
        TypedVariableLink(VariableNode("person"), TypeNode("ConceptNode")),
        TypedVariableLink(VariableNode("person_location"), TypeNode("ConceptNode")),
        TypedVariableLink(VariableNode("origin"), TypeNode("ConceptNode")),
        TypedVariableLink(VariableNode("destination"), TypeNode("ConceptNode")),
        TypedVariableLink(VariableNode("nobody"), TypeNode("ConceptNode"))
        )

    query =     AndLink(
                    InheritanceLink(VariableNode("person"), human),
                    StateLink(VariableNode("person"), VariableNode("person_location")),
                    StateLink(ListLink(VariableNode("person"), movement), approaching),
                    StateLink(robot, VariableNode("origin")),
                    StateLink(ListLink(VariableNode("person"), seen_picking), false),
                    StateLink(ListLink(VariableNode("person"), called_robot), false),
                    EvaluationLink(
                        PredicateNode("leads_to"),
                        ListLink(VariableNode("person_location"), VariableNode("origin"))
                    ),
                    EvaluationLink(
                        PredicateNode("leads_to"),
                        ListLink(VariableNode("origin"), VariableNode("destination"))
                    ),
                    AbsentLink(
                            StateLink(VariableNode("nobody"), VariableNode("destination"))
                    )
                )

    start_time = time.time()
    # query = GetLink(variables, query)
    chainer = BackwardChainer(_as=atomspace,
                      rbs=rbs, trace_as=None, control_as=None, focus_set=None,
                      target=query, vardecl=variables)
    chainer.do_chain()
    print("The BackwardChainer took {:.2f}\n--------------".format(time.time()-start_time))
    results = chainer.get_results()
    print_results(query, results)

test_conditional_instantiation_1 triggers warnings in pattern engine

The test_conditional_instantiation_1 unit test of the BackwardsChainerUTest triggers newly-installed errors (now down-graded to warnings) in the pattern engine. .. but unexpectedly passes anyway. The search with the problem has a body that looks like this:

(And
    (And
        (..many EvaluationLinks, some with variables, none are GPN ...))
    (Evaluation
          (GroundedPredicateNode "scm: true-enough")
          (... copy of the second AndLink above ...)))

The problem with this is that the pattern engine gets confused by this search, and does something off-the-wall and wacky... mostly because its trying to be backward-compatible with older styles, and because it didn't do very much checking before starting. Here's what happens:

The second AndLink and the Evaluation-GPN-link are marked as "evaluatable", therefore, no pattern-matching is done. However, the second AndLink contains stuff that are just naked terms, not wrapped in a PresentLink, so it tries to be backwards-compat and grounds one of the terms in it, some term that happens to have a variable in it. As part of the process, though, it moves up to the top - to the second And, and notices "oh hey, this is evaluatable, I better go and evaluate this!" so it goes into that code branch, and (as of a few days ago) notices that there are ungrounded variables, in it (and prints a warning). Well, evaluating that second And is a no-op, because none of the terms inside of it are actually evaluatable, so nothing happens, and the fact that there were ungrounded vars made no difference at all.

Eventually, it gets around to calling the GPN, with the same ungrounded vars in the arguments. and whatever happens .. happens. The unit test passes.

What should be happening is one of two things:

• During pattern compilation, it should check each and every term inside the second AndLink, realize that non of them are actually evaluatable, assume that what you actually wanted was an implicit PresentLink for each of them, and add them to the pool of clauses that need grounding.
• Same as above, but throw an error whenever it finds something that isn't actually evaluatable.

Fixing this in the pattern engine is ... tedious, and based on experience, painful, because there are probably all sorts of weird corner cases that assorted unit tests are testing. Its .. fixable, I guess ... but anyway -- right now, the BackwardChainer is almost surely not doing what you wanted, because the pattern engine is confused and falls into an undocumented/ unsupported code-path.

I opened opencog/atomspace#2631 to track the needed fix in the pattern engine.

Let me know what to do -- should the pattern engine be fixed ASAP, or would it be better to tweak the URE? The work-around is very very simple: just get rid of the second And -- it seems like its really not needed, for any reason that I can tell ... and removing it would be identical to the first fix I propose above!

add api to extract inference trace

Sometimes it is useful to have graph or tree for inference.
Like source -> rule -> rule -> rule -> result

Usecases:

• theorem proving
• planning

Remove focus set from URE?

Now that the URE supports having rule-base and knowledge in different atomspaces opencog/atomspace#1983 I wonder if we need to keep focus set support. I've never used it personally. Is anybody using it? Or has the intention of using it in the future?

Bogus always-false clauses

While debugging a failure, I spotted the following in a BindLink:

(Not (Identical (Concept "criminal") (Concept "criminal")))

This is constant (so it probably gets removed, I think? Not sure, cause its evaluatable...) and its always false... I can have the pattern matcher trap this on static analysis, but thought I'd let you know... the full link is:

(Bind
  (VariableList
    (TypedVariable (Variable "$who") (Type "ConceptNode"))
    (TypedVariable (Variable "$B-7e054a97") (Type "ConceptNode"))
    (TypedVariable (Variable "$y-281a7166") (Type "ConceptNode"))
    (TypedVariable (Variable "$z-8b8dc93") (Type "ConceptNode"))
  )
  (And
    (Evaluation
      (GroundedPredicate "scm: true-enough")
      (Inheritance (Concept "criminal") (Variable "$B-7e054a97")))
    (Evaluation
      (GroundedPredicate "scm: true-enough")
      (And
        (Evaluation
          (Predicate "sell")
          (List
            (Variable "$who")
            (Variable "$y-281a7166")
            (Variable "$z-8b8dc93")))
        (Inheritance (Variable "$who") (Concept "American"))
        (Inheritance (Variable "$y-281a7166") (Concept "weapon"))
        (Inheritance (Variable "$z-8b8dc93") (Concept "hostile"))))
    (Not (Identical (Concept "criminal") (Variable "$who")))
    (And
      (Evaluation
        (Predicate "sell")
        (List
          (Variable "$who")
          (Variable "$y-281a7166")
          (Variable "$z-8b8dc93")))
      (Inheritance (Variable "$who") (Concept "American"))
      (Inheritance (Variable "$y-281a7166") (Concept "weapon"))
      (Inheritance (Variable "$z-8b8dc93") (Concept "hostile")))
    (Present
      (Inheritance (Variable "$B-7e054a97") (Concept "criminal"))
      (Inheritance (Concept "criminal") (Variable "$B-7e054a97")))
    (Evaluation
      (GroundedPredicate "scm: true-enough")
      (Inheritance (Variable "$B-7e054a97") (Concept "criminal")))
    (Not (Identical (Concept "criminal") (Concept "criminal")))
  )
  (ExecutionOutput
    (GroundedSchema "scm: bc-deduction-formula")
    (List
      (Inheritance (Variable "$who") (Concept "criminal"))
      (ExecutionOutput
        (GroundedSchema "scm: conditional-full-instantiation-formula")
        (List
          (Inheritance (Variable "$who") (Concept "criminal"))
          (ImplicationScope (stv 0.99 0.99)
            (VariableList
              (TypedVariable (Variable "$x") (Type "ConceptNode"))
              (TypedVariable (Variable "$y") (Type "ConceptNode"))
              (TypedVariable (Variable "$z") (Type "ConceptNode")))
            (And
              (Inheritance (Variable "$z") (Concept "hostile"))
              (Inheritance (Variable "$x") (Concept "American"))
              (Evaluation
                (Predicate "sell")
                (List (Variable "$x") (Variable "$y") (Variable "$z")))
              (Inheritance (Variable "$y") (Concept "weapon")))
            (Inheritance (Variable "$x") (Concept "criminal")))
          (And
            (Evaluation
              (Predicate "sell")
              (List
                (Variable "$who")
                (Variable "$y-281a7166")
                (Variable "$z-8b8dc93")))
            (Inheritance (Variable "$who") (Concept "American"))
            (Inheritance (Variable "$y-281a7166") (Concept "weapon"))
            (Inheritance (Variable "$z-8b8dc93") (Concept "hostile")))))
      (ExecutionOutput
        (GroundedSchema "scm: bc-deduction-formula")
        (List
          (Inheritance (Concept "criminal") (Concept "criminal"))
          (Inheritance (Concept "criminal") (Variable "$B-7e054a97"))
          (Inheritance (Variable "$B-7e054a97") (Concept "criminal")))))
  ))

cmake fails due to unify already existing

Trying to cmake .. from /ure/build leads to the following error:

-- Build type: Release
-- CogUtil version 2.0.3 found.
-- AtomSpace found.
-- Boost version: 1.65.1
-- Found the following Boost libraries:
--   date_time
--   filesystem
--   serialization
--   system
--   thread
--   chrono
--   atomic
-- Boost version 106501 found.
-- CxxTest found.
-- Guile (2.2.3 >= 2.2.2) was found.
-- Python 3.7.3 interpreter found.
-- Python 3.7.3 libraries found.
-- Cython ( 0.29.1 >= 0.23.0) found.
-- Python destination dir found: /usr/local/lib/python3.7/dist-packages
-- Python install dir: /usr/local/lib/python3.7/dist-packages/opencog
-- Using nosetests executable /usr/bin/nosetests3
-- Valgrind Prefix: 
-- VALGRIND was found.
-- VALGRIND devel headers found.
CMake Error at opencog/unify/CMakeLists.txt:1 (ADD_LIBRARY):
  ADD_LIBRARY cannot create target "unify" because an imported target with
  the same name already exists.


CMake Error at opencog/unify/CMakeLists.txt:5 (TARGET_LINK_LIBRARIES):
  Cannot specify link libraries for target "unify" which is not built by this
  project.

Forward chainer is not stable against library changes.

The ForewardChainerUTest sometimes passes, and sometimes fails, depending on how the AtomSpace has been built, and depending on the random number generator. Changing the initial random see at line 111 causes the unit test to pass/fail randomly. In particular, the test_negation_conflict is the most sensitive to this.

ure/tests/ure/forwardchainer/ForwardChainerUTest.cxxtest

Lines 103 to 111 in a88b4df

	// XXX FIXME. This unit test is unstable with respect to
	// perturbations in the code base. In particular,
	// test_negation_conflict sometimes passes, and sometimes fails,
	// depending on how the AtomSpace has been compiled. The test
	// failure can be fixed by changing the seed value here, trying
	// different seeds until one finds one that allows the unit tests
	// to pass. Currently, a seed of 3 works for me. A seed of 0 used
	// to work, but doesn't any longer.
	randGen().seed(3);

Needless to say, this comes as an unhappy surprise. I lost two hours tracking this down.

Why not DualLink ?

So .. DualLink is a link type that can be used to search through a collection of rules, to see which rules might be applied in some given situation. Thus, if you have some large number of rules, (say, tens of thousands, like the chatbots) the DualLink will narrow this set down to the half-dozen which can actually be run "right now". Then, some other algo decides which of the half-dozen could, should be applied.

DualLink was designed with the intention that it can provide the backbone for forward-chaining or backward-chaining, by finding which premises can be attached to which outputs. Yet, a quick grep through the URE codebase shows that the URE does not use DuaLink.

So the question is .. why? Did DualLink simply not work well enough? Did it have the wrong form or style? Was it buggy? Was it too hard to use? Clearly, the URE has some other way of discovering chains ...

Since presumably the DualLink is not good enough for chain discovery, maybe there is some variation on it that would work better?

Support other fitness than maximizing confidence in URE

The URE currently only supports maximizing confidence as its fitness function to guide chaining. It should support other kind of fitnesses, in particular, maximizing strength as well. This would be especially important for moving MOSES optimization step to the URE, because we are interested in candidates we are not only confident about their fitness estimations, but also that have high fitness estimations.

The C++ code involved is https://github.com/opencog/atomspace/blob/master/opencog/rule-engine/backwardchainer/Fitness.h, see also https://github.com/opencog/atomspace/blob/master/opencog/rule-engine/backwardchainer/BackwardChainer.cc#L361 for an example of its use.

It's likely that BITNodeFitness will have to be properly adjusted when spread backward. For instance if we're after a high strength for some target, and the URE decides to expand that target with a deduction rule, then, the fitness function over the premises of deduction should be set such that maximize them will maximize strength on the target. That doesn't seem trivial, and moreover may require dependencies between fitnesses. The confidence fitness is really easy in comparison because in order to maximize the confidence of a conclusion, you merely need to maximize the confidence of its premises.

Have the unifier supports deep types

Motivation

The unifier https://github.com/opencog/atomspace/tree/master/opencog/unify, a crucial component of the URE https://github.com/opencog/atomspace/tree/master/opencog/rule-engine, must perform type intersection in the unification process.

Unfortunately type intersection has not been implemented for deep types, as a consequence deep types cannot be used in URE rules, or source or target variable declarations.

Task

To have the unifier support type intersection one would need to upgrade Unify::type_intersection to support deep types, so assuming we only bother about the inheritance cases of intersection, one would need to add deept type support to Unify::inherit https://github.com/opencog/atomspace/blob/master/opencog/unify/Unify.cc#L923.

Add GlobNode support to the unifier

In order to have the URE support GlobNode in its rules, the unifier needs to support GlobNode, as to avoid issues like https://github.com/opencog/atomspace/issues/2009

Support meta-rule in the URE

Overview

A meta-rule, which could also be called a rule schema, is a rule that
produces a rule. It is convenient to have the URE support that as
explained below.

Motivation

Some rules don't fit well within a single BindLink, such as
universal or conditional instantiations. They however fit very well as
meta-rules. What the URE would do is, upon selecting a meta-rule,
generate a rule out of it to build a forward or backward chaining
step.

Example: conditional instantiation

The conditional instantiation rule, as currently implemented looks
like this

Bind
  VariableList
    TypedVariable
      Variable "$X-decl"
      Type "TypedVariable"
    Variable "$P"
    Variable "$Q"
  LocalQuote
    ImplicationScope
      Variable "X-decl"
      Variable "$P"
      Variable "$Q"
  ExecutionOutput
    GroundedSchema "scm: instantiate"
    List
      ImplicationScope
        Variable "X-decl"
        Variable "$P"
        Variable "$Q"

What it does is, upon finding an implication link, calls the schema
instantiate that will generate a new pattern matcher query to find
an $X so that $P is true to some degree and substitute $X in
$Q by the solution of $X, then apply a formula to calculate the TV
of $Q after substitution.

In some ways it already is a meta-rule, but the process of unfolding
it into a rule is obfuscated inside instantiate and the Backward
Chainer is unable to run that process in reverse.

Let's now define it as a meta-rule

Bind
  VariableList
    TypedVariable
      Variable "$X"
      Type "VariableNode"
    TypedVariable
      Variable "$type"
      Type "TypeNode"
    Variable "$P"
    Variable "$Q"
  LocalQuote
    ImplicationScope
      TypedVariable
        Variable "$X"
        Variable "$type"
      Variable "$P"
      Variable "$Q"
  LocalQuote
    Bind
      TypedVariable
        Variable "$X"
        Variable "$type"
      And
        Variable "$X"
        Variable "$P"
      LocalQuote
        ExecutionOutput
          GroundedSchema "scm: implication-full-instantiation-formula"
          List
            Variable "$X"
            Variable "$P"
            Variable "$Q"

What this does is, given an matching implication, generate the rule

    Bind
      TypedVariable
        Variable "$X"
        Variable "$type"
      And
        Variable "$X"
        Variable "$P"
      LocalQuote
        ExecutionOutput
          GroundedSchema "scm: implication-full-instantiation-formula"
          List
            Variable "$X"
            Variable "$P"
            Variable "$Q"

That rule can then be applied to find a term for $X, rewrite $Q
with it and calculate its TV. The resulting rule is much simpler but
more importantly all premises are visible and thus the Backward
Chainer is able to turn them into subsequent targets. Moreover, it
should be able to generate new targets for the meta-rule itself,
because there are also visible, so for instance the implication itself
can be used as target, not just its implicant.

Add python ure_logger bindings

Python bindings for the ure_logger

https://github.com/opencog/ure/blob/master/opencog/ure/URELogger.h

are still missing. This makes working with the URE with a python a bit cumbersome.

I don't know the python bindings code too well but it seems to enable one need to

1. Have the python logger binding accept any logger, not just opencog's default one.
2. Introduce ure logger function helpers.

for both items can the scheme bindings can be used as exemplar, see

ure/opencog/scm/opencog/ure/ure-utils.scm

Lines 765 to 907 in 6444f8a

	(define (ure-logger-set-level! l)
	"
	Wrapper around cog-logger-set-level! using (cog-ure-logger) as logger.
	See (help cog-logger-set-level!) for more info.
	"
	(cog-logger-set-level! (cog-ure-logger) l))
	(define (ure-logger-get-level)
	"
	Wrapper around cog-logger-set-level! using (cog-ure-logger) as logger.
	See (help cog-logger-set-level!) for more info.
	"
	(cog-logger-get-level (cog-ure-logger)))
	(define (ure-logger-set-filename! filename)
	"
	Wrapper around cog-logger-set-filename! using (cog-ure-logger) as logger.
	See (help cog-logger-set-filename!) for more info.
	"
	(cog-logger-set-filename! (cog-ure-logger) filename))
	(define (ure-logger-get-filename)
	"
	Wrapper around cog-logger-get-filename using (cog-ure-logger) as logger.
	See (help cog-logger-get-filename) for more info.
	"
	(cog-logger-get-filename (cog-ure-logger)))
	(define (ure-logger-set-stdout! enable)
	"
	Wrapper around cog-logger-set-stdout! using (cog-ure-logger) as logger.
	See (help cog-logger-set-stdout!) for more info.
	"
	(cog-logger-set-stdout! (cog-ure-logger) enable))
	(define (ure-logger-set-sync! enable)
	"
	Wrapper around cog-logger-set-sync! using (cog-ure-logger) as logger.
	See (help cog-logger-set-sync!) for more info.
	"
	(cog-logger-set-sync! (cog-ure-logger) enable))
	(define (ure-logger-set-timestamp! enable)
	"
	Wrapper around cog-logger-set-timestamp! using (cog-ure-logger) as logger.
	See (help cog-logger-set-timestamp!) for more info.
	"
	(cog-logger-set-timestamp! (cog-ure-logger) enable))
	(define (ure-logger-error-enabled?)
	"
	Wrapper around cog-logger-error-enabled? using (cog-ure-logger) as logger.
	See (help cog-logger-error-enabled?) for more info.
	"
	(cog-logger-error-enabled? (cog-ure-logger)))
	(define (ure-logger-warn-enabled?)
	"
	Wrapper around cog-logger-warn-enabled? using (cog-ure-logger) as logger.
	See (help cog-logger-warn-enabled?) for more info.
	"
	(cog-logger-warn-enabled? (cog-ure-logger)))
	(define (ure-logger-info-enabled?)
	"
	Wrapper around cog-logger-info-enabled? using (cog-ure-logger) as logger.
	See (help cog-logger-info-enabled?) for more info.
	"
	(cog-logger-info-enabled? (cog-ure-logger)))
	(define (ure-logger-debug-enabled?)
	"
	Wrapper around cog-logger-debug-enabled? using (cog-ure-logger) as logger.
	See (help cog-logger-debug-enabled?) for more info.
	"
	(cog-logger-debug-enabled? (cog-ure-logger)))
	(define (ure-logger-fine-enabled?)
	"
	Wrapper around cog-logger-fine-enabled? using (cog-ure-logger) as logger.
	See (help cog-logger-fine-enabled?) for more info.
	"
	(cog-logger-fine-enabled? (cog-ure-logger)))
	(define (ure-logger-error . args)
	"
	Wrapper around cog-logger-error using (cog-ure-logger) as logger.
	See (help cog-logger-error) for more info.
	"
	(apply cog-logger-error (cons (cog-ure-logger) args)))
	(define (ure-logger-warn . args)
	"
	Wrapper around cog-logger-warn using (cog-ure-logger) as logger.
	See (help cog-logger-warn) for more info.
	"
	(apply cog-logger-warn (cons (cog-ure-logger) args)))
	(define (ure-logger-info . args)
	"
	Wrapper around cog-logger-info using (cog-ure-logger) as logger.
	See (help cog-logger-info) for more info.
	"
	(apply cog-logger-info (cons (cog-ure-logger) args)))
	(define (ure-logger-debug . args)
	"
	Wrapper around cog-logger-debug using (cog-ure-logger) as logger.
	See (help cog-logger-debug) for more info.
	"
	(apply cog-logger-debug (cons (cog-ure-logger) args)))
	(define (ure-logger-fine . args)
	"
	Wrapper around cog-logger-fine using (cog-ure-logger) as logger.
	See (help cog-logger-fine) for more info.
	"
	(apply cog-logger-fine (cons (cog-ure-logger) args)))
	(define (ure-logger-flush)
	"
	Wrapper around cog-logger-flush using (cog-ure-logger) as logger.
	See (help cog-logger-flush) for more info.
	"
	(cog-logger-flush (cog-ure-logger)))

ure/opencog/ure/URESCM.cc

Lines 117 to 118 in 6444f8a

	define_scheme_primitive("cog-ure-logger",
	&URESCM::do_ure_logger, this, "ure");

Replace specialized/incomplete type intersection code in unifier by TypeSetLink

It looks like the pattern matcher already implements a form of type intersection https://wiki.opencog.org/w/TypeSetLink. So it might be possible to replace the adhoc type intersection code of the unifier Unify::type_intersection by something more generic (perhaps improving TypeSetLink along the way if necessary).

This could be a better way to address https://github.com/opencog/atomspace/issues/1906 as well.

Add feature to enable/disable collection of Inference trails(Fcstat) in URE

Presently collection of inference trails is enabled by default. For creation of simple-english wikipedia or other atomese datasets, for use with the present chatbot, the collection of these trails isn't required. Having the option to disable them should help in squeezing in some more content into ram. There might be other performance benefits as well.

scheme@(guile-user)> (use-modules (opencog) (opencog atom-types) (opencog nlp) (opencog nlp chatbot) (opencog nlp relex2logic))
scheme@(guile-user)> (length (cog-get-trunk (Concept "dummy-source")))
$1 = 0
scheme@(guile-user)> (nlp-parse "This is the first test.")
$2 = ((SentenceNode "sentence@6f27c907-be77-47f2-97ba-ba6d4952fc0a")
)
scheme@(guile-user)> (length (cog-get-trunk (Concept "dummy-source")))
$3 = 7
scheme@(guile-user)> (nlp-parse "This is the second test.")
$4 = ((SentenceNode "sentence@56d6687a-3cec-4cb9-8547-43f4b61ff2ae")
)
scheme@(guile-user)> (length (cog-get-trunk (Concept "dummy-source")))
$5 = 14
scheme@(guile-user)> (nlp-parse "The quick brown fox jumped over the lazy dog, so they say or not.")                              
$6 = ((SentenceNode "sentence@d4182948-9d4c-4a6b-ba34-ef2080e4a6ee")
)
scheme@(guile-user)> (length (cog-get-trunk (Concept "dummy-source")))
$7 = 27
)

Unbalanced quotations

The outcome of issue opencog/atomspace#2886 is that there are multiple cases of unbalanced quote links in the URE. I don't know if this is a bug or a feature, if it's important or can be ignored.

These can be found by altering https://github.com/opencog/atomspace/blob/b158262242b00a4939cd1451c17b6ce99dda8cc9/opencog/atoms/core/Quotation.cc#L80-L87 uncommenting the throw, converting it to an assert, and running the URE unit tests. Some will crash, the stack trace will show how they got into the negative-quote-level territory.

URE Unable to detect user error

i ran FC, by providing the parameters in the wrong order, But it does not return an appropriate error message.

(cog-fc source base (List) (SetLink))
Backtrace:
In ice-9/boot-9.scm:
157: 10 [catch #t #<catch-closure 1a57c00> ...]
In unknown file:
?: 9 [apply-smob/1 #<catch-closure 1a57c00>]
In ice-9/boot-9.scm:
157: 8 [catch #t #<catch-closure 1a57ac0> ...]
In unknown file:
?: 7 [apply-smob/1 #<catch-closure 1a57ac0>]
?: 6 [call-with-input-string "(cog-fc source base (List) (SetLink))\n" ...]
In ice-9/boot-9.scm:
2320: 5 [save-module-excursion #<procedure 1c14870 at ice-9/eval-string.scm:65:9 ()>]
In ice-9/eval-string.scm:
44: 4 [read-and-eval #<input: string 30ffb60> #:lang ...]
37: 3 [lp (cog-fc source base (List) (SetLink))]
In unknown file:
?: 2 [opencog-extension cog-fc (# # # #)]
In ice-9/boot-9.scm:
102: 1 [#<procedure 30f6240 at ice-9/boot-9.scm:97:6 (thrown-k . args)> C++-EXCEPTION ...]
In unknown file:
?: 0 [apply-smob/1 #<catch-closure 1a57a80> C++-EXCEPTION ...]
ERROR: In procedure apply-smob/1:
ERROR: In procedure cog-fc: Not a node! (/home/vishnu/atomspace/opencog/atoms/base/Atom.h:193)
Function args:
((InheritanceLink (stv 0,9 0,9)
(ConceptNode "tom")
(ConceptNode "human")
)
(ConceptNode "rule-base")
(ListLink
)
(SetLink
)
)
ABORT: C++-EXCEPTION

Forward-chainer general discussion

Moving comments from opencog/atomspace#1004

There is a forward-chainer issue that shows up in the self-model prototype: the need to multiple steps or stages of rule-sets. That is, first, one must apply some rules from ruleset A, and only when these are done, then apply rules from ruleset B. After that, C and D can be run in parallel, but ruleset E cannot be used until both C and D have completed. The current robot-chatbot pipleline really does have about this many stages: ruleset A is relex2logic, B is the LG-to-control-language, C is the self-model update, D is the robot animation update, and E is a mish-mash of poorly implemented "action orchestration. Right now, this is done with a pile of ad-hoc scheme code to plumb everything together. Better plumbing would be nice.

A very different issue is the narrowing-down of rulesets. The current behavior infrstructure has maybe 50 or so rules, and so we can afford to run all of them at each inference step. However, this isn't scalable as the number of rules goes up.

We've already got a scalable solution for this in OpenPsi, but maybe the forward-chainer should do it too. The current working example is the AIML subsystem, where there are 20K or more rules, of which only a dozen or two are appropriate for the given input sentence. The cog-recognize function is used to narrow these own; its mostly integrated with openpsi, but needs polishing and enhancing.

More generally, we are currently using OpenPsi as a single-step chainer. Exactly how to manage that as a multi-step forward chainer is unclear. However, this discussion really does not belong in this bug report.

BackwardChainerUTest fails to build referencing Atomtable

atomspace/build/$ make test
...

[ 41%] Linking CXX executable BackwardChainerUTest
/usr/bin/ld: ../../../opencog/ure/libure.so: undefined reference to `opencog::AtomTable::extract(opencog::Handle&, bool, bool)'
/usr/bin/ld: ../../../opencog/ure/libure.so: undefined reference to `opencog::DefineLink::get_definition(opencog::Handle const&, opencog::AtomSpace*)'
/usr/bin/ld: ../../../opencog/unify/libunify.so: undefined reference to `opencog::AtomTable::getHandle(opencog::Handle const&) const'
collect2: error: ld returned 1 exit status
make[3]: *** [tests/ure/backwardchainer/CMakeFiles/BackwardChainerUTest.dir/build.make:132: tests/ure/backwardchainer/BackwardChainerUTest] Error 1

Have the backward chainer support URE rules without formula

Currently, in order to have the backward chainer string URE rules together, each rule requires a formula, i.e. it must be formatted as follows

BindLink
  <vardecl>
  <pattern>
  ExecutionOutputLink
    <formula>
    List
      <conclusion>
      <premise-1>
      ...
      <premise-n>

It does that in order to clearly identify conclusion vs premises, as the <pattern> term may contain premises as well as rule preconditions. However in some cases (such as algebraic transformations) you neither need preconditions nor formulas. So it would be good if the backward chainer could support rules with the following format

BindLink
  <vardecl>
  AndLink
    <premise-1>
    ...
    <premise-n>
  <conclusion>