Functional Programming

記号のパターンマッチング

Lisp / Scheme はリスト処理が得意なプログラミング言語ですが、もうひとつの得意分野に「記号処理」があります。今回は記号処理の例題として Lisp / Scheme の教科書では定番となっている、「記号のパターンマッチング」というプログラムを説明します。

●パターンマッチング

パターンマッチング (pattern matching) は「型合わせ」という検索方法のひとつです。たとえば、「太郎はコーヒーが好き」、「太郎はココアが好き」、「花子は紅茶が好き」というデータを、次のようなリストで表すことにします。

(taro like coffee)
(taro like cocoa)
(hanako like tea)

パターンマッチングは、このようなデータから情報を抽出するために使われます。データと同様にパターンもリストで表すのですが、リストの中に「パターン変数 (pattern variable) 」を使うことができるのが特徴です。パターン変数はいろいろな表現方法があるのですが、ここでは ? で始まるシンボル ^[*1] と定義します。パターン変数を含む例を次に示します。

(taro like ?x)
(taro ?y coffee)
(hanako ?x ?y)
(hanako ?z ?z)

パターン中にパターン変数を含まない場合は equal? によるリストの比較と同じ動作になります。したがって、(taro like coffee) というパターンはデータ (taro like coffee) と一致しますが、データ (taro like cocoa) とは一致しません。

パターン中にパターン変数を含んでいる場合、パターン中で最初に出現するパターン変数はワイルドカードのように働きます。たとえば、(taro like ?x) というパターンと (taro like coffee) というデータをマッチングさせてみましょう。この場合、各要素を比較していくと、taro と like は一致しますが、最後の要素 ?x と coffee が残ります。

?x はパターン変数ですが、このパターンの中で最初に現れたので、?x と coffee は一致するのです。したがって、(taro like ?x) と (taro likecoffee) は一致します。同様に、(taro like ?x) と (taro like cocoa) も一致します。

パターン変数はパターン中のどこに現れてもかまいません。(taro ?y coffee) と (taro like coffee) は ?y が like と一致するので、マッチングは成功します。(taro like cocoa) とマッチングさせると、?y は like と一致するのですが、coffee と cocoa は一致しないので失敗します。

また、パターン変数は複数使ってもかまいません。(hanako ?x ?y) はパターン変数 ?x と ?y がありますね。これと (hanako like tea) をマッチングさせてみます。すると、?x は like と、?y は tea と一致するので、マッチングは成功します。

今度は、(hanako ?x ?x) を考えてみます。同じパターン変数 ?x が 2 回使われていますね。データと一致したパターン変数は、その後パターンの中では一致したデータとして扱われます。(hanako like tea) とマッチングさせると、最初の ?x は like と一致します。2 番目の ?x は tea と比較することになりますが、?x は既に like と一致しているので like と tea を比較することになるのです。したがって、マッチングは失敗します。

(hanako ?x ?x) は (hanako like like) とか (hanako tea tea) のようなデータと一致しますが、この場合はデータに意味がありませんね。

●パターン変数は連想リストで管理する

Lisp / Scheme の用語では、変数に値を与えることを「束縛 (binding) 」といいます。また、値が与えられていない、未束縛の変数を「自由変数」と呼びます。パターン変数の場合、最初は自由変数であり、データとマッチングしたときに束縛されます。つまり、自由変数であればどんなデータとも一致しますが、束縛されていれば、その値を取り出してデータと比較することになります。パターンマッチングを実現する場合、この変数束縛の管理方法がポイントになります。

今回はオーソドックスに連想リストを使ってパターンマッチングを実現してみましょう。関数名は match とします。match は再帰を使ってリストを分解し、要素同士を比較していきます。match はマッチングに成功した場合、パターン変数とその値を格納する連想リストを返します。本稿では、この連想リストのことを「束縛リスト」と呼ぶことにします。次の例を見てください。

