型と素性

目次

• 素性構造
• 型階層
• 型の単一化
• 素性
• 素性構造の単一化
• 構造共有
• その他

素性構造

素性構造(feature structure, FS)とは， 各ノード，各エッジに名前のついた有向グラフのことです． ノードについた名前は型(type)と呼ばれ， エッジについた名前は素性(feature)と呼ばれます． 各ノードからどのような素性のエッジが出るか(以下では， 「各型がどのような素性を持つか」という言い方をします)というのは， そのノードの型から一意に決まります． 各素性の先はまた素性構造になっているので，素性構造とは， 型と素性からなる再帰的なデータ構造と言うことができます．

一番左の矢印で指されているノードは，根(root)と呼ばれる特別なノードで， どんな素性構造にも必ず一つ存在するノードです． また，型'Hail to Reason'がついているノードは， 二つのエッジの先となっています．このような構造を， 構造共有(後述)と呼びます．

このようなグラフをいちいち書くのは面倒なので， 一般に次のようなAVM(Attribute-Value Matrix) で記述します．

図3.2 素性構造のAVM表記の例

|~競走馬 ~| | 名前:ダンスインザダーク | | 系統:$1 Hail to Reason | | |~種牡馬 ~| | | 父:| 名前:サンデーサイレンス | | | |_系統:$1 _| | | |~繁殖牝馬 ~| | | 母:| 名前:ダンシングキイ | | |_ |_系統:Northern Dancer_| _|

これは，初めの図と同じ構造を表しています． 角かっこで囲まれた部分が，素性構造です． かっこ内の左上に書かれているものが，その素性構造の根の型で，その下に， それぞれの素性と，その素性の先の素性構造を書きます． 構造共有は，ダグ(上の図では， "$1")で表します(詳しくは後述)．LiLFeSが素性構造を画面に表示する時も， この記述方法を使います．

LiLFeSでは，各素性の先に来る素性構造の根の型を指定することができます． 例えば，上の例では， 素性'父'の先のノードは型'種牡馬'であるとすれば， '競走馬'や'Hail to Reason'が来ることができなくなります．

型階層

型(type)は，階層構造を持っています． 例えば，三角形の種類について， 次のような階層構造を作ることができます．

線で結ばれた関係はsupertype-subtypeの関係と呼ばれ，上の図では， 下側がsupertype，上側がsubtypeになっています． 全ての型('bot'を除く)は， 必ず一つ以上のsupertypeを持ちます． supertypeはsubtypeを汎化したもの， subtypeはsupertypeを特化したものと呼ばれ，上の例では， supertypeの概念を特殊化した概念が，subtypeになるようにしています． 型階層は，このような特殊化・一般化の関係を記述するのに使うのが一般的です． また，supertypeを遡っていった型，subtypeをたどっていった型も， それぞれsupertype, subtypeと呼ばれます． 上の図の一番下にある型 'bot'(bottom)は， LiLFeSに組み込みの型で，全ての型のsupertypeとなる型です．

型の単一化

型と型との間の演算として， 単一化(unification)が定義されます． 直観的には，上の図のような型階層の中で， 二つの型の共通のsubtypeのうち， いちばん一般的な型を見つける操作になります． このような型を，LUB(Least Upper Bound)と呼びます．

二つの型をそれぞれX,Yとすると，単一化は，LiLFeSでは

X = Y

> ?- X = 三角形, X = 二等辺三角形. X: 二等辺三角形 > ?- X = 二等辺三角形, X = 直角三角形. X: 直角二等辺三角形 > ?- X = 正三角形, X = 直角三角形. no

LiLFeSの型階層では， 単一化の結果(LUB)は一意に定まらなければならないという制約があります． つまり，二つの型の共通のsubtypeが複数あって， しかもその中にsupertype-subtypeの関係に無い型の組があるような階層構造は， 定義できないということです．例えば， 上の例で'二等辺三角形'と'直角三角形' とを直接のsupertypeとする新たな型Aを定義しようとすると， エラーになります．このような制限があるため， PROLOGの述語による表現より弱い表現になるわけですが，そのおかげで， 型の単一化の処理は高速に行なわれます．

