第 ８ 章 計 算 順 序
１ ． ボ デ ィ ア ト ム の 実 行 順 序
ル ー ル が 発 火 す る と 、
ETI
は 左 か ら 順 番 に ボ デ ィ ア ト ム を 実 行 し て い く 。 以 下 に 挙 げ る ル ー ル の 例 で は 、ボ デ ィ ア ト ム が 適 用 さ れ て い く 順 序 は 、(print a)→(print b)→(print c)
の 順 に な る 。 実 際 に ル ー ル を 記 述 し 、 ボ デ ィ ア ト ム の 実 行 順 序 を 確 か め て み よ う 。(P1)--> (print a),(print b),(print c).
ボ デ ィ に あ る print は 、印 刷・改 行 を 実 行 す る 組 み 込 み 述 語 で あ る 。し た が っ て 、最 初 に 表 示 さ れ た 文 字 列 が 何 で あ る か に よ っ て 、 最 初 に 実 行 し た ボ デ ィ ア ト ム を 見 つ け る こ と が で き る 。
(print〈 対 象 〉 )
[D]>(P1)
---D execution --- a
b c
--- succeeded.
(P1)
execution time: 60 [msec]
(P1)の ル ー ル を 記 述 し
ETI
で 実 行 す る と 、 結 果 は 右 の よ う に な る 。 デ ィ ス プ レ イ の 表 示 か ら 、 a を 印 刷 ・ 改 行 し 、 次 に ｂ を 印 刷 ・ 改 行 し 、 最 後 に ｃ を 印 刷 ・ 改 行 す る と い う よ う に 、 ボ デ ィ ア ト ム が 次 々 と 実 行 さ れ た 様 子 が わ か る 。
次 に 、 以 下 に 示 す ル ー ル を 考 え る 。
① (P2) --> (print a),(P3).
② (P3) --> (print b),(P4).
③ (P4) --> (print c).
①の ル ー ル は 、「(P2)の 実 行 は 、(print a)の 実 行 の 後 で 、(P3)を 実 行 す る 」 こ と を 表 し て い る 。②の ル ー ル は 、「(P3)の 実 行 は 、(print b)の 実 行 の 後 で 、(P4)を 実 行 す る 」 こ と を 表 し て い る 。③の ル ー ル は 、「(P4)の 実 行 は 、(print c)を実 行 す る 」 こ と を 表 し て い る 。 (P2)を 質 問 と し て 与 え た な ら ば 、 実 行 結 果 は 先 程 の(P1)の 実 行 結 果 と 同 じ に な る 。 さ ら に 、(P2)の ル ー ル の ボ デ ィ ア ト ム を 入 れ 替 え て 、(P3)，(print a)の 順 で 記 述 す る と 、ど の よ う な 実 行 に な る か 試 し て み よ う 。
(P2) --> (P3),(print a).
(P3) --> (print b),(P4).
(P4) --> (print c).
[D]>(P2)
---D execution --- b
c a
--- succeeded.
(P2)
execution time: 60 [msec]
こ の よ う に ル ー ル を 入 れ 替 え て 、(P2)と 入 力 す る と 、 実 行 結 果 は 右 の よ う に な る 。(P2)が 入 力 さ れ る と 最 初 に(P3)が 実 行 さ れ る の で 、(P3)の ル ー ル が 適 用 さ れ る 。 こ の ル ー ル で b を 印 刷 ・ 改 行 し 、(P4)が 実 行 さ れ る 。(P4)の ル ー ル が 適 用 さ れ る と c を 印 刷 ・ 改 行 す る 。 こ こ ま で の 段 階 で 、(P2)の ル ー ル の ボ デ ィ ア ト ム で あ る(P3) は 実 行 を 終 え た こ と に な る 。 そ し て 、 そ の 右 に あ る(print a)を 実 行 し 全 て の 計 算 を 終 え る 。 こ の よ う に し て 、(P2)に 対 す る 実 行 は 完 了 す る 。
さ ら に 、 以 下 の よ う な ル ー ル を 記 述 す る と 、 ど の よ う に 実 行 さ れ る で あ ろ う か 。
(P2) --> (print a),(P3).
(P3) --> (print b),(P4).
(P4) --> (print c),(P2).
上 記 の ル ー ル は 、(P4)の ル ー ル が 適 用 さ れ る と 、 再 び(P2)を 呼 び 出 す よ う に な っ て い る 。 し た が っ て 、(P2)と 入 力 す る と 、 ａ ｂ ｃ ａ ｂ ｃ … と 無 限 に 印 刷 を 続 け る の で あ る 。
２ ． ル ー ル の 適 用 順 序
ETI
で は 、 与 え ら れ た 質 問 に 対 し て 、 上 か ら 順 に ル ー ル の 適 用 を 試 み る 。 行 末 ま で 探 索 し 終 え て も 、 適 用 で き る ル ー ル が み つ か ら な け れ ば 、 こ の 質 問 に 対 す る 実 行 は 失 敗 す る 。[D]>(P5)
---D execution --- a
b c
--- succeeded.
(P5)
execution time: 60 [msec]
(1) 同 じ ヘ ッ ド を 持 つ ル ー ル の 場 合
ま ず 、 次 に 示 す ル ー ル を 記 述 し て み よ う 。
(P5)--> (print a),(print b),(print c).
(P5)--> (print 1),(print 2),(print 3).
(P5)--> (print X),(print Y),(print Z).
こ れ ら の ル ー ル を 記 述 し 、
ETI
で (P5) を 実 行 し て み る と 、 実 行 結 果 は 右 の よ う に な る 。 実 行 結果 を 見 る と 、 ３ つ の(P5)の ル ー ル の う ち 、 一 番 上 に あ る ル ー ル だ け が 適 用 さ れ た こ と が わ か る 。
こ の よ う に 、 同 じ ヘ ッ ド を 持 つ ル ー ル が 複 数 個 並 ん で い る と き に は 、 一 番 上 の ル ー ル だ け が 有 効 に な る 。
(2) ヘ ッ ド に 包 含 関 係 が あ る 場 合
今 度 は 、 ヘ ッ ド に 引 数 を 持 つ 、 以 下 の ３ つ の ル ー ル に つ い て 考 え る 。
①(P5 0)--> (print 1),(print 2),(print 3).
②(P5 1)--> (print X),(print Y),(print Z).
③(P5 *X)--> (print a),(print b),(print c).
例 え ば 、(P5 0)を 入 力 す る と １ ２ ３ と 表 示 す る 。(P5 1)を 入 力 す る と Ｘ Ｙ Ｚ と 表 示 す る 。 そ し て 、(P5 2)と 入 力 す る と ａ ｂ ｃ と 表 示 す る 。 こ の 実 行 過 程 を も う 少 し 詳 し く 見 て み よ う 。(P5 0)の 場 合 、 ① の ル ー ル が 適 用 さ れ て １ ２ ３ を 表 示 す る 。(P5 1)の 場 合 、 ① の ル ー ル が 適 用 さ れ ず ② の ル ー ル に 移 る 。 そ し て 、 ② の ル ー ル が 適 用 さ れ て Ｘ Ｙ Ｚ を 表 示 す る 。 (P5 2)の 場 合 、 ① に ル ー ル が 適 用 さ れ ず ② の ル ー ル に 移 る 。 そ し て 、 ② の ル ー ル に 適 用 を 試 み る 。 こ こ で も 適 用 さ れ な い の で ③ の ル ー ル に 移 る 。 す る と ③ の ル ー ル が 適 用 さ れ て 、
a b c
を 表 示 す る 。 こ れ ら の こ と を ま と め た の が 以 下 の 図 で あ る 。(P5 0）--> (print 1),(print 2),(print 3).
（P5 *X）--> (print a),(print b),(print c).
（P5 1）--> (print X),(print Y),(print Z).
（P5 2）
質問
（P5 0）（P5 1）
答 1 2 3
X Y Z
a b c
〇
〇
× ×
×
〇
(P5 0）--> (print 1),(print 2),(print 3).
（P5 *X）--> (print a),(print b),(print c).
（P5 1）--> (print X),(print Y),(print Z).
（P5 2）
質問
（P5 0）（P5 1）
答 1 2 3
X Y Z
a b c
〇
〇
× ×
×
〇
次 に 、 先 程 の ① の ル ー ル と 、 ③ の ル ー ル を 交 換 し て 、(P5 0)や(P5 1)や(P5 2)と い う 質 問 を 与 え る と 、 実 行 結 果 は ど の よ う に な る か 試 し て み よ う 。
③(P5 *X)--> (print a),(print b),(print c).
②(P5 1)--> (print X),(print Y),(print Z).
①(P5 0)--> (print 1),(print 2),(print 3).
こ の 結 果 、(P5 0)、(P5 1)、(P5 2)は 全 て ③ の ル ー ル が 適 用 さ れ て 、 ａ ｂ ｃ と 表 示 す る 。 こ れ は 、
(ｱ ) ③ の ル ー ル 中 の *X
は ど ん な 数 に も な れ る の で 、 ル ー ル は 常 に 適 用 可 能 で あ る 。(ｲ ) ① や ② の ル ー ル よ り も 上 段 に あ る た め 、 ③ の ル ー ル が 優 先 的 に 検 査 さ れ る 。
と い う ２ つ の 点 か ら 、 ③ の ル ー ル が 全 て の 質 問 を 受 け 入 れ て し ま う の で あ る 。(P5 0）--> (print 1),(print 2),(print 3).
（P5 *X）--> (print a),(print b),(print c).
（P5 1）--> (print X),(print Y),(print Z).
（P5 2）
質問
（P5 0）（P5 1）
答 a b c
〇 〇 〇
a b c
a b c
(P5 0）--> (print 1),(print 2),(print 3).
（P5 *X）--> (print a),(print b),(print c).
（P5 1）--> (print X),(print Y),(print Z).
（P5 2）
質問
（P5 0）（P5 1）
答 a b c
〇 〇 〇
(P5 0）--> (print 1),(print 2),(print 3).
（P5 *X）--> (print a),(print b),(print c).
（P5 1）--> (print X),(print Y),(print Z).
（P5 2）
質問
（P5 0）（P5 1）
答 a b c
〇 〇 〇
a b c
a b c
(3) 繰 り 返 し 計 算 を す る 場 合
次 に 以 下 の ル ー ル に つ い て 考 え て み よ う 。
①
(
P5 *X),{(> *X 1)} --> (print a),(print b),(print c),(:= *X1 (－ *X 2)),(P5 *X1).②(P5 1)--> (print X),(print Y),(print Z).
③(P5 0)--> (print 1),(print 2),(print 3)
あ る 正 の 整 数 を 与 え て 実 行 し て み る と 、 ａ ｂ ｃ ａ ｂ ｃ … と 何 回 か 表 示 を 続 け 、 そ の 数 が 奇 数 で あ れ ば 最 後 は 必 ず Ｘ Ｙ Ｚ と 表 示 し 、 偶 数 で あ れ ば 、 最 後 は 必 ず １ ２ ３ と 表 示 す る 。 例 え ば(P5 5)と 入 力 し た と す る 。 す る と 、 最 初 に ① の ル ー ル が 適 用 さ れ る 。 ① の ル ー ル が 適 用 さ れ た こ と で 、 ａ bｃ と 表 示 し 、 ５ か ら ２ を 引 き 、(P5 3)が 実 行 さ れ る 。(P5 3)に は ① の ル ー ル が 適 用 さ れ 、さ ら に ａ ｂ ｃ と 表 示 し 、３ か ら ２ を 引 き 、(P5 1)が 実 行 さ れ る 。(P5 1)に は ② の ル ー ル が 適 用 さ れ 、 Ｘ Ｙ Ｚ と 表 示 し て 実 行 を 完 了 す る 。 こ の 実 行 過 程 の 様 子 を 次 の 図 に 示 す 。
(P5 0）--> (print 1),(print 2),(print 3).
（P5 *X),{(> *X 1)} --> (print a),
(print b),(print c), (:= *X (- *X 2)),(P5 *X1).
（P5 1）--> (print X),(print Y),(print Z).
（P5 1）
質問
（P5 5）（P5 3）
答 a b c
×
〇
a b c
X Y Z
〇 〇
(P5 0）--> (print 1),(print 2),(print 3).
（P5 *X),{(> *X 1)} --> (print a),
(print b),(print c), (:= *X (- *X 2)),(P5 *X1).
（P5 1）--> (print X),(print Y),(print Z).
（P5 1）
質問
（P5 5）（P5 3）
答 a b c
×
〇
a b c
X Y Z
〇 〇
３ ． Ｅ Ｔ の 計 算 順 序
ET
の 計 算 順 序 に つ い て ま と め た も の を 以 下 に 示 す 。(P5 0）--> (print 1),(print 2),(print 3).
（P5 *X）--> (print a),(print b),(print c).
（P5 1）--> (print X),(print Y),(print Z).
ボディアトムの実行順序は 「左から右へ」
ルールの適用順序は
「上から下へ」
(P5 0）--> (print 1),(print 2),(print 3).
（P5 *X）--> (print a),(print b),(print c).
（P5 1）--> (print X),(print Y),(print Z).
ボディアトムの実行順序は 「左から右へ」
ルールの適用順序は
「上から下へ」
こ の よ う に
