第 ３ 章
ル ー ル の 記 法 と 意 味
１ ． 問 題 を 簡 単 化 に よ っ て 解 く
Ｅ Ｔ プ ロ グ ラ ミ ン グ で は 、 与 え ら れ た 質 問 を 問 題 の簡 単 化に よ っ て 解 く 。 そ の た め に 問 題 を 正 し く 簡 単 化 す る「 ル ー ル 」を 記 述 し て い く 。「 問 題 の 簡 単 化 に よ っ て 解 く 」と は ど う い う こ と だ ろ う か 。 そ れ を 説 明 す る た め に 、 簡 単 な 例 を 取 り あ げ て み よ う 。 例 え ば 、 正 の 整 数 Ａ と Ｂ が 与 え ら れ た と き 、A 割 る B の 余 り Xを 求 め る 問 題 を 考 え る 。
具 体 的 な 数 を 当 て は め て 考 え て み る と 、8 割 る ３ の 余 り を 求 め る に は 、 ８ か ら 割 る 数 で あ る ３ を 引 い た 、 ５ 割 る ３ の 余 り を 求 め れ ば よ い 。 同 様 に 、 ５ 割 る ３ の 余 り を 求 め る に は ２ 割 る ３ の 余 り を 求 め れ ば よ い 。 ２ 割 る ３ の 余 り は 明 ら か に ２ で あ る 。 だ か ら 答 え は ２ と な る 。 こ れ を 表 に 書 く と 右 の よ う に な る 。 こ の 問 題 の 簡 単 化 の 方 法 を ３ 通 り 考 え る 。
(1) A割 る B の 余 り X を 求 め る 問 題 は 、A＞B の と き 、 (A−B)割 る B の 余 り X を 求 め る 問 題 に 簡 単 化 で き る 。 (2) A割 る B の 余 り X を 求 め る 問 題 は 、A＜B の と き 、
Ｘ ＝A と な っ て 解 け る 。
(3) A割 る B の 余 り X を 求 め る 問 題 は 、A＝B の と き 、 Ｘ ＝ ０ と な っ て 解 け る 。
こ れ ら の 簡 単 化 を 用 い て 、 右 の 表 が 次 々 と 作 ら れ て い く 。
２ ． ET プ ロ グ ラ ミ ン グ に よ る 問 題 解 決 ２ ． １ ア ト ム
ET プ ロ グ ラ ミ ン グ で は 、 ア ト ム を 用 い た 記 述 に よ っ て 問 題 の 意 味 を 決 定 し 、 ル ー ル に よ る ア ト ム の 置 き 換 え に よ っ て 問 題 解 決 を 行 う 。 ア ト ム と は 、 こ れ 以 上 分 割 で き な い 最 小 単 位 の 文 （ 原 子 文 ） の こ と で あ り 、 述 語 と ０ 個 以 上 の 引 数 の 並 び で 表 わ さ れ る 。 例 え ば 、
「A が B よ り 大 き い 」 と い う 原 子 文 は 、 述 語 > 、 引 数 *A *Bを 用 い て 表 す と 、（ > *A *B）
と い う ア ト ム に な る （A、B は 変 数 で あ る と 解 釈 し 、*を つ け て 表 現 し て い る ）。
上 記 の 簡 単 化 に つ い て 、 文 を ア ト ム で 表 現 す る 方 法 を 決 め る 。 例 え ば 、「A 割 る B の 余 り は X で あ る 」 と い う 文 は 、「 余 り 」 と い う 意 味 を 持 つ remanider に 由 来 し て 、rem と い う 述 語 を 導 入 し 、(rem *A *B *X)と 表 す こ と と す る 。 ま た 、A＝B と い う 文 は 、 = を 導 入 し て（ = *A *B）と 表 す こ と と す る 。 ア ト ム と 文 の 関 係 を 以 下 に 示 す 。
(rem *A *B *X) … A 割 る B の 余 り は X で あ る （ > *A *B） … A が B よ り 大 き い
(:= *A1 (‑ *A *B)) … A 引 く B の 答 え は A1 で あ る
A B X
８ ３ Ｘ
５ ３ Ｘ
２ ３ Ｘ
２ ３ ２
(1) (1) (2)
(rem *A1 *B *X) … A1 割 る B の 余 り は X で あ る （ < *A *B） … A が B よ り 小 さ い
（ = *X *A） … X は A で あ る （ == *A *B） … A と B は 等 し い （ = *X 0） … X は 0で あ る
２ ． ２ 節
ア ト ム の 引 数 に 具 体 的 な 数 を 当 て は め た 質 問 、例 え ば「 ８ 割 る ３ の 余 り は*X で あ る 」と い う 質 問 文 は 、
(rem 8 3 *X)
と 表 さ れ る 。 正 確 に は 質 問 文 の ア ト ム は 、 節 と い う 記 述 で 表 さ れ る 。 節 は 、
(ans *X) <-- (rem 8 3 *X).
と い う 形 を し て お り 、「 ８ 割 る ３ の 余 り が*X で あ る な ら ば 、*X は 答 え で あ る 」と い う 意 味 を 持 つ 。ET プ ロ グ ラ ミ ン グ で は 、 節 の 矢 印 よ り 右 側 に あ る ア ト ム を ル ー ル で 書 き 換 え て い く こ と で 、 計 算 が 進 ん で い く 。 そ し て 、 全 て の ア ト ム が 適 用 さ れ て 矢 印 以 降 に 何 も な く な っ た と き 、 問 題 が 解 け た こ と に な る 。 以 下 の 例 は 問 題 が 解 け た こ と を 表 し た 節 の 記 述 で あ る 。
(ans 2) <--.
こ の よ う に 、 右 に あ る ア ト ム を 次 々 と ル ー ル で 変 換 し て い き 、 最 終 的 に は 全 て の ア ト ム が 消 滅 す る よ う に ル ー ル を 記 述 す れ ば よ い 。
２ ． ３ ル ー ル
そ れ で は 、 ２ ． １ 節 で 定 義 し た ア ト ム を 用 い て ル ー ル を 作 成 し て み よ う 。 前 節 の 簡 単 化 の 方 法 (1)〜(3)を ル ー ル で 表 現 す る と 、(1’)〜(3’)の よ う に な る 。
(1’) (rem *A *B *X),{(> *A *B)} ‑‑> (:= *A1 (‑ *A *B)),(rem *A1 *B *X).
(2’) (rem *A *B *X),{(< *A *B)} ‑‑> (= *X *A).
(3’) (rem *A *B *X),{(== *A *B)} ‑‑> (= *X 0).
(1’)の ル ー ル は 、 Ａ 割 る Ｂ の 余 り Ｘ は 、 Ａ ＞ Ｂ と い う 条 件 を 満 た し た と き 、 Ａ1＝ Ａ − Ｂ を 実 行 し 、 Ａ1 割 る Ｂ の 余 り Ｘ を 求 め る 問 題 に 置 き 換 え る こ と が で き る と い う こ と を 記 述 し て い る 。
(2’)の ル ー ル は 、Ａ 割 る Ｂ の 余 り Ｘ は 、Ａ ＜ Ｂ と い う 条 件 を 満 た し た と き 、Ｘ ＝ Ａ と な る
こ と を 表 し て い る 。
(3’)の ル ー ル は 、 Ａ 割 る Ｂ の 余 り Ｘ は Ａ ＝ Ｂ と い う 条 件 を 満 た し た と き 、 Ｘ ＝ ０ と な る 。 ８ 割 る ３ の 場 合 は Ａ ＝ Ｂ と な ら な い の で 、 こ の ル ー ル は 適 用 さ れ な い 。
こ れ ら ３ つ の ル ー ル は 、 Ａ が 正 の 整 数 ま た は ０ 、 Ｂ が 正 の 整 数 で あ れ ば 、 常 に 正 し く 簡 単 化 す る ル ー ル で あ る 。 (1’)〜(3’)の ル ー ル の 記 法 を 本 書 で は R (Rewrite) 式 と 呼 ぶ 。R 式 は 、 あ る 問 題 を 別 の 問 題 に 置 き 換 え る 方 法 を 直 感 的 に わ か り や す く 表 現 し て い る 。
も う 少 し 一 般 的 に 言 え ば 、R 式 は 、 例 え ば 、
〈 ア ト ム 1〉, {〈 ア ト ム 2〉,〈 ア ト ム 3〉} ‑‑> 〈 ア ト ム 4〉,〈 ア ト ム 5〉.
の 形 を し て い る 。 基 本 的 に 、 ア ト ム と ア ト ム が 並 ん で い る と き に は 、 コ ン マ で 区 切 り 、 最 後 は ピ リ オ ド で 終 わ る と い う 形 に な っ て い る 。 中 括 弧 の 中 に お い て も 、 い く つ か の ア ト ム が コ ン マ で 区 切 ら れ て 並 べ ら れ て い る 。
置 き 換 え よ う と す る ア ト ム （ こ こ で は 〈 ア ト ム １ 〉） を 、ヘ ッ ド(Head)と い う 。 ヘ ッ ド は １ つ の ア ト ム で あ り 、 ル ー ル の 最 も 左 に あ る ア ト ム が ヘ ッ ド と な る 。 そ し て 、 中 括 弧 で 囲 ま れ た ア ト ム(列)（ こ こ で は 〈 ア ト ム 2〉 と 〈 ア ト ム 3〉） は 、条 件 列(Cond)と い う 。 条 件 列 は ０ 個 以 上 の ア ト ム(列)で あ る 。 条 件 列 の ア ト ム が ０ 個 の 場 合 は 、 中 括 弧 と そ の 前 の コ ン マ を 省 略 で き る 。
次 に 、ア ト ム(列)同 士 を 矢 印 で つ な ぐ こ と は 、ア ト ム を 別 の ア ト ム(列)に 置 き 換 え る こ と を 意 味 す る 。 矢 印 以 降 に あ る 、 置 き 換 え ら れ る ア ト ム(列) （ こ こ で は 〈 ア ト ム ４ 〉 と 〈 ア ト ム ５ 〉）は 、ボ デ ィ(Body)と い う 。ボ デ ィ は ０ 個 以 上 の ア ト ム 列 で あ る 。ま た 、ボ デ ィ 中 の ア ト ム を ボ デ ィ ア ト ム と い う 。 こ の よ う に ル ー ル は 、 ヘ ッ ド 、 条 件 列 、 矢 印 、 ボ デ ィ で 構 成 さ れ る 。
上 の Ｒ 式 で は 、 ヘ ッ ド で あ る 〈 ア ト ム １ 〉 が 、 質 問 の 節 の 一 部 分 を 表 す ア ト ム に 対 応 し て い る 。 そ し て 、 中 括 弧 で 囲 ま れ た 〈 ア ト ム 2〉 と 〈 ア ト ム 3〉 は 、 ヘ ッ ド の パ タ ー ン に 一 致 し た ア ト ム を 、ボ デ ィ に 置 き 換 え る た め の 条 件 を 意 味 す る 。最 後 に 、ボ デ ィ で あ る〈 ア ト ム 4〉 と 〈 ア ト ム 5〉 は 、 置 き 換 え る 別 の ア ト ム を 意 味 す る 。 そ し て 、 最 後 の ピ リ オ ド は 、 ル ー ル の 末 尾 を 意 味 す る 。
い く つ か の Ｒ 式 の パ タ ー ン を 以 下 に 書 い て お こ う 。
・R 式 の パ タ ー ン の 例
〈 ア ト ム 1〉, {〈 ア ト ム 2〉} ‑‑> 〈 ア ト ム 3〉.
意 味 ： ア ト ム １ が ア ト ム ２ の 条 件 を 満 た し た と き 、 ア ト ム １ を ア ト ム ３ に 置 き 換 え る ル ー ル 。
〈 ア ト ム 1〉 ‑‑> 〈 ア ト ム 2〉,〈 ア ト ム 3〉,〈 ア ト ム 4〉. 意 味 ： ア ト ム １ を ア ト ム ２ と ア ト ム ３ と ア ト ム ４ の 列 に 置 き 換 え る ル ー ル 。
〈 ア ト ム 1〉, {〈 ア ト ム 2〉,〈 ア ト ム 3〉} ‑‑> .
意 味 ： ア ト ム １ が ア ト ム ２ と ア ト ム ３ の 条 件 を 満 た し た と き 、 ア ト ム １ を 取 り 除 く ル ー ル 。
〈 ア ト ム 1〉 ‑‑> .
意 味 ： ア ト ム １ を （ 無 条 件 で ） 取 り 除 く ル ー ル 。
１ つ の ル ー ル が 、 多 く の ア ト ム か ら 構 成 さ れ て い る 場 合 、 ル ー ル が 見 に く く な る 場 合 が あ る 。 ル ー ル が 見 や す く な る よ う に 字 下 げ を し た り 、 適 度 に 改 行 を 入 れ た り す る な ど の 工 夫 を す る こ と が 望 ま し い 。
〈 ア ト ム 1〉 ‑‑>〈 ア ト ム 2〉,
〈 ア ト ム 3〉,
〈 ア ト ム 4〉.
３ ． ル ー ル マ ッ チ ン グ に よ る 節 の 置 き 換 え
マ ッ チ ン グ と は 、 あ る 対 象 に 代 入 を 施 し て 、 も う 一 方 の 対 象 と の 一 致 を 試 み る 操 作 の こ と で あ る 。ET プ ロ グ ラ ミ ン グ で は 、ル ー ル が 節 に マ ッ チ し 、適 用 条 件 を 満 た し た と き に の み 、 ヘ ッ ド と 一 致 し た 節 中 の ア ト ム は 、 ル ー ル の ボ デ ィ ア ト ム に 置 き 換 え ら れ る 。 例 え ば 、
(ans *X) <‑‑ (rem 8 3 *X).
と い う 質 問 に 対 し て 、
(1’) (rem *A *B *X),{(> *A *B)} ‑‑> (:= *A1 (‑ *A *B)),(rem *A1 *B *X).
(2’) (rem *A *B *X),{(< *A *B)} ‑‑> (= *X *A).
(3’) (rem *A *B *X),{(== *A *B)} ‑‑> (= *X 0).
と い う ３ つ の ル ー ル が あ る と き 、 最 初 に (1’)の ル ー ル の ヘ ッ ド パ タ ー ン が 節 の パ タ ー ン に 一 致 す る か ど う か を 検 査 す る 。 こ の 場 合 は パ タ ー ン が 一 致 し 、 次 に 条 件 列 を 満 た す か ど う か の 検 査 が 行 わ れ る 。 ８ ＞ ３ と い う 条 件 を 満 た し て い る の で 、 こ れ で ボ デ ィ 中 の ア ト ム に 置 き 換 え て も よ い と い う こ と に な る 。し た が っ て 、最 初 の 節 は(1’)の ル ー ル の 適 用 に よ っ て 、
(ans *X) <‑‑ (:= *A1 (‑ 8 3)),(rem *A1 3 *X). (1’)の ル ー ル が 適 用 さ れ る
と な る 。:= の 述 語 は シ ス テ ム に あ ら か じ め 用 意 さ れ た 組 み 込 み 述 語 で あ り 、組 み 込 み 述 語 で 定 義 さ れ た ア ト ム は 、 ル ー ル の 適 用 と は 無 関 係 に 計 算 が 実 行 さ れ て 消 滅 す る 。
(ans *X) <‑‑ (rem 5 3 *X). 組 み 込 み 述 語 に よ る 実 行
次 の ア ト ム に 対 し て も(1’)の ル ー ル が 適 用 さ れ 、
(ans *X) <‑‑ (rem 2 3 *X). (1’)の ル ー ル が 適 用 さ れ る
と ア ト ム が 置 き 換 え ら れ る 。さ ら に(1’)の ル ー ル の 適 用 を 試 み る が 、条 件 部 で ２ ＞ ３ と は な ら な い の で 、次 に(2’)の ル ー ル の 適 用 が 試 み ら れ る 。今 度 は ２ ＜ ３ と い う 条 件 を 満 た す の で 、 (2’)の ル ー ル 中 の ボ デ ィ ア ト ム に 置 き 換 え ら れ る 。
(ans *X) <‑‑ (= *X 2).
= の 述 語 も 単 一 化 （ ２ つ の 対 象 に 代 入 を 施 し て 一 致 さ せ る 操 作 ） を 行 う 組 み 込 み 述 語 で あ り 、 *X は ２ と な っ て 、 ＝ 述 語 の ア ト ム は 消 滅 す る 。
(ans 2) <‑‑ .
こ う し て 、 す べ て の ア ト ム が 消 滅 し 、 (rem 8 3 *X)と い う 質 問 に 対 し て 、 *X は 2 で あ る と い う 結 果 が 導 か れ る の で あ る 。
注 ET に お け る ア ス タ リ ス ク (＊ )と 空 白 に 関 す る こ と
変 数 で あ る こ と を 表 す に は 、 半 角 の ア ス タ リ ス ク を 付 け る 必 要 が あ る 。 こ れ は シ ン ボ ル と 変 数 の 区 別 を つ け る た め で あ る 。ル ー ル は ア ト ム で 構 成 さ れ る が 、ア ト ム は S 式 と 呼 ば れ る 記 法 で 書 か れ て い る 。S 式 は 一 般 に 、 定 数 と 変 数 と 括 弧 で 構 成 さ れ る よ う な ひ と ま と ま り の 式 で あ る 。 定 数 に は 、 シ ン ボ ル 、 数 、 文 字 、 文 字 列 な ど が あ る 。 シ ン ボ ル と 変 数 は よ く 似 て い る 。 例 え ば 、apple は シ ン ボ ル で あ り 、*apple は 変 数 で あ る 。
シ ン ボ ル(演 算 子 も そ の 一 種)や 変 数 が 並 ん だ 場 合 に は 、そ れ ら を 空 白(半 角 で 一 文 字 以 上) で 区 切 る 必 要 が あ る 。 空 白 を あ け な い と 一 ま と ま り の 対 象(シ ン ボ ル ま た は 変 数)と し て み な さ れ て し ま う 。
・ 秀 丸 表 記 ・ 本 テ キ ス ト で の 表 記
注 演 算 子 の 記 法 に 関 す る こ と
ル ー ル 中 の 計 算 式 は 、 演 算 子 を 先 頭 に つ け る「 前 置 記 法 」で 表 現 す る 。 数 式 を 書 く 場 合 に は 、 演 算 子 を 間 に 置 く 中 置 記 法 で 記 述 す る こ と が 多 い が 、ET で は 中 置 記 法 で う っ か り ル ー ル を 記 述 す る と エ ラ ー と な る の で 注 意 が 必 要 で あ る 。
前 置 記 法 ・ ・ ・(＋ Ａ Ｂ) 中 置 記 法 ・ ・ ・(Ａ ＋ Ｂ)
(add *A *B *X) ‑‑>(:= *X (+ *A *B)).
