トップダウンに見えるコードも、
REPLて書くときはボトムアップ
（Common Lisp）

by
  • AtCoderの問題をCommon Lispで解くとき、完成したコードはトップダウンの構造を持つが、実際に書く順序はボトムアップになる。
  • REPLを使った開発では、まず小さな部品関数を作って動作確認し、それを積み上げて全体を組み立てていく。
  • 完成形のコードは外側から内側へと読む構造になっており、手続き型の「上から下へ流れる」書き方とは異なる。
  • この非対称性を意識すると、他人のコードを読むときに呼び出し構造を追いやすくなる。

関連記事

1. 問題：Fibonacci Reversed

AtCoderの問題をCommon Lispで解いていて、気づいたことがあります。
完成したコードの構造と、実際に書いた順序が、逆向きになっているのです。

整数 X1X_1、X2X_2 を受け取り、次のルールで数列を作ります。

  • F1=X1F_1 = X_1
  • F2=X2F_2 = X_2
  • Fn=reverse(Fn−1+Fn−2)F_n = \text{reverse}(F_{n-1} + F_{n-2})（n≥3n \geq 3）

ここで reverse は数を桁反転する操作で、たとえば 123 を反転すると 321、120 を反転すると 21 になります。
F10F_{10} を求めよ、という問題です。

1.1. 完成したコードと構造

(defun f-rev (n)
  (list->num (reverse (num->list n))))

(defun num->list (n)
  (loop with x = n
        while (> x 0)
        collect (mod x 10)
        do (setf x (floor x 10))))

(defun list->num (lst)
  (loop for n in lst
        for i from 0
        sum (* n (expt 10 i))))

(defun fib-rev (n dp x y)
  (cond ((gethash n dp))
        ((= n 1) x)
        ((= n 2) y)
        (t (setf (gethash n dp)
                 (f-rev (+ (fib-rev (- n 1) dp x y)
                           (fib-rev (- n 2) dp x y)))))))

(defun main ()
  (princ (fib-rev 10 (make-hash-table) (read) (read))))Code language: PHP (php)

完成したコードを main から呼び出し順に見てみると、こうなっています。

  • main は入力を受け取って fib-rev を呼びます。
  • fib-rev はメモ化再帰でフィボナッチ数列を計算し、各ステップで f-rev を呼びます。
  • f-rev は数を桁反転します。
    内部で num->list と list->num を呼びます。
  • num->list は数を各桁のリストに分解します。
  • list->num は桁のリストを数に戻します。

main が起点となり、fib-rev、f-rev、num->list へと呼び出しが深くなっていく、トップダウンな構造です。

2. 書いた順序はボトムアップだった

一方、REPLで実際に書いた順序は逆でした。

まずは、桁反転する f-rev 関数を作ることを考えました。
それを num->list、list->num、f-rev の3つの細かい関数に分解します。

まず num->list を書いて動かします。

(num->list 123)  ; => (3 2 1)Code language: PHP (php)

次に list->num を書いて、往復できることを確認します。

(list->num '(3 2 1))  ; => 123Code language: PHP (php)

それを組み合わせて f-rev を作り、桁反転が正しく動くことを試します。

(f-rev 120)  ; => 21Code language: PHP (php)

この f-rev を使って、fib-rev を定義していきます。

(defun fib-rev (n dp x y)
  (cond ((gethash n dp))
        ((= n 1) x)
        ((= n 2) y)
        (t (setf (gethash n dp)
                 (f-rev (+ (fib-rev (- n 1) dp x y)
                           (fib-rev (- n 2) dp x y)))))))

引数 n は何番目の項かを、x と y は F1F_1、F2F_2 の初期値を表します。
dp はハッシュテーブルで、一度計算した値を記録しておくメモ化のためのものです。

n が1か2なら初期値をそのまま返します。
それ以外は、一つ前と二つ前の項を再帰で求めて足し、その結果に f-rev で桁反転をかけます。
計算した値は dp に保存して、同じ項を再計算しないようにしています。

最後に main で、標準入力から x と y を読み取り、空のハッシュテーブルを dp として生成して fib-rev に渡します。

3. 時系列と依存関係の逆転

C++やPythonなどのコードでは、「readして、変換して、出力する」という時系列で書く、いわば「手続き型」のスタイルが一般的です。

# Python のコード例
x, y = map(int, input().split())

a = [x, y]
for i in range(2, 10):
    total = a[i - 1] + a[i - 2]
    reversed_str = str(total)[::-1]
    a.append(int(reversed_str))

print(a[9])Code language: Python (python)

これは、読む順番と実行順番が一致していますが、途中に息をつく区切りがないように感じます。
手続き型の長い関数は流れが追いやすいですが、途中の変数が何のためにあるか分かりにくくなりがちだからです。

一方、関数型の設計で完成したコードは、外側から内側へと読む構造になっています。
外側のコードは全体の構造を記述し、細部の実装は内側に依存しています。

ただ、REPLを使った開発ではその内側の部品から積み上げて作っています。
各関数が小さく独立していれば、完成前にREPLを使って部品ごとに動作確認でき、底から積み上げながら全体を組み立てられます。

3.1. 読みやすさへの影響

ただ、自分で書いたコードは、作った順番と各関数の役割を知っているので、読んで操作を追えますが、他人のコードを読むときは大変です。

呼び出しを追いかけながら、細部まで降りていく必要があるからです。
たとえば、fib-rev の中に f-rev が出てきたとき、それが何をするか分からなければ、定義まで飛んで確認することになります。

そのため、関数の命名は大事です。

4. まとめ

関数型のコードは、完成形だけ見るとトップダウンに設計されているように見えます。
REPLで育てるプロセスはボトムアップで進む。

この非対称性を意識すると、他人のコードの読み方にも役立つかもしれません。