AZ-PrologでHPSGなどの単一化文法を容易に実装するため、データ型として素性構造型を導入しました。
ICOTで開発されたCU-Prologを参考に仕様検討、動作検証をおこないましたが、次の点で異なります。
・セミコロンによる制約記述は取り入れておりません。
・変数に制約条件を直接記述するシンタックスを取り入れました。変数間の関係、チェックが簡素化できます。
・差分リストに似た素性構造の差分表現を導入しました。　

Version9.5で型付素性構造型を導入しました。　

素性構造型

＜素性構造＞を取り扱うモードのとき（default) 中括弧で括られた任意の個数の＜素性と値の対＞のみを要素とする並びを＜素性構造＞とします。
空を除き、＜素性と値の対＞を一つも要素としない場合、従来構造として扱います。混在はエラーとなります。

＜例＞

{}                空の素性構造
{ 氏名:山田太郎,生年月日:{年:1951,月:5,日:26},子供:[花子,一郎,二郎] ,趣味:X }
{ 品詞:動詞 |Else }      差分表現

素性構造でない従来型の例

{write(X),nl}

エラーとなる例

{ a:b,a:z }       同一素性が含まれている
{ a:b,x:z,A }     ＜素性と値の対＞と素性以外の項とが混在している
{ a:b,Z:z }       素性がアトムでない

＜素性と値の対＞
・'素性（アトム）' + '区切り記号(オペレータ）' + 素性値 で表現します。

＜素性＞
・素性は複合項のファンクタがアトムであることを必須とするのと同様に、アトムでなくてはなりません。
・素性は素性構造の同一レベルではユニークでなければなりません。
・素性値が素性構造をとり、階層が異なる場合は親側と同一の素性があってもよいでしょう。

＜素性値＞
・素性値は素性構造を含む任意の項です。

＜区切り記号＞
・区切り記号はデフォルトでは,':'であるが、変更することができます。(下記:fs_delimiter/2)

区切り記号を変更し、'/'とすれば、Cu-Prolog,CILなどのICOT標準表記となります。
ただし、区切り記号 '/ ' はyfxなので、a/b/c などでは/(/(a,b),c)となり素性名がアトムにならないので注意しましょう。
また、op述語で '/ ' をxfyに変更してしまうと、数値計算に支障をきたすので注意してください。

＜DCG補強項などとの混在＞
＜素性と値の対＞を一つも含まない中括弧の構造は、従来と同様に扱われることによりDCGの補強項も問題なく混在可能です。

is_adult(A,{level:child}):- A <18 ,!.
is_adult(A,{level:adult}).

