eigenclass logo
MAIN  Index  Search  Changes  PageRank  Login

Logic programming in Ruby: a tiny prolog interpreter and symbolic computation

Want some logic programming without leaving the comfort of your irb session?

I've taken the interpreter I found in a couple articles in Japanese, added syntactic sugar and some new predicates. It's quite powerful now; you can find below some logical programs, including symbolic differentiation and simplification.

If you want to play along, you're going to need my modified tiny_prolog.rb and a few new predicates defined in tiny_prolog_ext.rb.

Syntax

Logical code looks like this with the tiny Prolog-ish interpreter in Ruby:

require 'tiny_prolog_ext'

# rules
# read as "X and Y are siblings if Z is the parent of both"
sibling[:X,:Y] <<= [ parent[:Z,:X], parent[:Z,:Y], noteq[:X,:Y] ]
parent[:X,:Y] <<= father[:X,:Y]
parent[:X,:Y] <<= mother[:X,:Y]

# facts: rules with "no preconditions"
father["matz", "Ruby"].fact
mother["Trude", "Sally"].fact
father["Tom", "Sally"].fact
father["Tom", "Erica"].fact
father["Mike", "Tom"].fact

query sibling[:X, "Sally"]
# >> 1 sibling["Erica", "Sally"]

I've added some sugar to the original interpreter, so there's no need to predeclare the predicates, and rules/facts can be specified more naturally. So you basically define facts with

predicate[1,:X].fact  # predicate[1,:X] holds for any X
predicate[2, 1].fact  # predicate[2,1] holds

and rules with

predicate[:VAR1, :VAR2] <<= [ other[:VAR1], predicates[:VAR2] ]

meaning that predicate[:VAR1,:VAR2] holds if both other[:VAR1] and predicates[:VAR2] do.

You can omit the square brackets if there's only one predicate on the right hand side:

parent[:X,:Y] <<= father[:X,:Y]

The original interpreter was lacking a way to express things like

 succ(Y,X) :- X is (Y+1).

so I implemented a special predicate that can be used this way:

require 'tiny_prolog_ext'
succ[:X,:Y] <<= is(:Y,:X){|x| x+1}
query succ[1,:X]
# >> 1 succ[1, 2]

I also added

  • eq[:X,:Y] that tries to unify X and Y
  • noteq[:X,:Y] which holds if they differ
  • atomic[:X], notatomic[:X], numeric[:X] that will depend on the type of X
  • write[:X], writenl[:X] to #print and #puts X's value (there's also nl[:X] to * * write '\n' where :X is a dummy var)

Tower of Hanoi

Here's a more substantial logical program. You can see how unification and backtracking more than suffices to solve the Tower of Hanoi game:

require 'tiny_prolog_ext'

hanoi[:N] <<=  move[:N,"left","right","center"]
move[0,:X,:Y,:Z] <<= :CUT   # don't look for further solutions
move[:N,:A,:B,:C] <<= [
  is(:M,:N){|n| n - 1}, # reads as "M IS N - 1"
  move[:M,:A,:C,:B],
  write_info[:A,:B],
  move[:M,:C,:B,:A]
]
write_info[:X,:Y] <<= [
  write["move a disc from the "],
  write[:X], write[" pole to the "],
  write[:Y], writenl[" pole "]
]
query hanoi[2]
puts "Now with 4 discs..."
query hanoi[4]

The expected output is obtained when you run it:

   move a disc from the left pole to the center pole 
   move a disc from the left pole to the right pole 
   move a disc from the center pole to the right pole 
   1 hanoi[2]
   Now with 4 discs...
   move a disc from the left pole to the center pole 
   move a disc from the left pole to the right pole 
   move a disc from the center pole to the right pole 
   move a disc from the left pole to the center pole 
   move a disc from the right pole to the left pole 
   move a disc from the right pole to the center pole 
   move a disc from the left pole to the center pole 
   move a disc from the left pole to the right pole 
   move a disc from the center pole to the right pole 
   move a disc from the center pole to the left pole 
   move a disc from the right pole to the left pole 
   move a disc from the center pole to the right pole 
   move a disc from the left pole to the center pole 
   move a disc from the left pole to the right pole 
   move a disc from the center pole to the right pole 
   1 hanoi[4]

Symbolic differentiation

Alright, Hanoi is easy to solve in just about any language, but the following shows how easy symbolic computation becomes. We encode basic differentiation rules with relations like

 diff[:A, :VAR, :DA]

meaning that DA is the derivative relative to VAR of A.

require 'tiny_prolog_ext'

