知识图谱-klips-PROSAGA-码农传奇

Kotlin Language Integrated Production System (KLIPS)

Keywords

Rule Engine, Logical Programming, Declarative Programming, Rete, AI Engine, DSL

Right off the bat!

class MyRules : RuleSet() {
    init {
        rule(group = "GrandFatherRule") {
            val p1 = ref<String>() ; val p2 = ref<String>() ; val p3 = ref<String>()
            +FatherOf(p1, p2)
            +FatherOf(p2, p3)
            effect {
                +GrandFatherOf(p1, p3)
            }
        }
        rule(group = "GrandFatherRule") {
            val p1 = ref<String>() ; val p2 = ref<String>() ; val p3 = ref<String>()
            +FatherOf(p1, p2)
            +MotherOf(p2, p3)
            effect {
                +GrandFatherOf(p1, p3)
            }
        }
        rule(group = "SiblingsRule") {
            val p1 = ref<String>() ; val p2 = ref<String>() ; val p3 = ref<String>()
            +FatherOf(p1, p2)
            +FatherOf(p1, p3)
            guard(p2 gt p3)
            effect {
                +SiblingOf(p2, p3)
            }
        }
        rule(group = "SiblingsRule") {
            val p1 = ref<String>() ; val p2 = ref<String>() ; val p3 = ref<String>()
            +MotherOf(p1, p2)
            +MotherOf(p1, p3)
            effect {
                +SiblingOf(p2, p3)
            }
        }
        rule(group = "SiblingsSymmetryRule") {
            val p1 = ref<String>() ; val p2 = ref<String>()
            +SiblingOf(p1, p2)
            effect {
                +SiblingOf(p2, p1)
            }
        }
    }
}
val r = MyRules()
r.input.flush {
    +FatherOf("p1", "p2")
    +FatherOf("p2", "p3")
    +FatherOf("p1", "p22")
}

Still interesting? Well, lets dive!

Motivation

This library is inspired by the CLIPS (C Language Integrated Production
System), hence KLIPS does for Kotlin the same thing as CLIPS for C.
Why Kotlin? Kotlin is from JVM clan and more expressive than Java but
simpler than Scala. Kotlin have a good enough capabilities to design a
DSL allowing more or less smooth mix of rule declarations with ‘ordinary’
Kotlin code. Other reason is that Kotlin become a ‘weapon’ of choice for
more and more programmers for an Android devices. I believe this library
would be a helper for programmers developing AIs for their games for
Android.

Introduction

KLIPS provides DSL to specify a production rules and a rule engine
to trigger them. Rule have its left hand side (LHS) which specifies a
condition under which a rule will be activated, and a right hand side
(RHS) which specifies a what to do if rule decided to apply. Engine
solves a system of a rules against working memory in a reactive way i.e.
when it is changed. Working memory (WM) is a set of facts. Facts are
pieces of a data describing the state of a world of a particular program,
hence they are specific for each program and defined by a programmer.
Probably, it is more convenient for some domains to treat facts as an
events. Facts are pushed into WM as soon as they become known and if
conditions of some rules are satisfied then those rules become activated.
All activated rules form a collection called an agenda and at some point
a conflict resolution policy is applied. The purpose of a conflict
resolution is to decide which activated rule must be applied first. All
these concepts will be explained in more details bellow.

Fact

Fact is a data piece describing some aspect of a state of a world of
your program. Fact is quite similar to the concept of relation from
‘Relational Algebra’. Technically it is a subclass of the class
org.kotlin.dsl.Fact with some additional requirement about fields.
Lets see example:

class Actor(val id:Facet<Int>, val nrgy:Facet<Int>, val type:Facet<ActorType>) : Fact()
class At(val actorId:Facet<Int>, val cellId:Facet<Int>) : Fact()
class Adjacent(val cellId1:Facet<Int>, val cellId2:Facet<Int>) : Fact()
class Cell(val id:Facet<Int>, val resourceAmount:Facet<Double>) : Fact()
class MoveCommand(val actorId:Facet<Int>, val cellId:Facet<Int>) : Fact()

Please note that the primary constructors contain fields of type
org.kotlin.dsl.Facet. Facets are placeholders which may contain a
concrete constant or a reference (a variable if you wish). Facets
introduced due to we need to be able to reuse the same fact classes to
specify concrete data and patterns which contain references, this
became more clear bellow at the ‘Rule’ topic.
So the facts above, describe a simple domain in which may live some
actors, which may be located at some cell (tile), and some cells may be
adjacent and some other not (topology of space).
Now we put to WM some facts to initialize our world:

