すべてリストである

Gaucheプログラミング(立読み版) > 第1部: 思想 > すべてリストである

すべてリストである応援する

Scheme言語のリストには構文としての側面とデータ構造としての側面の2つがあります。ここではまず構文としての側面から見ていき、次にデータ構造としての側面に着目します。
cons手続きと対(pair)
Scheme言語の基本的なデータ構造は対(pair)です。対とは2つのデータが組になったデータ構造です。「対」は「たい」ではなく「つい」と読んでください。
Scheme言語では対を使ってリスト構造を表現しています。対を作るにはcons手続きが使えます。対を作るcons手続きはScheme言語で非常に重要な手続きのひとつです。
 gosh> (cons 1 2)
 (1 . 2)
cons手続きは対(pair)を作ります。Scheme言語では対を.(ドット記号)で表現します。この記法で対を表現したとき、特にドット対と呼ぶことがあります。

対を図で示してみます。この図は「計算機プログラムの構造と解釈第二版」で使われた図法で、「箱とポインタ記法」(box-and-pointer notation)と呼ばれています。
対は2個の連結した箱で表現され、それぞれ数値1と2を矢印で指し示しています。(この連結した箱はconsセルとも呼ばれます。consセルは対を実装するための方法のひとつです。consセルを使わなくても対は実装できますが、consセルを図示すると対が理解しやすいので本書ではこの図法を採用しました)
対は入れ子にすることができます。対の片方または両方の要素が対であってもかまいません。
 gosh> (cons (cons 1 2) 3)
 ((1 . 2) . 3)
対かどうかを調べるにはpair?手続きが使えます。
 gosh> (define p (cons 1 2)) ;; 1と2で対を作り、pという名前をつける
 p
 
 gosh> (pair? p)             ;; pは対か?
 #t
define構文はデータや手続きに名前をつけます。ここでは対(1 . 2)にpという名前をつけています。
pair?でpが対かどうか調べます。真偽値の真を表す#tが返るのでpは対です。
 
 gosh> (pair? 5)
 #f
真偽値の偽をあらわす#fが返るので数値5は対ではありません。
carとcdrで対の要素の値を得る
consとならんで重要なのは、対の要素の値を得る手続きcarとcdrです。それぞれカー、クダーと発音します。(Scheme言語処理系によってはcarにfirst、cdrにrestという別名を許している場合もあります。Gaucheではこの別名は特に定義されていません)
carは対の最初の要素の値を得ます。
 gosh> (car (cons 1 2))
 1
cdrは対の残りの要素の値を得ます。
 gosh> (cdr (cons 1 2))
 2
対が入れ子になっているときはどうでしょうか?
 gosh> (car (cons (cons 1 2) 3))
 (1 . 2)
 
 gosh> (cdr (cons (cons 1 2) 3))
 3
対((1 . 2) . 3)の最初の要素の値をcarで得た結果は先頭要素の値(1 . 2)です。cdrで得た残りの要素の値は3です。
carとcdrは入れ子になった対にも適用できます。得た要素の値が対のとき、さらに要素の値を得たいならcarやcdrを再度適用することになります。
対を使って並び(sequence)を表現する
並び(sequence)は基本的なデータ構造の一つです。Scheme言語では主に対を使って並びを表現します。
対を使って数値1 2 3 4の並びを表現してみましょう。
(cons 1 (cons 2 (cons 3 (cons 4 空))))
最後の要素4は空の要素と対にしています。以後、空の要素を「空要素」と呼ぶことにします。このcons式は次の式として評価されます。
(1 . (2 . (3 . (4 . 空))))
ここで空要素を()で表現することにします。
 (1 . (2 . (3 . (4 . ()))))