# dx / dx = 1
diff[:X,:X,1] <<= :CUT 
# dy / dx = 0   if y == atom
diff[:Y,:X,0] <<= [ atomic[:Y],noteq[:Y,:X] ]
# d(a + b) / dx = da/dx + db/dx
diff[plus[:A,:B], :X, plus[:DA,:DB]] <<= [ diff[:A,:X,:DA], diff[:B,:X,:DB] ]
# d(c * u)/dx = c * du/dx   if c == atom
diff[times[:C,:U], :X, times[:C,:DU]] <<= [ atomic[:C], noteq[:C,:X], diff[:U,:X,:DU], :CUT ]
# d(a * b)/dx = a * db/dx + b * da/dx
diff[times[:A,:B],:X, plus[times[:A,:DB],times[:DA,:B]]] <<=
  [ diff[:A,:X,:DA], diff[:B,:X,:DB] ]

diff[uminus[:Y],:X,uminus[:DY]] <<= diff[:Y,:X,:DY]
diff[minus[:U,:V],:X,minus[:DU,:DV]] <<= [ diff[:U,:X,:DU], diff[:V,:X,:DV] ]
diff[div[:U,:V], :X, :W] <<=   diff[times[:U,pow[:V,-1]], :X, :W]
diff[pow[:Y,:C], :X, times[:C,times[:W,pow[:Y,:E]]]] <<= [
  atomic[:C], noteq[:C,:X], is(:E,:C){|c| c - 1}, diff[:Y,:X,:W] ]
diff[ln[:Y], :X, times[:W,pow[:Y, -1]]] <<= diff[:Y,:X,:W]
diff[exp[:U], :X, times[:DU,exp[:U]] ] <<= diff[:U,:X,:DU] 
diff[pow[:V,:W], :X, :Z] <<= diff[exp[times[:W, ln[:V]]], :X, :Z] 

query diff[plus[times["x","x"], times[3,"x"]], "x", :D]
query diff[pow["x", 3], "x", :D]

The program outputs:

1 diff[plus[times["x", "x"], times[3, "x"]], "x", plus[plus[times["x", 1], times[1, "x"]], times[3, 1]]]
1 diff[pow["x", 3], "x", times[3, times[1, pow["x", 2]]]]
2 diff[pow["x", 3], "x", times[times[3, times[1, pow["x", -1]]], exp[times[3, ln["x"]]]]]

This is fine, but the expressions can be simplified considerably. Here's an initial attempt by defining these two predicates:

length[:X, :N]
s[:X,:Y]

Keep in mind that we're working with relations (which is but another way to consider functions), so instead of something like length(:X), we write length[:X,:N] meaning "the length of the X expression is N". s[:X,:Y] means that Y is a (simpler) expression that equals X.

I've used some Ruby-level code to avoid having the express all the rules relative to expression lengths manually.

require 'differentiate'

s[plus[:X,0], :X].fact
s[plus[0,:X], :X].fact
s[plus[:X,:Y], :E] <<= [ numeric[:X], numeric[:Y], is(:E,:X,:Y){|x,y| x+y} ]
s[times[:X,0], 0].fact
s[times[0,:X], 0].fact
s[times[1,:X], :X].fact
s[times[:X,1], :X].fact
s[times[:X,:Y], :E] <<= [ numeric[:X], numeric[:Y], is(:E,:X,:Y){|x,y| x*y} ]
s[times[times[:X,:Y], :W], times[:X,:Z]] <<= [ numeric[:Y], numeric[:W], is(:Z,:Y,:W){|y,w| y*w} ]
s[times[:X,times[:Y,:W]], times[:Z,:W]] <<= [ numeric[:X], numeric[:Y], is(:Z,:X,:Y){|x,y| x*y} ]
#s[times[:X,:Y], times[:Y,:X]].fact
s[times[:X,:Y], times[:U,:Y]] <<= s[:X,:U]
s[times[:X,:Y], times[:X,:U]] <<= s[:Y,:U]
s[times[:X,:Y], times[:U,:V]] <<= [s[:X,:U], s[:Y,:V]]
s[plus[:X,:Y], plus[:U,:Y]] <<= s[:X,:U]
s[plus[:X,:Y], plus[:X,:U]] <<= s[:Y,:U]
s[plus[:X,:Y], plus[:U,:V]] <<= [s[:X,:U], s[:Y,:V]]
s[times[:X,pow[:X,-1]], 1].fact

