Functional Programming

Scheme の基礎知識 [2]

前回はリスト、シンボル、文字列、整数値といった Scheme で使用するデータの種類と、関数の使い方について説明しました。今回は「変数 (variable)」と「評価 (evaluation)」について説明します。

●変数への代入

前回は関数を呼び出すとき、実引数の値が仮引数 (シンボル) に代入されることを説明しました。シンボルに値を代入するのは、関数呼び出しのときだけではありません。define は関数定義だけではなく、シンボルに値を代入することができます。

それでは、実際に define を使ってシンボルに値をセットしてみましょう。シンボル var に整数値 10 をセットします。

gosh[r7rs.user]> var
***ERROR : unbound variable: var
Stack Trace:
・・・省略・・・

gosh[r7rs.user]> (define var 10)
var
gosh[r7rs.user]> var
10

最初の実行結果を見て下さい。プロンプトが表示されている状態からシンボル名を入力すると、そこに格納されている値を表示します。この例では var に値がセットされていないので、エラーが表示されました。Scheme が起動されたときには、特別なシンボルを除いて、シンボルに値は設定されていません。値が定まっていないシンボルにアクセスしようとすると、このようなエラーが発生します。

次に、define でシンボルに値をセットします。define には第 1 引数にシンボル、第 2 引数にセットする値を渡します。Gauche の場合、define の返り値は値をセットしたシンボルになります。define はシンタックス形式なので、第 1 引数のシンボルは評価しないことに注意してください。define は第 1 引数をそのまま受け取り、第 2 引数を評価した結果をシンボルに代入します。たとえば、第 2 引数にリストを書けば、その実行結果がシンボルに代入されます。

gosh[r7rs.user]> (define var (+ 1 2 3))
var
gosh[r7rs.user]> var
6

gosh[r7rs.user]> (define var1 var)
var1
gosh[r7rs.user]> var1
6

2 番目の例のように、第 2 引数がシンボルであれば、そこに格納されている値が第 1 引数のシンボルに代入されます。

ここで、代入操作は変数が記憶している値を書き換えることに注意してください。

変数はひとつの値しか記憶できません。いま変数 var には 11 が記憶されています。define で var に 12 を代入します。そうすると、var の値は 12 となり、元の値である 11 は失われてしまいます。元の値を書き換えてしまうことを「破壊的」 ^[*1] といいます。逆に、値を変更しない操作は「非破壊的」といいます。値を読み取る操作は非破壊的です。したがって、元の値が必要な場合は、あらかじめほかの変数に値を移しておかなくてはいけません。

上図の例では、var の値を var1 に移しています。ただし、この場合でも var1 の値は破壊されることに注意してください。

Scheme の場合、シンボルに値を代入する操作は define だけではありません。Scheme には set! というシンタックス形式があり、シンボルの値を書き換えることができます。簡単な例を示しましょう。

gosh[r7rs.user]> (set! a 10)
***ERROR : symbol not defined: #<identifier ...>
Stack Trace:
・・・省略・・・

gosh[r7rs.user]> (define a 10)
a
gosh[r7rs.user]> a
10
gosh[r7rs.user]> (set! a 20)
20
gosh[r7rs.user]> a
20

set! は未定義のシンボルに値をセットすることはできません。関数型言語の場合、変数に対応するメモリ領域を確保する操作を「束縛 (bind)」といいます。define は新しい変数を束縛して値を代入することができますが、set! は値を書き換えることしかできないのです。最初に define で a に 10 をセットします。その後、set! で a の値を 20 に書き換えることができます。set! の返り値は R5RS, R7RS-small では未定義ですが、Gauche ではセットした値を返します。

なお、Scheme の場合、値を書き換える関数には ! マークを付けて注意を促しています。

●局所変数と大域変数

ところで、関数を実行する場合、仮引数に値が代入されますね。代入は破壊的な操作ですから、仮引数の元の値は書き換えられてしまうはずです。ところが、前回説明したように、関数の実行が終了すると、仮引数として使用された変数の値は元に戻ります。

それでは、前回定義した関数 square を使って、実際に確かめてみましょう。