input.flush {
    +Cell(0.facet, 0.5.facet) // Define cell 0 with some amount of resources
    +Cell(1.facet, 0.5.facet)
    +Cell(2.facet, 0.5.facet)
    +Cell(3.facet, 0.facet)
    +Cell(4.facet, 0.facet)
    +Adjacent(0.facet, 1.facet) // Define cells 0 and 1 as adjacent
    +Adjacent(0.facet, 2.facet) // Define cells 0 and 2 as adjacent
    +Adjacent(0.facet, 3.facet) // Define cells 0 and 3 as adjacent
    +Adjacent(0.facet, 4.facet) // Define cells 0 and 4 as adjacent
    +Actor(1.facet, 100.facet, ActorType.Worker.facet) // Define actor of type Worker with energy 100 units
    +At(1.facet, 0.facet) // Place actor at cell 0
}

The instruction input.flush is an API call which modifies a WM state,
please do not bother about that for now, but pay some attention to unary
plus before constructor call and <some const>.facet notation. There
are two basic operations against WM: assert fact and retire fact. The
unary plus is a synonym for an assert operation and means add fact to WM.
The unary minus before fact would be a synonym for retire operation i.e.
remove fact from WM. So, when we want to make program become aware about
some piece of data about world we do assert a fact, and if a fact is no
valid any more we do retire a fact. The notation <some const>.facet is
used to make a constant of type T become a FacetConst<T>.

Rule

Now lets add some rules to our world. Suppose we want to have a rule to
move actors through the world space i.e. cells. Such a rule may sound
like this:

If command 'move some actor to some cell' issued, 
and if the target cell is adjacent to the current cell of an actor, 
and if an actor have an energy level greater than 5 units, 
than place actor on target cell and decrease the energy level of that actor by 5 units.

Such a rule may be described using KLIPS DSL as follows:

// Move rule v1
rule {
    // LHS: begin
    // Create references
    val aid = ref<Int>("aid") // Actor ID reference with name "aid". If name is not specified it will be generagted which is not very convenient for debug printing.
    val cid = ref<Int>("cid")
    val cid0 = ref<Int>("cid0")
    val nrge = ref<Int>("nrgy")
    val type = ref<ActorType>("type")
    // Describe pattern
    +MoveCommand(aid, cid)
    +Actor(aid, nrgy, type)
    +At(aid, cid0)
    +Adjacent(cid, cid0)
    // Additional constraint -- energy level must be greater than 5 units
    guard(nrgy gt 5.facet)
    // LHS: end
    // RHS enclosed by effect call
    effect { sol ->
       -At(aid, cid0) // Actor not at cell cid0 any more
       +At(aid, cid)  // Actor become at cell cid from now
       -Actor(aid, nrgy, type) // Actor data become invalid
       +Actor(aid, (sol[nrgy] - 5).facet, type) // Actor data updated with lower energy level
       -MoveCommand(aid, cid) // Move command dismissed
    }
}

As you can see the rule declaration is done by notation like:

rule {
    ...        // facts which form a pattern (rule precondition)
    guard(...) // guard -- additonal boolean constraint against references (FacetRef's)
    effect { sol ->  // sol is a solution i.e. map FacetRef -> FacetConst
    ... // asserted and retired facts
    }
}

The pattern of a rule, i.e. LHS, consists of a facts constructors prefixed
with unary plus or unary minus. The unary plus before the fact constructor
means that fact is a part of a pattern. Unary minus before the fact means
that fact constructor is a part of a pattern but the appropriate bound fact
will be automatically retired when rule effect{} part (RHS) will be
applied to WM. So if we have a rule:

rule {
    +F1(x)
    effect {
        -F1(x)
        +F1(func(x))
    }
}

Then we can rewrite it as:

rule {
    -F1(x)
    effect {
        +F1(func(x))
    }
}

Hence the move rule v1 above may be rewritten in a shorter form as:

val aid = ref<Int>("aid") // Actor ID reference with name "aid". If name is not specified it will be generagted which is not very convenient for debug printing.
val cid = ref<Int>("cid")
val cid0 = ref<Int>("cid0")
val nrge = ref<Int>("nrgy")
val type = ref<ActorType>("type")
// Move rule v2
rule {
    -MoveCommand(aid, cid)
    -Actor(aid, nrgy, type)
    -At(aid, cid0)
    +Adjacent(cid, cid0)
    guard(nrgy gt 5.facet)
    effect { sol ->
       +At(aid, cid)  // Actor become at cell cid from now
       +Actor(aid, (sol[nrgy] - 5).facet, type) // Actor data updated with lower energy level    
    }
}