素性

各型は，素性(feature)を持つことができます． supertypeが素性を持っている場合はその素性を受け継ぎ，それに加えて， 新たな素性を付け加えることができます． 複数のsupertypeが存在する時には同じ素性を受け継ぐ可能性がありますが， その様な場合は，一つにまとめられます．LiLFeSでは， 同じ名前の素性を2度以上定義することはできないという制約があります．

例として，次のような型階層を考えます．角かっこ内が， その型で新たに定義される素性です．

ここで，'ストレート'と'フラッシュ'をsupertypeとする型 'ストレートフラッシュ'を定義すると，それは， '最小の数'と'スート'という2つの素性を初めから持っていることになります． もし型'ポーカーの役'に何らかの素性Aがあったとすると， それは'ストレート'と'フラッシュ'にも受け継がれ， さらに'ストレートフラッシュ'には，両方の直接のsupertypeから， 同じ素性Aを受け継ぐことになります．このときは， 素性Aは一つに合併され，結局， 'ストレートフラッシュ'は3つの素性を持つようになります．

素性構造の単一化

素性構造の単一化は，まず，根の型を単一化することから始まります． それに成功したら，つぎに，各素性をたどっていき， その先の素性構造を単一化します．この操作を再帰的に行ない， 全てのノードで単一化が成功すると， 全体の素性構造の単一化が成功したことになります．

ポーカーの役の例を使って， 次のような2つの素性構造の単一化を考えてみます．

|~ストレート ~| |_最小の数:10_| |~フラッシュ ~| |_スート:スペード_|

|~ストレートフラッシュ~| | 最小の数:10 | |_スート:bot _| |~ストレートフラッシュ~| | 最小の数:bot | |_スート:スペード _|

|~ストレートフラッシュ~| | 最小の数:10 | |_スート:スペード _|

構造共有

素性構造は，一般的なグラフ構造を有することができます．木構造との違いは， 複数のエッジの先が一つのノードになる可能性があるということです． このような構造を， 構造共有(structure sharing)と呼びます． 初めの例では，型'Hail to Reason'のノードで， 構造共有が起きています．AVMで表現する時は， 構造共有が起きているノードを根とする素性構造に対するAVMの前に， ダグ(dag) $x(xは任意の数字)を書き， 構造共有が起きている他のノードに同じダグを書いて表します．また， 構造共有されているノード以降の素性構造はどこか1箇所だけで書くことにし， 他のところでは省略することにすれば，ループを含む素性構造も， 有限の記述で表現できます．

構造共有を含む素性構造の単一化は， 前節の方法がそのまま適用できます．ただ， 構造共有が起きているという情報も，単一化されます． 例えば，次のような2つの素性構造を単一化する場合，

|~example ~| | A:$1 bot | | B:$1 | |_C:bot _| |~example ~| | A:bot | | B:$2 bot | |_C:$2 _|

|~example ~| | A:$1 bot | | B:$1 | |_C:$1 _|

その他

LiLFeSでは，PROLOGと同様に，リストを扱うことができます．

> ?- X = [1, 2, 3]. X: < 1, 2, 3 >

リストは，実際には素性構造になっています． リストの型は'list'で， 直接のsubtypeに'cons'と'nil'という型を持ちます． また，'cons'は， 'hd'と'tl'という素性を持ちます． Lispの言葉を借りれば，'hd'は'car'にあたり， 'tl'は'cdr'にあたります．従って， 上の例のリストは，次のような素性構造であるということになります．

|~cons ~| | hd:1 | | |~cons ~| | | | hd:2 | | | tl:| |~cons ~| | | | | tl:| hd:3 | | | |_ |_ |_tl:nil_|_|_|

素性構造ですから，構造共有も表現できます．例えば，次のようにして， 1と2が交互に無限に続く列を表現することができます．

> ?- X = [1, 2 | X]. X: [$1] < 1, 2 | [$1] ... >

LiLFeSでは，述語や素性名なども，全て素性構造として扱われています．