Ruby で作る Prolog 処理系 (補講)

2006.9.9 - 2006.10.10 (鈴)


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

1. はじめに

ここで述べる Ruby による Prolog 処理系 (以下，本処理系) では， 簡単のため，Ruby の構文要素を流用して Prolog プログラムを表現する。 たとえば， 

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

を下記のような Ruby スクリプトで表現する。 ここで require している tiny_prolog.rb が本処理系の実体である。 

require 'tiny_prolog'

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

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

tiny_prolog.rb が定義する関数 pred は， 新しい 述語 (predicate) オブジェクトを作る。 メソッド si は 節 (clause) を構成し，述語オブジェクトに登録する。

Prolog プログラムの実行とは， プログラムとして与えられた事実とルールについての質問， すなわち Prolog における ゴール (goal) に答えることである。 そのために本処理系ではイテレータ resolve を使う。 resolve はゴールを満たす変数値の集合体，つまり環境を算出してブロックに渡す。 

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

この例では下記の結果が得られる。 

$ ruby mortal.rb
socrates is mortal.
plato is mortal.
$

本処理系は Linux, Mac, Windows (Cygwin) 上の Ruby 1.6.7, 1.8.2, 1.8.5 および Java 上の JRuby 0.9.0 で動作を確認した。 特別なライブラリ等を使っていないため， おそらく現行のどの妥当な Ruby 実装でも動くと考えられる。

2. Ruby で構成する Prolog 構文

本処理系では Prolog 変数は Ruby のシンボルをそのまま利用する。 Prolog 述語はクラス Pred のインスタンスとして作る。

Pred の各インスタンスは名前 name と定義 defs を持つ。 defs の実体は Prolog 節を格納する配列である。 述語に対する配列要素参照演算を，ゴールを構築する関数として定義する。 少ない打鍵数で述語を構築できるように pred という関数を設ける。 

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

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 である。 si は述語の defs に Prolog 節として左辺 (self) と右辺 (rhs) のペアを追加する。 メソッド calls は Ruby 関数を コールバックする節を定義する。

*1Ruby の inspect と to_s の区別は， Python の repr() と str() に似ている。 しかし， repr() が (望ましくは eval() で再び同じ値が得られる) 文字列表現 (representation)， str() が (読みやすい) 文字列 (string)， という明確な意味付けを持つのに対して， デバッグ用の文字列表現 inspect に対する to_s の (一般用の) 文字列表現という立場はかなり微妙である。

配列に対する ruby の to_s の仕様は，典型的には， ファイルの各行からなる配列を出力するときに .join の 5 文字を省くことで one-liner をわずかに短くするために有益である。 しかし，それ以外での有用性は必ずしも明らかではない。 ある意味， 汎用言語であることを犠牲にして one-liner に対する便宜を優先したために， 明確な意味付けを to_s に持たせることに失敗したともいえる。 nil の to_s の結果が空文字列である (したがって，たとえば [nil, nil, nil].to_s の結果も空文字列である) にもかかわらず，nil を print すると "nil" が得られる， という Ruby の不規則性も， to_s の意味付けの微妙さ (ないしは潜在的な不安定さ) を表している， といってよいだろう。

2.1 Lisp のようなリスト

メソッド si で使われている関数 list は， 引数から Lisp のリストのような入れ子の配列を作る。 list という名称も Lisp の同機能の関数に由来する。 

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

ただし，これでは読みにくいため， inspect の結果が Lisp のリストのように "(g1 g2 g3)" と表現される Array 派生クラス Cons を定義する。 (ここで cons, car, cdr という奇妙な名前も Lisp に由来する。 それぞれコンス，カー，クダーと読む)。 

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

Cons クラスとその関数を利用すると，Prolog の例題として有名な， 第１引数と第２引数を連結したリストが第３引数に等しい， という述語 append を下記のように書ける。 このスクリプトの最後の３行では， 連結結果がリスト (1 2 3 4) に等しくなるような第１引数と第２引数の組み合わせを 求めている。 

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, 4)] do |env|
  printf "%p and %p\n", env[:A], env[:B]
end

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

$ ruby append.rb
nil and (1 2 3 4)
(1) and (2 3 4)
(1 2) and (3 4)
(1 2 3) and (4)
(1 2 3 4) and nil
$

