関数型プログラミング事始め (36) イミュータブル(1)
関数型プログラミングがはじめての方へ贈る入門の書
前節：ラムダ計算(2) 次節：イミュータブル(2)
参考書：
・五味 弘「はじめてのLisp関数型プログラミング」技術評論社(2016)
・大山口 通夫、五味 弘「プログラミング言語論」コロナ社(2008)
・五味 弘「関数型プログラミングと数学(ITと数学)」技術評論社(2021)
ミュータブルデータ（可変データ）は配列などの一般的なデータであり、プログラムで多用されています。しかし、誰かがどこかでいつでも値が変更されるデータであり、値が不変であると信じてプログラミングしていると、知らずに勝手に変えられてしまうと、それがバグの原因になります。ミュータブルデータはバグの原因になる悪魔です。そこでバグにならないイミュータブルデータが必要になり、天使として登場します。
イミュータブルデータでどうしても値を変更したいときはコピーするか追加型で実装することになります。このため効率はミュータブルデータよりも悪くなりますが、バグがない安心できるプログラミングができます。
3.5 イミュータブルデータ
イミュータブルデータ(immutable data)は、値が変更できないデータです。逆にミュータブルデータ(mutable data)は値が可変なデータで、こちらが普通のデータです。配列もミュータブルです。
しかし最近はミュータブルデータがバグの大きな原因であることから、なるべくイミュータブルデータが導入され、それを使うようになってきています。例えば、文字列型データは、JavaやC#など多くの言語でイミュータブルデータになっています。
なおコンピュータの計算モデルのひとつであるチューリングマシンでは、テープに記録されるデータは可変です。つまりコンピュータはミュータブルデータでモデル化され、実装されています。この意味ではイミュータブルデータはミュータブルデータで実装されることになります。この意味でイミュータブルの方がえらいのです！
ここではOK! ISLispを使ってイミュータブルデータを見ていきます。まずはislispを起動してください。なおISLisp処理系はLisp処理系の導入で紹介していますので参照してください。
> ISLisp Version 0.80 (1999/02/25)
>
ISLisp>
(1) リスト
Lispでは、リスト(list)は基本的な関数を使っている範囲では、イミュータブルデータです。ここで基本的な関数とはcar, cdr,consとこれらの関数から作られるappendやreverseなどの関数になります。
ISLisp>(defglobal a '(1 2 3))
A
ISLisp>a
(1 2 3)
ISLisp>(defglobal b (cons 0 a))
B
ISLisp>b
(0 1 2 3)
ISLisp>a
(1 2 3)
グローバル変数aにリスト(1 2 3)を代入して、その後にリストaに0を追加しても、リストaの値は不変です。これは当たり前に見えるかもしれませんが、どのような操作をしてもリストの値は不変ということを覚えてください。
次にリスト連結のappendを見ていきましょう。
ISLisp>(defglobal c (append a '(4 5 6)))
C
ISLisp>c
(1 2 3 4 5 6)
ISLisp>a
(1 2 3)
リストaの後ろにリスト(4 5 6)を追加してみます。この結果は(1 2 3 4 5 6)になります。そこでaの値を見ると(1 2 3)のままです。これがイミュータブルデータになっているということです。
リストaはどのような関数が実行されても、値は不変の(1 2 3)のままになり、知らずに値が変わり、バグになることはありません。素晴らしいです。
イミュータブルデータの実装方法には、追加型とコピー型があります。最初の例で示したconsによる場合は追加型です。つまり元のデータには影響を与えずに、データを追加していくというものです。
後半のappendによる場合はコピー型です。appendされるリストの先頭であるaをコピーして、コピーしたものに(4 5 6)のリストをappendしています。これによって元のaには影響を与えないようにしています。
(2) 配列
(a) 配列はミュータブル
イミュータブルな配列を考えていきます。Lispでは配列はミュータブルです。値が変更できるデータです。このため、イミュータブルな配列を手動で作る必要があります。この意味ではLispは関数型ではないという噂もありますが、それは噂なので、あまり信じないでください。
(b) 破壊的操作がない配列はイミュータブル
配列をイミュータブルにする一番簡単な方法は、配列の値を変更する破壊的操作ができる関数を提供しないことです。Lispにはsetfによって配列の値を変更できますので、setfできなくすればいいのです。事実、JavaやC#の配列の一種では、文字列にセット関数をなくすことで、文字列をイミュータブルにしています。
この実装のときには、配列の値を変えたいときはオリジナルの配列をコピーして、それに値を変えた配列を新たに生成するしかありません。これは前述のコピー型による実装になります。
でもこれは面倒です。文字列ではめったに値は変更されないでしょうから、この実装でいいかもしれませんが、普通の配列では不便すぎます。
(c) ランダムアクセスリスト
前述のコピー型の実装ではなく、追加型の実装を見ていきます。リストの要素にランダムアクセスが可能なリストであるランダムアクセスリスト(Random Access List, RAL)を使って、イミュータブルな配列を追加型で実装します。
ランダムアクセスリストは、リストのインデックスとその値がペア（ドット対）になっているリストです。
例えば((1 .10) (0 . 0) (2 .20) (3 . 30))のRALは、配列[0 10 20 30]と抽象データ型的に同等なものになります。
ここで抽象データ型(abstract data type)とは、データと操作が一体になっているデータ型で、データにアクセスするときは必ず一体となった操作のみにするというものです。例えば抽象データ型の配列であれば、配列のセット関数set-list-arefとゲット関数list-aref（と生成関数）のみにします。
それではset-list-arefとlist-arefを作ってみます。
ISLisp>
(defun set-list-aref (list index value)
(cons (cons index value) list) )
SET-LIST-AREF
ISLisp>
(defun list-aref (list index)
(cdr (assoc index list)) )
LIST-AREF
セット関数set-list-arefではリストに(インデックス . 値)を先頭に追加します。ゲット関数list-arefはassocによって、リストの先頭からインデックスが一致するものを見つけ、cdr部に格納されている値を返します。
それではこれらの関数を使ってみます。
ISLisp>(defglobal list1 ())
LIST1
ISLisp>(setf list1 (set-list-aref list1 3 30))
((3 . 30))
ISLisp>(setf list1 (set-list-aref list1 2 20))
((2 . 20) (3 . 30))
ISLisp>(setf list1 (set-list-aref list1 0 0))
((0 . 0) (2 . 20) (3 . 30))
ISLisp>(setf list1 (set-list-aref list1 1 10))
((1 . 10) (0 . 0) (2 . 20) (3 . 30))
ISLisp>(list-aref list1 1)
10
list1にset-list-arefで各要素をセットすると、((1 . 10) (0 . 0) (2 . 20) (3 . 30))になります。そしてインデックス1の値をゲットすると10が返ります。
ISLisp>(defglobal list2 (set-list-aref list1 1 100))
LIST2
ISLisp>list2
((1 . 100) (1 . 10) (0 . 0) (2 . 20) (3 . 30))
ISLisp>(list-aref list2 1)
100
ISLisp>(list-aref list1 1)
10
list2にlist1のインデックス1に100の値をセットしたRALを設定します。list2のインデックス1は100を返しますが、list1のインデックス1は10のままになります。これによりlist1のRALは抽象データ型的にイミュータブルになります。
このようにリストを使って、追加型でイミュータブルデータの実装ができます。RAL以外にも多くのリッチなデータを定義することができます。
(予告) (3) 色々なイミュータブルデータ
次回は今回のリストや配列以外の色々なイミュータブルデータを見ていくことにします。
いいなと思ったら応援しよう！
