マ ル セ イ ユPrologシ ス テ ム の 拡 張
杉 本 英 二
要 約
マ ル セ イ ユPrologの 機 能 をDEC‑10Prolog水 準 ま で 高 め る た め に,Fortran 組 込 述 語 と モ ニ タ 組 込 述 語 を 追 加 ・拡 張 し て 良 好 な 結 果 を 得 た 。 こ の 作 業 で,
マ ル セ イ ユPrologシ ス テ ム の 移 殖 と拡 張 の 良 さ を 確 認 し た 。
0.は じ め に
1973年 頃,Prologと い う 名 の 新 し い 言 語 が フ ラ ン ス ・マ ル セ イ ユ に 生 れ て か ら,ほ ぼ10年 が 経 過 した 。 最 初 のPrologはFortronに よ る イ ン タ プ リ タ [Bat]で あ っ た が,1977年 に はDEC‑10シ ス テ ム に ア セ ン ブ ラ で 書 か れ た コ ンパ イ ラ を 含 むPrologシ ス テ ムが 作 ら れ た[Per]。Warrenら は,こ の シ ス テ ム を 人 工 知 能 用 言 語 と して 高 い評 価 と 実 績 を 持 つLispと 比 較 し,適 合(U‑
nification)と い う 高 水 準 機 能 を 計 算 の 中 心 に 採 用 して い る に も か か わ らず 」 そ の 計 算 速 度 は 遅 く な い と 報 告 した[War]。 こ の 報 告 以 降,Prologは 人 工 知 能 用 の 言 語 と して 実 用 的 な 言 語 と み な さ れ る よ う に な っ た 。
マ ル セ イ ユPrologシ ス テ み は 移 殖 性 が 高 いFortranで 書 か れ て い た が,当 初 か らマ ニ ュ ァ ル の 不 備 が 原 因 で 移 殖 に は 苦 労 が 多 か ったrKlu1,[Su11。 日 本 で は,電 子 技 術 総 合 研 究 所 に お い て,こ のPrologが 最 初 に 移 殖 さ れProlog 研 究 の 開 始 と な っ た 。
一 方,DEC‑10Prologは ア セ ン ブ ラ記 述 で あ った た め 高 速 で あ り,ま た 組 込 述 語 も豊 富 で あ り,さ らに 利 用 者 マ ニ ュ ア ル[Per],が 完 備 さ れ て い た の で 多 くの 研 究 者 に 広 が っ た。 そ の 後Prologの 教 科 書 と い わ れ る 本[Clo]が こ の
原 稿 受領 日 昭 和59年11月21日
〔139〕
言 語 を 標 準 に 書 か れ,DEC‑10PrologはPrologの 標 準 と み な さ れ る よ う に な った 。
筆 者 は,]981年 に マ ル セ イ ユPrologを 本 学 の 計 算 機MECLOM‑COSMO
700Sに 移 殖 し た[Su1]。 そ の 後,述 語 名 を 仏 語 表 現 か ら英 語 表 現 へ 改 め,よ り 簡 便 に 使 う た め に フ ァ イ ル な ど か らPrologプ ロ グ ラ ム を 読 込 む 専 用 の 述 語 な ど を 付 加 し て,教 育 用 のPrologS言 語[Su2]を 作 った が,デ ー タ ベ ー ス 中 の 節 を 取 出 せ な い と い う基 本 的 な 問 題 点[Su1][Su2]は 残 っ た ま ま で あ っ た 。 DEC‑10PrologをCOSMO700Sに 移 殖 で き な い 以 上,考 え られ る選 択 は UlispP上 にProlog/KR[Nak]な ど のPrologイ ン タ プ リ タ を 移 殖 す る こ と と,
こ の マ ル セ イ ユPrologを 拡 張 す る こ と 以 外 に,DEC‑10Prolog水 準 のProlog を 手 に 入 れ る 方 法 が な い 。
筆 者 は,Lispを 持 た な い 計 算 機 で もPrologを 移 殖 し う る マ ル セ イ ユProlog の 拡 張 を 選 択 し,こ の 拡 張 が 可 能 か ど うか の 検 討 の た め マ ル セ イ ユPrologシ
ス テ ム の 解 読 作 業2〕を 行 って 次 の こ と が わ か っ た 。
① シ ス テ ム の 構 造 は 十 分 洗 練 さ れ て い て 理 解 容 易 で あ る こ と 。
②PrQlog文 法 は 固 定 さ れ て お らず,自 由 に 書 換 え る こ と が で き る こ と。
③ 新 規Fortran組 込 述 語 を 組 込 む こ と は 容 易 で あ る こ と 。
④ 適 合 操 作 の 実 現 は 構 造 共 有 方 式 が と られ て い て,現 在 の 実 現 手 法[Nij]
と 比 較 し て も 遜 色 は な い こ と 。
す な わ ち,マ ル セ イ ユPrologは,Fortranで 書 か れ た イ ン タ プ リ タ の た め に 遅 い と い う 唯 一 の 欠 点 が あ る に せ よ,マ ニ ュ ァ ル さ え 整 備 さ れ れ ば 移 殖 性 の 良 い ソ フ トウ ェ ア で あ り(①),拡 張 性 に 富 み(②,③),Pro1Q9の 本 体 は 今 だ に 時 代 遅 れ で は な い(④)の で,不 足 して い る 組 込 述 語 を 補 え ば 十 分 現 役 で 使 え る も の で あ る 。
1)畝 見 達 夫 氏 が 開発 したMEI.COM‑COSMO上 のL、isp1.9[Une]を 本 学 の 若林 信夫 助 教授 が 移殖 した 。
2)工 業 技 術院 電 子 技 術 総 合 研 究所 の 新 田克 己氏 か らの 移 殖 時 の様 々 な助 言 と デ ー タ構 造 等 に つ い て の ノ ー トが 唯 一 の 資 料 で あ った。 同氏 に深 く感 謝致 しま す。 ま た こ の 解読 作 業 を手 伝 って くれ た 私 の ゼ ミナ ー ル卒 業 生 の 若 林 厚 志,和 田雅 孝,山 田一 雄 の3君 に感 謝 致 します 。
マ ル セ イ ユPrologシ ス テ ム の 拡 張 141
こ の 度,マ ル セ イ ユPrologシ ス テ ム と イ ン タ プ リ タ に つ い て の 資 料 を 作 成 し31,.新 し く節 取 出 しの 述 語 を 組 込 み 「拡 張 マ ル セ イ ユProlog(PrologE)」
を 作 っ た の で 報 告 す る 。 』 ・
今 回 の 拡 張 作 業 で,筆 者 は マ ル セ イ9ユPrologシ ス テ ム の 入 力 と 出 力 と が, そ れ ぞ れ1文 字 単 位 の 入 力 と 出 力 の 組 込 述 語 だ け で 制 御 さ れ て し)るの を 発 見 し て,こ の シ ス テ ム の 非 常 に 大 き な 柔 軟 性 に 驚 ろ.かさ れ た 。 開 発 者 達 は,最 も根 元 的 な 述 語 の み をFortranで イ ン タ プ リ タ に 組 込 み,シ ス テ ム の 入 出 力 を 定 め る 文 法 や そ の 他 必 要 な 述 語 をPrologプ ロ グ ラ ム で 自 由 に 定 義 で き る よ う に し て,将 来 の 変 更 を 容 易 に して お こ う と 考 え た よ う だ 。
筆 者 あ 今 回 の 拡 張 に 当 って は,シ ス テ ム の 内 部 構 造 を 見 る 基 本 的 な 組 込 述 語 を3つ 用 意 し て,現 在 の マ ル セ イ ユPrologの 問 題 点 を 解 消 す る 述 語 を輩 富 に Prologプ ロ グ ラム で 定 義 で き る よ うに した 。 こ う して,デ ー タ ベ ー ス の 内 容 の リ
ス テ イ ング と,節 の 取 出 し を 使 ってPrologの イ ン タ プ リタ を 作 成 し,ト レ ー サ ー を 提 供 す る こ とが で き た 。 そ の 他 ,イ ン タ プ リタ ・プ ロ グ ラ ム の 虫41取 り と,エ ラ ー 表 示 機 能 の 追 加 や モ ニ タ の 会 話 機 能 の 拡 張 を 行 っ た 。 オ リ ジ ナ ル の マ ル セ イ ユPrologシ ス テ ム を で き る だ け 保 存 し な が らの 拡 張 を 行 な っ た が,こ の 拡 張 に よ って,教 育 上 に も研 究 開 発 上 に も 不 自 由 は しな くな り,DEC‑10Prolog 相 当 の 機 能 を 付 加 で き た 。
ユ.マ ル セ イ ユPrologシ ス テ ム の 概 略
マ ル セ イ ユPrologシ ス テ ム は,イ ニ ジ ャ ラ イ ザ(1)と イ ン タ プ リ タ(P) の2つ の プ ロ グ ラ ム と,イ ニ シ ャ ラ イ ザ の デ ー タ(D)で 構 成 さ れ て い る 。1と PはFortranで 書 か れ,1は 約400行,Pは 約2000行 の プ ロ グ ラ ム で あ る。
Dは200行 足 らず の デ ー タ で あ る 。1とDは,P{D動 作 に 必 要 な 初 期 値 の 設 3)技 術 マ ニ ュ ナ ル と保 守 マ ニ ュ アル を 作 成 し,付 録 に一 部 を ピ ック ア ップ して 掲 載 し
た。
4)1桁 の 数 の 計算 が正 し く計 算 され な い こ と,組 込 述 語ATOME実 行後 の作 業 領 域 の 解 放 が な くメ モ リを 無 駄 に 消 費 して い た こと,組 込 述 語 の 引 数 が原 因の 構 文 エ ラ
ー を エ ラー表 示 述 語ERREUR(*X)に 伝 え る こ と がで き ず,ど ん な エ ラーが 発 生 に い た のか 不 明で あ った こ と。
を 行 う 。
〔イ ン タ プ リ タPの 概 略 〕
イ ン タ プ リタ ・プ ロ グ ラ ム の 概 略 を[図1]に 示 す 。 導 出 の 制 御 は す べ て RESOUDで 行 な わ れ る。 組 込 述 語51が 目 標 の 場 合 に は 対 応 す るFortran組 込 み の サ ブ ル ー チ ンが 実 行 さ れ,利 用 者 定 義 の 述 語 の 場 合 に はRESOUDが 目 標 側 の イ ン ス タ ン ス(INSTR,CLAUSR)と 節 側 の イ ン ス タ ン ス(INSTA,CLAU 'SA)を 設 定 し(例[図A5(a)])
,そ れ らの 適 合 をUNIFIEが 行 な う。
DESCは,変 数 の バ イ ン デ イ ン グ 先 の ア ド レ ス を 探 し,SOREVは 組 込 述 語 の 実 行 後 の あ と 処 理 を 行 な い,SAUTは 項 の 構 造 体 の 中 か ら1っ の 構 造 を 切 出
し,BACKTは 再 試 行 の 制 御 を 行 う。
イ ン タ プ リ タ に は,こ の よ う にProlog文 法 を 定 め る 部 分 がFortranと して . 組 込 ま れ て お らず,単 に1文 字 入 力 の 述 語LU(*X)とLUB(*X),そ して1 文 字 出 力 述 語ECRIT(*X)の み が 用 意 さ れ て い る の み で あ る の で,Prologプ
ロ グ ラ ム や 質 問 の 入 力,あ る い は 結 果 の 出 力 な ど は 別 途 与 え な け れ ば な らな い 。 そ こ で こ れ らの 働 き を す るProlo9プ ロ グ ラ ム(モ ニ タ)を 与 え,こ れ の 制 御 下 に シ ス テ ム の 入 出 力 を 行 な う 。 モ ニ タ の 起 動 は イ ン タ プ リ タが,
?‑BOULOT.̀
MAIN一 照SOU DESC SOREV UNIFIE SAUT BACKT LU UNIV
LEGALF
}一 }
29個 の組 込 述 語 に対 応 す る17個 のサ ブ ルー チ ン
[図1]イ ン タ プ リ タ ・ プ ロ グ ラ ム あ 概 略 図
5)[Su1][Su2]を 参 照 の こ と 。
マ ル セ イ ユPrologシ ス テ ム の 拡 張 143
を 最 初 の 目標 と して 実 行 す る こ と で 行 な わ れ る 。 こ れ に よ っ て,一 担 モ ニ タが 起 動 さ れ る と シ ス テ ム の す べ て の 制 御 は モ ニ タ と して 書 か れ たPrologプ ロ グ.
ラ ム に よ っ て 行 な わ れ る 。
〔モ ニ タ の 入 力 〕
モ ニ タ はPrologプ ロ グ ラ ム だ が,イ ン タ プ リ タPが 動 作 す る た め に は,モ ニ タ は デ ー タ ベ ー ス に 内 部 の 表 現 形 式(付 録 の デ ー タ構 造 参 照)で 書 か れ て い な くて は な らな い 。 こ の モ ニ タ の 情 報 を イ ン タ プ リ タ の 実 行 に 先 立 って,デLニ
タ ベ ー ス に 書 込 む の が,イ ニ シ ャ ライ ザ1で,そ の た め の デ ー タ がDで あ る。
Dに は,Prologで 使 え る63個 の 基 本 文 字,イ ン タ プ リ タ が 直 接 参 照 す る 特 殊 な 述 語 関 数 の 定 義,モ ニ タ で 使 わ れ る 述 語 関 数 名 の 定 義 と モ ニ タ プ ロ グ ラ ム 自 体 が 含 ま れ て い る 。 こ れ ら は,付 録[図A1]の よ う にTABの1か ら5227 ま で に 展 開 さ れ る 。 そ の 他,Dに は,文 字 コ ー ドか らデ ー タ ベ ー ス 中 の 文 字 定 義 ア ド レ ス に 変 換 す るCALCULの デ ー タ も 含 ん で い る 。 も し コ ー ド体 系 を ASCIIか らEBCDICに 変 更 した い と き は こ こ を 変 更 す るだ け で,イ ン タ プ リ タ に は ま った く手 を 加 え る 必 要 は な い 。
〔モ ニ タ 用 の ソ ー ス プ ロ グ ラ ム 〕
モ ニ タ は,利 用 者 と シ ス テ ム の コ ミュ ニ ケ ー シ ョ ン を 行 な う部 分 で,い わ ば 会 話 形 シ ス テ ム の 顔 で あ る 。 適 切 な メ ッ セ ー ジ,あ る い は 文 法 の 変 更 な ど の よ う な 利 用 者 か ら 見 え る 姿 を 良 くす る た め に,モ ニ タ に 修 正 や 変 更 が 加 え ら れ る 。 と こ ろ が,Dに 書 か れ た ソ ー ス プ ロ グ ラ ム の 変 更 は か な り 煩 わ し い 。 例 え ば,
リス トの 接 合 は +APPEND(NIL,*Y,*Y).
+APPEND(*A.*X,*Y,*A.*Z)‑ApPEND(*X,*Y,*Z).
と書 か れ る が,Dで は こ れ を 1.2+1APPEND3NILOllNILO
4.2+1APPEND3.2123.214.2‑1APPEND3234NILO
と 書 か ね ば な ら な い 。
そ こ で,筆 者 は 上 の 表 記 の モ ニ タ ソ ー ス プ ロ グ ラ ム を 下 の 表 記 に 変 換 す る ア プ リケ ー シ ョ ンを 開 発 し た が,そ の た め に マ ル セ イ ユPrologシ ス テ ム の 文 法 上 の 拡 張 が 必 要 で あ っ た 。
乳 マ ル セ イ ユPrologに 不 足 し て い る 機 能
本 章 で は,DEC‑10Prologと 比 較 し て,文 法 上 の 形 式 的 な 点 や,組 込 述 語 に 対 す る 多 少 の 見 解 の 違 い は 別 に し て,真 に 不 足 して い る機 能 は 何 か を 検 討 す る 。
筆 者 はPrQlogシ ス テ ム を 利 用 者 側 か ら評 価 す る 場 合,[図2]の よ う に,副 作 用 を ま っ た く持 た な い枠 組 み だ け の 純Prologの 部 分,副 作 用 を 起 こ す 組 込 述 語 の 部 分,ProlQ9の プ ロ グ ラ ム の 表 現 を 規 定 す る 文 法,以 上 の3点 と,Pro.
Iogの 開 発 ・操 作 等 を ス ム ー ズ に 行 な う た め に 用 意 さ れ た 環 境 を 考 慮 し て い る 。 こ の う ち,純Prologは ど のPrologシ ス テ ム も共 通 の 入 力 導 出 法 そ の もの で あ る の で,シ ス テ ム に よ っ て 差 は 少 な い 。'
〔組 込 述 語 に つ い て 〕
ClocksinとMellishは,そ の 本[Cユo]の 中 で 組 込 述 語 の 章 を13に 分 け て 説 明 し て い る の で,こ れ に そ って 顕 著 な 点 の み を 指 摘 す る。
■ 一[図2]利 用 者 か ら見 たPrologの 姿
マ ル セ イ ユPrologシ ス テ ム の 拡 張 145
〔1>新 し い 節 の 入 力:ど ち ら も ほ ぼ 同 じ 機 能 を 持 っ て い る 。 マ ル セ イ ユPro‑
logは,読 込 む フ ァ イ ル を あ れ こ れ と 変 え る こ とが で き な い の で,急 に 他 の フ ァ イ ル 中 の プ ロ グ ラ ム が 必 要 に な った と き 不 便 で あ る 。
(2)節 の 項 と し て の 操 作:デ ー 多 ベ ー ス 中 の 節 を リ ス テ イ ン グ し た り,節 を 項 と し て 取 出 す こ と が で き な い の で,非 常 に 不 便 で あ る 。 節 を デ ー タ ベ ー ス に 登 録 す る 機 能 は あ る 。
⑧ 一 般 的 な 構 造 の 要 素 の 生 成 と ア ク セ ス:構 造 を 分 解 し た り 合 成 した り す る に はUNIVの み しか な い が,DEC‑10Prologの よ う に 豊 富 な 機 能 が あ れ ば 便 利 で あ る 。
㈱ フ ァ イ ル の 操 作:実 行 中 フ ァ イ ル を 開 い た り 閉 じた りす る機 能 は な い 。
・(5)PrologQ動 作 の 観 察:ト レー スや デバ ッ ク の た め の 用 意 は ま っ た く な い。
〔文 法 〕'
文 法上,演 算 子 の 宣 言が 可能 で あ るが,モ ニ タ中 の構 文 解 析 プ ロ グ ラムの 演 算 子 チ ェ ッ クの部 分が 不 完 全 な た め,節 の 表 現 に制 約 が あ る 亡Su2]。 この 制 約
を 解 消 した い。
そ の他,記 号 文字 は1字 の ア トム に限 定 さ れ て い るが,こ れ ら も英 字 と混 用 で き るよ うに 文法 を拡 張 した い。 これ は,モ ニ タ ソー ス プ ロ グ ラ ムの 表 現 の 変 換 に必 須 の 条 件 で あ る。
〔Prolo9の 環 境 〕
Prologシ ス テ ム は,完 成 し たPrologプ ロ グ ラ ム を 実 行 す る こ と の た め よ り も,プ ロ グ ラ ム 開 発 の た め に 使 わ れ る こ と の 方 が 多 い 。 そ の た め に,デ バ ッ ク の た め の プ ロ グ ラ ム の リ ス テ イ ン グ や ト レ ー ス な ど の 機 能 が 必 須 の 条 件 で あ る 。 特 に ダ イ ナ ミ ッ ク に 再 試 行 を 繰 返 す 言 語 で あ るか ら他 の 言 語 以 上 に 必 要 で あ る が,マ ル セ イ ユPrologに は,こ の た め の 用 意 は な く,そ の た め の 手 が か り さ え な い 。 上 記 の 組 込 述 語 ② の 節 の 取 出 しが で き れ ば,そ れ を 基 に,リ ス テ イ ン
グ や ト レ ニ ス のPrologプ ロ グ ラ ム を 開 発 す る こ と は 容 易 で あ る。
マ ル セ イ ユPrologシ ス テ ム は,節 を 消 す 組 込 述 語 を 持 って い る が,メ モ リ 上 で 実 際 に 消 さ れ る 訳 で は な い 。 こ の 操 作 を 多 用 す る と 有 効 メ モ リが 減 り実 行 不 能 に 陥 る。 こ れ を 回 復 歩 る に は 節 の 再 読 込 み し か な い が,そ れ に は デ ー タ ベ
ー ス 中 の 節 を 取 出 して フ ァ イ ル に 書 出 す こ と が 必 要 に な る 。
こ の よ う に,節 の 取 出 し は マ ル セ イ ユProlo9の 最 も緊 急 の 課 題 で あ る。
3.拡 張 と 実 現 法
(1)フ ァ イ ル の 操 作 の た め の 組 込 述 語 を 使 っ て,新 し い 節 入 力 用 の 述 語 を モ ニ タ で 定 義 し た 。
(21節 を 取 出 す た め の 基 礎 的 組 込 述 語 を 使 って,節 取 出 し と リ ス テ イ ン グ 用 の 述 語 を 定 義 し た 。
(3)UNIVを 使 っ て,functor(X,Y,Z)を 定 義 し た 。
〔4}FortranにOSの フ ァ イ ル 操 作 を 呼 出 す サ ブ ル ー チ ン を 用 意 して,組 込 述 語FILEOPEN(*X,*Y,*Z),FILECLOSE(*X)を 作 っ た 。*XはDCB
名,*Yは フ ァ イ ル 名,*ZはINかOUTで あ る 。 こ れ ら を 使 って,see, seen,teU,toldに 当 る述 語 を 定 義 し た 。
{5}節 取 出 しの 述 語 を 使 っ て,Prologに よ るPrologイ ン タ プ リタ を 作 成 し, ト レ ー ス の た め の メ ッ セ ー ジを 出 力 で き る よ う に した 。
〔文 法 〕
DEC‑10PrologのOP(precedence,type,name)構 文 を 採 用 し,モ 子 タ を 書 換 え た 。 一 重 引 用 記 号 ▼で 囲 ま れ た 部 分 を ア トム と す る よ う に モ ニ タ を 書 換 え た 。
〔Prolo9のi環 境 〕
節 取 出 し述 語 に よ っ て,ト レ ー ス 機 能 は 解 決 し た 。 こ の 機 能 と して,各 節 イ ン ス タ ン ス を 表 示 す る もの と,L.Byrdの 箱 モ デ ル 表 示 の2種 ⑱ ト レ ー ス を 用 意 した 。
マ ル セ イ ユ'Prologシ ス テ ム の 拡 張 147
カ ー ベ ー ジ コ レ ク シ ョ ン相 当 の 機 能 は,一 担 節 を フ ァ イ ル に 退 避 し,そ れ を 再 読 込 み す る こ と に し た 。
そ の 他 に,モ ニ タ ・ソ ー ス プ ロ グ ラ ム の 変 換 プ ロ グ ラ ム は, 文 法 を拡 張 した こ と で 作 成 で き た 。 組 込 述 語 の 手 ラ ー 処 理 ル ー チ ンに 誤 ま りが あ っ て エ ラ ー の 内 容 が 表 示 さ れ て い な か った の で 訂 正 し,さ ら に エ ラ ー を 含 む 節 と こ の 節 ま で の祖 先 も表 示 して デバ ック性 能 を 向上 させ た 。
〔節 取 出 し述 語 の 実 現 法 〕
こ れ らの 拡 張 の 一 部 で あ る節 の 取 出 し述 語 の 実 現 法 を 述 べ る 。DEC‑10Pro一 logのclause(X,Y)をFortran組 込 述 語 と して 組 込 む こ と は,マ ル セ イ ユ Prologの 仕 組 上 で き な い61。 そ こ で,1つ の 節 だ け 取 出 す 組 込 述 語CLAUSEG ET(*X,*Y)7)を 用 意 し,デ ー タ 構 造 に 従 い81再 試 行 の 度 に 順 番 に 上 か ら節 を
+GETCLAUSE(★TERM,★CLAUSE》
‑PO工NTER{★TERM
,★ENTRY,★ANY)
‑PLUS(★ENTRY
,1,★PRED》
‑TAB(★PRED,★ACP工 、,+》
‑L田(0 ,★ACPL)
‑TAB(★ACPL,★CLO,+)
‑Llr(0 ,★C五 〇)
‑GETCX(★CLO
,★CLAUSE).
+GE田CX(0,★W)
一/(一(GETCLAUSE(★X ,★Y)D
‑FA工L . +GETCX(★CLO,★CLAUSE》
‑CLAUSEGET(★CLO
,★CLAUSE》.
+GETCX(★CLO,★CL猷JSE》
‑PLUS(★CLO ,1,★SU工V)
‑TAB(★SU工V,★NEXTCLO,+》
‑GETCX(★1マEXTCLO ,★dLAUSE).
[譜1]
6)付 録A.4.に よ れ ば,組 込 述 語 は 再 試 行 さ れ な い 。 と こ ろ が,clause(X,Y)は 次 の 節 を 取 出 す た め に 再 試 行 で き な くて は い け な い 。 ・ 7)*Xがcloア ド レ ス の と き*Yはcloが 指 し て い る 節 で あ る 。
8)[図A31を 参 照 。
+CLAUSE(★X,★Y)‑GETCLAUSE(★X,+(★X).★Y).
[譜2]
+SET ̲OF̲CLAUSES(★TERM,★L工ST)
」PO工 煎TER(★TER腿 θ★E斑TRY r★ANY)
‑PLUS(★ENTRY
,1,★PRED)
‑TAB(★PRED,★ACPL,+》
‑LT(0
,★ACPL)
‑TAB(★ACPL,★CLO『,+》
‑LT(0 ,★CLO)
‑SOC(★TERM,★CLOr★L工ST》 . +SOC(★TERM,0,N工L).
+SOC《 ★TERM,★CLO,★C.★ 工」工ST》
‑C工 」AUSEGET(★C丑0,★C)
‑CHECIく(SOC
̲PATTERN(★TERM,★C》)
‑PLUS(★CLO,1,★SU工V}
‑TAB《 ★SU工V,★NCI」0,+》
‑SOC(★TER麗
,★ 四CLO,★L工ST).
+SOC(★TERM,★CLO,★L工ST)
‑PLUS(★CLO r1,★SU工V}
‑TAB(★SU工V,★ 煎CLO,+》
‑SOC(★TERM ,★NCLO,†L工ST).
+SOC ̲PATTERN《 ☆TERMr+(★TERM).★BODY). 1 +CHECK(★X)一 餌OT(NOT(★X)).
+NOT《 ★x)一 ★x‑/‑FA工L.
+NOT(★X》.
[譜3]
取 出 すGETCLAUSE(*X,*Y)9)を[譜 ユ]で 示 す よ う に 定 義 し た 。 この プ ロ グ ラ ム に 使 わ れ て い るTAB(*X,*Y,*Z)Io),PαNTER(*X,*Y,
*Z)ω は 今 回 の 拡 張 で 内 部 構 造 を 見 る た め に 組 込 ま れ た 述 語 で あ る。
CLAUSE(*X,*Y)は,*Xが 節 頭 と 適 合 す る時 に,*Yは そ の 節 体 と な る 9)*Xが 節 頭 の 関 数 子 と 同 じ名 前 と 引 数 を も つ 項 の と き,*Yは 節 で あ る 。
10)*Xが デ ー タ ベ ー スTABの ア ド レ ス で あ る と き,*Yは そ の ア ド レ ス の 値 で,*Z は そ の 符 号 で あ る 。
11)*Xが 項 イ ン ス タ ン ス で あ る と き,*Yは そ の 構 造 の ア ド レ ス で,*Zは ア ド レス の 値 で あ る 。
マ ル セ イ ユPrologシ ス テ ム の 拡 張 149
訳 だ か ら,マ ル セ イ ユProlog文 法 に 従 っ て,[譜2]の よ う に 定 義 で き る。
以 上 の3つ の 組 込 述 語 か ら,副 産 物 と して デ ー タ ベ ー ス 中 の 複 数 の 節 を1つ の リス ドに ま と め る 述 語SET̲OF̲CLAUSES(*X, ,*Y)12)を[譜3]の よ う に 定 義 す る こ と もで き,こ れ ら の 新 し い 組 込 述 語 は 非 常 に 有 効 で あ った 。
4.参 考 文 献
[Bat]
[elo]
[Klu]
[Na幻
[Nij]
[Per]
[SuI]
[Su2]
[Une]
[War]
G.Battani,H.Meloni,"InterpreteurduLangagedeProgram‑
maもionProlo琴",Grouped'lnteiligenceArtificielleMarseilヱe‑Luminy, (1973)。
W.F.Clocksin,C.S.Mellish,"ProgramminginProlog",Springer‑
Verlag(1981).
F.Kluzniak,"THÈMARSEILLEINTERPRETER'‑APERSONAL PERSPECTIVE"inimplementationsofPROLOG,EllisHorwood (1984).
H.Nakashima,"Prolog/KRUser'sManua1"東 京 大 学 大 型 計 算 機 セ ン タ ー(1983)
。
日 本 情 報 処 理 開 発 協 会,日 本 電 子 工 業 振 興 協 会,"第5世 代 コ ン ピ ュ ー タ,ロ ジ ッ ク ・ プ ロ グ ラ ミ ン グ の 調 査 研 究"(1982).
L.M.Pereira,F.C.N。Pereira,D.H.D.Warren,"User'sGuideto DECSystem‑10Prolog",Dept.ofArtificialIntelligence,Univ.of Edinburgh,〈1978).
杉 本 英 二,̀̀述 語 論 理 型 言 語Pro1Q9の 紹 介",小 樽 商 科 大 学 商 学 討 究33‑1 (1982).
,"教 育 用Prolog言 語:PrologS",小 樽 商 科 大 学 商 学 討 究34‑3 (工984)..
畝 見 達 夫,"MELCOM‑COSMO上 で のLISP1.9の 開 発",情 報 処 理23‑1
(1982).
D.H。D.Warren,L。M.Pereira,F.C.N.Pereira,"PROI.OG‑the languageanditsimplimentationcomparedwithLISP",Proc.Symp, onAIandProg.languages,SIGPLANnotes,12,No18(1977),
12)*Xで 与 え られ る項 の 関 数 子 を 節 頭 に もつ 節 の リス トが*Yで あ る。
、
付 録
A.マ ル セ イ ユPrologイ ン タ プ リタ の 内 部 構 造 1.デ ー タ構 造
(1)デ ー タ ベ ー ス,
デ ー タ ベ ー ス は25000.次 元 の 配 列TABで,そ の 概 略 を[図A1]に 示 す 。 配 列 の サ イ ズ は 小 ・さ く も大 き く も可 能 で あ る。
(i)文 字 の 定 義
記 号 は27種,英 字 は 大 文 字 の み で26文 字 と数 字 の 計63文 字 で あ る 。 記 号 の 最 初 に 定 義 さ れ る記 号 は 空 白 で な け れ ば な らな い 。1文 字 の 定 義 に 配 列6個 を 使 い6番 目 に は, .そ の 文 字 のASCIIコ ー ドが 入 り 印 刷 た 使 わ れ る[図A2 (a)]。 文 字 の 定 義 の 順 番 は,Prologの 組 込 述 語 で 文 字 の 大 小 の 判 定 に 利 用 さ れ
る。
(iD特 殊 な 述 語 の 定 義
イ ン タ プ リ タ が デ ー タ ベ ー ス 中 の 節 を 読 取 る時 の 手 が か り と して,リ ス ト関 数 ・とNIL,正 の 句 と 負 の 句 を 作 る た め の 関 数+と 一,さ らに,モ ニ タ 起 動 用 の 節 一BOULOT.と す エ ラ ー 処 理 用 の 節 一ERREUR(*X).を 定 義 して い る 。 [図A2(c)]に リ ス ト関 数 ・の 例 を 示 す 。
TAB 1
(NIL)(・)(+}←)(BOULOT)(ERREUR)
↓ ↓ ↓ ↓
38639ユ399406 ↓ ↓
426449458
』講ゴ'粛 』薮享正 憎〕マ ヅ 酢 醜
63個 の 基 本文 字 の定 義 一BOULOT‑ERREUR(*X)
4592ヱ3825000
耀"藤 斎 鞭藩'藤 癩布
述 語 関数 名 の定i義
[図A1]TABの 概 略 図
特殊な述語関数の定義 ITERIVAR
522,!!
(a)文 字 の定 義 形 式
マ ル セ イ ユPrologシ ス テ ム の 拡 張151
注:()は ポイ ン タ を表 わす
例(・)は・の 定 義 ア ドレ スへ の ポ イ ン タ
支 字 ユー ド poidsprednom
(b)組 込 述 語LU(*X)の 述 語 名 定i義
poidsprednomaxternext 述 語 属 性 部
一1 述 話 引 用 部 kasbの 鎖
(c}リ ス ト数 関 ・の 定 義
(・)(NIL)046
記肋 文捲 醐 ↑ 述言臨 民
(・)はこ の ア ド レ ス を 指 す
(d)+FRIEND(MARY,*X)‑LIKES(*X,MARY).の 内 部 表 現
/節 の引用 ばこのア ドレス *Xは 一1で 表 わ され て い る
LIKESの 定義
[図A2]デ ー タ構 造 (iii)述 語 ・関 数 定 義 の 構 造
マ ル セ イ ユProlQ9シ ス テ ム で は,シ ス テ ム で は,述 語 と関 数 は 同 一 の 表 現 で あ り区 別 は な い 。 こ れ ら は[図A2(b)]に 示 す よ う に3つ の 成 分 か ら定 義 さ れ て
い る。 そ の 図 は 組 込 述 語LU(*X)の 例 で あ る。『poidsは 引 数 の 個 数 で あ る 。 predが 負 の 値 の と き は,そ の 述 語 がFortranの 組 込 述 語 で あ り 一nは イ ン タ プ リ タ 内 のn番 目 の 副 プ ロ グ ラ ム で 組 込 述 語 が 実 行 さ れ る こ と を 示 して い る 。 predが 正 の 値 の と き はPrologに よ る述 語 定 義 が な さ れ て お り,そ の 値 は,こ の 述 語 を 定 義 す る節 へ の ポ イ ン タ が あ る ア ド レ ス を 示 して い る 。predが 零 な ら こ の 述 語 を 定 義 す る節 が ま だ 存 在 して い な い こ と を 示 す 。 こ の 例 のLUは,引 数 を1個 持 つ1番 目 の 組 込 述 語 で あ る こ と が わ か る 。
nomは 印 字 名 部 へ の ポ イ ン タ で あ る 。印 字 名 部 は 文 字 へ の ポ イ ン タ の リ ス ト で あ る。 そ の ポ イ ン タ は 文 字 定 義 のpoidsア ド レ ス を 指 す 。 同 様 に 関 数 や 述 語 も そ れ ぞ れ のpoidsア ド レ ス を 指 す 。[図A2(c)]に 示 す よ う に リ ス ト関 数 ・ は 値 が2のpoidsア ド レス で 参 照 さ れ る。
axterは,Fortranプ ロ グ ラ ム がProlog手 続 を 経 由 せ ず に 述 語 を 引 用 す る
際 に 用 い る 。 、
next信 述 語 名 定 義 の ハ ッ シ ュ 鎖 を 作 っ て い て,次 の 述 語 名 定 義 のpoidsア ド レ ス を 指 して い る 。
述 語 引 用 部 は,関 数 子 と 変 数 を 表 わ し て い る 。 変 数 は 負 の 値 で 順 に 一1,‑2,
‑3 ,… とpoidsの 値 ま で 続 け られ る 。 リ ス ト関 数 ・の 述 語 引 用 部 の 意 味 は
・(*X ,*Y) を 表 わ し て い る 。
(iv)節 定 義 の 構 造
節 は 関 数 子 前 置(prefix)形 の リ ス トで 表 わ さ れ る。例 え ば,DEC‑10Prolog で は
friend(mary,X):‑likes(X,mary).
と 表 わ す 節 を,マ ル セ イ ユPrologで は 次 の よ う に 表 わ す 。 +FRIEND(MARY,*X)‑LIKES(*X,MARY).
し か し,内 部 で は 句 の1つ ひ と つ を リ ス トに し た 次 め 形 の 関 数 前 置 形 に な って い る 。
+(FRIEND(MARY,*X)).一(LIKES(*X,MARY)).NIL
マ ル セ イ ユProldgシ ス デ ム の 拡 張 153
FRIENDの 定 義 部 入 口
/!
poidsprednomaxternext 2
acplacmo
,
suiv
'
節+FRIEND(MARY,*X)‑LIKES(*X,MARY)の 内 部 表 現
clo
suiv .
0 節+FRIEND(MARY,JOHN)の 内 部 表 現
clo
[図A3]LIKES(*X,*Y)の 定 義 節 へ の ア ク セ ス
す な わ ち,
.(+(FRIEND(MARY,*X)),.(一(LIKES(*X,MARY)),NIL)) で あ る。 結 局[図A2(d)]と 表 わ さ れ る 。
こ の 例 で は,*Xが 一1と 符 号 化 さ れ て い るが,変 数 を 多 く含 め ば,そ れ ら は 一2,‑3と 符 号 化 さ れ る 。 節 の 先 頭 に は,そ の 節 の 中 で 使 わ れ て い る 変 数 の 個 数 が 書 か れ て い る。
さ て,述 語 の 定 義 に は 複 数 個 の 節 が 使 わ れ る。 そ れ らの 節 へ の ア ク セ ス を [図A3]に 示 す 。 こ の 例 で は,FRIEND(*X,*Y)の 述 語 名 定 義 のpreaポ イ
ン タ は,+で 始 ま る節 へ の ポ イ ン タ(acpl)と 一 で 始 ま る節 へ の ポ イ ン タ(acmo) の 対 を 指 す 。acplを た ど る と,最 初 の 節 へ の ポ イ ン タ(clO,suiv)対 に 至 り こ のclOの 値 に よ って 最 初 の 節 に ア ク セ ス で き る 。suivの 値 が 零 で な い な ら次 の 節 が 存 在 し て い る。 こ の よ う に 節 はacpエ を 入 口 と す る鎖 に 繋 が れ て い る 。
(2).ハ ッ シ ュ 表
述 語 名 定 義 へ の ア ク セ ス は,述 語 名 の 先 頭 の4文 字 をmod800で 乱 数 化 す
る 。 ハ ッ シ ュ 表 は800次 元 の 配 列CLESで あ る 。
(3)文 字 の ハ ッ シ ュ 表
読 み 込 ん だ 文 字 や 記 号 を そ れ らが 定 義 さ れ て い る デ ー タ ベ ー ス 中 の ア ド レス に 変 換 す る256次 元 の 配 列CALCULが 文 字 の ハ ッ シ ュ 表 で あ る 。
CALCUL(ASCIIコ ー ド+1) が そ の 文 字 の 定 義 ア ド レ ス を 指 す 。
(4)数 値 と 変 数
文 字 や 述 語,関 数 な ど は デ ー タ ベ ー ス 中 の ア ド レ ス で 参 照 さ れ る が,数 値 や 変 数 は 負 の 値 で 表 わ さ れ て い る。‑1か ら 一1000ま で は 変 数 で あ る。 正 の 整 数 nは,‑n‑1000の 値 で 符 号 化 さ れ る の で 一1000以 下 の 値 と な る 。 た だ し,1 桁 の 数 値 は 数 字 で 表 わ さ れ る。
2.変 数 の バ イ ン デ ィ ン グ
Prologの 実 行 時 に は,以 前 は 未 定 だ っ た 変 数 に 値 が 決 ま って く る こ と が 多 い 。 節 の 中 の1つ の 変 数 は,同 じ変 数 で あ って も節 が 次 々 と 呼 出 さ れ る た び に, そ の 値 は 異 な る の で これ ら を 呼 出 しで 区 別 す る 。 こ の 概 念 を イ ン ス タ ン ス(in‑
stance)と よ び,こ れ に よ って 変 数 を 一 意 的 に 識 別 で き る 。
す な わ ち,イ ン ス タ ン ス は 節 に 含 ま れ る 菱 数 の 解 釈 を 与 え る と 考 え て も よ い 。 例 え ば,[図A2(d)]の 節 を 指 す ポ イ ン タ をPと し,変 数*XはKENで あ
と い う イ ン ス タ ン ス を 指 す ポ イ ン タ をloと して,2組 〈lo,P>で +FRIEND(MARY,KEN)‑LIKES(KEN,MARY).
と い う 内 容 を 表 わ す 。 イ ン ス タ ン ス を 変 え て,変 数*XはBOBで あ る と い う イ ンス タ ン ス を11と す る と2組 〈Il,P>は
+FRIEND(MARY,BOB)‑HKES(BOB,MARY).
を 表 わ し て い る 。
こ の よ う な 方 法 で 動 的 に 節(あ る い は 項)の 表 現 を す る 方 法 を,構 造 共 有 方
マ ル セ イ ユPrologシ ス テ ム の 拡 張
instI2 instIl
155
変 数 一1変 数 一3変 数 一2変 数 一1
instI2のバイ ンデ ィングinstIlの バ イデ ィング情報 情報
[図A4]イ ン ス タ ンス記 述 例 式 と よ ぶ 。
マ ル セ イ ユPrologは,こ の 構 造 共 有 方 式 を 採 用 して い る 。 い く つ か の 変 数 が 節 に 含 ま れ て い る か ら,そ れ らを 順 に 一1,‑2,‑3と 符 号 化 し,こ の 殖 を 情 報 読 出 し の 基 準 点instか ら の 変 差 と 考 え る こ と に よ っ て,そ の 変 数 に つ い て の バ イ デ ィ ン グ 情 報 を イ ン ス タ ン ス の 記 述 中 か ら取 出 す こ と を 容 易 に して い る [図A4]。
イ ン ス タ ン ス の 記 述 は,デ ー タ ベ ー ス と 同 じ配 列TABの 後 方 の ス タ ッ ク に 書 か れ る。1個 の 変 数 の 記 述 に 配 列2個 を 用 い,や は り,〈lij,Pij>で バ ィ ン デ ィ ン グ を 表 現 す る 。 こ の 図 で は ス タ ッ ク は 右 か ら左(高 位 か ら低 位 ア ド レ ス) へ 成 長 す る 。
3.導 出 に よ る イ ン ス タ ン ス の 生 成
目 標 の 句 と 節 頭 の 句 と が あ って,そ れ らの 適 合(unification)操 作 に よ っ て 適 合 性 を 判 断 し,適 合 した 節 か ら適 合 後 の 節 体(導 出 形)を 得 る 操 作 を 導 出 と 呼 ぶ 。 適 合 操 作 と い う の は,目 標 の 句 と 節 頭 の 句 が,ま っ た く同 じ 表 現 に な う よ う に そ れ ら に 含 ま れ る 変 数 に 項 を バ ィ ン デ ィ ン グ す る こ と で あ る 。
o:+FRIEND(MARY,*X)‑LIKES(*X,MARY).
の 節 に 対 して,
g:?‑FRIEND(MARY,KEN).
9:
ol
CLAUSR
▼ 騨R
FRIENDMARYKEN
の定義 の定義 の定 義
LIKES の定 義
〔図A5(a)ユ.目 標gと 節oの 導 出
(つ(一} (NIL
FRIEND の定義
MARYKEN
の定義 の定義
.USR
▼
(・)(+) 一1(・)(一)‑1 (NIL)
LIKES の定義
9の 変数バ イデ ィ ング 情 報
Cの 変数バ イデ ィ ング 情報
8:
INSTR
̀
9の 変 数 バ イ.
ンデ ィ ン グ情 報
6の 変数 バ インデ ィン グ 情報
[図A5(b)]目 標gと 節 σの 導 出 形 を 新 た な 目標 とす る
と い う 質 問 を 行 う と,oの*Xに8のKENが 代 入 さ れ て,次 の 導 出 形 が 得 ら れ る:
7:‑LIKES(KEN,MARY)
この 導 出 を[図A5(a)]に 示 す 。 導 出 に 先 立 っ て,目 標 句 を イ ン ス タ ン ス と し て 特 定 す る た め に2つ の ポ イ ン タCLAUSRとINSTRが セ ッ トさ れ,節 頭 で はCLAUSAとINSTAが セ ッ トさ れ る 。 節 を 見 つ け てCLAUSAを 設 定 す る 方 法 は[図A3]で 示 さ れ る 経 路 を 通 って 行 な わ れ,INSTAは ス タ ッ ク の 頭 に 設 定 さ れ る 。 こ れ ら2つ の イ ン ス タ ン ス,
〈INSTR,CLAUSR>と 〈INSTA,CLAUSA>
の 適 合 の 結 果,INSTAの 第 ユ変 数 にKENが バ イ ン デ ィ ン グ さ れ る 。 す な わ ち, イ ン ス タ ン ス,
マ ルセ イユProlo9シ ス テ ムの 拡 張157
〈INSTR,KENの ポ イ ン タ ア ド レ ス 〉 と バ イ ン デ イ ン グ さ れ る 。
導 出 形7は,こ のoの 節 体 とINSTAで 決 定 さ れ る イ ン ス タ ン ス で あ る 。 こ れ は 次 の 導 出 の 目 標 イ ン ス タ ンス と な る も の で,[図A5(b)]に そ れ を 示 して い る 。 す な わ ち,〈CLAUSR,INSTR>が 導 出 形7で あ る 。
4.'導 出 の 制 御
導 出 の 制 御 は す べ て,11000次 元 の 配 列PILEで 行 な わ れ る 。 制 御 情 報 は こ の ス タ ッ ク に 積 ま れ る 。 導 出1回 に つ い て,そ の 制 御 情 報 が 次 の5項 目 に つ い て 記 録 さ れ る 。
(i)parp:導 出 の 目 標 側 の 句 を 含 む イ ン ス タ ン ス を 生 成 した 親 目 標 の goalpの ス タ ッ ク 中 の ア ド レ ス
(ii)goalp:導 出 の 目 標 側 の 句 へ の ポ イ ン タ
(iii)clop:目 標 の 句 に 対 応 して 選 ば れ た 節 のcloへ の ポ イ ン タ (iv)ins七ap:clopで 指 す 節 あ イ ン ス タ ン ス 記 録 ア ド レ ス
(v)trailp:再 試 行 時 に ク リア す べ き 変 数 の バ イ ン デ ィ ン グ ア ド レ ス [図A6]に[図A5(b)]の と き の 制 御 情 報 を 示 す 。
parpはgoalpで 指 す 目標 のINSTRを 探 す た め,あ る い は 導 出 終 了 後 の 次 の 目 標 ⑱ 決 定 に 使 わ れ る。goalpが 組 込 述 語 の と き は,clopは 零 で あ る 。『
goalpが 利 用 者 定 義 の 述 語 で,対 応 す る 節 が あ れ ば そ のcloア ド レ ス をclopが 指 ナ 。 しか し,こ の 節 がcutに よ り凍 結 さ れ る と き に は,clopは 零 化 さ れ る 。 イ ン タ プ リ タ は,再 試 行 時 に 新 し い 節 を 探 す た めclopを 調 べ るが,dopが 零 だ と再 試 行 を 行 な わ ず,さ ら に上 流 の 再 試 行 へ と 進 む 。 従 っ て,【組 込 述 語 は 再 試 行 さ れ る こ と が な い 。trailpの 値 だ け は 負 で 記 録 さ れ 他 の 記 録 と は 区 別 さ れ る 。 そ の 理 由 は,trailpは0個 以 上,必 要 な 個 数 だ け 記 録 さ れ る の で,一 定 の 幅 が 決 ま ら ず,特 に 他 と 区 別 す る必 要 が あ る 。[図A6]で はtrailpは な い 。
[図A6]で は,こ れ か らLIKESに 対 応 す る節 をLIKESの 定 義 を た ど り, 節 のcloア ド レ ス をclopに 書 き 込 み,CLAUSAを 設 定 す る 。 さ ら に,変 数 バ
9: (・)〔 一 (NIL) FRIEND
の定義 MARY
の定義 ⑧LAUSR INSTR
▼
o= (・)(+} 一1(・}(一) 一1 (NIL)
PILE:
pa「p clO
parp LIKES の定義
9〔ゆclopi1Btap 9ρalp
8の 変数バ イ ンデ ィン グ情報
̀の 変数 バ イ デ ィング情報
?‑FRIEND(MARY,?‑LIKES(KEN,
KEN)の 導出情報MARY)の 導出情報
[図A6]目 標gと 節 σの導 出 の制 御 情 報
イ ン デ ィ ン グ の ス タ ッ ク を 新 しい 節 の 先 頭 の 数(節 の 変 数 の 個 数,[図A2〈d)]
参 照)だ け 確 保 し,そ れ に 対 応 し たinstをinstapが 指 し,INSTAを 設 定 す る 。
こ れ で 適 合 も し く は,組 込 述 語 の 実 行 を 行 な う こ と が で き る 。