Ruby 1.6.* の場合，printf の引数の %p を %s に，env[...] を env[...].inspect に変更されたい。

3. 環境クラス Env

ここまでの記述では，イテレータ resolve がブロックに与えるパラメタとして 環境 (environment) を見てきた。 環境は単一化 (unification) 操作とともに Prolog の内部動作の基礎を構成する。

本処理系は環境をクラス Env のインスタンスで表す。 インスタンスはハッシュ表 (Prolog 変数をキー， その変数値と環境のペアを値とする) を保持する。 dereference メソッドは， 具体的な値または未セットの変数が得られるまで間接参照を繰り返す。 dereference メソッドの本体に含まれる式 Symbol === t は， t が Prolog 変数であるか否かを判定する。 

class Env
  def initialize
    @table = {}
  end
  def put(x, pair)
    @table[x] = pair
  end
  def get(x)
    return @table[x]
  end
  def delete(x)
    @table.delete(x) {|k| raise "#{k} not found in #{inspect}"}
  end
  def clear
    @table.clear
  end
  def dereference(t)
    env = self
    while Symbol === t
      p = env.get(t)
      break if p.nil?
      t, env = p
    end
    return [t, env]
  end
  def [](t)
    t, env = dereference(t)
    return case t
           when Goal then Goal.new(t.pred, env[t.args])
           when Cons then cons(env[t[0]], env[t[1]])
           when Array then t.collect {|e| env[e]}
           else t
           end
  end
end

これまで環境 env から Prolog 変数 :X の値を取り出すとき， 配列要素参照演算を使って env[:X] と書いてきた。 しかし，上記の def [](t) の記述から分かるように， この演算は入れ子になったデータ構造のなかに現れる変数を 再帰的に展開した値を返す関数であり， 引数には一般の Prolog 項 (term) が可能である。 したがって， 前節の append 述語スクリプトの最後の３行を 次のように書いてもよい。 

t = append[:A, :B, list(1, 2, 3, 4)]
resolve (t) {|env|
  p env[t]
}

実行例を示す。 

$ ruby append2.rb
append[nil, (1 2 3 4), (1 2 3 4)]
append[(1), (2 3 4), (1 2 3 4)]
append[(1 2), (3 4), (1 2 3 4)]
append[(1 2 3), (4), (1 2 3 4)]
append[(1 2 3 4), nil, (1 2 3 4)]
$

$ cat append3.rb
require 'tiny_prolog'

APPEND = pred 'append'

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

T =  APPEND[:A, :B, list(1, 2, 3, 4)]
resolve(T) {|env|
  p env[T]
}
$ irb -r append3.rb
append[nil, (1 2 3 4), (1 2 3 4)]
append[(1), (2 3 4), (1 2 3 4)]
append[(1 2), (3 4), (1 2 3 4)]
append[(1 2 3), (4), (1 2 3 4)]
append[(1 2 3 4), nil, (1 2 3 4)]
irb(main):001:0> t = APPEND[list(1, 2), list(3, 4), :X]
=> append[(1 2), (3 4), :X]
irb(main):002:0> resolve (t) {|env| p env[t]}
append[(1 2), (3 4), (1 2 3 4)]
=> [[append[nil, :A, :A], nil], [append[(:A . :X), :Y, (:A . :Z)], (append[:X, :Y, :Z])]]
irb(main):003:0> 

def query(*goals)
  count = 0
  printout = proc {|x|
    x = x[0] if x.length == 1
    printf "%d %s\n", count, x.inspect
  }
  resolve(*goals) {|env|
    count += 1
    printout[env[goals]]
  }
  printout[goals] if count == 0
end

irb(main):004:0> query APPEND[:X, :Y, list("foo", "bar", "baz")]
1 append[nil, ("foo" "bar" "baz"), ("foo" "bar" "baz")]
2 append[("foo"), ("bar" "baz"), ("foo" "bar" "baz")]
3 append[("foo" "bar"), ("baz"), ("foo" "bar" "baz")]
4 append[("foo" "bar" "baz"), nil, ("foo" "bar" "baz")]
=> nil
irb(main):005:0>

4. 単一化関数 _unify

処理系内部で単一化操作を実現しているのは下記の関数 _unify である。 環境 x_env, y_env のもとで項 x, y を単一化する。 単一化に成功したとき true を返す。 単一化の対象が未セットの変数ならば，他方の変数値にセットする。 

