 # 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
puts "Now with 4 discs..."
query hanoi
```

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
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
```

### 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 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.