function Foil(examples, target) returns a set of Horn clauses
inputs: examples, set of examples
target, a literal for the goal predicate
local variables: clauses, set of clauses, initially empty
while examples contains positive examples do
clause ← New-Clause(examples, target)
remove positive examples covered by clause from examples
add clause to clauses
return clauses
function New-Clause(examples, target) returns a Horn clause
local variables: clause, a clause with target as head and an empty body
l, a literal to be added to the clause
extended_examples, a set of examples with values for new variables
extended_examples ← examples
while extended_examples contains negative examples do
l ← Choose-Literal(New-Literals(clause), extended_examples)
append l to the body of clause
extended_examples ← set of examples created by applying Extend-Example
to each example in extended_examples
return clause
function Extend-Example(example, literal) returns a set of examples
if example satisfies literal
then return the set of examples created by extending example with
each possible constant value for each new variable in literal
else return the empty set
Function ?? Sketch of the Foil algorithm for learning sets of first-order Horn clauses from examples. New-Literals and Choose-Literal are explained in the text.