Welcome to stilpo’s documentation!¶
Contents:
Classic Problem Solver¶
API¶
depth-first-solver creates depth first solver.
(depth-first-solver :is-goal goal?
:operators operators
:is-identical identical?)
breadth-first-solver creates breadth first solver.
(breadth-first-solver :is-goal goal?
:operators operators
:is-identical identical?)
best-first-solver creates best first solver.
(best-first-solver :is-goal goal?
:operators operators
:is-identical identical?
:distance distance-left)
a*-solver creates a solver that implements a* search.
(a*-solver :is-goal goal?
:distance distance-left
:distance-between distance-between
:operators operators
:is-identical identical?))
goal? is a function that accepts a single parameter state and
returns True or False indicating if the goal has been reached.
operators is a function that accepts a single parameter and returns
a list of tuples where first element is a function that can create a new
state from old one and second element is textual description of the transition.
identical? is a function accepting two states and returning True or
False indicating if the states are considered equal. This function is
used to detect loops in search path.
distance is a function that estimates distance left for given state. It
is used to optimize search path in best first and a* search.
distance-between is a function that can calculate cost or distance between
two different states. It is used to optimize a* search.
Example¶
Classic problem solver (CPS for short) is a solver based on simple search and goal detecting routine. Systems starts from an initial state and expands through problem space by trying different operations according to given search criteria.
If we wanted to solve the following problem:
You have 2 jugs, with capacity of 4 and 5 liters. Your task is to measure 2 liters of water. You have unlimited amount of water in your disposal.
A high level example of typical solver initialization and execution:
(require [stilpo.cps [operator]])
(import [stilpo.cps [breadth-first-solver valid-operators]])
(def b-solve (breadth-first-solver :is-goal goal?
:operators operators
:is-identical identical?))
(-> (b-solve initial-state)
(print-solution))
breadth-first-solver is a function that will create a solver that uses
breadth first search when called. This solver can then be used to solve one
or more problems (it doesn’t retain state between calls).
We represent state of our problem as a dictionary (any other data structure would work too, stilpo isn’t that particular about it). At the beginning, there are two jugs, both empty:
(def initial-state {:jug-4 0
:jug-5 0})
Detecting goal in our case is simple. When ever one of the jugs holds exactly two liters of water, we’re done:
(defn goal? [state]
(or (= (:jug-4 state) 2)
(= (:jug-5 state) 2)))
CPS needs to know which operators it can perform to any given state. Operator is just a function that when applied to a state, will return a new state. You are free to structure your code in the way you prefer, but stilpo has an utility functions for building operators and detecting when they can be applied.
operator macro is used to define special function that represents an
operation that can be done to a state:
(operator empty-jug-4 "pour 4 liter jug empty"
(> (:jug-4 state) 0)
{:jug-4 0
:jug-5 (:jug-5 state)})
First parameter is name of the function being defined, second one is
textual description that can be printed out to specify solution to the
problem. Third parameter is a form that returns true if operator is legal
for given state. Rest of the code is used to create a new state that has
been modified (4 liter jug poured empty in this example).
Each discrete action is defined as an operator like above and then packed into a function that can check which operators are valid for given state and return their application:
(defn operators [state]
"all valid operators for given state and their descriptions"
(valid-operators state empty-jug-4 empty-jug-5
fill-jug-4 fill-jug-5
pour-4-to-5 pour-5-to-4))
Final tool we need to define is detection of identical states. This is used by search algorithm to prune possible loops from the solution:
(defn identical? [state1 state2]
(and (= (:jug-4 state1) (:jug-4 state2))
(= (:jug-5 state1) (:jug-5 state2))))
We of course would like to print out our solution, so we define
pretty-print to do that task for us:
(require [hy.extra.anaphoric [ap-each]])
(defn pretty-print [path]
(when path
(ap-each path
(cond [(in :action it)
(print (.format "{0} (jugs: {1} and {2})"
(:desc (:action it))
(:jug-4 (:state it))
(:jug-5 (:state it))))]
[true (print "starting")]))))
Function simple walks the path and prints out textual info of action taken and amount of water held by each jug:
startingfill 4 liter jug with water (jugs: 4 and 0)pour water from 4 liter jug to 5 liter jug (jugs: 0 and 4)fill 4 liter jug with water (jugs: 4 and 4)pour water from 4 liter jug to 5 liter jug (jugs: 3 and 5)pour 5 liter jug empty (jugs: 3 and 0)pour water from 4 liter jug to 5 liter jug (jugs: 0 and 3)fill 4 liter jug with water (jugs: 4 and 3)pour water from 4 liter jug to 5 liter jug (jugs: 2 and 5)
Tiny Rule Engine¶
API¶
create-tre creates a tiny rule engine
(setv tre (create-tre "Example" :debug False))
assert! asserts a fact into a given rule engine
(assert! tre (hy is lisp))
rule creates a new rule and inserts it into a rule engine
(rule tre (?x is lisp)
(assert! tre (?x is awesome)))
Sometimes you would want to force variable values be unique:
(rule tre (?x is on bottom of well)
(rule (?y is on bottom of well)
(unique ?x ?y)
(assert! tre (?x and ?y are on bottom of well))))
run execute tiny rule engine until all rules and assertions are processed
(run tre)
show show assertions associated with given symbol
(show tre 'hy)
true? check if given assertion holds
=> (true? tre '(hy is awesome))
True
push-tre creates a new context where to try things
=> (rule tre (?x uses flux-capacitor)
(assert! tre (?x is from future)))
=> (push-tre tre "Assuming Hy is using flux-capacitor")
=> (assert! tre (hy uses flux-capacitor))
=> (run tre)
=> (true? tre '(hy is from future))
True
frame-title retrieves name of current frame
=> (frame-title tre)
"Assyming Hy is using flux-capacitor"
pop-tre discards the most recent frame
=> (pop-tre tre)
=> (true? tre '(hy is from future))
False
try-in-context is useful for creating a context and trying out a thing
inside of it, before discarding the context automatically.
=> (rule tre (?x uses Python)
(assert! tre (?x is modern system)))
=> (rule tre (?x uses Lisp)
(assert! tre (?x is timeless system)))
=> (rule tre (?x uses quantum computing)
(assert! tre (?x is future system)))
=> (try-in-context tre (hy uses quantum computing)
(print (true? '(hy is future system))))
True
=> (true? '(hy is future system))
False
Example¶
Tiny rule engine is pattern directed inference system that operates on symbols and patterns. Essentially, it deduces new assertions based on existing assertions and rules.
For example, we can deduct family relations:
First step is to initialize tiny rule engine and bind a symbol to it:
(setv tre (create-tre "family"))
Assertions (true statements) are created with assert!. Once a truth has been
asserted, there is no way to remove it. This is because doing so would have to
remove all rules and assertions that it might have created and their results and
so on. Keeping track of web of assertions and rules would have been rather
complicated and error prone system, so it was left out.
(assert! tre (Alice is parent of Bob))
(assert! tre (Bob is parent of Charlie))
Rules are used to create new assertion and rules based on existing ones. They consist of a pattern and body. When tiny rule engine executes a rule, it processed through all assertions, checking if any of them match the pattern. When a match is found, body of the rule is executed. Special notation is used to introduce free variables in the pattern that can then be used in the body:
(rule tre (?x is parent of ?y)
(assert! tre (?y is children of ?x)))
(rule tre (?x is parent of ?y)
(rule tre (?y is parent of ?z)
(assert! tre (?x is grand-parent of ?z))))
(rule tre (?x is grand-parent of ?y)
(assert! tre (?y is grand-children of ?x)))
Final step in our example is to execute the engine and review the results, which should show that Alice indeed is grand parent of Charlie:
=> (run tre)
=> (show tre 'Alice)
Alice is parent of Bob
Alice is grand-parent of Charlie
Charlie is grand-children of Alice
Bob is children of Alice
=> (true? tre '(Alice is grand-parent of Charlie))
True
The order of adding rules and assertions into tiny rule engine doesn’t matter. Engine will keep processing rules until no further changes occur in assertions. It is even possible to run tiny rule engine in REPL, working with rules and assertions step by step.
Justification Based Truth Maintenance System¶
Justification Based Truth Maintenance System or JTMS for short
API¶
create-jtms create instance of JTMS
create-node create node in TMS
assume-node make node an assumption and enable it
enable-assumption turn assumption 'in
retract-assumption turn assumption 'out
justify-node justify a node with justification
in-node? check if node is 'in
out-node? check if node is 'out
assumptions-of-node list all assumptions and premises having effect to this node
supporting-justification-for-node which justification is currently supporting a node
Tools¶
Tools module contain assortment of tools that are generally useful in writing problem solvers.
unify¶
unify tries to unify an assertion with a pattern, while capturing joker and
wildcard values. If unification is successful, a dictionary containing captured
variables is returned. If unification failed, None is returned instead.
Interface (unify [assertion pattern bindings unique-symbols])
assertions-expressionpatternpattern as s-expression, may contain?xand*xbindingsdictionary containing predefined values for variablesunique-symbolstuple of tuples defining variables that should be unique
=> (unify '(Hello World) '(Hi there, ?x) {} (,))
None
=> (unify '(Hello World) '(Hello ?x) {} (,))
{'?x 'World}
=> (unify '(Hello Charlie Brown) '(Hello *x) {} (,))
{'*x '(Charlie Brown)}
=> (unify '(foo bar baz) '(?x bar ?y) {} (,))
{'?x 'foo '?y baz}
=> (unify '(foo bar foo) '(?x bar ?y) {} (,))
{'?x 'foo '?y foo}
=> (unify '(foo bar foo) '(?x bar ?y) {} (, (, '?x '?y)))
None
fill-assertion¶
fill-assertion replaces variables in assertion with their respective values
from supplied bindings.
Interface (fill-assertion [assertion bindings])
assertions-expression containing ?x and *x variablesbindingsdictionary containing variables and their values
=> (fill-assertion '(Hello ?x) {'?x 'World})
'(Hello World)
License¶
Copyright (c) 2016 Tuukka Turto
Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the “Software”), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:
The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.
THE SOFTWARE IS PROVIDED “AS IS”, WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
What is stilpo?¶
Stilpo is a generic ai library for Hy, although at least parts of it should be usable by Python programs too. It is based on ideas explained in excellent Building Problem Solvers by Kenneth D. Forbus and Johan de Kleer and Paradigms of Artificial Intelligence Programming: Case Studies in Common Lisp by Peter Norvig.
Stilpo was also a greek philosopher, who was interested in logic and dialetic.