def _unify(x, x_env, y, y_env, trail, tmp_env)
  loop {
    if Symbol === x
      xp = x_env.get(x)
      if xp.nil?
        y, y_env = y_env.dereference(y)
        unless x == y and x_env == y_env
          x_env.put(x, [y, y_env])
          trail << [x, x_env] unless x_env == tmp_env
        end
        return true
      else
        x, x_env = xp
        x, x_env = x_env.dereference(x)
      end
    elsif Symbol === y
      x, x_env, y, y_env = y, y_env, x, x_env
    else
      break
    end
  }
  if Goal === x and Goal === y
    return false unless x.pred == y.pred
    x, y = x.args, y.args
  end
  if Array === x and Array === y
    return false unless x.length == y.length
    for i in 0 ... x.length
      return false unless _unify(x[i], x_env, y[i], y_env, trail, tmp_env)
    end
    return true
  else
    return x == y
  end
end

引数 trail は，この単一化でセットされた変数とその環境を記録する。 この記録は，後で同じ述語の別の定義を試す前に今の単一化を取り消す (いわゆるバックトラックをする) ために使われる。 引数 tmp_env は，すぐに廃棄される予定の環境であり， そこでの単一化は trail に記録しない。

前述の append 述語でリストの分離/連結操作が可能なのは， ここで Array の各要素について再帰的に単一化しているからである。

文字列定数や数値定数は，末尾の return x == y で等価性が判定される。

5. イテレータ resolve

イテレータ resolve の定義を下記に示す。

与えられたゴールの並びが nil ならば再帰の底である。 そうでなければ，先頭のゴール goal と残り rest に分割する (goal, rest = body)。

ゴールが :CUT の場合は後述する。

ゴールの述語定義の配列 goal.pred.defs の各要素について， for 文ループでゴールと定義左辺 d_head の単一化を試みる (_unify 呼び出し)。

定義右辺 d_body が Proc の場合は後述する。

単一化に成功したとき，定義右辺 d_body を， その環境 d_env のもとで解決する (外側の _resolve_body 呼び出し)。

外側の _resolve_body 呼び出しが解を一組みつけたとき， 仮引数と結合している実引数にその解がもたらされている。 もとのゴール並びの残り rest を，実引数の環境 env のもとで解決する (内側の _resolve_body 呼び出し)。

すべてに対して解決したら，yield する。

for 文で次のループに入る前に，単一化前の状態に変数値を戻す (trail に対する for 文と，d_env.clear)。 いわゆるバックトラックである。 

def resolve(*goals)
  env = Env.new
  _resolve_body(list(*goals), env, [false]) {
    yield env
  }
end

def _resolve_body(body, env, cut)
  if body.nil?
    yield
  else
    goal, rest = body
    if goal == :CUT
      _resolve_body(rest, env, cut) {
        yield
      }
      cut[0] = true
    else
      d_env = Env.new
      d_cut = [false]
      for d_head, d_body in goal.pred.defs
        break if d_cut[0] or cut[0]
        trail = []
        if _unify_(goal, env, d_head, d_env, trail, d_env)
          if Proc === d_body
            if d_body[CallbackEnv.new(d_env, trail)]
              _resolve_body(rest, env, cut) {
                yield
              }
            end
          else
            _resolve_body(d_body, d_env, d_cut) {
              _resolve_body(rest, env, cut) {
                yield
              }
              d_cut[0] ||= cut[0]
            }
          end
        end
        for x, x_env in trail
          x_env.delete(x)
        end
        d_env.clear
      end
    end
  end
end

$_trace = false
def trace(flag)
  $_trace = flag
end

def _unify_(x, x_env, y, y_env, trail, tmp_env)
  lhs, rhs = x_env[x].inspect, y.inspect if $_trace
  unified = _unify(x, x_env, y, y_env, trail, tmp_env)
  printf("\t%s %s %s\n", lhs, (unified ? "~" : "!~"), rhs) if $_trace
  return unified
end

*2 この Ling の発言は典型的なジェネレータには妥当だが， _resolve_body のように自らや他のジェネレータを利用するジェネレータについては (当たらずとも遠からずではあるが) 不正確である。 7. および 8. を参照されたい。