ドット対の表記で、ドットに対応する開き括弧と閉じ括弧をまとめて省略できるという規則があります。上記のドット対で「. (」と、それに対応する「)」を一組づつ省略してみましょう。
 (1 . (2 . (3 . (4 . ()))))
 ↓
 (1 . (2 . (3 . (4)))
 ↓
 (1 . (2 . (3 4)))
 ↓
 (1 . (2 3 4))
 ↓
 (1 2 3 4)
Gaucheの対話型インタプリタで(cons 1 (cons 2 (cons 3 (cons 4 ()))))を評価すると、(1 2 3 4)と評価されることが確認できます。
 gosh> (cons 1 (cons 2 (cons 3 (cons 4 ()))))
 (1 2 3 4)
最後の要素が空要素になっている対をリストと呼びます。リストを簡単に作り出すにはcons手続き以外にlist手続きが使えます。
 gosh> (list 1 2 3 4)
 (1 2 3 4)
リストも対なのでpair?、car、cdr、consが使える
リストもまた対なので、pair?やcar、cdrがそのまま使えます。
 gosh> (pair? (list 1 2 3 4))
 #t                       ;; リスト(1 2 3 4)は対である
 gosh> (car (list 1 2 3 4))
 1                        ;; リスト(1 2 3 4)の先頭要素の値は数値1
  
 gosh> (cdr (list 1 2 3 4))
 (2 3 4)                  ;; リスト(1 2 3 4)の残り要素の値は(2 3 4)
リストの先頭に要素を追加するのは簡単です。先頭に要素を追加するにはcons手続きが使えます。
 gosh> (cons 0 (list 1 2 3 4))
 (0 1 2 3 4)
append手続きでリストを連結する
リストの“末尾”に要素を追加するのは簡単ではありません。今まで見たように、リスト(1 2 3 4)の最終要素は4ではありません。最終要素は空要素()です。
たとえばリスト(1 2 3 4)の“末尾”に5を追加して(1 2 3 4 5)にするには、最終要素のひとつ前に5を追加する必要があります。
 gosh> (cons 1 (cons 2 (cons 3 (cons 4 (cons 5 ())))))
 (1 2 3 4 5)
リストを連結するにはappend手続きが使えますが、リスト(1 2 3 4)に5をappend手続きで連結した結果はリストになりません。
 gosh> (append (list 1 2 3 4) 5)
 (1 2 3 4 . 5)
(append (list 1 2 3 4) 5)は次の式と等価です。
 (cons 1 (cons 2 (cons 3 (cons 4 5))))
結局、リスト(1 2 3 4)の“末尾”に要素5を追加するには以下の式を使います。
 gosh> (append (list 1 2 3 4) (list 5))
 (1 2 3 4 5)
これで前の式、
(cons 1 (cons 2 (cons 3 (cons 4 (cons 5 ())))))
と等価になりました。
空要素は対か?
リストの最終要素である空要素()は対でしょうか? Gaucheの対話型インタプリタで確かめてみましょう。
 gosh> (pair? ())
 #f
()は対ではありません。では()はリストでしょうか?
空要素はリストか?
空要素がリストかどうか確かめてみましょう。リストかどうかを調べるにはlist?手続きが使えます。list?を空要素に適用してみましょう。
 gosh> (list? ())
 #t
空要素はリストです。今まで仮に「空要素」と呼んできたものは本当は空リストと呼ぶのが正しいのです。
ドット対(1 . 2)はリストか?
リストかどうか調べるにはlist?を使えばよいことが分かりました。ではドット対(1 . 2)はリストでしょうか?
 gosh> (list? (cons 1 2))
 #f
ドット対(1 . 2)はリストではありません。
「リストは対である」は正しいか?
空リストが対でないことはすでに確かめました。では、先に述べた「リストはまた対である」は正しいでしょうか?
今まで調べた結果を表にまとめてみましょう。
述語ドット対(1 . 2) 空リスト空でないリスト
pair? #t #f #t
list? #f #t #t
ドット対(1 . 2)は対であるがリストではない
空リストは対ではないがリストである
空でないリストは対でありかつリストである
この事実から「リストはまた対である」を以下の通りに修正する必要があります。
空リストは対ではない
空でないリストは対である
なぜ「配列」でなく対で並びを表現するのか?
SchemeをはじめとするLisp言語では、なぜ「配列」でなく対で並びを表現するのでしょうか?
対で並びを表現すれば、いくらでも入れ子構造にすることができる
入れ子構造になった対は再帰的に処理することができる
あらゆるデータ構造を(入れ子構造になった)対で表現できる
入れ子構造になった対でプログラムコードも表現できる
これまで見てきたように、対はcons手続きでいくらでも入れ子構造にすることができます。また、入れ子構造になった対にcar、cdrを適用すればどんな要素も取り出すことができます。これは、添え字で要素の値を得る「配列」とは対照的です。
入れ子構造になった対に繰り返しcar、cdrなどを適用したいとき、再帰的に処理することができます。これは、再帰的に処理することが困難な配列構造と対照的です。
再帰的な処理の例として、リストをひとつ引数にとり、リストの要素のうち奇数だけを加算するodd-sigma手続きを書いてみます。
 (define (odd-sigma ls)
   (cond ((not (pair? ls))                    ;; リストが空か?
           0)                                 ;; 0を返す
         ((odd? (car ls))                     ;; 先頭要素が奇数か?
           (+ (car ls) (odd-sigma (cdr ls)))) ;; 先頭要素と残りの奇数要素の総和
         (else                                ;; 先頭要素が偶数
           (odd-sigma (cdr ls)))))            ;; 残りの奇数要素の総和
 odd-sigma
 
 gosh> (odd-sigma (list 1 2 3 4 5))
 9
cond式は条件判定のための式です。condは英語のcondition(条件)に由来します。条件を複数記述でき、条件に合致したとき式の値を返します。
 (cond (条件1 式1)
       (条件2 式2)
       ...
       (else  式n))
まず、式(not (pair? ls))でリストが空かどうかを判定します。空リストなら0を返します。
つぎに、式(odd? (car ls))で、先頭要素が奇数かどうか判定します。先頭要素が奇数なら、「先頭要素」と「残り要素のうち奇数の要素の総和」を加算します。残り要素のうち奇数の要素の総和を計算するためにodd-sigma手続き自身を適用しています。
上記のどれでもないとき、つまり先頭要素が偶数のときはelseで始まる式が評価されます。先頭要素を除き、残り要素のうち奇数要素の総和を計算しています。ここでもodd-sigma手続き自身を適用しています。
odd-sigma手続きは再帰的に働きます。構文上は単に自分自身を関数適用している(呼び出している)だけで、反復的な制御構造はどこにも現れていません。
再帰については「再帰は制御構造ではなく単なる手続き呼び出しである」で詳しく説明します。
入れ子構造になった対であらゆるデータ構造が表現できます。さらに、入れ子構造になった対でプログラムコードも表現できるのです。このことは「プログラム自身もリストである」で詳しく説明します。
プログラム自身もリストである
Schemeを含むLispプログラムの大きな特徴は、プログラム自身もリストだということです。ちょっとポール・グレアムの意見に耳を傾けてみましょう。
LispのプログラムコードはLispのデータオブジェクトから出来ている。それは、ソースコードは文字列で出来ていて、文字列は言語でサポートされている、というようなつまらない意味じゃない。Lispのコードは、ひとたびパーザによって読まれたら、あなたが解析することができるデータ構造になるんだ。コンパイラの動作を理解していれば、Lispの構文は奇妙だと言ってもLispには構文が無いと言ってもたいした違いは無いということがわかるだろう。他の言語ならコンパイラが構文解析して内部に作られる構文木を、Lispでは直接プログラムとして書き下すわけだ。しかも、この構文木はプログラムからアクセスできるから、構文木自身を操作するプログラムを書くことができる。Lispではそのようなプログラムをマクロと呼ぶ。いわば、プログラムを生成するプログラムだ。
「普通の奴らの上を行け」2001 川合史朗訳
Schemeが括弧を多用した(奇妙な)構文を採用したのは伊達や酔狂ではありません。プログラムコードがそのままデータ構造になるので、言語処理系そのものを拡張するのが非常に容易になっています。
言語処理系そのものを拡張する例は「第2部文法」の「マクロ」で触れています。
 
by えんどうやすゆき | Permalink | Comments(1) | Trackbacks(0)