sdiff[:U,:X,:SDU,:N] <<= [ diff[:U,:X,:DU], s[:DU,:SDU], length[:SDU,:N] ]
length[:X,1] <<=  atomic[:X]
%w[uminus ln exp].each{|m| length[eval(m)[:X], :N] <<= [ length[:X,:M], is(:N,:M){|m| m+1} ] }
%w[plus minus times div pow].each do |m|
  length[eval(m)[:X,:Y], :P] <<= [ length[:X,:N], length[:Y,:M], is(:P,:N,:M){|n,m| 1+n+m} ]
end

def diff_and_simplify(fx)
  solution, len = nil, 1000
  resolve sdiff[fx, "x", :D, :N] do |env|
    if env[:N] < len
      solution = env[:D]
      len = env[:N]
    end
  end
  puts "Differentiating and simplifying #{fx.inspect}"
  puts "Solution (length: #{len}): #{solution.inspect}" if solution
end

diff_and_simplify plus[times["x","x"], times[3,"x"]]

We now get:

   Differentiating and simplifying plus[times["x", "x"], times[3, "x"]]
   Solution (length: 5): plus[plus["x", "x"], 3]

Not bad. The simplification rules aren't complete but they worked fine in that example (I'm leaving that as an exercise to the reader).


hanoi - somekool (2006-11-14 (Tue) 05:25:57)

is it normal

query hanoi[10] crash?

