プログラミングを頑張る日記

プログラミングを勉強して、ハッカーになろう

Common Lispを頑張る(54)

クリスマスでしたね。彼女と復縁しました。
どうでもいいですね。久しぶりに「Land of Lisp」をやります。
第Ⅳ部「Lispは科学なり」、第14章「関数型プログラミングLispをレベルアップ」です。

関数型プログラミング

数学の関数には以下のような性質があり、プログラムもそれに従うことで関数型になれると。
■関数は引数が同じならば常に同じ結果を返す(参照透過性)。
■関数は、外部の変数を決して参照しない(変数の値が変わらないならばOK?)。
■関数呼出しが変数の値を変更することはない。
■関数の目的は、引数から値を計算することのみ。
■関数は外の世界に影響を与えない。
■関数は外の世界からの情報を受けとらない。

とはいえ全てのプログラムを関数型プログラミングスタイルで書くことは不可能。
外界に何もしてくれない(副作用のない)PCはインテリアにしかならないですね。
そして副作用を持つ汚いコードは「命令形」と呼ばれるそうです。
さて、ということでプログラミングを綺麗にする原理はこれ。
1.まず、大きい部分は関数型プログラミングスタイルで書く。
2.最後、小さい部分に必要な副作用を含ませて外界と繋ぐ。

関数型プログラミングスタイル例

品物を管理するプログラムという体の例があります。

CL-USER> (defun add-widget (database widget)
           (cons widget database))      ;副作用なし、きれい
ADD-WIDGET
CL-USER> (defparameter *database* nil)  ;副作用の匂い
*DATABASE*
CL-USER> (defun main-loop ()
           (loop (princ "品物の名称を入力してください: ") ;副作用
              (setf *database* (add-widget *database* (read))) ;ここでも副作用
              (format t "現在データベースには以下の品物が含まれます: ~a~%" *database*))) ;ここでも!
MAIN-LOOP
CL-USER>

めっちゃ単純ですね。不浄な(命令型な)部分が大きいのは、プログラム全体が小さすぎるからで、
プログラムが大きければ不浄の部分は割合として小さくなるそう。

add-widgetは関数的なコードなので、新しい値を返すことしかできません。
よってデータベースに品物を追加することが、今までのデータベースに品物を追加した
新しいデータベースを作って返すという形でしかできません。
これだけ聞くととんでもなく効率の悪い酷い方法です。
が、以前「実践Common Lisp」の方で知りました、consするだけならばcdr部分のリストは
リサイクルされるので本当に全てを複製している訳でないのです。
こういった「ずる」こそが効率的な関数型プログラミングを可能にするテクニックであるそう。
そしてこのテクニックの前提にあるのが以前のデータを変更しないという関数型プログラミングの考え方。
ふむふむ。

高階プログラミング

でも関数型プログラミングって実際どう書くのさ、への答えが高階プログラミングです。
それは関数を引数として受けとる関数であり、コードの合成を可能としてくれます。
リストの各要素に2を足すようなプログラムを考えてみます。

CL-USER> (defparameter *my-list* '(1 2 3 4 5))
*MY-LIST*
CL-USER>

今さらな話題ではあります。mapcarで一発です。まあ一旦忘れてください。

命令型での解法
CL-USER> (loop for n below (length *my-list*)
              do (setf (nth n *my-list*) (+ (nth n *my-list*) 2)))
NIL
CL-USER> *my-list*
(3 4 5 6 7)
CL-USER>

う~む、醜いですね。とはいえ利点もあるようです。
利点1.古いリストを使い回しているのでメモリ効率がよい。
利点2.ループする動作と各要素に2を足すという仕事を確かに合成し、こなしている。

そしてデメリット。
その1.元のリストを破壊している。*my-list*をいつのまにか変更してしまうようなことを、
プログラムに「隠された状態」があると言うそう。
しかもここで破壊しているのはリテラルリスト...。
その2.リストの現在の位置を指定するために変数を使わなければならない。
むやみに変数を増やすことはバグの温床となる。

関数型スタイルでの解法

まずは関数型スタイル初心者のつもりで(実際そうなのですが)高階プログラミングを使わない例を模写。

CL-USER> (defun add-two (list)
           (when list
             (cons (+ 2 (car list)) (add-two (cdr list)))))
ADD-TWO
CL-USER> (add-two *my-list*)
(5 6 7 8 9)
CL-USER> *my-list*
(3 4 5 6 7)
CL-USER>

わかりやすい再帰ですね。
これは先程の命令型の2つのデメリットがなくて好ましいと思いきや、
利点2の「仕事の合成」という面からみると、要素に2を足すということとリストを走査することが
混然としてしまっていると言えるようです。

高階プログラミングでの解法

では満を持して。

CL-USER> (mapcar (lambda (x) (+ x 2)) *my-list*)
(5 6 7 8 9)
CL-USER> *my-list*
(3 4 5 6 7)
CL-USER>

ほれぼれとしますね。当然元のリストに変更は加えません。
リストの走査はmapcarの仕事で、2を足すのはlambdaで定義された関数の仕事です。
高階プログラミングによって関数型スタイルを崩さず独立したコード同士を組み合わせる例でした。

ここから残りは関数型プログラミングの総評みたいな2ページがあり、それで14章は終わりです。
「やっぱ時代は関数型っしょ」という感じの顔で使いこなしていきたいですね。