誰向けかわからないCommon Lispでの関数型プログラミング入門とその未来

Lispと言えば関数型言語という印象を持つ人が多いようです。

まあ正直に言うと、Common Lispに関して言えば違うんですけどね。Common Lispは効率のためと言えばループも代入も使いまくるし、構造体もクラスもある。実際書かれたコードも関数型プログラミングとは程遠いことも多くて、たとえば僕が作ったClackのコードを見ればオブジェクト指向言語だって言っても信じると思います。

僕自身、繰り返しをわざわざ再帰で書くよりもloop使うことが多いです。最近loopに頼りすぎてて良くないなーと思うことが多く、Common Lispでも性能が重要でないところは関数型っぽく書く癖をつけないとなー、と思っていろいろ考えています。なんでもloopだと可読性が悪い。

特に、僕が今作っているCommon Lisp方言の「CL21」では関数プログラミングをもっとしやすくする機能を入れたいと思っています。

そういうわけで、最近はCommon Lispでの関数型プログラミングの方法について調べてCL21に取り込むことをしています。

だいたいまとまったので、Common LispとCL21で関数型プログラミングをするチュートリアルみたいなものを午前四時のローテンションで書いてみました。

以下の2章立てです。

Common Lispでの関数型プログラミングの現状
CL21での関数型プログラミングの未来

今読み返してみると、しれっとScheme知ってる前提だったりして、これ誰向けだよ、みたいな感じですが、まあご容赦ください。というかCL21のほうが本題だったりするので入門っぽい話を読みたくなかったら2章までスクロールしてください。

Common Lispでの関数型プログラミングの現状

関数

Common Lispで関数を定義するにはdefunを使います。

(defun 関数名 (パラメータ*)
  "ドキュメント文字列 (任意)"
  本体*)

例えば、Schemeで良く使われるiotaは以下のように定義できます。iotaはstartから始まるn個のリストを返します。

(defun iota (n &optional (start 0))
  (if (zerop n)
      nil
      (cons start (iota (- n 1) (1+ start)))))

(iota 10)
;=> (0 1 2 3 4 5 6 7 8 9)

(iota 5 3)
;=> (3 4 5 6 7)

無名関数

Common Lispで無名関数を作るにはlambdaを使います。

(lambda (n)
  (and (zerop n)
       (integerp n)))
;=> #<Anonymous Function #x302002ECCE3F>

無名関数を単に呼び出すときは、通常の関数の位置にlambdaフォームを書けばいいだけです。

((lambda (n)
   (and (zerop n)
        (integerp n)))
 3)
;=> NIL

((lambda (n)
   (and (zerop n)
        (integerp n)))
 0)
;=> T

((lambda (n)
   (and (zerop n)
        (integerp n)))
 0.0)
;=> NIL

高階関数

高階関数とは、関数を引数として受け取ったり、返り値として(無名)関数を返すような関数のことです。

例えば、多くの言語ではmapという関数がありますね。関数とリストを受け取り、リストのそれぞれの要素について関数を適用するようなものです。

Common Lispではこのような機能はmapcarと呼ばれています。