(match '(taro like ?x) '(taro like coffee) '())
=> ((?x . coffee))

(match '(taro ?y coffee) '(taro like coffee) '())
=> ((?y . like))

(match '(hanako ?x ?y) '(hanako like tea) '())
=> ((?y . tea) (?x . like))

関数 match は 1 番目の引数にパターンを、2 番目の引数にデータを、3 番目の引数に束縛リストを受け取ります。データにはパターン変数が含まれていないことに注意してください。

最初はどのパターン変数にも値は入っていないので、引数には空リストを渡します。match はパターン変数がなくても、マッチングが成功したときは空リストを返します。

(match '(taro like coffee) '(taro like coffee) '())
=> '()

(match '(hanako like tea) '(hanako like tea) '())
=> '()

マッチングが失敗した場合はシンボル fail を返すことにします。

(match '(taro ?y coffee) '(taro like cocoa) '())
=> fail

(match '(hanako ?x ?x) '(hanako like tea) '())
=> fail

match を作る前に、パターン変数を管理するための関数を作っておきましょう。まず、要素がパターン変数であるかチェックする関数 variable? です。

リスト : 要素はパターン変数か

(define (variable? pattern)
  (and (symbol? pattern)
       (char=? #\? (string-ref (symbol->string pattern) 0))))

最初に、述語 symbol? で pattern がシンボルであることを確認します。次に、関数 symbol->string でシンボルを文字列に変換して、関数 string-ref で先頭文字を取り出します。そして、述語 char=? で文字が #\? であることをチェックします。

次は、束縛リストにデータを追加する add-binding を作ります。

リスト : 束縛リストに追加する

(define (add-binding var val binding)
  (cons (cons var val) binding))

これも簡単ですね。引数 var に変数名、val に値、binding に束縛リストを受け取ります。まず cons で var と val をドット対にまとめ、それを cons で binding の先頭に追加します。返り値はパターン変数を追加した束縛リストになります。

●match の実装

それでは match を作ります。リスト操作の基本である car と cdr でリストを分解して要素を比較していきます。ここで肩慣らしに、リストが等しいかチェックする述語 equal-list? を作ってみましょう。簡単のため、アトムの判定は述語 eqv? を使うことにします。再帰定義に慣れていればすぐに作れると思います。

考え方は簡単です。2 つの引数がアトムであれば eqv? で比較すればいいですね。リスト同士であればリストの car を比較します。このとき、リストの要素がリストの場合もあるので eqv? で比較することはできません。ここは再帰の出番ですね。equal-list? を呼び出して比較すればいいわけです。

その結果が等しい場合はリストの cdr を比較します。ここでも equal-list? を呼び出します。2 つの引数がアトムでもなくリストでもない場合は、不一致と判定すればいいでしょう。プログラムは次のようになります。

リスト : リストが等しいか

;;; アトムか
(define (atom? x) (not (pair? x)))

;;; リストの比較
(define (equal-list? ls1 ls2)
  (cond
   ((and (atom? ls1) (atom? ls2))
    (eqv? ls1 ls2))
   ((and (pair? ls1) (pair? ls2))
    (and (equal-list? (car ls1) (car ls2))
         (equal-list? (cdr ls1) (cdr ls2))))
   (else #f)))

述語 atom? でアトムのチェック、述語 pair? でリストのチェックを行います。引数 ls1 と ls2 がリストの場合、リストの先頭要素を car で取り出して equal-list? を再帰呼び出しします。その結果が真であれば、残りのリストを equal-list? でチェックします。

match の場合も基本的な考え方は equal-list? と同じです。ここにパターン変数の処理を付け加えればいいわけです。パターン変数とのマッチングは関数 match-variable で行い、リストの比較は関数 match-pieces で行うことにすると、プログラムは次のようになります。

リスト : パターンマッチング

(define (match pattern datum binding)
  (cond
   ((variable? pattern)
    (match-variable pattern datum binding))
   ((and (atom? pattern) (atom? datum))
    (match-atoms pattern datum binding))
   ((and (pair? pattern) (pair? datum))
    (match-pieces pattern datum binding))
   (else 'fail)))

パターン変数はシンボルなので atom? で判定すると真になってしまいます。このため、最初に variable? で引数 pattern がパターン変数かチェックしています。pattern と datum がアトムであれば eqv? で比較します。この処理は match-atoms で行います。pattern と datum がリストであれば、match-pieces でチェックを行います。ここで match が再帰呼び出しされます。それ以外の場合は fail を返します。

まず簡単な match-atoms から見ていきましょう。

リスト : アトム同士のマッチング

(define (match-atoms pattern datum binding)
  (if (eqv? pattern datum) binding 'fail))

pattern と datum を述語 eqv? で比較します。等しい場合は連想リスト binding を返し、そうでなければ fail を返します。

次は、パターン変数とのマッチングを調べる match-variable です。

リスト : パターン変数とのマッチング

(define (match-variable var datum binding)
  (let ((val (assoc var binding)))
    (if val
        (match (cdr val) datum binding)
        (add-binding var datum binding))))

まず、束縛リスト binding からパターン変数 var を assoc で検索します。assoc は var を発見したらドット対を返すので、それを val にセットします。パターン変数が見つかれば、その値を使って再度マッチングを試みます。これは match を再帰呼び出しすればいいですね。値は (cdr val) で取り出すことができます。パターン変数が binding に無い場合は、そのパターン変数はまだ束縛されていません。そこで、add-binding を呼び出して binding にパターン変数と値を登録します。

次はリストのマッチングを行う match-pieces です。

リスト : リストのマッチング

(define (match-pieces pattern datum binding)
  (let ((result (match (car pattern) (car datum) binding)))
    (if (eq? result 'fail)
        'fail
        (match (cdr pattern) (cdr datum) result))))

リストを car と cdr で分解してマッチングしていきます。まず pattern と datum の要素を car で取り出して、match を再帰呼び出しします。結果は result にセットします。マッチングに失敗したら fail を返します。マッチングに成功したら、残りのリストを match で調べます。このとき、束縛リストは binding ではなく result を使うことがポイントです。最初に呼び出した match により、新しいパターン変数が追加されているかもしれないからです。

これでプログラムは完成です。簡単な実行例を示します。

gosh[r7rs.user]> (match '(taro like coffee) '(taro like coffee) '())
()
gosh[r7rs.user]> (match '(taro like tea) '(taro like coffee) '())
fail
gosh[r7rs.user]> (match '(taro like ?x) '(taro like coffee) '())
((?x . coffee))
gosh[r7rs.user]> (match '(taro ?x ?y) '(taro like coffee) '())
((?y . coffee) (?x . like))
gosh[r7rs.user]> (match '(taro ?x ?x) '(taro like coffee) '())
fail

実際にプログラムを動かして、いろいろ試してみてくださいね。

●ユニフィケーション

次はパターンとパターンを照合する「ユニフィケーション (unification) 」 ^[*2] を作ってみましょう。関数名は unify とします。unify はパターン変数とパターン変数を照合する分だけ match よりも処理は複雑になります。次の実行例を見てください。

(unify '(taro like coffee) '(taro like ?x) '())
=> ((?x . coffee))

(unify '(taro like coffee) '(taro ?y coffee) '())
=> ((?y . like))

(unify '(hanako like tea) '(hanako ?x ?y) '())
=>  ((?y . tea) (?x . like))

match では第 2 引数にパターンを与えることはできませんが、unify はパターンでもかまいません。unify は match と同様に、成功した場合は束縛リストを返し、失敗した場合は fail を返します。

次は、ユニフィケーションの特徴的な例を示しましょう。

(unify '(hanako ?x ?y) '(hanako ?a ?b) '())
=> ((?y . ?b) (?x . ?a))

(unify '(hanako ?x ?y) '(hanako ?x ?y) '())
=> ((?y . ?y) (?x . ?x))

ユニフィケーションでは、パターン変数の値がパターン変数になることもあります。最後の例のように、自分自身が値となる場合もあります。このような場合でもユニフィケーションは成功するのです。

●unify の実装

それでは unify を作っていきましょう。処理は match とほぼ同じですが、第 2 引数にもパターン変数が含まれるため、その処理を追加することになります。

リスト : ユニフィケーション

(define (unify pattern datum binding)
  (cond
   ((variable? pattern)
    (unify-variable pattern datum binding))
   ((variable? datum)
    (unify-variable datum pattern binding))
   ((and (atom? pattern) (atom? datum))
    (unify-atoms pattern datum binding))
   ((and (pair? pattern) (pair? datum))
    (unify-pieces pattern datum binding))
   (else 'fail)))

引数 datum がパターン変数かチェックする処理を追加しています。unify-atoms と unify-pieces は match を unify に置き換えただけで、match-atoms と match-pieces と同じです。

リスト : アトムとリストのユニフィケーション

;;; アトムとのユニフィケーション
(define (unify-atoms pattern datum binding)
  (if (eqv? pattern datum) binding 'fail))

;;; リストのユニフィケーション
(define (unify-pieces pattern datum binding)
  (let ((result (unify (car pattern) (car datum) binding)))
    (if (eq? result 'fail)
        'fail
        (unify (cdr pattern) (cdr datum) result))))

次は、パターン変数とのユニフィケーションを行う unify-variable を作ります。unify-variable は match-variable と処理が異なる箇所があります。ユニフィケーションの場合、パターン変数とパターン変数は一致しますが、パターン変数とそれと同じパターン変数を含むパターンとは一致しないからです。次の例を見てください。

(unify '(taro like ?x) '(taro like (coffee black)) '())
=> ((?x coffee black))

(unify '(taro like (coffee ?x)) '(taro like (coffee black)) '())
=> ((?x . black))

(unify '(taro like ?x) '(taro like (coffee ?x)) '())
=> fail

coffee の種類をリストで表すことにしました。最初の例では、?x は (coffee ブラック) となります。2 番目の例では、?x はブラックとなり、coffee の種類を求めることができます。

それでは、最後の例はどうなるのでしょうか。?x と (coffee ?x) を照合させることになります。この場合、最初の ?x は taro が like なものを表しているのに、次の ?x は coffee の種類を表すことになり矛盾してしまいます。したがって、?x と (coffee ?x) は不一致と判定しなくてはいけないのです。

それでは unify-variable を作りましょう。パターン変数と値を束縛リストに追加するときに、値の中に同じパターン変数がないことを確認します。この処理を関数 inside? で行います。

リスト : パターン変数とのユニフィケーション

(define (unify-variable pattern datum binding)
  (let ((val (assoc pattern binding)))
    (if (and val
             (not (eq? pattern (cdr val))))
        (unify (cdr val) datum binding)
        (if (inside? pattern datum binding)
            'fail
            (add-binding pattern datum binding)))))

実は、match-varibale との違いがもうひとつあります。ユニフィケーションの場合、同じパターン変数同士の照合は成功するので、束縛リストの中には、たとえば (?x . ?x) というドット対が含まれることがあります。このため、束縛リストから変数の値を探し、それを使って単純に unify を再帰呼び出しすると困ることが起こるのです。?x の値は ?x ですから、同じことをずっと繰り返すことになり、再帰呼び出しが停止しないのです。これを回避するために、最初の if でパターン変数とその値が異なることを確認しています。

そして、束縛リストにパターン変数と値を追加する前に関数 inside? を呼び出して、同じパターン変数が値の中で使われていないかチェックします。それでは inside? を作りましょう。

リスト : 同じパターン変数が含まれているか

(define (inside? var datum binding)
  (if (eq? var datum)
      #f
      (inside-sub var datum binding)))

inside? は引数 datum (パターン変数の値) に引数 var (パターン変数) が含まれていれば #t を返し、そうでなければ #f を返します。実際の処理は関数 inside-sub で行います。ユニフィケーションは同じパターン変数の照合であれば成功するので、var と datum が同じパターン変数であれば #f を返します。

リスト : inside? 本体

(define (inside-sub var datum binding)
  (cond
   ((eq? var datum) #t)
   ((atom? datum) #f)
   ((variable? datum)
    (let ((val (assoc datum binding)))
      (if val
          (inside-sub var (cdr value) binding)
         #f)))
   (else
    (or (inside-sub var (car datum) binding)
        (inside-sub var (cdr datum) binding)))))

inside-sub はリストを car と cdr で分解しながら、パターン変数 var が含まれているかチェックします。最初に var と datum が等しいか eq でチェックします。結果が真であればデータの中に同じパターン変数を見つけたので #t を返します。

次に、datum がアトムであれば、これ以上分解できないので #f を返します。datum がパターン変数の場合は、その値に var が含まれているかチェックします。assoc で束縛リストから datum を探索し、値が見つかれば inside-sub を再帰呼び出しします。そうでなければ #f を返します。

それ以外の場合は datum はリストなので、car と cdr でリストを分解して inside-sub を再帰呼び出しします。変数 var が見つかったら探索を中断して #t を返せばいいので、or を使っていることに注意してください。つまり、CAR 部を調べてた結果が #t ならば or は #t を返しますし、#f であれば次の CDR 部の探索が行われます。

これでプログラムは完成です。簡単な実行例を示します。

gosh[r7rs.user]> (unify '(taro like coffee) '(taro like coffee) '())
()
gosh[r7rs.user]> (unify '(taro like coffee) '(taro like ?x) '())
((?x . coffee))
gosh[r7rs.user]> (unify '(taro like coffee) '(taro ?y coffee) '())
((?y . like))
gosh[r7rs.user]> (unify '(taro like coffee) '(taro ?y x) '())
fail
gosh[r7rs.user]> (unify '(taro like coffee) '(taro ?y ?x) '())
((?x . coffee) (?y . like))
gosh[r7rs.user]> (unify '(hanako ?x ?y) '(hanako 'a 'b) '())
((?y quote b) (?x quote a))
gosh[r7rs.user]> (unify '(hanako ?x ?y) '(hanako ?a ?b) '())
((?y . ?b) (?x . ?a))
gosh[r7rs.user]> (unify '(hanako ?x ?y) '(hanako ?x ?y) '())
((?y . ?y) (?x . ?x))
gosh[r7rs.user]> (unify '(taro like ?x) '(tario like (coffee black)) '())
fail
gosh[r7rs.user]> (unify '(taro like ?x) '(taro like (coffee black)) '())
((?x coffee black))
gosh[r7rs.user]> (unify '(taro like (coffee ?x)) '(taro like (coffee black)) '())
((?x . black))
gosh[r7rs.user]> (unify '(taro like ?x) '(taro like (coffee ?x)) '())
fail

実際にプログラムを動かして、いろいろ試してみてくださいね。

●参考文献

1. Patrick Henry Winston, Berthold Klaus Paul Horn, 『LISP 原書第 3 版 (1) (2)』, 培風館, 1992

●プログラムリスト

;;;
;;; match.scm : 記号のパターンマッチング
;;;
;;;             Copyright (C) 2011-2020 Makoto Hiroi
;;;
(import (scheme base))

;;; パターン変数か
(define (variable? pattern)
  (and (symbol? pattern)
       (char=? #\? (string-ref (symbol->string pattern) 0))))

;;; 束縛リストに追加する
(define (add-binding var val binding)
  (cons (cons var val) binding))

;;; アトムか
(define (atom? x) (not (pair? x)))

;;; リストの比較
(define (equal-list? ls1 ls2)
  (cond
   ((and (atom? ls1) (atom? ls2))
    (eqv? ls1 ls2))
   ((and (pair? ls1) (pair? ls2))
    (and (equal-list? (car ls1) (car ls2))
         (equal-list? (cdr ls1) (cdr ls2))))
   (else #f)))

;;; パターンマッチング
(define (match pattern datum binding)
  (cond
   ((variable? pattern)
    (match-variable pattern datum binding))
   ((and (atom? pattern) (atom? datum))
    (match-atoms pattern datum binding))
   ((and (pair? pattern) (pair? datum))
    (match-pieces pattern datum binding))
   (else 'fail)))

;;; アトム同士のマッチング
(define (match-atoms pattern datum binding)
  (if (eqv? pattern datum) binding 'fail))

;;; パターン変数とのマッチング
(define (match-variable var datum binding)
  (let ((val (assoc var binding)))
    (if val
        (match (cdr val) datum binding)
        (add-binding var datum binding))))

;;; リストのマッチング
(define (match-pieces pattern datum binding)
  (let ((result (match (car pattern) (car datum) binding)))
    (if (eq? result 'fail)
        'fail
        (match (cdr pattern) (cdr datum) result))))

;;; ユニフィケーション
(define (unify pattern datum binding)
  (cond
   ((variable? pattern)
    (unify-variable pattern datum binding))
   ((variable? datum)
    (unify-variable datum pattern binding))
   ((and (atom? pattern) (atom? datum))
    (unify-atoms pattern datum binding))
   ((and (pair? pattern) (pair? datum))
    (unify-pieces pattern datum binding))
   (else 'fail)))

;;; アトム同士のユニフィケーション
(define (unify-atoms pattern datum binding)
  (if (eqv? pattern datum) binding 'fail))

;;; リストのユニフィケーション
(define (unify-pieces pattern datum binding)
  (let ((result (unify (car pattern) (car datum) binding)))
    (if (eq? result 'fail)
        'fail
        (unify (cdr pattern) (cdr datum) result))))

;;; パターン変数とのユニフィケーション
(define (unify-variable pattern datum binding)
  (let ((val (assoc pattern binding)))
    (if (and val
             (not (eq? pattern (cdr val))))
        (unify (cdr val) datum binding)
        (if (inside? pattern datum binding)
            'fail
            (add-binding pattern datum binding)))))

;;; 内部に同じパターン変数があるか
(define (inside? var datum binding)
  (if (not (eq? var datum))
      (inside-sub var datum binding)
      #f))

(define (inside-sub var datum binding)
  (cond
   ((eq? var datum) #t)
   ((atom? datum) #f)
   ((variable? datum)
    (let ((val (assoc datum binding)))
      (if val
          (inside-sub var (cdr value) binding)
          #f)))
   (else
    (or (inside-sub var (car datum) binding)
        (inside-sub var (cdr datum) binding)))))

●Prolog ライクなユニフィケーション

関数型言語のパターンマッチング、とくに Erlang でのリストのマッチングは Prolog とよく似ています。そうはいっても、パターンマッチングと Prolog の「ユニフィケーション (unification) 」は異なります。Erlang のパターンマッチングは右辺式に未束縛変数 (自由変数) があるとエラーになりますが、Prolog のユニフィケーションは右辺式に自由変数があってもかまいません。Prolog の場合、自由変数同士のマッチングは成功しますし、右辺式 (たとえばリストなど) の中に自由変数が含まれていてもかまいません。

Prolog のユニフィケーションは本稿で作成した unify の動作と少し異なります。unify の場合も自由変数同士の照合は成功します。ところが、自由変数とリストを照合する場合、リストの中に同じ自由変数が含まれていると照合は失敗します。簡単な例を示しましょう。

(unify '?x '(a . ?y) '())
=> ((?x a . ?y))
(unify '?x '(a . ?x) '())
=> fail

最初の例は ?x と (a . ?y) を照合します。リストの中には同じ変数 ?x がないので照合は成功します。次の例はリストの中に同じ自由変数 ?x があるので照合は失敗します。Prolog ではどちらの場合も照合に成功します。SWI-Prolog での実行例を示します。

?- X = [a | Y].

X = [a|Y] ;

No
?- X = [a | X].

X = [a, a, a, a, a, a, a, a, a|...] ;

No

結果を見ればおわかりのように、X = [a | X] は「循環リスト」になります。右辺のリストにある X は自由変数ですが、Prolog はこのようなリストでも扱うことができます。また、右辺と左辺で同じ自由変数 X がありますが、このようなユニフィケーションでも Prolog では実行することができます。X は自由変数なので、X の値はリスト (セルの先頭アドレス) になります。セルの終端は X なので、先頭のセルとつながって循環リストになるわけです。

unify でも Prolog のようなユニフィケーションを行わせることは可能です。次のリストを見てください。

リスト : パターン変数とのユニフィケーション

(define (unify-variable pattern datum binding)
  (let ((val (assoc pattern binding)))
    (if (and val
             (not (eq? pattern (cdr val))))
        (unify (cdr val) datum binding)
        (if (inside? pattern datum binding)
            'fail
            (add-binding pattern datum binding)))))

関数 unify-variable で pattern が自由変数のとき、それが datum の中に含まれているか inside? でチェックしています。このチェックを外せば unify でも循環リストを作ることができます。

それでは実際に試してみましょう。

gosh[r7rs.user]> (unify '?x '(a . ?x) '())
((?x a . ?x))
gosh[r7rs.user]> (unify '(?x ?x) '((a . ?x) ?x) '())
=> 無限ループ

確かに ?x と (a . ?x) の照合には成功しますが、そのあとに ?x と ?x を照合すると無限ループに陥ります。このとき、関数の呼び出しは次のようになります。

1. (unify '?x '?x '((?x a . ?x)))
2. (unify-variable '?x '?x '((?x a . ?x)))
3. (unify '(a . ?x) ?x '((?x a . ?x)))
4. (unify-variable '?x '(a , ?x) '((?x a . ?x)))
5. (unify '(a . ?x) '(a . ?x) '((?x a . ?x)))
6. a の照合に成功したあと 1 に戻る

このように循環的なデータがあると正常に動作しないのです。そこで、循環データをチェックする処理を追加します。次のリストを見てください。

リスト : パターン変数とのユニフィケーション (2)

(define (unify-variable pattern datum binding)
  (let ((val (assoc pattern binding)))
    (cond
     ((and val
           (eq? datum (cdr val)))
      ;; pattern の値と datum が等しい (循環データ)
      binding)
     ((and val
           (not (eq? pattern (cdr val))))
      (unify (cdr val) datum binding))
     (else
      (add-binding pattern datum binding)))))

束縛リスト binding から求めた値 val が datum と eq? で等しい場合、pattern は束縛されていて、かつデータが循環していることがわかります。binding をそのまま返します。これで循環データにも対応することができます。

それでは実行してみましょう。

gosh[r7rs.user]> (unify '(?x ?x) '((a . ?x) ?x) '())
((?x a . ?x))
gosh[r7rs.user]> (unify '(?x ?x) '((a . ?x) (?a . ?z)) '())
((?z a . ?x) (?a . a) (?x a . ?x))
gosh[r7rs.user]> (unify '(?x ?x) '((a . ?x) (?a ?b . ?z)) '())
((?z a . ?x) (?b . a) (?a . a) (?x a . ?x))
gosh[r7rs.user]> (unify '(?x ?x) '((a . ?x) (?a ?b ?c . ?z)) '())
((?z a . ?x) (?c . a) (?b . a) (?a . a) (?x a . ?x))
gosh[r7rs.user]> (unify '(?x ?x) '((a . ?x) (?a ?b ?c ?d . ?z)) '())
((?z a . ?x) (?d . a) (?c . a) (?b . a) (?a . a) (?x a . ?x))

?x と (a . ?x) を照合したあと、?x の値は確かに循環リストとして機能しています。このように、unify でも Prolog のようなユニフィケーションを行わせることができます。