CodeZine(コードジン)

特集ページ一覧

Rubyで作るProlog処理系

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

  • LINEで送る
  • このエントリーをはてなブックマークに追加
2006/08/14 00:00

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

目次
Ruby上のPrologで書いたハノイの塔とその実行例
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にしてください。

  • LINEで送る
  • このエントリーをはてなブックマークに追加

修正履歴

  • 2011/03/18 15:31 沖ソフトウェアの URL を変更しました。

  • 2006/11/08 09:14 本処理系の拡張・応用例を参考資料に追記しました。

  • 2006/11/06 18:45 課題の説明について追記しました。

著者プロフィール

あなたにオススメ

All contents copyright © 2005-2022 Shoeisha Co., Ltd. All rights reserved. ver.1.5