Provides an implementation of McCarthy's amb operator with
binding forms and acceptance test operator.
(accept condition ret)Function.
(amb & [binds & body])Function.
A macro that provides a non-deterministic way to traverse a space
and find a single solution amongst potentially many. If the search
space is exhausted then [[amb](#fogus.rv.amb/amb)](#fogus.rv.amb/amb) will return nil. The general form
of [[amb](#fogus.rv.amb/amb)](#fogus.rv.amb/amb) is as follows:
(amb <bindings> <execution body>)
Where <bindings> is a typical Clojure bindings form:
[<name1> <value1> ... <nameN> <valueN>]
And <execution body> is one or more Clojure expressions.
Within the execution body the (accept <condition> <expression>)
form is used to test some combination of the bindings for adherence
to a <condition> and return an <expression> that serves as the
return value of the call to [[amb](#fogus.rv.amb/amb)](#fogus.rv.amb/amb).
A call to (amb) (i.e. without bindings and body) will exhaust
immediately and thus result in nil as its value.
Constraints solving functions that operate on a Constraint Description which is a map describing a constraint description containing the mappings:
- :variables -> seq of LVars
- :formula -> list describing a predicate expression composed of a mix of the LVars in :variables and Clojure functions.
(satisfy* {:keys [variables formula :as c]})Accepts a map describing a constraint description containing the mappings:
- :variables -> seq of LVars
- :formula -> list describing a predicate expression composed of a mix of the LVars in :variables and Clojure functions
This function will use the constraint description to calculate the all of the values for the LVars that satisfy the formula. The result is a seq of maps with mappings from LVar -> value. If there is no way to satisfy the formula then an empty seq is the result.
The ordering of the results of this function is not guaranteed to be stable.
(satisfy1 {:keys [variables formula :as c]})Accepts a map describing a constraint description containing the mappings:
- :variables -> seq of LVars
- :formula -> list describing a predicate expression composed of a mix of the LVars in :variables and Clojure functions
This function will use the constraint description to calculate the first set of values for the LVars that satisfy the formula. The result is a map with mappings from LVar -> value. If there is no way to satisfy the formula then an empty map is the result.
The first found result of this function is not guaranteed to be stable.
Most functions in rv work off of one or more of the following core concepts:
Entity: a hashmap with a :kb/id key mapped to a unique value and namespaced keys.
{:kb/id :person/john-doe :person/name "John Doe" :person/age 42}
Table: a set of hashmaps or Entities. Tables represent unstructured or semi-structured collections of data.
#{{:kb/id :city/blt :city/name "Baltimore"} {:kb/id :city/atl :city/name "Atlanta"}}
Fact: a vector triple in the form [entity-id attribute value] that describe that a given entity has an attribute with a specific value. You can tie facts together by referencing their :kb/ids.
[:person/john-doe :person/age 42] [:city/blt :city/name "Baltimore"]
Relation: a set of Facts pertaining to a particular Entity. You can tie facts together by referencing :kb/ids in value positions.
#{[:person/john-doe :person/age 42] [:city/blt :city/name "Baltimore"] [:person/john-doe :address/city :city/blt]}
LVar: a logic variable that can unify with any value in its :range
(map->LVar {:domain 'x :range (range 0 5)})
Ground: a concrete value, like a keyword, number, string, etc.
42, "John Doe", :city/blt
Query: a set of Facts containing a mix of LVars and Grounds used to find bindings for the LVars that satisfy a set of Facts.
Rules: a set of Facts describing derived or synthetic relations in terms of existing ones.
Production: a map containing :antecedent -> query and :consequent -> Facts to be asserted if the query fires.
KB: a set of Relations about many Entities and possibly containing Productions. It represents all the knowledge currently known or derivable.
Constraint Description: a set of LVars and a Formula describing the domain of their values.
Formula: a list describing a predicate expression of mixed LVars and clojure functions.
(->AnyT)(->AskT)(->IgnoreT)(lv? %1)(map->relation entity)
(map->relation idfn entity)Converts a map to a set of tuples for that map, applying a unique :kb/id if the map doesn't already have a value mapped for that key.
Relation values that are sets are expanded into individual tuples per item in the set with the same :kb/id as the entity and the attribute that the whole set was mapped to.
An idfn is a function of map -> id and if provided is used to override the default entity id generation and any existing :kb/id values.
(table->kb table)
(table->kb idfn table)Converts a Table into a KB, applying unique :kb/id to maps without a mapped identity value.
See map->relation for more information about how the entities in the table are converted to relations.
An idfn is a function of map -> id and if provided is used to override the default entity id generation and any existing :kb/id values.
A minimal implementation of Datalog.
(entity kb id)Given a KB and an id within that KB, returns a map containing all of the attr->val mappings for that logical 'entity'.
(q query kb)
(q query kb rules)Queries a knowledge base or a set of relations given a vector form of a query and an optional set of rules.
A query takes the form:
[:find find-spec :where clauses]
A find-spec can be any number of lvars like:
[:find ?e ?v :where ...]
or a tuple containing a mix of lvars and grounds which is used to build output tuples from the query results:
[:find [?e :an/attribute ?v] :where ...]
The :where clauses are any number of tuples containing a mix of lvars and grounds:
[:find ... :where [?e :an/attribute ?v] [?e :another/attr 42]]
:where clauses may also contain filters defined as calls to predicates used to constrain the values that may bind to lvars:
[:find ... :where [?e :an/attribute ?v] (= ?v 42)]
The possible filter predicates are: =, not=, <, >, <=, >=
rules are a vector of lists where each list defines a rule with a single head tuple followed by any number of rule clauses:
([?p :relationship/parent ?c] [?p :relationship/father ?c])
The rule above defines a syntheic relation called
:relationship/parent defined in terms of another relation
relationship/father. Rules describe synthetic relations derived
from real relations in the data or other synthetic relations
derived from previous rule applications.
(query->map query)Accepts the vector form of a Datalog query and outputs a map of the component sections as keyword->seq mappings.
I came across the Soundex algorithm when researching the retro KAMAS outlining application. Soundex is a phonetic algorithm for indexing words by sound.
(encode word & {:keys [numeric?], :as opts})Soundex is an algorithm for creating indices for words based on their English pronunciation. Homophones are encoded such that words can be matched despite minor differences in spelling. Example, the words "Ashcraft" and "Ashcroft" are both encoded as the same soundex code "A261".
This function accepts the following keyword arguments:
:numeric? -> true numerically encodes the entire word rather than using the default soundex letter prefix.
Provides internal unification functions. DO NOT USE THIS NS. There is no guarantee that it will remain stable or at all.
Common learning-related functions and protocols.
(-generalize lhs rhs)(-init basis)
(-init basis arity)(-specialize lhs neg rhs)Version spaces are a binary classification, empirical learning algorithm.
The approach, as described in 'Version spaces: a candidate elimination approach
to rule learning' by Tom Mitchel (1977) takes training examples (currently
Tuples of a like-arity) and manages a 'version space'. A version space is a
map containing two 'boundaries' :S and :G. The :G boundary contains 'hypotheses'
corresponding to the most general versions of the training data that are consistent
and :S is the most specific versions. When a version space is presented with a new
example it runs a 'candidate elimination' algorithm to modify the boundaries :S
and :G accordingly. Examples can be marked as 'positive' examples, meaning
that they are preferred instances. Anything not marked as 'positive' are taken as
negative examples. Once trained, a version space can classify new examples as
::positive or ::negative. If new examples are not covered by the existing hypotheses
in either boundary then they are classified as ::ambiguous instead.
(applicable? vs example)
(applicable? vs example positive?)Returns true if at least one hypothesis in the version space vs is consistent
with the example and false otherwise.
(arity-vec n)Returns a vector template for arity n.
(best-fit vs example)Returns the best-fit hypothesis coverage analysis (see explain) for a given
version space vs and compatible example. The metadata of the best fit return will
have a mapping of ::fit-from -> :S or :G pertaining to which boundary set the
fit came from.
(classify vs example)Attempts to classify an example using the given version space vs.
Returns ::positive, ::negative, or ::ambiguous if the boundaries
G and S are incongruent.
(collapsed? vs)
(collapsed? g s)Returns if a version space vs or boundaries g and s have collapsed.
That is, training data have caused the hypotheses to become inconsistent,
making further classification impossible.
(consistent? vs example)
(consistent? vs example positive?)Returns true if all hypotheses in the version space vs's general and specific
boundaries are consistent with the example features and classification.
(converged? vs)
(converged? g s)Returns if a version space vs or boundaries g and s have
converged. That is, training has caused the boundaries to converge to a single
case.
(covers? hypothesis example)Takes a hypothesis from a version space and returns if the example is
consistent with it.
(explain vs example)Returns a structure explaining how the classifier reaches a conclusion,
given a version space vs and a compatible example.
The map returned contains the mappings:
:explain/classification-> the result of the call toclassify:explain/example-> the example givenexplain/G-> a sequence of hypotheses coverage analysis structures in the G boundaryexplain/S-> a sequence of hypotheses coverage analysis structures in the S boundary
The hypotheses coverage analyses contain the mappings:
:hypothesis-> The hypothesis inspected:covers?-> true or false if the hypothesis covers the example:similarity-> A ratio of hypothesis coverages over its arity:mismatched-features-> a sequence of the features of the hypothesis that do not match the example
A mismatched feature of a hypothesis has the mappings:
:position-> the position of the feature in the hypothesis:constraint-> the value or wildcard at that position
The information provided is sufficient for informing human-in-the-loop learning interactions.
(refine vs example)
(refine vs example positive?)Given a version space vs and an example, returns a new version space
with boundaries adjusted according to the given example's features and
classification. An example is marked as positive by attaching a metadata mapping
:positive? -> boolean or by passing a boolean as the last argument. The
explicit classification argument will always dominate the metadata
classification.
The simplest possible production rules system that uses a set of EAV tuples as its knowledge base.
(apply-production production facts context)(cycle qf kb)Feeds the results of states into a function qf that is responsible for detecting when production firings have stopped and returns an augmented fact set.
(naive-qf states)Takes the last environment in a long sequence of states in the hope that the sequence was long enough that all of the productions fired in creating it.
(select-production selection-strategy {:keys [productions facts]})Builds a sequence of bindings paired with each production and then uses a selection function to execute one of the productions that matched.
(states kb)Will apply the result of one production firing to the fact base and feed the result forward into the next firing.
(step kb)
(step choice-fn kb)Takes a set of productions and facts and returns a new fact base based on the application of single production.
(unifications [clause & more :as clauses] facts context)Walks through all of the clauses in an implied antecedent and matches each against every fact provided. Returns a seq of contexts representing all of the bindings established by the antecedent unifications across all facts provided.
Common search-related functions and protocols.
Functions related to graph-search algorithms.
Function(s) related to heuristic-guided search.
(add-route _ node new-route)Adds a route to a node as a seq of nodes. Implementors of this function
should return an instance of the object implementing this protocol.
(cost-of _ node)Returns the cost to visit node.
(estimate-cost _ node goal)Returns an estimated cost of the route from node to goal.
(neighbors-of _ node)Returns a seq of neighbors of the given node.
(route-of _ node)Given a node, returns the route associated with it.
A* search implementation.
(astar graph start-node goal-node)Implements a lazy A* best-first graph traversal algorithm. Takes a
graph object implementing both of the fogus.rv.search.GraphSearch
and fogus.rv.search.HeuristicSearch protocols and a start-node
and goal-node describing the bounds of the search. Returns of map
with keys :path mapped to a sequence of nodes from start-node to
goal-node and :cost describing the cost of the path. This search
guarantees to return the lowest cost path as long as one exists.
In the event that there is no path to the goal-node the current result
is undefined.
(cart colls)(f-by f key coll)(pairwise-every? pred xs ys)(positions-of pred & xs)(process-bindings bindings)