CommonLisp でできるだけたくさんの方法で階乗計算を実装してみた

Lisp Advent Calender 2015の7日目の記事です。
書いたら夏休みの自由研究そのものになっておりました。レポートを評価する先生の気分でご覧ください。

(2016年1月14日：コメントいただいた単純ループについての誤記を訂正)

結論から

整頓した結果として 19種類　の方法を紹介します。
別々の定義として試したものは全体で 32種類あります。排除した条件については後述します。

テストを含むソースコードはGitHubの記事用公開リポジトリに置いてあります。

大前提

• CommonLispが標準で持っている機能のみで実装する
  • つまり, ライブラリを利用しないこと
• 10, 50, 100, 1000の階乗計算に対して t を返す関数を定義すること
  • 関数名は実装に応じて変えている factorial-dotimesなど。
  • それ以外の呼び出しを行った場合：原則考慮しない
  • できる限りfactorialの定義に沿った答えを返すようにする
• 変数の宣言・定義は最小限にとどめる。
  • n : 引数 n! を計算結果とする
  • k : １～ｎを利用する場合のカウンタ変数
  • k-1 : dotimes が 0 オリジンなので、計算用に＋１する必要があるという目印として
  • acc : 積算値を保持する変数

factorial-test.lisp

(= (factorial 10) 3628800)
(= (factorial 50) 30414093201...)
(= (factorial 100) 93326215443...)
(= (facotrial 1000) 4023872600770...)

実装一覧

実行環境と動作確認は、Windows 10 + SBCL 1.2.14 にて確認しました。

dotimes

factorial.lisp

(defun factorial-dotimes (n)
  (let ((acc 1))
    (dotimes (k-1 n)
      (setf acc (* acc (1+ k-1))))
    acc))

dotimesの戻り値は必ずnil, 処理結果は別に保持する必要があります。

単純loop (マクロ) (loop マクロではない)

factorial.lisp

(defun factorial-simple-loop (n)
  (let ((k 1)
        (acc 1))
    (loop
      (when (> k n) (return acc))
      (setf acc (* acc k))
      (incf k))))

return を指示しないと戻り値が nil という点に注意が必要です。

doとdo*

factorial.lisp

(defun factorial-do (n)
  (do ((k 1 (1+ k))
       (acc 1 (* acc k)))
      ((> k n) acc)))

factorial.lisp

(defun factorial-do* (n)
  (do* ((k 1 (1+ k))
        (acc 1 (* acc k)))
       ((>= k n) acc)))

なぜ 見た目がそう変わらない do, do* をわざわざ両方紹介したのかと言えば、
典型的な境界値バグを作りこみやすい処理だからです。
この = が必要か、不必要か。私にはわかりませんわかりますが時間を下さい。

今回の記事を書く上で最も多くのエラーを出力（少なくとも１０回以上）した処理です。

再帰的定義

factorial.lisp

(defun factorial-recursive (n)
  (if (<= n 1)
      1
      (* n (factorial-recursive (1- n)))))

無駄がないです。遊びもないです。

• Q : format による値のデバッグがしたくなったらどうしますか？
• A : progn を導入しましょう。

labels を用いた再帰的定義

factorial.lisp

(defun factorial-labels (n)
  (labels ((rec (n)
             (if (< n 1)
                 1
                 (* n (rec (1- n))))))
    (rec n)))

labels を導入するだけで関数定義の汚い部分が一気に隠せてしまう優れものです。

labels を用いた末尾再帰定義

factorial.lisp

(defun factorial-labels-tail-recursion (n)
  (labels ((rec (n &optional (acc 1))
             (if (< n 1)
                 acc
                 (rec (1- n) (* n acc)))))
    (rec n)))

そう。不用意に触られると危険な optional もね。

loop マクロ

factorial.lisp

(defun factorial-loop (n)
  (loop for k from 1 to n
        for acc = 1 then (* acc k)
        finally (return acc)))

sum, collectを使うときは簡単なんですが、そうじゃなくloop内の計算結果を式の評価結果する場合に