The primary goal of an engine is to find such a binding of references
which is satisfying a pattern. Such a binding called ‘solution’. Note
that solution satisfies also a guard optionally existing in an LHS.
Remember school? It is very similar like finding a solution for a system
of an equations, where an equations are facts and variables are references.

After solution is found then the references in an effect{...} are
substituted with constants and asserted or retired against WM. But there
are cases when we want to explicitly specify the constant facet for some
fact at effect{...} like from example above:

    effect { sol ->
       +Actor(aid, (sol[nrgy] - 5).facet, type)    
    }

the expression (sol[nrgy] - 5).facet does the computation of a new
value of an energy level decreasing the old one it by 5 and converting
an ordinary Kotlin value to FacetConst by calling an extension
property facet. As you can see, to get the Kotlin value
(i.e. not FacetConst but T) bound to particular reference we use
sol[ref] call.

Now we need another one rule:

// Adjacency symmetry rule
rule {
    +Adjacent(cid0, cid)
    effect {
        +Adjacent(cid, cid0)    
    }
}

The rule above ensures that if cid0 adjacent to cid then cid
adjacent to cid0. This adjacency symmetry rule required for move rule
successful work. When we initialized our world we have asserted a set of
adjacency facts but we did not asserted their reversed counterparts and
without the adjacency symmetry rule it would lead to a problem of not
triggering the move rule which could be solved by asserting also a reversed
adjacency facts, but it is much better to add a rule generating what we need.

More on ‘guard’

Guard is a way to impose an additional constraints on possible values
denoted by references. For example above have we specified that we are
interested only in those solutions where energy (nrgy) value is greater
than 5:

guard(nrgy gt 5.facet)

the function guard takes a boolean expression made by infix operator
gt (greater than). There are other operators:

gt - greater than
ge - greater or equal
lt - less than
le - less or equal
eq - equal
and - conjunction
or - disjunction
so the more complex guard could look like:
```
guard( (x gt y) and (z le 5.facet) )
```
There is also another way to specify guard:
```
guard { sol -> sol[nrgy] > 0 }
```
I.e. pass to guard boolean function (predicate) accepting solution
sol. This approach give us more for complicated cases like:
```
guard { sol -> max(0, sol[nrgy] - sol[nrgy1]) > 0 }
```

More on ‘effect’

The high order function effect (RHS) may contain any code e.g. side
effect which must be executed if condition met. When rule set is created
the rules are ‘compiled’ into special representation called ‘rete’. At
the phase of such a ‘compilation’ the LHS is executed and pattern (facts)
obtained, but RHS (i.e. lambda passed to the effect) is executed at
‘runtime’ when rule is decided to be applied. In example above we have
no any side effects and using effect only to change a WM.

Rule priority

In a real world rule sets, it is very probable a situation when we have
a several rules activated (in agenda) which have their effects non
commutative. That is the order of an application of the effects may be
important. For this case we want to give a simple hint to the engine —
priority:

rule( priority = 10.5 ) {
    ...
}

The lower value the higher priority. If priority is not specified then
it is generated in accordance to the appearance in a rule set, i.e. very
first rule in a rule set have highest priority.

Computation semantics

To prepare a set of rules we must create a subclass of
org.klips.dsl.RuleSet like that:

class MyRules : RuleSet() {
    init {
        rule {
            ...
            effect {
                ...
            }
        }
        rule {
            ...
            effect {
                ...
            }
        }
        ...
    }
}

After that we are able to start to use our rule system as follow:

    val r = MyRules()
    r.input.flush {
        +F1(a,b,c)
        +F2(a,b)
        ...
    }

The method flush allow us to apply a set of facts to the rule system WM.
We should have some high level view about how such an application handled:

1. facts pushed to the queue `qf`
2. while `qf` is not empty repeat
     2.1. take a fact from `qf` and apply it to the WM (assert or retire)
     2.2. some rules may be 
        2.2.a. activated and pushed into `agenda` along with their solution
        2.2.b. deactivated and purged from `agenda` along with their solution
3. if `agenda` is not empty 
    3.1. take a pair (rule, solution) with highest priority from the `agenda`
    3.2. compute an effect of a rule using the solution and obtain a set of asserted and retired facts 
    3.3. push them to the `qf`
    3.4. go to 2.
4. flush is finished.

So after flush is returns a multiple rules may be triggered and have
applied their effects.