*3 広い意味で Algol 系に属する CLU のイテレータ定義はいわゆる関数定義と同様の構文であり， return 文ではなく yield 文を使用した。 その動作は一見するとコルーチンのように見えるが， 任意の文脈で使うことはできず， for 文の "for 変数宣言 in イテレータ呼び出し" に制限されていた。 文献 7 の 10.3.10 には
"...a yield effectively calls the loop body, which returns to the iterator when it is finished." 「yield 文は実質的にループ本体を呼び出す。 ループ本体は終了するとイテレータにリターンする」
"Imposing the limitations on iterators was done to get the efficient, single stack implementation, albeit at the expense of some expressive power. For example, iterators cannot be used to compute whether two lists have the same elements, because to do this you need to iterate through the two lists side by side, and CLU only allows iterator calls to be nested." 「イテレータに制限をかけたのは，いくらかの表現力を犠牲にしようとも， 効率の良い単一スタック実装を得るためだった。 たとえば，二つのリストが同じ要素を持つかどうかを計算するために イテレータを使うことはできない。なぜなら， そうするためには二つのリストを並行してイテレートしなければならないが， CLU はイテレータ呼び出しを入れ子にすることしか許していないからである」
とあり，コルーチンではなく yield からの呼び出しによる実装方法， それによる効率性と表現力の限界など，ほとんどあらゆる点で Ruby のイテレータのさきがけとなっていたことがうかがわれる。 CLU のイテレータが Alphard のジェネレータ (用語が紛らわしいが， これは今日の Python や Java のイテレータ・クラスの祖先にあたる。 インスタンス変数，コンストラクタ， next メソッドに相当するものを構文として明示的に備えていた) をヒントに発明されたのは 1975 年ごろのことである。

5.1 コールバック

上記でもしも d_body が Proc だったならば， 配列要素参照演算 d_body[] で関数適用を行う。 これにより Prolog 内部から Ruby 関数を呼び出すことができる。 このとき引数として渡される コールバック用環境のクラス CallbackEnv の定義は次のとおりである。 実装詳細にかかわる trail と複雑な仕様の _unify を隠蔽し， 項の展開と単一化のメソッドだけを提供する。 これは典型的にはそれぞれ変数値の参照と設定に利用される。 

class CallbackEnv
  def initialize(env, trail)
    @env, @trail = env, trail
  end
  def [](t)
    return @env[t]
  end
  def unify(t, u)
    return _unify(t, @env, u, @env, @trail, @env)
  end
end

たとえば，第１引数から第２引数を減算した値と第３引数を単一化する述語は， 次のように書ける。 

subt = pred 'subt'
subt[:A, :B, :X].calls {|env|
  a, b = env[:A], env[:B]
  env.unify(:X, a - b)
}

ここで subt[10, 2, :X] を resolve すると，:X の値が 8 になる。

5.2 カット演算子

cut と d_cut はカット演算子に対するフラグである。 入れ子になった関数呼び出しの奥底でフラグを立てられるように， 長さ１の配列で変数引数を代用する。 カット演算子 :CUT は， 探索木の枝刈りをすることによってバックトラックを制御する。 ゴール p[:X], g1, g2, g3 が与えられたとき， 

p[:X] .si g1, :CUT, g2
p[:X] .si g3

で g1 が成功した (つまり満たす解が見つかった) とき， :CUT を通り過ぎた時点で g1 の別解， および述語 p に対するもうひとつの定義の本体 g3 への探索木が刈り取られる。 p[:X] が成功するかしないかは，g2 によって決定される。 g2 の解がすべて失敗したとき，他の可能性をさがすことなく p[:X] が失敗する。

つまり，Ruby 風に表現すると，次のような制御構造を表現できる。 

def p(X)
  if g1 then g2
        else g3 end
end

カット演算子とコールバックの使用例としてクイックソートのプログラムを示す。 

require 'tiny_prolog'
trace(false)

le = pred 'le'                  # Less than or Equal to
le[:A, :B].calls {|env|
  a, b = env[:A], env[:B]
  a <= b
}

qsort = pred 'qsort'; partition = pred 'partition'

qsort[cons(:X, :L), :R, :R0] .si \
   partition[:L, :X, :L1, :L2],
   qsort[:L2, :R1, :R0],
   qsort[:L1, :R, cons(:X, :R1)]
qsort[nil, :R, :R] .si