1. デフォルトが nil であること。
2. finally, return を組み合わせる必要があること。

この２点を知るまでに時間がかかりました。知ってしまえばこちらのものである。

loop マクロ (ｎ～１での計算)

factorial.lisp

(defun factorial-loop-decrement (n)
  (loop for k downfrom n downto 1
        for acc = n then (* acc k)
        finally (return acc)))

downfrom, downto でないと降順では動かないということに注意が必要です。
from, toだけで大丈夫かと一瞬期待しましたがそんなことはありませんでした。
詳細については実践 common lisp に記載があります。

tagbody

(defun factorial-tagbody (n)
  (let ((acc 1)
        (k 1))
    (tagbody
      factorial   (when (> k n)
                        (return-from factorial-tagbody acc))
                  (setf acc (* acc k))
                  (incf k)
                  (go factorial))))

なぞのタグと おもむろに現れる go がとても特別な色合いを醸し出すtagbody。
よくは知らないが、きっと処理が速いのでしょう。

少しひねった実装

ここからは繰り返しを少し離れた、あるいは少しひねった処理を紹介します。

補助関数：iota1-n 関数

数値 n を受け取り、1～nをリストとして含む関数を補助用に準備しています。

factorial.lisp

(defun iota1-n (n)
  (loop for i from 1 to n
        collecting i))

この関数を一般化したものが iota関数と呼ばれる関数です。
有名なCommon Lispユーティリティライブラリであるalexandriaに含まれています。

let を使わずにacc を定義 - optional 引数で。

factorial.lisp

(defun factorial-args-optional (n &optional (acc 1))
  (dotimes (k-1 n)
    (setf acc (* acc (1+ k-1))))
  acc)

引数に変数定義を逃がすというのは、short coding の世界で知った技ではあります。
この関数に第二引数を与えて処理をすることは推奨されません。

* の性質を用いる。apply を使う

factorial.lisp