square の定義 : (define (square x) (* x x))

gosh[r7rs.user]> (define x 10)
10
gosh[r7rs.user]> (square 20)
400
gosh[r7rs.user]> x
10

最初に define で x に 10 を代入します。次に、(square 20) を実行します。このとき、仮引数 x に 20 が代入され、square が実行されますね。その結果 (* 20 20) が計算されて 400 という値が返されます。そして、実行終了後に x の値を確かめてみると、最初にセットした値 10 のままです。

このように、仮引数として使用される変数は、その関数が実行されている間だけ有効なのです。このような変数を「局所変数 (local variable)」といい、それ以外の変数を「大域変数 (gloabl variable)」といいます。

最初 define で変数 x に値をセットしましたが、このとき x は仮引数ではないので、大域変数として扱われるのです。関数が実行されるときは、x は仮引数として使用されているので、局所変数として扱われます。

上図を見てください。関数 foo で変数 x に 100 を、y に 200 を代入しました。変数 x は関数 foo の仮引数です。この場合、x は局所変数として扱われます。変数 y は仮引数ではないので大域変数として扱われます。したがって、foo の実行が終了しても、大域変数 y の値は 200 に書き換えられたままになります。実際に試してみると、次のようになります。

gosh[r7rs.user]> (define x 10)
x
gosh[r7rs.user]> (define y 20)
y
gosh[r7rs.user]> (define (foo x) (set! x 100) (set! y 200))
foo
gosh[r7rs.user]> (foo 1000)
200
gosh[r7rs.user]> x
10
gosh[r7rs.user]> y
200

これは値を代入する例でしたが、変数の値を求める場合も同じです。Lisp / Scheme では、変数 (シンボル) の値をアクセスする場合、その変数が仮引数であれば、それを局所変数として扱います。この場合は、大域変数にアクセスしません。変数が仮引数でなければ大域変数をアクセスします。

局所やら大域やら難しい話になりましたが、この違いはプログラムを作成する場合、とても重要になります。とくに、局所変数の機能は、関数を部品のように使うためには必須の機能なのです。まあ、実際にプログラムを作るようになると、すぐに理解できることなので心配は無用です。

●評価しちゃだめ

Lisp / Scheme の変数は、どのようなデータ型でも格納することができます。ほかのプログラミング言語では、変数に格納するデータの種類をあらかじめ決めておかなければならないものがあります。たとえばＣ言語の場合、変数 a に整数値を格納する場合は int a というように、a に格納するデータの種類を決めます。そして、a には整数値以外のデータを格納することはできません。

Lisp / Scheme の場合、変数 a には整数値、文字列、シンボル、リストなど S 式であれば何でも格納することができます。ところで、整数値は define や set! で変数に代入できましたが、シンボルやリストを変数に代入することができるのでしょうか。define や set! の第 2 引数は「評価」されることを思い出してください。

gosh[r7rs.user]> (define x 10)
x
gosh[r7rs.user]> (define y x)    <-- 引数 x が評価され 10 が y に代入される
y
gosh[r7rs.user]> y
10

変数 y にシンボル x を代入する場合、define にそのまま x を与えると、x が評価されてその値が y に代入されてしまいます。リストの場合は、それがプログラムとして実行されるので、リスト自身を変数に代入することはできません。シンボルやリストを変数に代入するときは、引数が評価されては困るのです。そのため、引数を評価しないようにする関数が用意されています。次の例を見てください。