SystemStackError: stack level too deep

       from ./tiny_prolog.rb:85:in `get'
       from ./tiny_prolog.rb:96:in `dereference'
       from ./tiny_prolog.rb:103:in `[]'
       from ./tiny_prolog.rb:218:in `[]'
       from ./tiny_prolog_ext.rb:26
       from ./tiny_prolog.rb:177:in `[]'
       from ./tiny_prolog.rb:177:in `_resolve_body'
       from ./tiny_prolog.rb:172:in `each'
       from ./tiny_prolog.rb:172:in `_resolve_body'
       from ./tiny_prolog.rb:183:in `_resolve_body'
       from ./tiny_prolog.rb:172:in `each'
       from ./tiny_prolog.rb:172:in `_resolve_body'
       from ./tiny_prolog.rb:184:in `_resolve_body'
       from ./tiny_prolog.rb:179:in `_resolve_body'
       from ./tiny_prolog.rb:185:in `_resolve_body'
       from ./tiny_prolog.rb:161:in `_resolve_body'

... 2760 levels...

       from ./tiny_prolog.rb:183:in `_resolve_body'
       from ./tiny_prolog.rb:172:in `each'
       from ./tiny_prolog.rb:172:in `_resolve_body'
       from ./tiny_prolog.rb:178:in `_resolve_body'
       from ./tiny_prolog.rb:172:in `each'
       from ./tiny_prolog.rb:172:in `_resolve_body'
       from ./tiny_prolog.rb:183:in `_resolve_body'
       from ./tiny_prolog.rb:172:in `each'
       from ./tiny_prolog.rb:172:in `_resolve_body'
       from ./tiny_prolog.rb:183:in `_resolve_body'
       from ./tiny_prolog.rb:172:in `each'
       from ./tiny_prolog.rb:172:in `_resolve_body'
       from ./tiny_prolog.rb:154:in `resolve'
       from ./tiny_prolog.rb:232:in `query'
       from (irb):35

mfp 2006-11-16 (Thr) 04:02:34

Ruby's stack can't go very deep, so it doesn't come as a surprise. tiny_prolog.rb seems to be using way too many stack frames though :-|


How to Do this in Ruby/Prolog - Vijay (2006-11-02 (Thr) 22:29:26)

Great work! How to express lists?

For example: How to do a member predicate?

member([X|_],X):-!. member([_|L],X):-member(L,X).

mfp 2006-11-05 (Sun) 02:23:13

There's #cons and #list:

$ cat member.rb 
require 'tiny_prolog_ext'

member[cons(:X,:Y), :X] <<= :CUT
member[cons(:Z,:L), :X] <<= member[:L,:X]

list = list(*(0..10))
query member[list, 1]
query member[list, 11]

$ ruby member.rb 
1 member[(0 1 2 3 4 5 6 7 8 9 10), 1]
0 member[(0 1 2 3 4 5 6 7 8 9 10), 11]

Cool! - Gregory Brown (2006-10-29 (Sun) 21:41:13)

Man, I swear I was looking at the prolog wikipedia entry the other day saying "I should write a Ruby interpreter for prolog".

Now you've gone and taken the wind out of my sails, Mauricio!

Very cool though :)

mfp 2006-10-30 (Mon) 16:39:59

I didn't write the interpreter, only some extensions (a few important predicates) and the additional syntax sugar --- blame the original author (鈴) ;)


In straight Ruby - Greg Buchholz (2006-10-28 (Sat) 17:32:07)

Here's a slightly different way to write a symbolic differentiator in Ruby, which uses overloading and Ruby symbols. Here's an example of the usage...

# Create a regular Ruby function...
#  f(x) = x^2 + 12x - 7
f = lambda {|x| x*x + 12*x - 7}

# Print the symbolic form
puts f.call(:x)
# Print the numeric value at f(10)
puts f.call(10)
# Symbolically differentiate 
puts f.call(:x).sym_diff(:x)
# Value of f'(10)
puts f.call(:x).sym_diff(:x).to_proc.call(10)

mfp 2006-10-30 (Mon) 08:09:45

#  f(x) = x^2 + 12x - 7
f = lambda {|x| x*x + 12*x - 7}

nice :)


Logic programming - EdBorasky (2006-10-28 (Sat) 13:26:06)

Have you seen the Scheme equivalent, Kanren/Mini-Kanren?

http://kanren.sourceforge.net/

mfp 2006-10-28 (Sat) 15:15:18

wow, Kanren is way bigger (and more "serious") than tiny_prolog.rb The syntax differs from prolog's even more, though :)

(miniKANREN is about the same size + easy to read, thank you for the pointer!).


original articles? - TomP (2006-10-28 (Sat) 12:36:40)

This is very cool. Thanks!

Do you read Japanese? It would be interesting to get a translation of the original articles.

mfp 2006-10-28 (Sat) 13:44:03

Do you read Japanese? It would be interesting to get a translation of the original articles.

I can read it but it takes some time (rikaichan makes it easier). As for translating it, it'd be a good exercise :) but we'd have to ask for permission first. To be honest, I'm thinking right now that maybe I went too far by redistributing tiny_prolog.rb (?).

TomP 2006-10-28 (Sat) 14:24:41

Can't hurt to contact the author now and see what he thinks. I'd be surprised if he wasn't supportive. It's not you you're pretending his work is yours, or distributing something he hasn't already made freely available. You're really just making his work known to a wider audience.

On a different note, I'm going to have to study this a bit first, but I wonder whther there might not be a more Rubyish syntax for describing predicates?

mfp 2006-10-28 (Sat) 15:07:38

I wonder whther there might not be a more Rubyish syntax for describing predicates?

Sure, you can discard my syntactic sugar altogether (it's just eye candy anyway :) and use the original syntax:

require 'tiny_prolog'

human = pred 'human'; mortal = pred 'mortal'

human['socrates'] .si
human['plato'] .si
mortal[:X] .si human[:X]

drmabuse 2006-11-01 (Wed) 02:02:40

Cool stuff!

I'm not too familiar with logical programming, it's not clear to me, what is the meaning of 'si'. Why did you call the method like that, and not, say, 'no'?

mfp 2006-11-01 (Wed) 03:34:07

Quoting from the original author (鈴 - Ling):

ラテン語の sī 「スィー」,意味は「もしも」。 本当は英語の if を使いたかったけれど予約語だから。

It's the latin "si", meaning "if". Actually, I wanted to use "if", but it's a reserved word.

.si feels quite natural if you know a Romance language. (Evenmoreso in Spanish than in e.g. French, since we can disambiguate it orthographically: sí (yes) != si (if)).

trans 2006-11-04 (Sat) 18:53:13

I did something similiar about a year or two ago. It doesn't use backtracking, but rather an inefficient brute force form of deduction process. But my goal was less about that logic engine behind the scenes and more about making a cool interface. Here's what I managed:

 
 require 'test/unit'
 
 module TestLogic
 
   include Predicate::LogicInclusion
   extend Predicate::LogicExtension
 
   def man(x) end
 
   def woman(x) end
 
   def tool(x) end
 
   def mortal(x)
     woman(x) | man(x)
   end
 
   def can_use(x, y)
     ( man(x) | woman(x) ) & tool(y)
   end
 
 end
 
 class TC_Predicate < Test::Unit::TestCase
 
   include TestLogic
 
   def setup
     man('socrates')
     woman('dido')
     tool('hammer')
     can_use('me', 'ball')
   end
 
   def test_facts
     assert(man?('socrates'), "man?('socrates')")
     assert(woman?('dido'), "woman?('dido')")
     assert(tool?('hammer'), "tool?('hammer')")
     assert(can_use?('me', 'ball'), "can_use?('me', 'ball')")
   end
 
   def test_deductions
     assert(mortal?('socrates'))
     assert(mortal?('dido'))
     assert(can_use?('socrates','hammer'))
     assert(can_use?('dido','hammer'))
   end
 
   def test_queries
     assert(man(/.*/).include?(['socrates']))
     assert(woman(/.*/).include?(['dido']))
     assert(mortal(/.*/).include?(['socrates']))
     assert(mortal(/.*/).include?(['dido']))
     assert(can_use(/.*/,/.*/).include?(['socrates', 'hammer']))
     assert(can_use(/.*/,/.*/).include?(['dido', 'hammer']))
     assert(can_use(/.*/,/.*/).include?(['me', 'ball']))
   end
 
 end

mfp 2006-11-05 (Sun) 02:27:10

The syntax looks really nice. Have a pointer to Predicate::LogicInclusion/Predicate::LogicExtension's sources? ;)

rubynoob 2006-12-03 (Sun) 17:36:15

Doesn't the Dependency Injection code given here: http://onestepback.org/index.cgi/Tech/Ruby/DependencyInjectionInRuby.rdoc remind you of a prolog unification process ? I suspect this could be used to implement the unification more efficiently and perhaps with a reduced stack usage. As for backtracking, continuations seems like a good choice. Any thoughts on this guys ?

mm 2006-12-06 (Wed) 18:15:58

fyi, The Ruby-licensed sources for trans' Predicate::LogicInclusion/Predicate::LogicExtension are in the facets library: http://facets.rubyforge.org/repo/lib/facets/more/predicate.rb

- Gordon (2007-02-24 (Sat) 11:01:18)

So, I'm trying to do this using tiny_prolog, but I'm stuck. Am I making a stupid mistake?

 require 'tiny_prolog_ext'
 
 def _
   AnonymousVariable.new.sym
 end
 
 class AnonymousVariable
   attr_reader :sym
   def initialize
     @sym = "S#{object_id}".intern
   end
 end
 
 member[cons(:Z,_), :Z] <<= :CUT
 member[cons(_,:L), :Z] <<= member[:L,:Z]
 
 next_to[:X, :Y, :List] <<= iright[:X, :Y, :List]
 next_to[:X, :Y, :List] <<= iright[:Y, :X, :List]
 
 iright[:L, :R, cons(:L, cons(:R , _ ))]
 iright[:L, :R, cons(_ , :Rest)] <<= iright[:L, :R, :Rest]
 einstein[:Houses, :Fish_Owner] <<= [ 
     eq[:Houses, list(list('house', 'norwegian', _, _, _, _), _, list('house', _, _, _, 'milk', _), _, _)],
     member[list('house', 'brit', _, _, _, 'red'), :Houses],
     member[list('house', 'swede', 'dog', _, _, _), :Houses],
     member[list('house', 'dane', _, _, 'tea', _), :Houses],
     iright[list('house', _, _, _, _, 'green'), list('house', _, _, _, _, 'white'), :Houses],
     member[list('house', _, _, _, 'coffee', 'green'), :Houses],
     member[list('house', _, 'bird', 'pallmall', _, _), :Houses],
     member[list('house', _, _, 'dunhill', _, 'yellow'), :Houses],
     next_to[list('house', _, _, 'dunhill', _, _), list('house', _, 'horse', _, _, _), :Houses],
     member[list('house', _, _, _, 'milk', _), :Houses],
     next_to[list('house', _, _, 'marlboro', _, _), list('house', _, 'cat', _, _, _), :Houses],
     next_to[list('house', _, _, 'marlboro', _, _), list('house', _, _, _, 'water', _), :Houses],
     member[list('house', _, _, 'winfield', 'beer', _), :Houses],
     member[list('house', 'german', _, 'rothmans', _, _), :Houses],
     next_to[list('house', 'norwegian', _, _, _, _), list('house', _, _, _, _, 'blue'), :Houses],
     member[list('house', :Fish_Owner, 'fish', _, _, _), :Houses]
   ]
 
 query einstein[:Houses, :Fish_Owner]

mfp 2007-02-24 (Sat) 12:55:39

Nice, it was just a few changes away from running.

There was a problem with the member predicates and a missing .fact for the first iright statement. I've put the working version in More logical programming in Ruby: solving Einstein's riddle (Zebra puzzle) to give it some more visibility.

Thank you!


Trans Predicate - Trans (2007-03-03 (Sat) 20:32:14)

Hi--

I move the predicate code from Facets to ToadCode b/c it was too expiremental in nature. You can now browse it here instead:

 http://toad.rubyforge.org/src/predicate/

T.