Edited at

関数型の紹介と最適化について語りたい

関数型言語とか関数型プログラミング、最近になってちょっと有名になってきたけど実際にはそこまで世間に馴染んでない気がします。

かつてMITではコンピュータサイエンスの授業としてSICP(Structure and Interpretation of Computer Program)という教科書を使っていましたが、その教科書での使用言語はSchemeというLispでした。(SICPのリンク)

最近はLispからPythonに変わったらしいけど、ここから察するに関数型ももう少し人権を獲得しててもいいような気が...

ぼく自身はLisperなのでLispをアツく推しているのですが、どうもみんなプログラミングを始めるというとPythonとかRuby、Cあたりに手を出すのでLisperのぼくはちょっと悲しいです....

余力のある方はLispとかHaskell、Scalaに手を出してみてください....

とまあ前置きが長くなりましたが、本稿では関数型プログラミングスタイルとその最適化について紹介します。

ちなみに本稿での使用言語はCommon Lispで処理系はSBCLとします。


関数型における最適化

最適化の手法をババっと書いていこうかと思ったのですが、その前にまず関数型プログラミングについて一度おさらいしてどういう特徴があるのか確認、その上で最適化の余地などを考察していこうと思います。


関数型プログラミングとは

そもそも関数というのは何か値を入力したら何か値を出力する箱みたいなものって感じです。

Screen Shot 2019-01-04 at 15.25.52.png

まあ雑な感じで説明すると関数とはこういうものですよね。

数学的にもう少し厳密な説明をすると、関数とは以下の性質を満たすものです。(Land of Lispより引用)


  1. 関数は渡される引数が同じであれば常に同じ値を返す(参照透過性)

  2. 関数は外部の変数を参照しない

  3. 関数の呼び出しが変数の値を変えることはない

  4. 関数の目的は引数から値を計算することのみである

  5. 関数はそれ以外に外界に影響を与えない(副作用)

  6. 関数は外界から情報を受け取らない

これらを可能な限り満たすのが関数型プログラミングスタイルと呼ばれるものです。

定義域から値域への矢印が関数の仕事ですね。

Screen Shot 2019-01-04 at 15.23.31.png

ちょっと具体的に、例えば整数が格納されたリストがあり、それら各要素をインクリメントするコードを書きたいとしましょう。

このときPythonで命令型に書くと以下の通りになります。


test.py

for i in range(len(lst)):

lst[i] += 1

ちなみにCommon Lispで命令型で書くと以下の通りになります。


test.lisp

(loop for i below (length *lst*)

do (setf (nth i *lst*) (incf (nth i *lst*))))

もちろん、このコードでもやりたいことは叶うし別に問題ないです。

ただ、このコードではリストlstが破壊的な操作によって要素に変更が行われており、もし他の箇所でもリストlstが使われいるとバグの温床となるということや、リストlstの操作のために一時変数iを使っていて、こうした一時変数の存在はコードを膨らませてバグを生みうる原因となるなどが指摘できます。

さて、Lisperはこのような命令型の書き方はせず以下のような書き方をします。


hoge.lisp

(mapcar (lambda (x) (incf x)) lst)


Common Lispではmapcarという高階関数を使うことでこのように簡潔に書けます。


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

関数型プログラミングスタイルとして特徴的なのが基本的にfor文やwhile文などのループ構文を使わずに再帰によってループを表現するというところでしょう。

例えば関数型の入門の際によく持ち上げられる問題としてn!を計算するコードを書くというものがあります。

n! = n \times (n-1) \times \dots 1

これは命令型だとfor文を使って以下のように書けます。


factorial.py

answer = 1

for i in range(1, n+1):
answer *= i

これは階乗の式を素直に実装していると思います。

しかし、この階乗の式を以下のように再帰的に見ることもできます。

a_n = n! \\

a_n = n \times a_{n-1}

これを用いることで、関数型では以下のように書くことができます。


hoge.lisp

(defun factorial (n)

(if (= n 1)
1
(* n (factorial (- n 1)))))

命令型のコードと関数型のコードを比較すると、命令型ではカウンタとしての一時変数iが使われているのに対して関数型は一時変数を使わずにスッキリ記述できています。


結局のところ関数型は何がいいのか

以上のコードを見て「....で?」って感想の人はいるかもしれません。

もちろん命令型の書き方の方が可読性は高いし、何をしているのかが明確でわかりやすいでしょう。

ただ、その上で関数型の良さとして


  1. 一時変数を使わないので簡潔に書ける

  2. コードが膨らまない

  3. バグが減る

あたりが挙げられると思います。

これらの恩恵は関数は副作用を生まずに値を計算するだけという性質に起因しています。

というのも、関数型は一時変数やリストの破壊的操作を嫌うので、結果としてコードが行うのは関数に基づく計算のみで、そうしてコードが簡潔になるのです。


関数型は万全なのか

ここまで見て関数型すげええええ!!俺も関数型始めるわ!!!ってなった人はいるでしょう。

ぼく自身も関数型erなので関数型に惚れ込んでくれると嬉しいです。ハピハピです。

ただ、大切なこととして関数型は万全ではありません。

もちろん、関数型はコードが簡潔になってバグは減り、プログラマー側も頭が良くなったような気分になってハッピーです。

しかし、問題となってくるのがパフォーマンスです。

性能やパフォーマンスは関数型プログラマーにとって悩みどころで、というのも既存の変数やデータ構造に変化を入れずに常に新しい値を作るのはメモリをめっちゃ食うわけです。

そしてスピードも大して出ないし、結局のところ関数型スタイルはコードが簡潔になるだけの技術だったのです。

はい、終わり。お疲れ様でした〜。








...というような終わり方はしません。

ここまでは関数型プログラミングスタイルの入門、いや、門前です。