gosh[r7rs.user]> (define y 'x)
y
gosh[r7rs.user]> y
x
gosh[r7rs.user]> (define y '(1 2 3 4))
y
gosh[r7rs.user]> y
(1 2 3 4)

引用符 ' をつけると、その次の S 式は評価されません。引用符は関数 quote の省略形で、'x は Scheme 処理系によって、(quote x) と変換されます。quote はシンタックス形式で、引数を評価せずにそのまま返す働きをします。したがって、(define y 'x) の場合、(quote x) が評価されて x 自身が返り値となります。つまり、シンボル x に格納されている値が取り出されるのではなく、x 自身が関数に渡されるのです。その結果、変数 y にシンボル x を代入することができます。

同様に、リストの場合も引用符をつけることで、変数に代入することができます。この場合、リストは評価されない、つまり、プログラムとして実行されないので、最初の要素が関数である必要はありません。'(1 2 3 4) は (quote (1 2 3 4)) に変換され、それが評価されて (1 2 3 4) というリスト自身が関数 define に渡されるのです。

この場合、リストはプログラムではなくデータとして扱うことになります。リストにプログラムとデータという 2 つの役割を持たせていることが、ほかの言語とは最も異なる Lisp / Scheme の特徴です。

シンタックス形式以外の関数は引数を必ず評価するので、リストやシンボル自身をデータとして扱うために quote を頻繁に使うことになります。いちいち (quote (1 2 3 4)) と書いていては面倒だし、プログラムが読みにくくなってしまいます。そこで、'(1 2 3 4) のような省略形が使われるようになりました。

なお、シンボルとリスト以外のデータは、評価されても自分自身になる自己評価フォームですから、数値や文字列には引用符を付ける必要はありません。

●基本的なリスト操作

さて、これでリストをプログラムだけではなく、データとして扱うことができるようになりました。Lisp の由来である「LISt Procseeor」からもわかるように、Lisp / Scheme はリストを扱うことが得意のプログラミング言語です。ここでリスト操作の基本関数を説明しましょう。

(1) car list : リストの先頭の要素を取り出します。
(2) cdr list : リストの先頭要素を取り除いたリストを返します。

                 図 : car と cdr の操作

car と cdr は関数ですので、リストには引用符をつけることを忘れないでください。また、リスト以外のデータを与えるとエラーとなります。

car と cdr はリストを分解します。上図に示すように、car は先頭のセルの CAR 部に格納されたデータを返します。cdr は CDR 部に格納されたデータ (後ろに接続されているセル) を返します。つまり、先頭要素を除いたリストを返すことになります。

それでは、要素がひとつしかないリストの cdr はどうなるでしょうか。実際に試してみましょう。

gosh[r7rs.user]> (cdr '(a))
()

cdr は先頭の要素を取り除いたリストを返しますが、それはセルの CDR 部を返す働きと同じです。前回で、最終セルの CDR にはリストの終わりを示す特別なデータが格納されることを説明しました。したがって、要素がひとつしかないリストに cdr を適用 ^[*2] すると、リストの終端を表すデータが取り出されます。もうおわかりだと思いますが、この特別なデータが () なのです。() は「空リスト (empty list)」を表すリスト型 ^[*3] のデータです。

          リスト (1 2 3) の構造

              図 : リストの終端 (その１) 

今までのリストは、すべて終端に () がセットされています。なお、car と cdr にリスト以外のデータを与えるとエラーになります。Scheme の場合、car と cdr に空リストを与えてもエラーになります。Common Lisp の car と cdr とは違うので注意してください。

●ドット対とドットリスト

ところが、Scheme 処理系の立場になって考えてみると、リストの終端は CDR 部に格納されるデータがコンスセル以外であれば、そこがリストの終端であることがわかります。つまり、() でなくてもかまわないのです。

リストの終端が () 以外のデータである場合、そのリストを次のように表します。

左右のカッコの中間にドット ( . ) を置き、左側に CAR 部のデータを、右側に CDR 部のデータを書きます。つまり、リスト (a) は (a . ()) と表すことができます。このようなデータを「ドット対 (dotted pair)」と呼びます。たとえば、CAR 部がシンボル a で CDR 部がシンボル b であれば (a . b) となります。

普通のリストもドット対を使って表現できます。リスト (a b c) は、上図に示すように (a . (b . (c . ()))) と表すことができます。最初のセルの CAR は a で CDR はセルですから ( を書いて、次のセルの CAR と CDR を書いていきます。

それでは、リスト (a b c) の終端を d に変えてみましょう。ドット対を使った表記法では (a . (b . (c . d))) となりますが、これは (a b c . d) と表すことができます。このように、() 以外のアトムで終端されたリストを「ドットリスト (dotted list)」とか「行儀の悪いリスト (improper list)」と呼びます。

●リストの分解と合成

もう少し car と cdr の例を見てみましょう。

(car '((a b) (c d) (e f))) => (a b)
(cdr '((a b) (c d) (e f))) => ((c d) (e f))

リストの要素は (a b) であり、a ではないことに注意してください。a を取り出したい場合は car を 2 回適用します。

(car (car '((a b) (c d) (e f)))) => a

最初の car の引数はリスト (car '((a b) (c d) (e f))) ですから、この S 式が評価されて、(a b) という結果になります。このリストが最初の car に適用されて a を取り出すことができるのです。

それでは、2 番目の要素 (c d) を取り出す場合はどうするのでしょう。この場合は、car と cdr を組み合わせれば簡単に実現できます。

(car (cdr '((a b) (c d) (e f)))) => (c d)

最初の car の引数はリスト (cdr '((a b) (c d) (e f))) ですから、この S 式が評価されると先頭の要素 (a b) が取り除かれて、((c d) (e f)) という結果になります。このリストが最初の car に適用されて (c d) を取り出すことができるのです。

このように、car と cdr を組み合わせることで、リストのどの要素にもアクセスすることができるのです。Lisp / Scheme には car と cdr を組み合わせた関数 cXXr, cXXXr, cXXXXr が用意されています。X には a または d を書きます。(caar ls) は (car (car ls)) と同じ働きをし、(caddr ls) は (car (cdr (cdr ls))) と同じ働きをします。

なお、R7RS で cXXXr, cXXXXr を使用する場合、ライブラリ (scheme cxr) を import する必要があります。Gauche の REPL は RSR7 モードで起動すると、R7RS ライブラリを自動的に import しています。

次は、リストの合成を行う関数を説明します。

(3) cons x y       : CAR 部に x を CDR 部に y をセットしたセルを返します。
(4) list [args]    : args を要素とするリストを返します。
(5) append [lists] : 引数のリストを連結して返します。

cons は新しいコンスセルを生成し、そのコンスセルの CAR 部に第 1 引数 x を CDR 部に第 2 引数 y をセットします。x がデータで y がリストの場合、cons はリスト y の先頭にデータ x を追加したリストを返します。

                     図 : cons の動作

もし、引数が両方ともアトムであれば、cons はドット対を返します。また、引数 x はリストでも大丈夫です。

(cons 'a 'b) => (a . b)
(cons '(a b) '(c d)) => ((a b) c d)

car と cdr で分解したリストは cons で合成することができます。

                      図 : リストの分解と合成

この関係は、リストを操作する関数を作る場合の基本です。とても重要な関係なので、覚えておいてください。

関数 list は、その引数を要素とする新しいリストを返します。

                         図 : list の動作

上図のように、list は引数を新しいリストの要素として格納します。引数がリストの場合は、それが要素となります。リスト同士を繋ぐのではないことに注意してください。

これに対し、append はリスト同士を接続します。したがって、引数はリストでなければいけません。アトムを与えるとエラーになります。

                          図 : append の動作

append はリストを接続する場合、新しいセルを作成して引数の要素を格納します。ただし、最後の引数については、上図のように新しいセルを生成しません。要素自体には何もしないことに注意してください。

(append '((a b) (c d)) '(e f))   => ((a b) (c d) e f)
(append '((a b) (c d)) '((e f))) => ((a b) (c d) (e f))
(a b c d e f) ではないことに注意

このように、要素がリストの場合でも、そのリストの要素を取り出すことはせずに、引数の要素を並べるだけです。それから、append は複数のリストを引数に与えることもできます。

(append '(a b) '(c d) '(e f))      => (a b c d e f)
(append '(a) '(b c) '(d e) '(f g)) => (a b c d e f g)

この場合、引数のいちばん最後のリストについては、新しいセルを生成しません。それ以外の引数に対して、新しいセルを生成することになります。最初の例では、(a b), (c d) について新しいセルを生成します。次の例では、(a), (b c), (d e) について新しいセルを生成します。

●リストの操作は非破壊的

今まで説明した関数は変数の値を変更しません。

gosh[r7rs.user]> (define var '(a b c d))
(a b c d)
gosh[r7rs.user]> (cdr var)
(b c d)
gosh[r7rs.user]> var
(a b c d)
gosh[r7rs.user]> (cons 1 var)
(1 a b c d)
gosh[r7rs.user]> var
(a b c d)

もし変数 var の値を変更したい場合は、set! と組み合わせて使います。

gosh[r7rs.user]> (set! var (cons 1 var))
(1 a b c d)
gosh[r7rs.user]> var
(1 a b c d)
gosh[r7rs.user]> (set! var (cdr var))
(a b c d)
gosh[r7rs.user]> var
(a b c d)

●まとめ

今回はここまでです。最後に、今まで説明したことについて、簡単に復習しておきましょう。

1. 変数への代入は define と set! を使う。変数への代入は、今まで格納していた値を破壊する。
2. 変数には局所変数と大域変数がある。
3. 局所変数は、関数が実行されている間だけ有効である。
4. 大域変数への代入は、関数の実行が終了しても残っている。
5. 空リストは () で表す。
6. 普通のリストは、終端を () で表す。() 以外で終端されたリストをドット対、ドットリストという。
7. 引数を評価させたくないときは引用符 ( ' ) をつける。
8. リストを分解する関数は car と cdr である。
9. リストを組み立てる関数は cons, list, append である。
10. car, cdr, cons, list, append は変数の値を変更しない。変数の値を書き換えるときは set! と組み合わせて使う。

次回は、実行する処理を条件によって選択する方法と、同じ処理を何回も繰り返す方法を説明します。この方法を理解すると、おもしろいプログラムを作ることができるようになります。お楽しみに。

●問題

• cons と list で次に示すリストを作ってください
• xs : (a (b) ((c)) (((d))))
• ys : ((a b c) (d e f) (g h i))
• zs : ((a . b) (c . d) (e . f))
• 上記リストで各要素を取り出す S 式を作ってください
• リスト xs の n 番目の要素を取り出す関数 list-ref xs n を使うと簡単

●解答

gosh[r7rs.user]> (define xs (list 'a (list 'b) 'c (list (list 'd)) 'e (list (list (list 'f)))))
xs
gosh[r7rs.user]> xs
(a (b) c ((d)) e (((f))))
gosh[r7rs.user]> (define ys (list (list 'a 'b 'c) (list 'd 'e 'f) (list 'g 'h 'i)))
ys
gosh[r7rs.user]> ys
((a b c) (d e f) (g h i))
gosh[r7rs.user]> (define zs (list (cons 'a 'b) (cons 'c 'd) (cons 'e 'f)))
zs
gosh[r7rs.user]> zs
((a . b) (c . d) (e . f))

gosh[r7rs.user]> (car xs)
a
gosh[r7rs.user]> (list-ref xs 0)
a
gosh[r7rs.user]> (caadr xs)
b
gosh[r7rs.user]> (car (list-ref xs 1))
b
gosh[r7rs.user]> (caddr xs)
c
gosh[r7rs.user]> (list-ref xs 2)
c
gosh[r7rs.user]> (caar (cadddr xs))
d
gosh[r7rs.user]> (caar (list-ref xs 3))
d
gosh[r7rs.user]> (car (cddddr xs))
e
gosh[r7rs.user]> (list-ref xs 4)
e
gosh[r7rs.user]> (caaaar (cdr (cddddr xs)))
f
gosh[r7rs.user]> (caaar (list-ref xs 5))
f

gosh[r7rs.user]> (caar ys)
a
gosh[r7rs.user]> (caddr (caddr ys))
i
gosh[r7rs.user]> (list-ref (list-ref ys 2) 2)
i

gosh[r7rs.user]> (caar zs)
a
gosh[r7rs.user]> (cdar zs)
b
gosh[r7rs.user]> (caadr zs)
c
gosh[r7rs.user]> (cdadr zs)
d
gosh[r7rs.user]> (caaddr zs)
e
gosh[r7rs.user]> (cdaddr zs)
f