a(X) --> { X={age:A#is_adult(A,X)} },b(X).
b(X) --> { write(end),nl },[end].

展開： a(X,S,T) :- freeze(A,is_adult(A,X)),X={age:A}, b(X,S,T).
展開： b(X,[end|T],T):-write(end),nl.

|?-X = {age:30},a(X,[end],[]).
end
X       = {age:30,level:adult}
yes

型付素性構造型

素性構造に型概念を導入したデータ構造を型付素性構造と呼びます。素性構造モードが型付素性構造モードの時に利用可能です。
型を導入することで概念の階層構造を表現することができます。型は型名を表すアトムの後方に '&' 演算子を付与して表記されます。
型付素性構造は

型&素性構造

という書式で表されます。素性構造の部分に関する書式は型のない素性構造と共通です。素性構造内部の素性値も型を持つため、入れ子構造をとることができます。

型を導入することで、階層を持った概念の記述や、概念どうしの関係性に関する処理を簡潔に行うことができます。型が存在しない場合、概念の階層関係を冗長な素性構造を用いて表現する必要があったり、概念間の推論手順を明示的に記述する必要があったりするなど、プログラムが煩雑になることがありますが、型を導入することでこれを簡単に表現し処理することができます。

また、型と素性、素性と素性値に対して制約条件を課すことができ、コンサルト時に型推論、型検査が行われます。このため、プログラムを簡潔で安全なものにすることができます。

型付素性構造の利用にあたっては、前もって型の定義、および型と素性の関係について定義を行っておく必要があります。これは以下の構文を用いて行います。

型 <- [型1, 型2, ...] + [素性1:素性1の型, 素性2:素性2の型, ...].

左辺の型は右辺の 型1, 型2, ... を継承した型として定義されます。ある型を基準として、それ自身または先祖にあたる型を supertype と呼び、それ自身または子孫にあたる型を subtype と呼びます。

型1, 型2, ... および 素性1の型, 素性2の型, ... は、これよりも前の行であらかじめ定義しておく必要があります。

定義された型がとることのできる素性は、親の型の素性および 素性1, 素性2, ... に限られ、それ以外の素性を持つことはできません。また、素性1, 素性2, ... がとることのできる値は、それぞれ 素性1の型, 素性2の型, ... の subtype に限られます。

組み込み型として bot, list, string, atom, integer, float が用意されています。bot はすべての型の supertype となる特殊な型であり、残りはそれぞれリスト、文字列、アトム、整数、実数を指定する際に用いられます。

詳しくは 9-2-6.型付素性構造の詳細 を参照してください。

組込述語

:- fs_mode(_,0).

:- fs_delimiter(_,!).
:- op(550,xfy,!).
a({a!b,c!d}).

 |?- X={a:{b:bb,c:cc}},fstructure(X).
 yes

% コンサルトする型定義ファイル (以降の例で共通)

三角形 <- [bot] + [色:atom].
二等辺三角形  <- [三角形].
直角三角形  <- [三角形].
直角二等辺三角形  <- [二等辺三角形, 直角三角形].
正三角形 <- [二等辺三角形].

| ?- type_supertypes(直角二等辺三角形, X).
X       = [直角二等辺三角形,二等辺三角形,直角三角形,三角形,bot]
yes

|?- type_subtypes(二等辺三角形, X).
X       = [二等辺三角形,直角二等辺三角形,正三角形]
yes

| ?- type_struct(直角二等辺三角形, X, Y, Z).
X       = [二等辺三角形,直角三角形],
Y       = [直角二等辺三角形,二等辺三角形,直角三角形,三角形,bot],
Z       = [色:atom]
yes

型 <- [supertype1, supertype2, ...] + [素性1:素性1の型, 素性2:素性2の型, ...].

素性構造モード (述語 fs_mode/2を参照) によって、ユニフィケーションの振る舞いが異なります。

素性構造型を利用しないモード (モード 0)

通常のユニフィケーションの原則に従います。

| ?- X = {Y, c:d}, X = {a:b, Z}, write(X), nl.
{a:b,c:d}
X       = {a:b,c:d},
Y       = a:b,
Z       = c:d
yes

| ?- X = {a:b, c:d}, X = {c:d, a:b}, write(X), nl.
no

| ?- X = {a:b, c:d}, X = {c:d, e:f}, write(X), nl.
no

型のない素性構造型モード (モード 1)

デフォルトのモードです。

・素性構造は素性構造または変数とのみユニフィケーションします。他の型とでは失敗します。
・素性構造１と素性構造２のユニフィケーションにおいて、
（1）１に含まれる素性が２の同一階層に含まれるとき、その素性値同士を再帰的にユニフィケーションします。
（2）１に含まれる素性が２の同一階層に含まれないとき、また２に含まれる素性が１の同一階層に含まれないとき
含まれないほうの素性構造にその＜素性と値の対＞が追加され、１と２は同一構造となります。
（3）リストを素性構造に見立てたユニフィケーションと異なり、要素の出現順位、要素数に関わりなく単一化が可能です。

＜例＞

% 素性を指定しての素性値の取り出し
|?- X= {a:S,b:c,c:d},X={c:Z}.
X = {a:S,b:c,c:d}
Z  = d
yes

% 注意：含まれない素性での素性値の取り出しは追加になる
|?- X= {a:S,b:c,c:d},X={q:Z}.
X = {a:S,b:c,c:d,q:Z}
yes

% 素性値のユニフィケーション、含まれない<素性と値の対>の追加
|?- X= {a:Z,b:c},Y={a:3,d:e},X=Y.
X = {a:3,b:c,d:e}
Y = {a:3,b:c,d:e}
Z = 3
yes

% 素性値が異なりFailする
|?- X= {a:{a:b,c:c},b:c},Y={a:3,d:e},X=Y.
no

% 素性値に対しても再帰的に素性構造ユニフィケーションが適用される
|?- X={a:{b:bb}},Y={a:{c:cc}},X=Y.
X       = {a:{b:bb,c:cc}},
Y       = {a:{b:bb,c:cc}}
yes

% Heap上の素性構造とのユニフィケーション（1）
a({}).
|?- X={b:bb},a(X).
X   = {b:bb}
yes

%  Heap上の素性構造とのユニフィケーション（2）
b({c:cc}).
|?- X={b:bb},b(X).
X    = {b:bb,c:cc}
yes

% Heap上の定義は変わらない
|?- listing.
a({}).
b({c:cc}).
yes

% 素性構造の差分表現
% （１）ある素性構造（X）から所定の素性を含まない素性構造（T）の抽出
?- X={a:b,c:d},X={c:d|T}.
T = {a:b}
X = {a:b,c:d}
yes

?- X={a:b,c:d},X={q:m|T}.
T = {a:b,c:d}
X = {q:m,a:b,c:d}
yes

% （２）ある素性構造（T）を差分とする素性構造（X）の表現（生成）
?- T={a:b},X={b:c|T}.
X={b:c,a:b},
T={a:b}
yes
 
% （３）切り出された差分は、束縛の有無に関わらず別素性構造となり切り出し元に影響を与えない
?- X={b:c|T},T={a:b}.
X={b:c}
T={a:b}
yes
 
?-X={a:b,c:d},X={c:d|T},T={e:f}
X={c:d,a:b}
T={a:b,e:f}
yes

% 要素の削除
rm_cat({cat:_|T},T).
|?- rm_cat({phon:walk,cat:verb,sc:[noun]}, Else).
Else = {phon:walk,sc:[noun]}
yes
 
% 構造の変更
change_ha_to({は格:H,と格:T | Else },{は格:T,と格:H | Else }).
|?- change_ha_to({と格:ジョンレノン,は格:オノヨーコ, head:結婚した },Ans).
Ans = {は格:ジョンレノン, と格:オノヨーコ, head:結婚した }
yes

＜注意＞ 素性構造の差分表現を用いる際、差分の箇所に置かれた変数を節の頭部と本体にまたがってマッチさせることはできません。そのような記述を行った場合、動作結果は未保証です。

% (不適切な例) 差分 L が頭部と本体の両方に登場するが、これらはマッチしない
p(X,{a:Z|L}) :- X = {a:Z|L}.
| ?- p({b:bb,a:aa},Y).
Y    = {a:aa}
yes

% (適切な例) 差分 L が本体の 2 か所に現れる。これはマッチする
q(X,Y) :- X = {a:Z|L}, Y = {a:cc|L}.
| ?- q({b:bb,a:aa},Y).
Y   = {a:cc,b:bb}
yes

% (適切な例) 差分 L が頭部の 2 か所に現れる。これもマッチする
r({a:_|L},{a:cc|L}).
| ?- r({b:bb,a:aa},L).
L       = {a:cc,b:bb}

型付素性構造型モード (モード 2)

まず型どうしの単一化が試みられ、それに成功すると、引き続いて素性構造の単一化が行われます。素性構造の内部についても、再帰的に同様の処理が繰り返されます。素性構造自体の単一化の仕組みはモード1と同じです。

型の単一化とは、両方の型の subtype の中で最も一般的な型を見つけることです。次のような型定義においては、a と b を単一化すると b に、 b と c を単一化すると d になります。b と e は単一化することができません。

% 型定義
a <- [bot] + [f:atom, g:atom].
b <- [a].
c <- [a].
d <- [b, c].
e <- [a].

この型定義をもとにして型付素性構造の単一化を行ったのが以下の例です。

| ?- X = a&{p:s}, X = a&{q:t}. % モード 1 でも 2 でも同じ結果
X = a&{p:s, q:t}.
yes

| ?- X = b&{p:s}, X = c&{q:t}. % モード 1 だと b も c も単なるアトムなので失敗する
X = d&{p:s, q:t}.
yes

| ?- X = b&{p:s}, X = e&{q:t}. % モード 2 でも型の単一化ができなければ失敗する
no

詳しくは、9-2-6.型付素性構造の詳細 を参照してください。

ソース ($InstallDir)/system/pl/fs_utility.pl

＜ 1: 素性と値の対 と 素性,素性値の相互変換＞
fs_av/3
(1)Arg1の <素性と値の対> からArg2：素性,Arg3：素性値へ分解
(2)Arg2：素性,Arg3：素性値　から＜素性と値の対＞を生成します。

|?- fs_av(attr:value,A,V).
A  = attr,
V = value
yes

|?- fs_av(AV,attr,value).
AV = attr:value
yes

＜ 2:素性構造とコア構造(','/2)の相互変換 ＞
fs_body/2
(1) Arg1:素性構造からArg2:コア構造を取り出します。
(2) Arg2:コア構造をArg1:素性構造へ変換します。

|?- fs_body({a:bb},Core). 
Core = (a:bb,_)
yes

|?- fs_body(FS,(a:bb,_)).   
FS   = {a:bb}
yes

＜ 3:動的に素性構造を生成します ＞
fs_new/3
Arg1を素性名、Arg2を値とする素性構造を生成し、Arg3に単一化します。

|?- fs_new(a,aaa,X).             
X  = {a:aaa}
yes

|?- Q=q,fs_new(Q,S,X).           
X  = {q:S}
yes

|?- X={a:b},Q=q,fs_new(Q,S,X).   
X  = {a:b,q:S}
yes

＜ 4:素性構造の全要素をリストに展開します ＞
fs_list/2
(1)素性構造(Arg1)の全要素をリスト(Arg2)に展開します。
(2)リスト(Arg2)を素性構造(Arg1)に変換します。

|?- fs_list({category:noun_phrase,number:singular},L).
L = [category:noun_phrase,number:singular]
yes

|?- fs_list(FS,[category:noun_phrase,number:singular]).
FS = {category:noun_phrase,number:singular}
yes

|?-X={a:bb,c:dd},fs_list(X,L),fs_list(X,[e:qq]).
X       = {a:bb,c:dd,e:qq},
L       = [a:bb,c:dd]
yes

＜ 5:ある素性:値が素性構造に含まれているか調べます ＞
fs_member/2
Arg1調べる要素側の変数は単一化するが　リストの要素を調べるmember/2と異なり、Arg2素性構造側は単一化はしません。単一化したい時は、後述のpvalue/3を利用します。

|?- fs_member(number:X,{category:noun_phrase,number:singular}).
X = singular
yes

| ?- fs_member(number:X,{category:noun_phrase,number:Y}).
X = X_20, Y = Y_22
yes

| ?- fs_member(number:d,{category:noun_phrase,number:X}).
no

| ?- fs_member(number:X,{category:noun_phrase,number:{p:Y}}).
X = {p:_20}, Y = Y_22
yes

| ?-fs_member(a:{b:bb,c:X},{a:{c:1,b:bb}}).
X       = 1
yes

＜ 6:素性構造のコピー ＞
fs_copy/2
Arg1の素性構造を制約情報を含めた同一構造にコピーしArg2に単一化します。

|?- s_constraints_mode(_,on).
yes
|?- X={a:P#(P=A),b:A},fs_copy(X,Y),Y={a:aa}.
X       = {a:_75,b:A_63},
P       = _75,
A       = A_63,
Y       = {a:aa,b:aa}
yes

＜ 7: 素性構造の結合 ＞
fs_append/3
二つの素性構造を元の素性構造は変えず結合した新しい素性構造を生成しArg3に単一化します。

|?- X={a:S,b:bb},Y={b:Q,e:S},fs_append(X,Y,Z).
X  = {a:S_62,b:bb},
Y  = {b:Q_70,e:S_62},
Z  = {b:bb,e:_160,a:_160}
yes

単純に二つの素性構造を結合するだけなら、素性構造のユニフィケーションでよいでしょう。

|?- X={a:aa},Y={b:bb},X=Y.
X= {a:aa,b:bb},
Y= {a:aa,b:bb}
yes

＜ 8:任意個の素性構造を結合 ＞
fs_appends/2
複数の素性構造を結合した新しい素性構造を生成しArg2に単一化します。

|?-X={a:S,b:bb},Y={b:Q,e:Q},fs_appends([X,Y,{a:Q}],D).
X       = {a:S_70,b:bb},
S       = S_70,
Y       = {b:Q_78,e:Q_78},
Q       = Q_78,
D       = {a:bb,b:bb,e:bb}
yes

＜ 9:素性構造に含まれる素性リストをArg2に単一化する ＞
pnames/3 (Cu-Prolog 組込互換）
Arg1を素性名、Arg2を値とする素性構造を生成し、Arg3に単一化します。

|?- pnames({a:aa,b:bb,c:cc},L).  
L = [a,b,c]
yes

＜ 10:素性構造(Arg1)に含まれる素性(Arg2)の値をArg3に単一化します ＞
pvalue/3 (Cu-Prolog 組込互換）
相当する素性がない場合にはfail します。

|?- pvalue({a:aa,b:bb,c:cc},b,V).  
V = bb
yes
|?- pvalue({a:aa,b:bb,c:cc},q,V).  
no

|?- FS={a:aa,b:bb,c:cc,q:C}, pvalue(FS,q,1).  
FS      = {a:aa,b:bb,c:cc,q:1},
C       = 1
yes

% 深い階層の素性へのアクセスの簡略表現
|?- pvalue({a:aa,b:{d:dd,q:{f:bb}},c:cc},b:q:f,V).  
V = bb
yes

＜ 11:素性構造をAVM形式で表示します ＞
fs_writeAVM/1

| ?- fs_writeAVM({ 氏名:山田太郎,生年月日:{年:1951,月:5,日:26},趣味:X }).
 |~                    ~|
 | 氏名:    山田太郎    |
 | 生年月日:|~       ~| |
 |          | 年:1951 | |
 |          | 月:5    | |
 |          | 日:26   | |
 |          |_       _| |
 | 趣味:    X_56        |
 |_                    _|
X       = X_56
yes

ICOTで開発された CU-Prologに付属のサンプルプログラム、シンプルHPSGをAZ-Prolog用に書き換えたものが
sample/nluに格納されていますので、これを動かしてみましょう。

%%%%%%%%%% hpsg.pl %%%%%%%%%%%%%%
:- ['tree.pl'].         % CU-Prologの組込述語 tree/1 をAZ-Prolog用に書いたもの
p(Sentence):-
	parse0(Cat,H,Sentence,[]),
	nl,tree(H),nl,write('category= '),write(Cat),nl.

parse0(MCat,MHist,Str,Rest):-
	lookup(Str,SubStr,Cat,Hist),!,
	parse1(Cat,Hist,MCat,MHist,SubStr,Rest).

parse1(Cat,H,Cat,H,Str,Str).
parse1(LCat,LHist,GCat,GHist,Str,Rest):-
	psr(LCat,RCat,MCat,RN),
	parse0(RCat,RHist,Str,SubStr),
	parse1(MCat,t(t(MCat,RN,[]),LHist,RHist),GCat,GHist,SubStr,Rest).

%     LeftCategory               RightCategory              MotherCategory

psr({head/H, sc/[RH|PSC],ph/LP},{head/RH,sc/[],ph/RP},     {sc/PSC,head/H,ph/PP},1):-append(LP,RP,PP).
psr({head/RH,sc/[],      ph/LP},{head/H,sc/[RH|PSC],ph/RP},{sc/PSC,head/H,ph/PP},2):-append(LP,RP,PP).

lookup([Word|X],X,{ph/[Word],head/Cat,sc/SC},t(Cat,[Word],[])) :-dict(Word,Cat,SC).

dict(mary, noun, []).
dict(john, noun, []).
dict(meets,verb,[noun,noun]).
    % : 以下の単語定義略
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

＜実行例＞

>prolog
|?- consult('hpsg.pl').
yes
|?- p([mary,meets,john]).

{sc/[],head/verb,ph/[mary,meets,john]}---1
 |--{sc/[noun],head/verb,ph/[mary,meets]}---2
 |   |--noun---[mary]
 |   |__verb---[meets]
 |__noun---[john]

category= {sc/[],head/verb,ph/[mary,meets,john]}
yes

9-2-6.型付素性構造の詳細へ続きます。