Rubyで作るProlog処理系

複数のクラスから構成されるRubyプログラムの実例

プログラミング言語Prologの基本的な動作は、200行ほどのRubyプログラムで実現できます。ここでは筆者がRubyで作成したProlog処理系を解説します。本稿は、Rubyで記号処理を実現したい、スクリプトにルールベースの推論エンジンを内蔵させたい、単純に数個のクラスから構成されるまとまったRubyプログラムをみたいなど、Rubyの実例としても有用です。

Ruby上のPrologで書いたハノイの塔とその実行例

はじめに

　1970年代にヨーロッパを主な舞台として生まれ育ったプログラミング言語Prolog（programming in logic）は、事実とルールから一種の自動推論を行う点に特徴があります。その基本的な動作は200行ほどのRubyプログラムで実現できます。ここでは、筆者がRubyで作成したProlog処理系を解説します。

　Prologによる簡単なプログラム例を下記に示します。

list1

human(socrates).
human(plato).
mortal(X) :- human(X).

　これは「ソクラテスは人間（human）である」「プラトンは人間である」という事実と、「人間ならばいつか死ぬ（mortal）」というルールを書いたものです。mortal(X) :- human(X)は、変数Xが実際には何であったとしても、もしもhuman(X)が成り立つならば（つまりXが人間ならば）、mortal(X)が成り立つ（つまり、Xはいつか死ぬ）という意味です。

　簡略化のため、本処理系ではRubyの構文要素を流用してPrologプログラムを表現します。関数predの戻り値オブジェクトでhumanのような述語（predicate）を、シンボル:Xで変数Xを、そして文字列でsocratesなどを表現します。事実やルールの記述には、メソッドsi（ラテン語の「もしも」）を使います。上記のPrologプログラムは下記のようなRubyスクリプトで表現されます。

list2

require 'tiny_prolog'

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

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

　Prologプログラムの実行とは、与えられた事実とルールについての質問に答えることです。質問のために本処理系ではイテレータresolveを使います。resolveは質問の答えとなる変数値の集合体（つまり環境）をブロックに渡します。答えるべき質問のことをPrologではゴール（goal）と呼びます。

list3

resolve mortal[:X] do |env|
    printf "%s is mortal.＼n", env[:X]
end

　list3ではゴールとしてmortal[:X]を与えています。その意味は「mortalであるような:Xとは？」です。Prologがゴールを求めて動き出します。下記の結果が得られます。

実行結果

socrates is mortal.
plato is mortal.

対象読者

　本稿は、Rubyで記号処理を実現したい、Rubyスクリプトにルールベースの推論エンジンを内蔵させたい、あるいは単純に、数個のクラスから構成されるある程度まとまった長さのRubyプログラムの実例を見てみたい、といった方に対する手頃なお手本として役立つと思います。

必要な環境

　本処理系は少なくともLinux、Mac、Windows（Cygwin）上のRuby1.6.7／1.8.2／1.8.4、およびJava上のJRuby0.9.0で動作しています。特別なライブラリなどは使っていませんので、現行のどのRubyでも動くはずです。

Rubyで構成するProlog構文

　前節の説明でまず疑問に思われたことは、おそらく、具体的にどうRubyでProlog構文を表現しているのか？ ということでしょう。

　Prolog変数は、Rubyのシンボルをそのまま使いますから特にクラスなどは設けません。

　Prolog述語には、クラスPredのインスタンスを使います。各インスタンスには名前nameと定義defsをもたせます。defsの実体はPrologプログラムの事実とルールを格納する配列です。少ない打鍵数で述語を構築できるようにpredという関数を設けます。

list4

class Pred
    attr_reader :defs
    def initialize(name)
        @name = name
        @defs = []
    end
    def inspect
        return @name
    end
    def [](*args)
        return Goal.new(self, args)
    end
end

def pred(x) return Pred.new(x) end

　Prolog述語に引数を与えたものがゴールになります。素直に考えると、クラスPredに対する関数適用演算子を再定義してゴールを表現すべきところですが、Rubyにはそれができませんから、配列要素の参照の再定義def [](*args)でGoalインスタンスを作ります。

list5

class Goal
    attr_reader :pred, :args
    def initialize(pred, args)
        @pred, @args = pred, args
    end
    def si(*rhs)           # ラテン語の「もしも」
        @pred.defs << [self, list(*rhs)]
    end
    def calls(&callback)
        @pred.defs << [self, callback]
    end
    def inspect
        return @pred.inspect + @args.inspect
    end
end

　Goalクラスの主要なメソッドは、事実やルールを定義するsiです。例えばmortal[:X].si(human[:X])は、述語mortalの属性defsに、.siの左辺（self）と右辺（rhs）のペアを追加します。ただし、このとき右辺に関数listを適用します。

　メソッドcallsは、Ruby関数を呼び出す述語の定義に使います。これによりPrologで数値演算や入出力を実現できます。

Lispのようなリスト

　関数listは、引数からLispのリストのような入れ子の配列を作ります（listという名前もLispの関数名から採っています）。

list6

list(g1, g2, g3) ⇒ [g1, [g2, [g3, nil]]]

　このような配列を作る理由は、配列の先頭g1と、残りの[g2, [g3, nil]]とに分けて再帰処理を行うためです。

　ただし、このままでは値を画面表示したとき読みづらいので、inspectメソッドで文字列化したとき､Lispのリストのように(g1 g2 g3)と表現されるようArrayの派生クラスConsを定義します（ここでcons, car, cdrという奇妙な名前もLispに由来しています。それぞれコンス、カー、クダーと読みます）。

list7

class Cons < Array
    def initialize(car, cdr)
        super(2)
        self[0], self[1] = car, cdr
    end
    def inspect
        repr = proc {|x|
            car, cdr = x[0], x[1]
            if cdr.nil? then [car.inspect]
            elsif Cons === cdr then repr[cdr].unshift(car.inspect)
            else [car.inspect, '.', cdr.inspect]
            end
        }
        return '(' + repr[self].join(' ') + ')'
    end
end
  
def cons(car, cdr) return Cons.new(car, cdr) end
  
def list(*x)
    y = nil
    x.reverse_each {|e| y = cons(e, y)}
    return y
end

　本来のPrologも、基本的なデータ型としてLispのようなリストを備えています。Consクラスは、リストを扱うPrologプログラムを書くときにも利用できます（ただし、Prologのリストは､内部構造はLispと同じですが、文字列化した表現がRubyの配列と似ていて紛らわしいという難点があります。これがConsクラスでLisp流儀の表現方法を採った理由です）。

　例えば、第1引数と第2引数を連結したリストが第3引数に等しい、というProlog述語appendは、下記のように記述できます。このスクリプトの最後の3行では、連結結果が「(1 2 3)」に等しくなる第1引数と第2引数の組み合わせを求めています。

list8

require 'tiny_prolog'

append = pred 'append'

append[nil, :A, :A] .si
append[cons(:A, :X), :Y, cons(:A, :Z)] .si append[:X, :Y, :Z]

resolve append[:A, :B, list(1, 2, 3)] do |env|
    printf "%p and %p＼n", env[:A], env[:B]
end

　実行すると次のような結果が得られます。

実行結果

nil and (1 2 3)
(1) and (2 3)
(1 2) and (3)
(1 2 3) and nil

注

　Ruby 1.6.*の場合、printfの引数の%pを%sに、env[...]をenv[...].inspectにしてください。