(mapcar #'1+ '(1 2 3 4 5))
;=> (2 3 4 5 6)

#'という記号は他の言語では特殊なので説明が必要ですね。

まずCommon Lispでは関数と変数の名前空間が分かれています (LISP-2という分類)。たとえば、Common Lispには関数listがありますが、同時に同じ名前のlistという変数を定義して使うこともできます。

このとき気をつけなければいけないのは、単にlistと書いたときに、それが変数なのか関数なのかを区別する必要があるということです。Common Lispで通常listを値として評価した場合、変数として扱われます。

(defvar list '(1 2 3))

list
;=> (1 2 3)

listを関数として扱いたいときは、#'をつけます。

#'list
;=> #<Compiled-function LIST #x3000000B4D6F>

上のmapcarでは1+という変数を渡しているのではなく、関数1+を渡したいので、#'が必要なのです。

また、reduceもよく使われる高階関数です。reduceはリストの先頭から渡された関数に適用し、さらにその返り値とリストの次の値を適用することを繰り返して結果を返す関数です。reduceは他の言語ではfoldとかinjectと呼ばれることもあります。

;; (+ (+ 1 2) 3) と同じ
(reduce #'+ '(1 2 3))
;=> 7

高階関数の使い道

上述した高階関数の便利なところは、その汎用性です。引数として渡す関数によってさまざまな用途に使えます。小さく汎用的なパーツを組み合わせて段々と大きくしていく手法はボトムアッププログラミングとして知られていますね。

たとえば、reduceを使うと以下のような関数が簡単に定義できます。

(defun sum (list)
  "数字のリストを受け取り、その合計値を返す"
  (reduce #'+ list))

(defun factorial (n)
  "数字を一つ受け取り、その階乗を返す。 n! = 1 * 2 * 3 * ... * n"
  (reduce #'* (iota n 1)))

sumは数字のリストを受け取り、その合計値を返します。factorialは数字を一つ受け取り、その階乗を返します。

mapcarではzipという関数が定義できます。

(defun zip (&rest lists)
  (apply #'mapcar #'list lists))

applyは一番最後の引数をリストとして扱って関数を呼び出す方法です。

zipは複数のリストを受け取り、その要素一つ一つをまとめあげる関数です。

(zip '(1 2 3) '(a b c) '(松 竹 梅))
;=> ((1 A 松) (2 B 竹) (3 C 梅))

関数合成 (compose)

さて、高階関数を使って組み合わせることで多くの関数を定義することを説明しました。この章ではさらに「関数合成」というテクニックを紹介します。

たとえば、関数gの返り値を関数fに渡したいとき、(f (g x)) のように書けばいいのはわかりますね。

この処理を高階関数に渡すには、無名関数を作るのが最もナイーブな方法です。

(lambda (x)
  (f (g x)))

しかし、組み合わせる関数がもっと多くなったときはどうでしょうか。

(lambda (x)
  (f (g (h (i (j (k x)))))))

長くなりますしだんだんと読みづらくなってしまいます。

このようなとき便利なのが「関数合成」です。ここでは関数composeを使います。関数composeはCommon Lispの仕様に含まれないため、Alexandriaのようなユーティリティライブラリを使うか、もしくは以下のようにreduceで簡単に定義できます。

(defun compose (fn &rest functions)
  (reduce (lambda (f g)
            (lambda (&rest args)
              (funcall f (apply g args))))
          functions
          :initial-value fn))

composeを使うとさき先ほどの例は以下のようになります。

(compose #'f #'g)

関数を引数で渡すだけなので括弧も少なく済みますね。

例として、リストの各要素の sin(n + 1) をリストとして返す処理は以下のように書けます。

(mapcar (compose #'sin #'1+) '(1 2 3 4 5))
;=> (0.9092974 0.14112 -0.7568025 -0.9589243 -0.2794155)

mapcarを2回使っても同じ結果が出ますが、リストを2回走査する必要があるし、ループのたびにリストを新しく作るためメモリ消費面でも良いコードではありません。

;; 良くない
(mapcar #'sin
        (mapcar #'1+ '(1 2 3 4 5)))

conjoin & disjoin

関数合成の例として、他にもconjoinとdisjoinという関数もよく使われます。

これらは各関数の返り値の真偽によって関数を複数実行する機能です。

たとえば、「ゼロかつ整数である」という条件の処理は以下のように書けます。

(lambda (n)
  (and (zerop n)
       (integerp n)))

この処理もcomposeのときのように、適用する関数が多い場合に煩雑になってしまいます。

このような処理を関数合成で解決するのがconjoinです。

(import 'alexandria:conjoin)

(funcall (conjoin #'zerop #'integerp) 0)
;=> T

(funcall (conjoin #'zerop #'integerp) 0.0)
;=> NIL

conjoinはandで関数を繋げた無名関数を返します。一方でdisjoinはorで関数を繋げます。

たとえば(disjoin #'plusp #'minusp)はプラスかマイナスの数値なら真を返します。つまりゼロではないという条件になります。

(funcall (disjoin #'plusp #'minusp) 100)
;=> T

(funcall (disjoin #'plusp #'minusp) 0)
;=> NIL

ちなみに余談ですが、ゼロかどうかはzeropで判断できるので、その返り値を反転させて返すほうが賢い実装ですね。

(funcall (lambda (n) (not (zerop n))) 0)
;=> NIL

このようなnotを加えるだけの呼び出しもよく使われるので、単に返り値の真偽を反転させる関数を返す関数complementというものもあります。

(funcall (complement #'zerop) 0)
;=> NIL

CL21での関数型プログラミングの未来

さて、ここからが実は本題です。

Common Lispで関数型プログラミングの機能をひと通り紹介しました。Common Lispでも十分に関数型プログラミングができますね。

しかし、僕が作っている新しいCommon Lisp方言の「CL21」では、より関数型プログラミングをしやすいようにするつもりです。たとえば、Common Lispには無いcomposeやconjoin、disjoin、curry、rcurryを含めました。

それだけでなく、さらにそれを簡易に使えるリーダマクロもあります。#'です。

Common Lispで#'はシンボルか、lambda式にしか使えなかったのですが、CL21ではこのリーダマクロに機能を追加したもので上書きしています。

実際のコードを見せたほうが早いかもしれません。

(funcall (conjoin #'zerop #'integerp) 0)
;=> T

;; ↑と同じ
(funcall #'(and zerop integerp) 0)
;=> T


(funcall (disjoin #'plusp #'minusp) 0)
;=> NIL

;; ↑と同じ
(funcall #'(or plusp minusp) 0)
;=> NIL

#'(and zerop integerp) と書くと conjoin に展開され、#'(or zerop integerp) と書くと disjoin に展開されます。

これは単に短いだけでなく、andとorという一般的な単語を使うことで直感的です。

さらに、もう想像つくと思いますが、complementに対応するものはnotです。

(funcall (complement #'zerop) 0)
;=> NIL

;; ↑と同じ
(funcall #'(not zerop) 0)
;=> NIL

もちろん、これらは組み合わせて使うこともできます。

(remove-if-not #'(and integerp
                      (or (not evenp)
                          zerop))
               (iota 11))
;=> (0 1 3 5 7 9)

composeだけはそのままcomposeを使います。

(mapcar (compose #'sin #'1+) '(1 2 3 4 5))
;=> (0.9092974 0.14112 -0.7568025 -0.9589243 -0.2794155)

;; ↑と同じ
(mapcar #'(compose sin 1+) '(1 2 3 4 5))
;=> (0.9092974 0.14112 -0.7568025 -0.9589243 -0.2794155)