ここからの最適化のあたりが関数型の本当の面白いところなのです。


関数型プログラミングスタイルでの最適化

ここまでで関数型のお気持ちがわかったということで、これからはガンガン最適化をしていきます。


末尾呼び出し最適化

まず最初に紹介するのは末尾呼び出し最適化です。

先述の通り、関数型スタイルはfor文などのループ構文を嫌い、再帰によってループを表現します。

しかし、この再帰はただやってしまうとめちゃくちゃメモリを食うことになります。

ここでもう一度nの階乗を求めるコードを考えましょう。


hoge.lisp

(defun factorial (n)

(if (= n 1)
1
(* n (factorial (- n 1)))))

この再帰を先述した通りのコードだとコード内部で行なっている作業としてはまずm!を求めたあとに(m+1)を掛けなければいけないというようになっています。

つまり関数factorialを呼ぶたびにあとで結果にm+1を掛けなきゃとコードの中で考えているわけです。

Screen Shot 2019-01-04 at 17.09.54.png

インタプリタやコンパイラ内ではこのデカい値をいちいち記憶しており、そうしてプログラムスタックが溢れてクラッシュするのです。

ここで登場するテクニックが末尾呼び出しというテクニックです。

このテクニックは関数自体を呼ぶのがしんどいんだから、途中で値を保存するやつを用意しておけばいちいち記憶しなくていいじゃんというのが基本コンセプトとなっています。

コードは以下のようになります。


hoge.lisp

(defun factorial (n)

(labels ((f (m acc)
(if (= m 1)
acc
(f (- m 1) (* m acc)))))
(f n 1)))

この場合の階乗を求めるコードでは、途中結果を保存するためのacc(アキュミュレータと呼ばれる)という余分な引数を扱うローカル関数fを用意することで階乗を求めます。

ローカル関数とaccを用いたこのコードの良さとしては今までのように途中の値を覚えておく必要がなくスタック操作を省けるのでとても高速なのです。

このコードではローカル関数fを用意したあと、最後にそのコードをポンと呼び出すわけですね。

末尾呼び出し最適化によって関数型のコードは不要なスタック操作を省けてかなり高速化させることができるので有用な最適化手法です。


メモ化

メモ化とはクロージャによる最適化手法です。


クロージャとは

以下のようなコードを考えます。


hoge.lisp

(let ((number 0))

(defun my-print (exp)
(print number)
(print exp)
(incf number)
nil))

letで定義される変数はレキシカル変数と呼ばれるものです。

そしてこのlet内で定義された関数my-printではこのレキシカル変数をインクリメントしています。

では、このmy-printを呼び出すとどうなるでしょう?

Screen Shot 2019-01-04 at 18.23.09.png

関数を呼び出すたびにnumberの値はインクリメントされていきます。

let内で定義した値はlet内でのローカル変数ではなく、このブロックが終了したのちにも生きています。

実はガベージコレクションが最初に実装されたのはLispなのですが、本当にガベージコレクションが働いていたらこのletでの定義されたnumberはゴミとして回収されてメモリから抹殺されているはずです。

このようにletの外でも変数が生きているのがクロージャの効果なのです。


コードを最適化する

フィボナッチ数を計算するコードを考えてみましょう。

Fibonacci(1) = 1 \\

Fibonacci(2) = 1 \\
Fibonacci(n) = Fibonacci(n-1) + Fibonacci(n-2) \ \ (n \ge 3)

これを愚直にコードで実装すると以下の通りになります。


hoge.lisp

(defun fibonacci (n)

(if (or (= n 1) (= n 2))
1
(+ (fibonacci (- n 1)) (fibonacci (- n 2)))))

このコードではFibonacci(n)を計算するためにFibonacci(n-1)を計算し直しています

このもう一度計算し直すところ、途中の計算結果をメモしておくことで最適化ができそうな気がしませんか?

では、先ほどの末尾呼び出し最適化と合わせてフィボナッチ数を求めるのを最適化してみましょう。


hoge.lisp

(let ((acc '(1 1)))

(defun fibonacci (n)
(if (< n 3)
(car acc)
(setf acc (cons (+ (car acc) (cadr acc))
acc)))
(if (< n 3)
(car acc)
(fibonacci (- n 1)))))

このコードでは計算したフィボナッチ数をacc-listの頭に追加していってフィボナッチ数列を作ってるわけです。

このテクニックにより二度手間を避けることができます。


他の最適化手法

関数型プログラミングにはこれ以外の最適化手法として遅延評価などたくさんあります。

他の手法については興味を持った人はSICPなどで勉強してみてください。

いい勉強になると思います。


まとめ

先日On Lispを読み終わって、一度何かしら勉強した形跡を残すべきかなぁと思い、今回は関数型プログラミングについての知識をまとめました。

冒頭でも触れた通り、やっぱり関数型はどうもまだ注目されていないようです....

なんでだろう?

まあなんにせよ、今回の記事を読んで関数型プログラミングの手法に興味を持ってくれればいいなと思います。

ではお疲れ様でした!


追記

コードが間違っていたので訂正するついでに手元の環境で最適化手法を使ってどのくらい高速化できてるか確認してみたのですが、SBCLのコンパイラの最適化の方が圧倒的に高速化できてるということがわかりました。

Screen Shot 2019-01-08 at 14.09.01.png

こちらの画像を見ていただくとわかる通り、factorial1がなんの工夫もしてないやつでfactorial2が末尾呼び出しを使ったやつです。

これらの速度を測ってみたところ、前者のなんの最適化してないやつのほうが速いということがわかりました....

流石はSBCL....ぼくみたいな凡人が思いつきのゴミみたいな最適化手法を乗せたところでコンパイラ側の最適化の方が優秀ということですね....

まあ....今後もがんばっていきましょう....