There was an interesting thread on Ruby Talk recently about Truth Maintenance Systems (TMS). One reason to use a TMS is to validate inferences, given certain truths. We'll focus on that application here.
This week's Ruby Quiz is to build an inference engine that is capable of answering questions based on the provided truths.
Note that our Perl friends have already done this quiz, with their own Perl Quiz of the Week. It was an interesting problem that generated good solutions and discussion. Because of that, I'm going to copy the format used there, originally by Dan Sanderson and Mark Jason Dominus.
You should be able to teach your engine truths with the following inputs:
All PLURAL-NOUN are PLURAL-NOUN.
No PLURAL-NOUN are PLURAL-NOUN.
Some PLURAL-NOUN are PLURAL-NOUN.
Some PLURAL-NOUN are not PLURAL-NOUN.
You should also be able to query your engine with the following questions:
Are all PLURAL-NOUN PLURAL-NOUN?
Are no PLURAL-NOUN PLURAL-NOUN?
Are any PLURAL-NOUN PLURAL-NOUN?
Are any PLURAL-NOUN not PLURAL-NOUN?
Describe PLURAL-NOUN.
Here's a sample run straight out of the Perl Quiz to show how all of this fits together:
> All mammals are hairy animals.
OK.
> All dogs are mammals.
OK.
> All beagles are dogs.
OK.
> Are all beagles hairy animals?
Yes, all beagles are hairy animals.
> All cats are mammals.
OK.
> All cats are hairy animals.
I know.
> Are all cats dogs?
I don't know.
> No cats are dogs.
OK.
> Are all cats dogs?
No, not all cats are dogs.
> Are no cats dogs?
Yes, no cats are dogs.
> All mammals are dogs.
Sorry, that contradicts what I already know.
> Some mammals are brown animals.
OK.
> Are any mammals dogs?
Yes, some mammals are dogs.
> Are any dogs brown animals?
I don't know.
> Some dogs are brown animals.
OK.
> All brown animals are brown things.
OK.
> Are any dogs brown things?
Yes, some dogs are brown things.
> Describe dogs.
All dogs are mammals.
All dogs are hairy animals.
No dogs are cats.
Some dogs are beagles.
Some dogs are brown animals.
Some dogs are brown things.
> Are all goldfish mammals?
I don't know anything about goldfish.
In the discussion of the Perl Quiz, some very interesting examples were posted. Here's my favorite, which we'll call extra credit:
> All dogs are mammals
OK.
> No octopuses are mammals
OK.
> Are any octopuses dogs?
I don't know.
That's not the correct answer. See how your engine answers that question.
Quiz Summary
irb(main):005:0> are any programmers happy programmers?
=> Yes, some programmers are happy programmers.
irb(main):006:0> are all Ruby programmers happy programmers?
=> Yes, all ruby programmers are happy programmers.
irb(main):007:0> are any Python programmers happy programmers?
=> I don't know.
True artificial intelligence doesn't seem that far off after all.
Did you know you could use irb as an interface like that? I didn't! Be sure and glance at Pit Capitain's code to see just how that is done.
Daniel Sheppard sent in a nice object model, translating the rules into a class hierarchy. I recommend browsing through that too.
Here though, I want to look into Paulo Capriotti's code. Paulo decided to model the relationships as a directed graph, where vertices are the groups and edges represent their relationships. To save a little work, Paulo used the graph Ruby library as a starting point. Here's the beginning of the solution:
def opposite_type(type)
type == :provable_true ? :provable_false : :provable_true
end
class Property
attr_reader :name, :type
def initialize(name, type)
@name = name
@type = type
end
def opposite
Property.new(@name, @type == :positive ? :negative : :positive)
end
def Property.create(x)
if x.respond_to?(:opposite)
x
else
Property.new(x, :positive)
end
end
def hash
"#{@name}##{@type}".hash
end
def eql?(other)
@name == other.name and @type == other.type
end
alias == eql?
def to_s
res = @name
if @type == :negative
"not-" + res
else
res
end
end
end
# ...
First we see the definition of a simple helper method to convert between two opposites: Things we can prove to be true and things we can prove are false.
Next, we have a helper class for a Property. I wasn't sure what that meant at first, so I had to dig a little. Obviously, much of this class is just support for hashing the object (hash() and eql?()). We have a class method to create() a Property when needed and an interesting method to give us an opposite() Property. The to_s() method is also interesting. We can see from it that a negated Property gets a leading "not-" when converted to a String.
All of this clicked into place for me when I turned on Paulo's debug mode and watched the code work. Here's an example:
> All dogs are mammals
adding edge dog, not-dog, provable_false
adding edge not-dog, dog, provable_false
adding edge dog, dog, provable_true
adding edge not-dog, not-dog, provable_true
adding edge mammal, not-mammal, provable_false
adding edge not-mammal, mammal, provable_false
adding edge mammal, mammal, provable_true
adding edge not-mammal, not-mammal, provable_true
...
adding edge dog, mammal, provable_true
adding edge not-mammal, not-dog, provable_true
...
adding edge not-mammal, dog, provable_false
adding edge not-dog, mammal, provable_false
...
adding edge mammal, not-dog, provable_false
adding edge dog, not-mammal, provable_false
...
As you can see, a Property is a representation of the groups we are describing to the inference engine. Opposites represent everything not in that Property, or group. So the "dog" Property has an opposite of "not-dog", or non-dog, if it's easier to think of that way.
What's the rest of that stuff about edges and what we can prove though? That's the graph being built, as I mentioned earlier. Let's examine that code now:
class Knowledge < DirectedHashGraph
attr_reader :contradiction
def initialize
@contradiction = false
super
end
# Add a property and some tautologies.
# Here we assume that the property and
# its opposite are not void.
def add_property(x)
x = Property.create(x)
safe_add_edge(x, x.opposite, :provable_false)
safe_add_edge(x.opposite, x, :provable_false)
safe_add_edge(x, x, :provable_true)
safe_add_edge(x.opposite, x.opposite, :provable_true)
x
end
# Add en edge. Never throw.
def safe_add_edge(x, y, type)
catch(:add_edge_throw) do
add_edge(x, y, type)
end
end
# Add an edge. Throw if the edge already exists.
def add_edge(x, y, type)
debug_msg "adding edge #{x}, #{y}, #{type}"
if self[x,y]
unless self[x,y] == type
@contradiction = true
debug_msg " \tcontradiction"
throw :add_edge_throw, :contradiction
else
debug_msg "\ti know"
throw :add_edge_throw, :i_know
end
else
super(x, y, type)
end
end
# Add an edge and its contrapositive.
def add_assertion(*args)
x, y, type = get_stmt(*args)
catch(:add_edge_throw) do
add_edge(x, y, type)
add_edge(y.opposite, x.opposite, type)
:normal
end
end
# Extract statement values.
def get_stmt(*args)
case args.size
when 1
x, y, type = args[0].x, args[0].y, args[0].type
when 3
x, y, type = args[0], args[1], args[2]
else
raise "Invalid argument list in #{caller.first}"
end
return add_property(x), add_property(y), type
end
# Discover all possible deductions
# and add the corresponding edges to the graph.
def deduce
each_vertex do |v1|
each_vertex do |v2|
each_vertex do |v3|
if self[v1,v2] == :provable_true and
self[v2,v3] == :provable_true
add_assertion(v1, v3, :provable_true)
end
if self[v2,v1] == :provable_false and
self[v2,v3] == :provable_true
add_assertion(v3, v1, :provable_false)
end
if self[v1,v2] == :provable_true and
self[v3,v2] == :provable_false
add_assertion(v3, v1, :provable_false)
end
break if @contradiction
end
end
end
end
# Return true if a statement is provable.
# Return false if its negation is provable.
# Return nil if it is undecidable.
def test(*args)
x, y, type = get_stmt(*args)
case self[x,y]
when nil
return nil
when type
return true
else
return false
end
end
end
# ...
This class isn't as complicated as it appears, once you grasp the flow of how it's used. When an assertion is made to the engine, it will first call test() to see if it already knows that information or if it contradicts any other information.
Assuming the test passes, add_assertion() gets called. That method starts by calling get_stmt() to turn its arguments into two properties and a type (:provable_true or :provable_false). Note that the return sequence of get_stmt(), uses add_property() to ensure that the graph already contains basic relationships for that property (all dogs are dogs, for example). These basic relationships are added using safe_add_edge(), which is really just a shell over add_edge() that filters out the symbols that are thrown by the latter. Getting back to add_assertion(), we can see that it too uses add_edge(), but it returns the symbol thrown or its own :normal to indicate if we already knew about the assertion or if it contradicts what we did know. I know that's a lot to take in, but if you just follow the chain of method calls it's pretty basic stuff.
Finally, deduce() is called after an assertion has been added. By walking the edges, deduce() will fill in any details the new assertion uncovers. This is done by checking relationships between three independent complete sets of vertices, so relationships of the form one -> two -> three will be spotted.
You can see that this class is always monitoring for a @contradiction in each of these methods. However, I don't think this ever comes into play, since each assertion is tested before it's added. (Correct me if I'm wrong Paulo!)
On to the user interface:
["Assertion", "Question"].each do |c|
Struct.new(c, :x, :y, :type)
end
class UI
# Parse input and return a statement
def get_statement(line)
case line
# assertions
when /^all (.*)s are (.*)s\.?$/
return Struct::Assertion.new( Property.create($1),
Property.create($2),
:provable_true )
when /^no (.*)s are (.*)s\.?$/
return Struct::Assertion.new( Property.create($1),
Property.create($2).opposite,
:provable_true )
when /^some (.*)s are not (.*)s\.?$/
return Struct::Assertion.new( Property.create($1),
Property.create($2),
:provable_false )
when /^some (.*)s are (.*)s\.?$/
return Struct::Assertion.new( Property.create($1),
Property.create($2).opposite,
:provable_false )
# questions
when /^are all (.*)s (.*)s\?$/
return Struct::Question.new( Property.create($1),
Property.create($2),
:provable_true )
when /^are no (.*)s (.*)s\?$/
return Struct::Question.new( Property.create($1),
Property.create($2).opposite,
:provable_true )
when /^are any (.*)s not (.*)s\?$/
return Struct::Question.new( Property.create($1),
Property.create($2),
:provable_false )
when /^are any (.*)s (.*)s\?$/
return Struct::Question.new( Property.create($1),
Property.create($2).opposite,
:provable_false )
# description
when /^describe (.*)s\.?$/
return Property.create($1)
else
return nil
end
end
# Return a description of the relation
# between x and y.
# Assume that x is positive and that
# x -> y is not undecidable.
def describe_edge(x, y, aff = true)
case @k[x,y]
when :provable_true
case y.type
when :positive
return "All #{x.name}s are #{y.name}s"
when :negative
return "No #{x.name}s are #{y.name}s"
end
when :provable_false
case y.type
when :positive
if aff
return "Some #{x.name}s are not #{y.name}s"
else
return "Not all #{x.name}s are #{y.name}s"
end
when :negative
if aff
return "Some #{x.name}s are #{y.name}s"
else
return "Not all #{x.name}s are not #{y.name}s"
end
end
end
end
# Return a list of sentences which describe
# the relations between x and each other node.
# Assume that x is positive.
def describe_node(x)
res = []
@k.each_vertex do |y|
if y.type == :positive and not x == y
if @k[x,y] == :provable_true
res << describe_edge(x,y)
elsif @k[x,y.opposite] == :provable_true
res << describe_edge(x,y.opposite)
elsif @k[x,y]
res << describe_edge(x,y)
elsif @k[x,y.opposite]
res << describe_edge(x,y.opposite)
end
end
end
res
end
def say(value)
case value
when true
"Yes"
when false
"No"
else
"I don't know"
end
end
def initialize
@k = Knowledge.new
end
def wait_for_input
print '> '
gets
end
def run
while line = wait_for_input
line.chomp!
line.downcase!
stmt = get_statement(line)
if stmt.class == Struct::Assertion
case @k.test(stmt)
when true
puts "I know"
when false
puts "Sorry, that contradicts what I already know"
else
@k.add_assertion(stmt)
@k.deduce
puts "OK"
end
elsif stmt.class == Struct::Question
value = @k.test(stmt)
print say(value)
if value.nil?
print "\n"
else
puts ", #{describe_edge(stmt.x, stmt.y, value).downcase}"
end
elsif stmt.class == Property
describe_node(stmt).each do |sentence|
puts sentence
end
else
puts "I don't understand"
end
end
end
end
def debug_msg(msg)
puts msg if $debug
end
if $0 == __FILE__
ui = UI.new
ui.run
end
Again, this looks like a lot of code, but it's not overly complicated, once you find the flow. Look at the last few lines to get a hint about where to begin. First, initialize() creates a Knowledge object to keep tract of our assertions and answer our questions. From that point on, run() handles the interactive session.
The first thing you need to know is that run() uses a couple of helper methods: say() for output and wait_for_input() for input. It also calls get_statement() to parse input. The return from get statement is either a single Property (the "describe" command), a Struct::Assertion representing an assertion made, or a Struct::Question representing a question asked. You can see those Structs defined just before the UI class starts. They're just two properties and a type.
The other thing to notice about get_statement() is that it does very basic Regexp based parsing. It uses a super clever trick of spotting a trailing "s" to find the two groups in a line like, "Are all Ruby programmers happy programmers?" Of course, this does not work across all legal inputs:
> All oxen are mammals.
I don't understand
> All James's pets are Dana's pets.
OK
> Are all James's pets Dana's pets?
I don't know
To see another approach, examine Pit Capitain's parsing, especially the IE.split() method.
Getting back to run() in Paulo's UI class, you'll see that the rest of the method just handles the three different returns from get_statement(). Assertions are handled as I explained earlier. Questions rely on describe_edge() for answers and the "describe" command triggers a call to describe_node(). That's the entire UI.
I promise to end this long summary very soon now, but I wanted to mention just one more detail. Paulo uses a helper method all through the code that's defined near the end. Here's another look at it:
puts msg if $debug
end
The goal here is obvious, print a lot of extra information if I set this global variable to true. This is a trick that we all use sometimes in testing. I just wanted to suggest one minor change to enhance this trick: Switch $debug to $DEBUG. Then you can trigger the messages with a command-line switch like so:
$ ruby -e 'p $DEBUG'
false
$ ruby -d -e 'p $DEBUG'
true
Slide that one into your bag of tricks, because it comes in handy.
My thanks to all three submitters for some really great code to poke around in and play with.
Tomorrow, we have a simple but handy hack to explore. It's an easy quiz so I want to see all you beginners out there playing along!