partition[cons(:X, :L), :Y, cons(:X, :L1), :L2] .si \
   le[:X, :Y], :CUT,
   partition[:L, :Y, :L1, :L2]

partition[cons(:X, :L), :Y, :L1, cons(:X, :L2)] .si \
   partition[:L, :Y, :L1, :L2]

partition[nil, :Y, nil, nil] .si

query qsort[list(3, 14, 1, 5, 926, 5, 35, 8, 9, 79), :RESULT, nil]

実行例を示す。qsort の第１引数をソートした結果が第２引数に得られる。 

$ ruby qsort.rb
1 qsort[(3 14 1 5 926 5 35 8 9 79), (1 3 5 5 8 9 14 35 79 926), nil]
$

プログラム中の trace(false) を trace(true) にするとトレース出力が得られる。 

$ ruby qsort.rb
        qsort[(3 14 1 5 926 5 35 8 9 79), :RESULT, nil] ~ qsort[(:X . :L), :R, :R0]
        (...略...)
        qsort[nil, :R1, (3 5 5 8 9 14 35 79 926)] ~ qsort[nil, :R, :R]
        qsort[nil, :R, (1 3 5 5 8 9 14 35 79 926)] !~ qsort[(:X . :L), :R, :R0]
        qsort[nil, :R, (1 3 5 5 8 9 14 35 79 926)] ~ qsort[nil, :R, :R]
1 qsort[(3 14 1 5 926 5 35 8 9 79), (1 3 5 5 8 9 14 35 79 926), nil]
        qsort[(1), :R, (3 5 5 8 9 14 35 79 926)] !~ qsort[nil, :R, :R]
        (...略...)
        qsort[(3 14 1 5 926 5 35 8 9 79), :RESULT, nil] !~ qsort[nil, :R, :R]
$

参考のため本来の Prolog 構文による partition 述語を示す。 本来の表記方法ではカット演算子が「!」であること， cons(:X, :Y) が [X|Y] であることに注意されたい。 

partition([X|L], Y, [X|L1], L2) :-
        X =< Y, !,
        partition(L, Y, L1, L2).

partition([X|L], Y, L1, [X|L2]) :-
        partition(L, Y, L1, L2).

partition([], Y, [], []).

6. おわりに

ここでは Ruby の構文要素を利用して小さな Prolog 処理系を作成した。 バックトラックで次々と値を返すことが Prolog の基本動作だから， Prolog ゴールの問い合わせを Ruby のイテレータとして実現した。 組込み述語はないが， カット演算子やコールバックなどの基本機能を備えており， 潜在的に広範なプログラムが可能である。 例としてクイックソートを示した。

この処理系に，記号表などの隠された大域変数はない。 ローカルに定義した述語はローカルに， グローバルに定義した述語はグローバルに使用できる。 Ruby プログラム内で同時に複数の Prolog プログラムを並行的に使うこともできる。

参考資料

本稿の内容は基本的に下記の要約，注釈，および補足である。

  1. Rubyで作るProlog処理系 (CodeZine, 2006)

Ruby については下記を参考にした。

  1. まつもと & 石塚:「オブジェクト指向スクリプト言語 Ruby」, アスキー出版, 1999, ISBN 4-7561-3254-5
  2. 原:「Ruby プログラミング入門」, オーム社, 2000, ISBN 4-274-06385-2
  3. Thomas & Hunt 著, 田和訳: 「達人プログラマーガイド プログラミング Ruby」, ピアソン・エデュケーション, 2001, ISBN 4-89471-453-1

Haskell および Common Lisp (初版) については下記を参考にした。

  1. S. P. Jones 編:「Haskell 98 Language and Libraries, The Revised Report」, Cambridge University Press, 2003, ISBN 0-521-82614-4
  2. G. Steele:「Common LISP: The Language」, Digital Press, 1984, ISBN 0-932376-41-X

Algol 68, Pascal, CLU 等の歴史については下記を参考にした。

  1. T. J. Bergin & R. G. Gibson 編: "History of programming languages", ACM Press, 1996, ISBN 0-201-89502-1

CLU のループ文に影響を与えた Alphard については下記を参照した。 ここでいう generator は 今日の Java や Python に見られるイテレータ・クラスに相当する。

  1. M. Shaw, W. A. Wulf & R. L. London: Abstraction and verification in Alphard: defining and specifying iteration and generators, CACM, Vol. 20, No. 8 (August 1977), pp.553-564, 1977, ISSN 0001-0782

