第 1 1 章 リ ス ト
1 . リ ス ト と は
リ ス トと は 対 象 が 順 に 並 ん だ も の で あ る 。 最 も 単 純 な 形 の リ ス ト は 、 定 数 、 変 数 、 ま た は こ の 両 方 を 半 角 の 空 白 で 区 切 っ て 並 べ 、 全 体 を 丸 括 弧 で 囲 ん だ も の で あ る 。 リ ス ト の 中 に 含 ま れ る 対 象 を 、 リ ス ト の要 素と い う 。 そ の 要 素 の 数 を リ ス ト の長 さと い う 。 要 素 が 全 て 数 で あ る リ ス ト を数 リ ス トと い う 。
( 1 2 3 4 5 6) (a b c d e f) (*A *B *C *D *E *F) (1 *X 3 4 *Y *Z)
ま た 、 リ ス ト 自 体 も リ ス ト の 要 素 に な る こ と が で き る 。 こ れ を 「 リ ス ト の リ ス ト 」 と 呼 ん で い る 。 こ れ を 使 え ば 、 行 列 な ど を リ ス ト で 表 現 す る こ と も 可 能 で あ る 。 す な わ ち 行 列 の 1 行 を 数 リ ス ト で 表 し 、そ れ ら を 並 べ た リ ス ト を 作 れ ば 、「 リ ス ト の リ ス ト 」と し て 行 列 が 表 現 さ れ る 。
1 2 3 ((1 2 3) 4 5 6 → (4 5 6) 7 8 9 (7 8 9))
そ し て 、 要 素 が 全 く 含 ま れ て い な い も の も リ ス ト で あ り 、 そ れ を空 リ ス トと 呼 ぶ 。ET プ ロ グ ラ ミ ン グ で は 、 空 リ ス ト を ( ) と 書 き 、 リ ス ト の 長 さ は 0 で あ る 。
2 . 頭 部 と 尾 部
リ ス ト の頭 部と は 、 リ ス ト の 先 頭 の 要 素 で あ る 。 リ ス ト の尾 部は リ ス ト の 2 番 目 以 降 の 要 素 か ら な る リ ス ト で あ る 。 例 え ば 、(1 2 3 4 5 6) と い う リ ス ト の 頭 部 は 1 で あ り 、 尾 部 は リ ス ト (2 3 4 5 6) で あ る 。 逆 に 、 頭 部 が 1 、 尾 部 が (2 3 4 5 6) の リ ス ト は (1 2 3 4 5 6) で あ る 。 一 般 に 、 頭 部 と 尾 部 か ら 作 ら れ る 対 象 は 、( 頭 部 | 尾 部 ) の 形 に 書 か れ る 。 し た が っ て 、 頭 部 が 1 、 尾 部 が (2 3 4 5 6) の 場 合 に は 、 そ れ ら か ら 作 ら れ る 対 象 は 、(1|(2 3 4 5 6)) と な る 。 実 際 は (1 2 3 4 5 6) は (1|(2 3 4 5 6)) の 略 記 で あ り 、 両 者 は 全 く 同 じ リ ス ト を 表 し て い る 。そ の た め 、頭 部 が 1 、尾 部 が (2 3 4 5 6) の リ ス ト は (1 2 3 4 5 6) で あ る と い え る 。 以 下 の 式 を ETI に 入 力 し 、 直 接 実 行 し て 結 果 を 確 認 し な さ い 。
① (= *X (1|(2 3 4 5 6)))
② (= *X (1 2|(3 4 5 6)))
③ (= *X (1 |(2|(3 4 5 6))))
全 て(= *X (1 2 3 4 5 6)) に な る
こ れ ら の リ ス ト は 内 部 的 に は 全 く 同 一 の デ ー タ で あ る 。ETIは 、 そ の 最 も 簡 単 な 表 示 方 法 で あ る (1 2 3 4 5 6) を 用 い て 答 を 返 す 。
リ ス ト は 縦 棒 を 用 い て (*A|*X) と 表 現 す る と 、頭 部 と 尾 部 は そ れ ぞ れ*A と*X に な る 。 尾 部 は リ ス ト で あ る の で 、(*X) と 表 現 し が ち で あ る が 、こ れ は 長 さ が 1 の リ ス ト を 意 味 す る の で 誤 り で あ る 。 仮 に (*A|*X) を (1|(2 3)) と し て 、 尾 部 を(*X)と 指 定 し て 取 り 出 す と ((2 3)) と な る 。こ れ は 、(2 3) を 要 素 と し た 長 さ 1 の リ ス ト( リ ス ト の リ ス ト )で あ る こ と を 意 味 し て い る 。
3 . 単 一 化 に よ る リ ス ト の 操 作
単 一 化 ( = ) と は 、 対 象 と な る 第 1 引 数 、 第 2 引 数 の 両 方 に 代 入 を 施 し 、 一 致 さ せ る 組 み 込 み 述 語 で あ る 。 単 一 化 は 両 方 の 引 数 に 代 入 を 施 す こ と が で き 、(= *A *B)と (= *B *A) の よ う に 引 数 同 士 を 入 れ 替 え て も 結 果 は 変 わ ら な い 。 単 一 化 に よ っ て 、 対 象 が あ る 形 に な っ て い る か を 判 定 し た り 、 対 象 を 作 り 出 し た り す る こ と が で き る 。 例 え ば 、 リ ス ト の 頭 部 と 尾 部 を 求 め る た め に 、 単 一 化 を 使 う こ と が で き る 。 以 下 に 示 す ル ー ル を 記 述 し 、 質 問 を 与 え て 計 算 を 実 行 し な さ い 。
(ulA *Y) ‑‑> (format "(*A│*X) と /a を 単 一 化 す る と 、 " (*Y)),(ulA2 *Y).
(ulA2 *Y),{(= (*A│*X) *Y)} ‑‑> (format "*A は /a 、 *X は /a に な る 。 /n" (*A *X)).
(ulA2 *Y) ‑‑> (format "失 敗 す る 。 /n" ( )).
こ こ で 、format は ETI の 組 み 込 み 述 語 で あ り 、 (format < 出 力 フ ォ ー ム > < 対 象 リ ス ト > )
の シ ン タ ッ ク ス で 記 述 す る 。 例 え ば 「A は ×× 、B は ○ ○ に な る 」 と い う 文 を 表 示 さ せ た い と き 、format を 用 い て 以 下 の よ う に 記 述 す れ ば よ い 。
(format "A は /a 、 B は /a に な る 。 /n" (*A *B))
一 般 に format は 、 で 囲 ま れ た 文 字 列 を 出 力 す る 。 文 字 列 中 の /a や /n な ど は 制 御 記 号 で あ り 、/n は 改 行 を 表 し 、/a は 対 応 す る 対 象 に 置 き 換 え る こ と を 意 味 す る 。 対 応 す る 対 象 は format の 末 尾 に 書 か れ た 対 象 リ ス ト 内 に あ り 、 出 力 フ ォ ー ム の 左 か ら i 番 目 の /a が 、 対 象 リ ス ト 中 に あ る 第 i 番 目 の 要 素 の format 実 行 時 の 値 に 置 き 換 え ら れ る 。 し た が っ て 上 の 例 で は 、 ××と ○ ○ の 部 分 に は 、format 実 行 時 の*A、*B の 値 が 入 る 。 (ulA (1 2 3 4 5 6))と い う 質 問 を 入 れ る と 、 以 下 の よ う に 表 示 さ れ る 。
[D]> (ulA (1 2 3 4 5 6))
---D execution ---
(*A|*X) と (1 2 3 4 5 6) を 単 一 化 す る と 、 * A は 1 、 *X は ( 2 3 4 5 6 ) に な る ---
succeeded.
(ulA (1 2 3 4 5 6))
execution time: 0 [msec]
同 様 に 、( ) 、(1)、 (1 2)、 (1 2 3)や 定 数 1、abc、 リ ス ト の リ ス ト ((1 2 3)(4 5 6)) の 場 合 も 実 行 し て み る と 、 そ れ ぞ れ の 質 問 に 対 し て 、 次 の よ う に 出 力 さ れ る 。
(*A│*X) と ( ) を 単 一 化 す る と 、 失 敗 す る 。
(*A│*X) と (1) を 単 一 化 す る と 、*A は 1、*X は ( ) に な る 。 (*A│*X) と (1 2) を 単 一 化 す る と 、*A は 1、*X は (2) に な る 。 (*A│*X) と (1 2 3) を 単 一 化 す る と 、*A は 1、*X は (2 3) に な る 。 (*A│*X) と 1 を 単 一 化 す る と 、 失 敗 す る 。
(*A│*X) と abc を 単 一 化 す る と 、 失 敗 す る 。
(*A│*X) と ((1 2 3)(4 5 6)) を 単 一 化 す る と 、*A は(1 2 3)、*X は ((4 5 6)) に な る 。
さ ら に 、(= (*A│*X) *Y)の 引 数 同 士 を 入 れ 替 え て 、(= *Y (*A│*X))と し た 場 合 を 調 べ る 。 以 下 に 示 す ル ー ル を 記 述 し 、 質 問 を 与 え て 計 算 を 実 行 し な さ い 。
(ulB *Y) ‑‑> (format "(*A│*X) と /a を 単 一 化 す る と 、 " (*Y)),(ulB2 *Y).
(ulB2 *Y),{(= *Y (*A│*X))} ‑‑> (format "*A は /a 、 *X は /a に な る 。 /n" (*A *X)).
(ulB2 *Y) ‑‑> (format "失 敗 す る 。 /n" ( )).
例 え ば 、 質 問 (ulB (1 2 3 4 5 6)) を 入 れ て 実 行 す る と 、 以 下 の よ う に 表 示 さ れ る 。
[D]> (ulB (1 2 3 4 5 6))
---D execution ---
(1 2 3 4 5 6 ) と ( * A│ * X) を 単 一 化 す る と 、 * A は 1 、 *X は ( 2 3 4 5 6 ) に な る
--- succeeded.
(ulB (1 2 3 4 5 6))
execution time: 0 [msec]
単 一 化 の 引 数 は 対 称 な の で 、ulB は ulA と 同 じ 結 果 を 与 え る 。
4 . 頭 部 の 要 素 を 2 つ に し た 場 合 の リ ス ト の 単 一 化
(*A *B│*X) の パ タ ー ン と リ ス ト な ど を 単 一 化 さ せ た ら ど う な る か 。以 下 に 示 す プ ロ グ ラ ム を 記 述 し て 、 質 問(ulC (1 2 3 4 5 6))を 入 れ て 実 行 し な さ い 。
(ulC *Y) ‑‑> (format "(*A *B│*X) と /a を 単 一 化 す る と 、 " (*Y)),(ulC2 *Y).
(ulC2 *Y),{(= *Y (*A *B│*X))}
‑‑> (format "*A は /a 、 *B は /a 、 *X は /a に な る 。 /n" (*A *B *X)).
(ulC2 *Y) ‑‑> (format 失 敗 す る 。 /n ( )).
(ulC (1 2 3 4 5 6))を 与 え て 実 行 す る と 、 画 面 に は 以 下 の よ う に 表 示 さ れ る 。
[D]> (ulC (1 2 3 4 5 6))
---D execution ---
(* A *B │* X ) と ( 1 2 3 4 5 6 ) を 単 一 化 す る と 、 * A = 1 、 * B= 2 、 * X = (3 4 5 6) に な る
--- succeeded.
(ulC (1 2 3 4 5 6))
execution time: 0 [msec]
同 様 に 、( ) 、(1)、 (1 2)、 (1 2 3)や 定 数 1、abc、 リ ス ト の リ ス ト ((1 2 3)(4 5 6)) の 場 合 も 実 行 し て み る と 、 そ れ ぞ れ の 質 問 に 対 し て 、 次 の よ う に 出 力 さ れ る 。
(*A *B│*X) と ( ) を 単 一 化 す る と 、 失 敗 す る 。 (*A *B│*X)と (1) を 単 一 化 す る と 、 失 敗 す る 。
(*A *B│*X)と (1 2) を 単 一 化 す る と 、*A は 1、*B は 2、*X は ( ) に な る 。 (*A *B│*X)と (1 2 3) を 単 一 化 す る と 、*A は 1、*B は 2、*X は (3) に な る 。 (*A *B│*X)と 1 を 単 一 化 す る と 、 失 敗 す る 。
(*A *B│*X)と abc を 単 一 化 す る と 、 失 敗 す る 。
(*A *B│*X) と ((1 2 3)(4 5 6)) を 単 一 化 す る と 、*A は(1 2 3)、*B は (4 5 6)、*Xは ( ) に な る 。
5 . リ ス ト の パ タ ー ン
リ ス ト 処 理 で よ く 使 わ れ る パ タ ー ン を 列 挙 し て お こ う 。
( ) 長 さ が 0 の リ ス ト
(*A *B) 長 さ が 2 の リ ス ト (*A *B│*X) 長 さ が 2 以 上 の リ ス ト
頭 部 をC A R(the Contents of the Address part of a Register の 略 語 、 カ ー と 言 う ) と 呼 び 、 尾 部 をC D R(the Contents of the Decrement part of a Registerの 略 語 、 ク ダ ー と 言 う )と 呼 ぶ こ と も あ る 。ま た 、C A R と C D R を 縦 棒 で 結 び つ け た 構 造 体 (CAR|CDR) の こ と を 、C O N S(コ ン ス と 言 う)と 呼 ぶ 。
6 . 簡 単 な リ ス ト 処 理
リ ス ト 処 理 を 行 う 上 で 、 先 頭 要 素 の 抽 出 、 先 頭 要 素 の 除 去 、 リ ス ト 合 成 は 基 本 的 な 操 作 で あ る 。 先 頭 要 素 の 抽 出 と は リ ス ト の 先 頭 の 要 素 を 求 め る こ と で あ る 。 先 頭 要 素 の 除 去 と は 、 リ ス ト の 先 頭 の 要 素 を 取 り 除 い た リ ス ト を 与 え る こ と で あ り 、 尾 部 だ け を 抽 出 す る 。 リ ス ト 合 成 は 対 象 と リ ス ト か ら 新 た な リ ス ト を 作 る 。 次 の 述 語 を 考 え る 。
(first *x *y) ・・・ *y は*xの 頭 部 で あ る 。 (rest *x *y) ・・・ *yは*xの 尾 部 で あ る 。
(cons *a *b *y) ・・・ *y は*aを 頭 部 、*bを 尾 部 と す る 構 造 体 で あ る 。 こ れ ら の 述 語 を 処 理 す る た め に 、 次 の ル ー ル を 記 述 し な さ い 。
; 先 頭 要 素 の 抽 出 ( リ ス ト の 頭 部 を 求 め る ) (first (*A│*B) *Y) ‑‑> (= *Y *A).
; 先 頭 要 素 の 除 去 ( リ ス ト の 尾 部 を 求 め る ) (rest (*A│*B) *Y) ‑‑> (= *Y *B).
; リ ス ト 合 成 ( 対 象 と リ ス ト か ら 新 た な リ ス ト を 作 る ) (cons *A *X *Y) ‑‑> (= *Y (*A│*X)).
記 述 し 終 え た ら 、ETIを 起 動 し て 質 問 (first (1 2 3 4 5 6) *Y)、(rest (1 2 3 4 5 6)
*Y)、(cons 0 (1 2 3 4 5 6) *Y) を 入 れ て 、 計 算 を 実 行 し な さ い 。
こ の 結 果 、 先 頭 要 素 を 抽 出 す る と *Y は 1 と な り 、 先 頭 要 素 を 除 去 す る と (2 3 4 5 6)と な り 、 リ ス ト 合 成 を 行 う と (0 1 2 3 4 5 6) と そ れ ぞ れ 答 が 求 ま る 。