導入
今回は Lisp の処理系の 1 つである Scheme を使って再帰処理の必要性について書きたいと思います。
Lisp について
これから買い出しに行くお母さんが買い物一覧みたいなメモを取りますよね。
・たまご
・ゴミ袋
・牛乳
・お刺身
・ニンジン
・・・
この項目を列挙したもの、これがリストです。そして、Lisp は「リスト」という構造に基づくパラダイムを処理するプログラミング言語です。「すべてはリストである」という考え方に基づきます。プログラムで扱うデータはすべてリストです。
前提となる事柄
Lisp(Scheme) では、
関数・・・「手続き」
実行・・・「評価」
と呼びます。
他の言語をすでに勉強している場合は、「手続き」は関数のこと、「評価」は実行すること、と読み替えてもらって構いません。
リスト
数字のリストであれば
'(4 3 7 1 10 9)
のようにカッコで括って表現します。今は先頭のアポストロフィ（「'」）は気にしないでください。
リストの作り方
リストの作り方の前に、２つの要素を１つに結びつける手続き cons を紹介します。cons は「コンスセル」と読みます。
gosh> (cons 1 2)
(1 . 2)
このように二つの要素を１つにまとめることができます。
コンスセルの操作
１つ目の要素を取り出す手続きは car (「カー」と読みます)、残りの要素を取り出す手続きは cdr (「クダー」と読みます) を使います。
gosh> (car (cons 1 2))
1
gosh> (cdr (cons 1 2))
2
さて、cdr の説明では「二つ目の要素を取り出す」ではなく「残りの要素を取り出す」と説明しました。なんで「二つ目の要素を取り出す」という説明じゃいけないの？と思ったかも知れません。その点についてはコンスセルでリストを扱うと理解できると思います。
リストをコンスセルを使って作る
リストはコンスセルを使って作ることができます。早速具体例を見てみましょう。
gosh> (cons 1 (cons 2 (cons 3 '())))
(1 2 3)
３つの要素を持つリストを作ってみました。ここで、「'()」は空リストのことです。空リストは要素を一つも持たないリストです。
リストから要素を取り出してみる
まず先頭の要素を取り出す説明をするのですが、その前に、
(cons 1 (cons 2 (cons 3 '())))
これが何度も現れるのは見づらいため define 手続きを使って lst に束縛しておきます。define 手続きは第二引数を第一引数に束縛する手続きです。
(define 第一引数 第二引数)
「束縛」という言い方がややこしいと思いますが、要するに第二引数を第一引数の名前で参照します、という宣言のようなものです。別の名前を付けると言ってもいいでしょう。例を示します。
(define x 5)
これはコンピュータのメモリ上のどこかに 5 という数値データを用意し、その場所を x という名前で参照します。
という意味になります。
具体的に define してみます。
gosh> (define lst (cons 1 (cons 2 (cons 3 '()))))
lst
こうすることで、
(cons 1 (cons 2 (cons 3 '())))
を以降 lst という名前で参照することが出来るようになります。
gosh> lst
(1 2 3)
lst を評価すると、確かに cons を使って作ったリストを返します。
前置きが長くなりましたがリストの操作をやってみましょう。Lisp (Scheme) のリストを操作する手続きは基本的に car と cdr しかありません。「え？それだけ？」と思うかも知れませんが、car と cdr があれば十分なのです。
car は先頭の要素を返し、cdr は先頭の以外の要素を返します。
gosh> (car lst)
1
gosh> (cdr lst)
(2 3)
2 を取り出したい場合はどうすれば良いでしょうか。そうです lst を cdr してから car すれば良いのです。
gosh> (car (cdr lst))
2
3 も取り出してみましょう。
gosh> (car (cdr (cdr lst)))
3
cdr を二回して car すればよいです。
つまりリストとは？
リストとは、(要素 . リスト) のコンスセルの再帰的表現になっています。もう一度次の手続きをよく眺めてみてください。
(cons 1 (cons 2 (cons 3 '())))
リストがマトリョーシカのような再帰的な構造をしている事が感じ取れたでしょうか？
リストを処理するプログラムの具体例
リストの各要素に手続きを評価する手続き map があります。map は Scheme に標準で用意されている手続きです。早速具体例を見てみましょう。
gosh> (map even? '(1 2 3 4 5))
(#f #t #f #t #f)
map 手続きは次のように書き、
(map 手続き リスト)
「リスト」の各要素に対して「手続き」を評価し、新しく出来たリストを返します。
even? 手続きは偶数か否か真偽値を返す手続きです。偶数なら #t (真）を、そうでないなら #f (偽)を返します。
次にリストの各要素を 2 倍してみましょう。
gosh> (map (lambda (n) (* 2 n)) '(1 2 3 4 5))
(2 4 6 8 10)
ちょっとややこしくなってきました。lambda という手続きが出てきましたが今は気にしないで雰囲気だけ感じ取ってください。
次は二乗してみましょう。
gosh> (map (lambda (n) (* n n)) '(1 2 3 4 5))
(1 4 9 16 25)
map 手続きの中身を考えてみる
よく「車輪の再発明はしてはいけない」と言います。すでにライブラリとして用意されているものを自分で作ってはいけない、という戒めです。が、プログラミング言語の学習においては「車輪の再発明」はとても意義のあることですので気にしないで再発明していきましょう。
(define (my-map proc items)
(if (null? items)
'()
(cons (proc (car items))
(my-map proc (cdr items)))))
いきまりコードを示しましたが、map 手続きの中身を書くとこのようになります。
(map 手続きはすでに用意されているので my-map のように少し違う名前にするのをおすすめします。)
(define (my-map proc items)
最初の行は define を使って、これから示す手続きに my-map という名前で束縛します。
このとき引数についても定義できます。my-map 手続きは二つの引数を取り、それぞれ proc と items です。proc に手続きを、items にリストを取ります。これは map と同じです。
次に手続きの本体です。
(if (null? items)
'()
(cons (proc (car items))
(my-map proc (cdr items)))))
コードの詳しい説明に入る前に、まずリストを cdr で取り出すと、最後は必ず、空のリスト「'()」を返します。
gosh> (define lst (cons 1 (cons 2 (cons 3 '()))))
lst
gosh> lst
(1 2 3)
gosh> (cdr lst)
(2 3)
gosh> (cdr (cdr lst))
(3)
gosh> (cdr (cdr (cdr lst)))
()
リストを処理する場合は、空リスト「'()」が現れたら処理を停止すればよいことがわかるでしょうか？
リストが空リストか否かを調べる手続きが null? です。空リストなら真値を、空リストでないなら偽値を返します。
（Scheme においては、真偽値を返す手続きは、その手続き名の最後に「?」を付けるのが慣習となっています)
gosh> (null? '())
#t
gosh> (null? '(1 2 3))
#f
次は if 手続きです。
(if 条件 条件が真値のときに評価する手続き 条件が偽値のときに評価する手続き)
と書きます。条件には、真偽値を返す手続きを書きます。if 手続きは、どちらか一方の手続きを評価し、その結果の値を返します。
gosh> (if (< 1 2) 456 789)
456
gosh> (if (> 1 2) 456 789)
789
蛇足ですが、if 手続きは「特殊構文」と呼ばれ通常の手続きとは動作がちょっと違います。しかし、今は気にしなくてかまいません。
つまり my-map 手続きは、items が空リストのときは、空リスト「'()」を返して終了します。
空リストではないときは、
(cons (proc (car items))
(my-map proc (cdr items)))
の部分を評価します。
これは、
・先頭の要素に proc 手続きを評価し新しい要素を作り、
・先頭以外の要素に対して my-map を評価し、
・上記二つを要素に持つコンスセルを作ります。
ということです。
先頭以外の要素に my-map を再評価しているのがわかるでしょうか？ my-map 手続きの中で、my-map 手続きを評価しています。リストは「(要素 . リスト)」であるコンスセルの再帰的構造でありマトリョーシカのようになっていると説明しました。手続きにも同様にマトリョーシカのような再帰的構造が現れている事がわかると思います。
評価してみる
作った my-map 手続きを再掲します。特に、my-map 手続きの中で、my-map 手続きを評価（呼び出し）している点に注目してください。さらには、手続きの定義には define を使いますが、これは my-map 手続きの本体部分が第二引数であり、 (my-map proc items) の部分が第一引数であることにも注目してみてください。手続きの定義とは、手続き群に名前を付けることと同義です。
(define (my-map proc items)
(if (null? items)
'()
(cons (proc (car items))
(my-map proc (cdr items)))))
では、my-map を使って、リストの各要素を 100 倍してみましょう。
gosh> (my-map (lambda (n) (* 100 n)) '(1 2 3 4 5))
(100 200 300 400 500)
まとめ
map 処理を「再発明」することで、Lisp (Scheme) における手続きの基本的な作成方法を見ました。
次回は再帰処理を使うと便利なケースと、その必要性について書きたいと思います。
つづく！（たぶん）