本処理系は，下記の Python による Prolog 実装をベースとしている。

  1. Python で作る Prolog 処理系

5.2 のクイックソート・プログラムは下記で配布されている PrologCafe091 に含まれる examples/bench/qsort.pl を参考にした。 Prolog Cafe は Java による代表的な Prolog 処理系のひとつである。

  1. Prolog Cafe: A Prolog to Java Translator System

7. 追記: ジェネレータとイテレータ

def range(n)
  i = 0
  while i < n
    yield i
    i += 1
  end
end

class MyRange
  def initialize(n)
    @n = n
    @q = 0
  end

  def next()
    loop {
      case @q
      when 0
        @i = 0
        @q = 1
      when 1
        if @i < @n
          @q = 2
          return @i             # yield i
        else
          @q = 3
        end
      when 2
        @i += 1
        @q = 1
      when 3
        raise "end of iteration"
      end
    }
  end
end

$ irb -r range.rb
irb(main):001:0> range(3) {|i| p i}
0
1
2
=> nil
irb(main):002:0> r = MyRange.new(3)
=> #<MyRange:0x57d04 @q=0, @n=3>
irb(main):003:0> r.next()
=> 0
irb(main):004:0> r.next()
=> 1
irb(main):005:0> r.next()
=> 2
irb(main):006:0> r.next()
RuntimeError: end of iteration
        from ./range.rb:32:in `next'
        from ./range.rb:16:in `loop'
        from ./range.rb:16:in `next'
        from (irb):6
irb(main):007:0>  

$ ruby -v
ruby 1.8.2 (2004-12-25) [powerpc-darwin8.0]
$ ./tak.rb
1 tak[4, 2, 0, 1]
./tiny_prolog.rb:104:in `_unify': stack level too deep (SystemStackError)
        from ./tiny_prolog.rb:103:in `loop'
        from ./tiny_prolog.rb:103:in `_unify'
        from ./tiny_prolog.rb:130:in `_unify'
        from ./tiny_prolog.rb:129:in `each'
        from ./tiny_prolog.rb:129:in `_unify'
        from ./tiny_prolog.rb:195:in `_unify_'
        from ./tiny_prolog.rb:163:in `_resolve_body'
        from ./tiny_prolog.rb:160:in `each'
         ... 952 levels...
        from ./tiny_prolog.rb:160:in `_resolve_body'
        from ./tiny_prolog.rb:142:in `resolve'
        from ./tiny_prolog.rb:220:in `query'
        from ./tak.rb:31
$

*4 この Suzu の発言は， 一見するとイテレータの構文についての疑問に基づいているが，実は過去のトラウマに起因している。その原因となったのは， 関数適用の解釈が空白文字に依存するという (おそらくは Perl に由来する) Ruby の構文則である。
プログラム中で通常無視されるはずの空白文字が意味をもつことに関しては， 複合文の構造が字下げに依存する Python 等が通俗的には悪名高い。 しかし，見た目どおりの字下げ (ただし '\t' 文字は Unix の慣習に従い 8 タブ扱い) ですべてが説明される Python の明快さと比較すると，表立ってはいないが， 空白に関する Ruby の構文則は微妙で複雑であり，簡潔な説明が困難である。 事実，本稿であげた Ruby の参考文献はどれも， その正確なルールを記述せず， 「プログラマの意図をできるだけ推測して解釈を行います」(文献2.§2.4) 等の叙述にとどめている。 現実には，人間の意図を推測するなんらかの新技術が使われているわけではなく， あらかじめ想定された書き方に対し， 定型ルールによる「推測」が見掛け上機能するにすぎない。
したがって，ときには気まぐれとも思われる結果が得られる。 たとえば，無引数関数 a の結果に「変数 b を足し，c を足す」ということを Ruby スクリプト上で強調しようと a +b +c と書くと， a(b + c) と解釈されてエラーになる。 空白だけの違いであるが a + b + c と書いたときは問題ない。 文脈依存だが，a が関数ではなく変数である場合はどちらでも問題ない。 GNU コーディング規約の書き方にならって関数と丸カッコのあいだに空白文字をおくと， さらに非直感的な結果に悩まされることになる。 同様のルールをもつ Perl は "If it looks like a function call, it is a function call." (L. Wall et al.: Programming Perl 2nd ed., O'Reilly, 1996, p.77) と説明している。しかし，一定の勢力をもつ GNU コーディング規約に対し， この説明は意味をもたない。
プログラミング言語の構文解析器に人間のような常識や機転を与えることは， 現在の技術ではできない。 プログラミング言語に煩雑な構文則を規定しても， 決して自然言語と同じ柔軟性は得られない。 現代のプログラミング言語は，微妙で説明しにくいルールではなく， 適度に明快で分かりやすいルールを規定し， その組み合わせの自由を提供するのが普通である。 この教訓に Perl と Ruby はなんら技術的裏付けなしに挑戦し， 技術的必然として失敗している。 今日の両言語の成功は，この挑戦のおかげではなく， むしろこの挑戦にもかかわらず，あるいはこの挑戦とは関係なく (他の長所と利点により) 得られたものであると言ってよい (つまり，「そんな宣伝文句の真偽はともかく」である)。
Suzu が Ruby について部分的に詳しかったり，無知だったり， 無条件の称賛に懐疑的なのは， 過去いったんは学ぼうとして Ruby のこの欠陥を無意識に感じ取り， 「普通に使えそう」にないと見限って離れたことが背景にある。

8. 追記: ジェネレータとイテレータ − 実験

実験に使用する 再帰的な２重ループの Python ジェネレータと Ruby イテレータを示す。 表記法の違いを除き，両者の定義本体は同一である。 

def iter1(n):
    if n == 1:
        yield 1
    else:
        for x in iter1(n - 1):
            for y in iter1(n - 1):
                yield x + y

def iter1(n)
  if n == 1
    yield 1
  else
    iter1(n - 1) {|x|
      iter1(n - 1) {|y|
        yield x + y
      }
    }
  end
end

実験プログラムは，上記の定義を含む iter_test.py と iter_test.rb である。 下図は n=4 に対する結果である。


n=4 に対する iter1 の呼び出しごとのスタック高さ (左が Python のジェネレータ, 右が Ruby のイテレータ)

n=1 から n=20 までの，のべ呼び出し回数 (calls) と，最大スタック高さ (nests) を測った様子を示す。 

$ ./iter_test.py 1 20
n=1: 2 calls, 2 nests
n=2: 6 calls, 3 nests
n=3: 14 calls, 4 nests
n=4: 30 calls, 5 nests
n=5: 62 calls, 6 nests
n=6: 126 calls, 7 nests
n=7: 254 calls, 8 nests
n=8: 510 calls, 9 nests
n=9: 1022 calls, 10 nests
n=10: 2046 calls, 11 nests
n=11: 4094 calls, 12 nests
n=12: 8190 calls, 13 nests
n=13: 16382 calls, 14 nests
n=14: 32766 calls, 15 nests
n=15: 65534 calls, 16 nests
n=16: 131070 calls, 17 nests
n=17: 262142 calls, 18 nests
n=18: 524286 calls, 19 nests
n=19: 1048574 calls, 20 nests
n=20: 2097150 calls, 21 nests
$ 

$ ./iter_test.rb 1 20
n=1: 1 calls, 5 nests
n=2: 3 calls, 8 nests
n=3: 7 calls, 15 nests
n=4: 15 calls, 30 nests
n=5: 31 calls, 61 nests
n=6: 63 calls, 124 nests
n=7: 127 calls, 251 nests
n=8: 255 calls, 506 nests
./iter_test.rb:18: stack level too deep (SystemStackError)
        from ./iter_test.rb:17:in `iter1'
        from ./iter_test.rb:7:in `iter1'
        from ./iter_test.rb:8:in `iter1'
        from ./iter_test.rb:7:in `iter1'
        from ./iter_test.rb:8:in `iter1'
        from ./iter_test.rb:8:in `iter1'
        from ./iter_test.rb:7:in `iter1'
        from ./iter_test.rb:7:in `iter1'
         ... 748 levels...
        from ./iter_test.rb:7:in `iter1'
        from ./iter_test.rb:27
        from ./iter_test.rb:25:in `each'
        from ./iter_test.rb:25
$

Java で作る Prolog 処理系 へつづく


Copyright (c) 2006 Oki Software Co., Ltd.