;;; * function has simple solution
(defun factorial-apply (n)
  (apply #'* (iota1-n n)))

apply に与える引数は、リストです。リストの中身を対象関数の引数として展開します。

reduce による一括処理

factorial.lisp

(defun factorial-reduce (n)
  (reduce #'* (iota1-n n)))

mapcar を使おうと思い立ったのはよかったのですが、mapcar は原則入力と出力が１対１の対応となっていました。

複数の値を一つの値へまとめるような処理を行う場合には reduce を使うということです。他言語ではfold とも。

CLOS の method として integer 型にfactorialという関数を追加

factorial.lisp

(defmethod factorial-clos-method ((n integer))
  (apply #'* (iota1-n n)))

CLOSの関数定義は、C++,JavaやC#のクラス定義を知っていると独特に見えてしまいます。関数がクラスに応じて動作を変えるのです。初めて知ると違和感を感じます。クラスに関数が所属するものという意識が強いもので。

上記の例はapply による処理と全く変わりませんが、解釈は大きく変わります。

なお、defgenericによる関数定義は暗黙に作成されることを期待した形です。

マクロによる定義１：* の性質を用いる形へ

factorial.lisp

;;; macro : target => (* 1 2 3 .. n)
(defmacro factorial-with-macro (n)
  `(* ,@(iota1-n n)))

マクロによる定義は関数による定義と見た目は似ていても内情は大きく異なります。

一見正しく見えるこの処理ですが、少なくともこの式に (factorial-with-macro (1+ 3)) のように引数を式として与えると、正しく動いてほしいところですが、結果はエラーとなります。

より適切な定義は？悲しいことに検討しきれていません。gensym を使って変数を定義するとか？

マクロによる定義２：再帰的にも見える定義で

factorial.lisp

;;; macro : target => (* n (* n-1 (* n-2 (* ... (* 2 1))))))
(defmacro factorial-with-recursive-macro (n)
  (if (<= n 1)
      `1
      `(* ,n (factorial-with-recursive-macro ,(1- n)))))

上記の形は macroexpandで展開が途中で止まります。macroexpandはあくまで
最初に現れた要素がマクロの場合に限って展開してくれるというものです。

マクロによる定義３：末尾再帰的にも見える定義で

factorial.lisp

;;; macro : target => (* 1 (* 2 (* 3 (* ... (* n-1 n)..))))
(defmacro factorial-with-outside-macro (n &body body)
  (if (<= n 1)
      `(* 1 ,@body)
      `(factorial-with-outside-macro ,(1- n) (* ,n ,@body))))

macroexpandで最終的な形まで展開できる定義となっています。

階乗の定義であれば リストの長さを使っても大丈夫

factorial.lisp

(defun factorial-length (n)
  (do ((n-lst '(nil) (push 'nil n-lst))
       (acc 1 (* acc (length n-lst))))
      ((>= (length n-lst) n) acc)))

変数を１ずつ増やす代わりに、リストの長さを１ずつ増やして使ってみました。わざわざそうする意味はあるのでしょうか？ないと思います。必死でひねり出したネタ要素です。何をしているかのわかりづらさではこの中で一番高いかと思います。

考察

繰り返し処理の種類 : １０種類

紹介した処理の方法について、繰り返し処理の差としてのみ見た場合にまったく別とみなせるのは、変わった定義法を除けばdotimes, 単純なloop, do, loopマクロ, 再帰定義, tagbody, reduceの７種類でした。ここに現れていない繰り返し処理の方法としてdolist, map系関数, 暗黙にmapする関数 がありますが、これを含めても１０種類です。

私としては「思っていたより少なかった、それこそ２０以上ありそうな気がしていた」けれど「普通の言語なら３つぐらい。言語としては多いように感じた」というところです。関数やマクロの数に注目すれば、map系関数が５～７種類（未確認）と、暗黙にmap処理を行う関数が１０以上挙がるため、関数やマクロの数だけを見ればもっと多くあるかと思います。

各々の処理内容に差が表れている要因としては次のように分けられるように見られました。

• letによる別の変数定義が必要かどうか
  • 別途必要 : dotimes, 単純loop, tagbody
  • 利用するうえで必要 : do, loopマクロ
  • 不必要 : 再帰定義, reduce
• 式の評価結果が計算結果となるかどうか
  • ならない（nilである）: dotimes, 単純loop, tagbody
  • 明示的に指定が必要(デフォルトnil) : do, loopマクロ
  • かならずなる必要がある : 再帰定義, reduce

うーん、繰り返し処理のパラダイムがおおむね３つに分けられるということでしょうか？

何を同じとし、違うとするか：発散する要素

やろうと思えば、ちょっとした差（変数名が違う、スペースが違う、etc）があることを別の定義とします、という言い方もできなくはないですが、そうしてできた定義には本質的に、、、本質的にとはなんだ、という話もあるのですが、、、差がなく、そもそも別々とするものは何かという話になってしまいます。

今回の場合、まず、次の要素は作成開始の時点で排除しています

• わずかなスタイルの差、スペースの差、インデントの差
• 変数名が違うだけの定義を新たな答えとすること
• 無駄な変数を定義すること
  • しかしソースに残した factorial-dotimes-too-redundant 関数は 例として無駄な変数を作っています
• 未紹介 : 不必要にlet を分けること
  • とはいえ、不必要な変数を排除している場合、 変数が２つ以上なければ見た目は変わりません
  • 変数の数 の階乗通りぐらいには発散するのではないでしょうか
  • ソースにはどれぐらいのパターンができるかの検討結果として factorial-dotimes-too-redundant などを残しています。

そして、記事中では次のようなバリエーションが増える要素については紹介していません。

• リストを用いて処理をするようにする : 繰り返し種別 * １倍程度増える（ソース中＋９通り）
• 数値の取り方を変える：繰り返し種別 * 思いついた方法の数程度増える（現状３倍）
• 数値を降順に処理する：繰り返し種別 * １倍程度増える
• マクロによる定義にする : 何も考えないで作るだけで無限に増える？２倍以上の増加

未紹介：リストを用いて処理をするもの

dolist, dotimes を除くすべての方法が、やりようによって数値でもリストでも処理をすることが可能です。そして、処理内容には大きな差が見られないように思ったため、作成はしてみましたが紹介するのは避けました。dotimes, dolist がいかに単用途特化型であるかということがくっきりわかります。

dolist だけは特別扱いしてもよかったかなと思わないでもないですがdotimes のほとんど裏返しのようなものなのでやっぱりやめました。

未紹介：数値の取り方を特別な方法にするもの

とはいえ、length を １～ｎの数値を保持する方法だけを代表として紹介しました。他には、ソースに残しているものとしては次のものがあります。

• リストを伸ばし、length を 1～n を表す変数とする（本文紹介あり）
• iota を生成したうえで nth の要素をとる方法
• iota を生成したうえで１～ｎを探してそのインデックスを使う方法

うーん。どれぐらい回りくどく処理ができるのでしょう。それはそれで気になります。

未紹介：降順で処理

降順で処理する場合も大した差はありません。ないはずです。

• dotimes は基本的に昇順でしか処理しない
• loopマクロ はdownfrom, downto をしないと降順にできない（本文紹介あり）
• do, 単純loop, recursive, tagbodyはそんなに変わらない

ソースにも載っていません。気づいたのが投稿前日だったためです。loopマクロとマクロによる定義にのみ降順での処理を作成しておきました。

未紹介：マクロによる定義

紹介したマクロ定義による処理内容は３つです。３つで許してください。

作成していて気づいたのですが、紹介したマクロ定義以外の処理を単純にマクロの展開系として使うことが可能です。そうするだけでパターンは２倍になるでしょう。そうする意味はおそらくないですが。

加えて、この点については特に問題だと思っているのですが、今回紹介したマクロの例についてすべてが、引数に式を与えた場合にエラーになります。マクロについていかに無知であるかということを痛感しました。まだまだ、優れた＆実用的なマクロを書けるようになるには道のりが長いようです。

結局、どれぐらい書けるのか、どれぐらい発散するのか。やり始めるとどれぐらいになるか見通しが立たず、３つでやめた、というのが本音です。

あとがき

Common Lisp での繰り返し処理はずいぶんあるように見えるが、実際のところどれぐらいのバリエーションが作れるのだろう？そんな疑問から始めた個人的な調査が発端でありました。

代表的な課題として、当初は１～１０の和を計算する方法を課題としていました、Advent Calenderに掲載するにあたって、足し算はやったから掛け算にしよう！ということで掛け算にしてみました。階乗計算って再帰的定義の代表格みたいに紹介されることも多いですし。

階乗にしてよかったと思います。足し算は、繰り返しを必要としない数学的定義がたくさんありすぎて、話題としては面白いのですが考えは発散しやすいです。階乗は数学的定義できっちりとした値を求める式は探した限り近似値しか見つかりませんでした（今回は採用していません）その分、繰り返し以外の要素はずいぶん排除できたように思います。

単体テスト

今回作成した関数のテスト用に、テストフレームワークライブラリを別に調査していました。（別の記事に書くなりなんなりしようと思っています）最終的にFiveAMを採用しました。すごく簡単にかけたので。

とはいえ、テスト関数がほぼ is しかないということには閉口しました。proveのように各種テスト用の関数を準備してくれてもよいのにな、と。

おわりに

ウェブのCommonLispソースをでは、多くがloopで書かれています。その理由もなんとなくわかった気がします。一番なんかわかりやすいです。読みやすいです。間違えないです。

再帰的定義も簡潔さという点で悪くないのですが、ちょっとデバッグは難しくおもいます。スタックだの末尾最適化だのcommon lisp では避けられるということを聞いていると、やっぱり自分でも避けようと思うものです。

ほかにも今回していないこととして速度の問題は気になっているところではあります。今後機会を作って検討してみたいところです。