Clojureのloop/recurに相当するモノをつくってみた話.

golangを勉強すべく, lisp処理系などを実装し始めたのだが, vmなんて気の利いたモノは実装しないので, 末尾呼び出し最適化など は望むべくもない. しかしながら再帰の使えないlisp処理系などクソである. いろいろ考えた末, Clojureのrecurなら実装できそうなことが分かった. 機能としては限定的だが少ない手数で作れるためちょっとした処理系にはおすすめだろう. ということでどういうモノを作ったのか説明してみる.

末尾呼び出し最適化とは

[SICP]から必要な言葉を引っ張ってくる.

再帰

ここに来る人はこんな説明いらないとは思うのだが, 念のため. 素朴には, 関数を記述するのに関数自身への呼び出しが含まれている, というもので, たとえば階乗n!を計算するfactorialという関数は

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

などと書かれる. これは

• 1!は1である
• n!は(n-1)!にnをかけたモノである

という階乗n!の定義にしたがったものである. これを計算すると n * (factorial n - 1)がたくさん「積み上がる」ことになる.

もう一つの書き方は,

(define (factorial n)
  (fact-iter 1 1 n))

(define (fact-iter product counter max-count)
  (if (> counter max-count)
      product
      (fact-iter (* counter product)
                 (+ counter 1)
                 max-count)))
  

というもので, [SICP]では線形反復と呼んでいるようだ. 途中の結果とカウンタ, 上限を次々と渡している点が特徴である. 命令的な言語におけるfor-loopのようなモノである.

末尾呼び出し

ものすごくシンプルな例を出すと, 次のようになる.

(define f (n)
  (if (< n 3)
    (f (+ n 1))
    n))
      

"関数の呼び出し"が, fにおける"最後の計算"になっている, その事を末尾呼び出しという.

末尾呼び出し最適化

末尾呼び出し最適化とは, 末尾呼び出しの場合は, 「積み上がり」を生じさせずにloopでかけますよ という事. しかも自動でできる. 具体的には先ほどのfはこんな感じになる.

      fopt(n){
        for ; n < 3 ; {
          n += 1
        }
        return n
      }
  

唐突にgolangに変わってしまって申し訳ないのだが, fが最適化されるとこのようなfopt相当の"振る舞い"を示す. schemeの処理系はこの最適化が必須である([R5RS], [R6RS]等)

forで書きたくない, 作りたくない

lispの処理系を作っている手前, 他の処理系で処理できるコード, 具体的にはsrfiとかのコードを参考にすることにすることなるのだが, 当然再帰を使って書かれている. これを手動でfor構文で書き直す必要がある. その書き換えは確実にできるわけではなく, バグの原因である.

さらにはforを実現する構文を処理系にいれる必要がある. ところが相性が悪い. 具体的にはbreakやreturn, continueを入れる必要があるが, これはjumpでありどこに飛ぶかを制御する必要がある. vmベースでない場合, Eval関数に環境とS式を渡して評価するインタプリタになるが forのEval関数呼び出しまで抜ける必要が出てくるが, Eval呼び出しの 深さがマッチしている保証がどこにもなく, 処理系の実装に用いる言語によっては 困難もしくは適切な記述が難しい(golangでこの目的でpanic/recoverを使うことは邪悪だろう). かといって, stack over flowの可能性のある再帰呼び出しを行う訳にはいかない.

loop/recur

そこでloop/recurの登場となる. これはClojure[clj]の構文である. Clojureに関しての日本語の情報は[stu]が詳しい. JVMの制限上, schemeのような再帰呼び出し最適化が不可能であるため用意された. 具体的なコード例をあげてみよう

(define xs (loop [i 0 xs '()]
             (if (< i 3)
               (recur (+ i 1) (cons i xs))
               xs)))

このコードは

1. loopの部分でiに0を, xsに'()を束縛し,
2. i < 3ならば recurの処理を(後述)
3. そうでないならxsを返す

という処理になっている. loopはxsが返ってくると xsをそのまま返す. ある種のletだと思っていて良い.

recurなのだが loopで作られた束縛に異なる値を束縛した環境を 別途作り, 再びloop内部を先頭から評価するという挙動をする. したがって初回の実行は i = 0, xs = '()なので

  recur 1 (0)
  

となり, loop [i 1 xs (1)]相当で次のloopが開始される.

実装してみる

方針

loopでRecur Objectを作り, recurに束縛, recurがevalされる度に 新たにenvを作るという方針にした. 処理系の束縛は深い束縛である(Scopeがnestする度にEnvironmentが積み重なっていく).

どの辺につっこむか? というイメージを得るために 対象のコードと[SICP]のevalのコードを引用しておく. loopもrecurもapplyされるモノである.

(define xs (loop [i 0 xs '()]
             (if (< i 3)
               (recur (+ i 1) (cons i xs))
               xs)))

(define (eval exp env)
  (cond ((self-evaluating? exp) exp)
        ((variable? exp) (lookup-variable-value exp env))
        ((quoted? exp) (text-of-quotation exp))
        ((assignment? exp) (eval-assignment exp env))
        ((definition? exp) (eval-definition exp env))
        ((if? exp) (eval-if exp env))
        ((lambda? exp)
         (make-procedure (lambda-parameters exp)
                         (lambda-body exp)
                         env))
        ((begin? exp) 
         (eval-sequence (begin-actions exp) env))
        ((cond? exp) (eval (cond->if exp) env))
        ((application? exp)
         (apply (eval (operator exp) env)
                (list-of-values (operands exp) env)))
        (else
         (error "Unknown expression type -- EVAL" exp))))  
  

次にgolang側のloop実装コード. Recur Objectを作るときに内部で環境を作っている. 肝はEvalして返ってきたObjectがRecurならばfor-loopするということだ. これによって, loopの位置に制御が戻る. またRecur Objectが持っている環境がEvalに使われている.

 env.Bind("loop", Closure(func(dynamic Environment, cdr Pair) interface{} {
  r := NewRecur(dynamic, Car(cdr))
  var x interface{}
  for recuring := true; recuring; {
   for _, b := range List2Arr(Body(cdr)) {
    x = Eval(r.Env(), b)
   }
   _, recuring := x.(*Recur)
   if !recuring {
    return x
   }
  }
  panic("never reach")
 }))
  

Eval内部でRecur ObjectがApplyされる近辺.

• Cdr(expr)で(recur (+ i 1))の(+ i 1)を保持している.
• r.Updateで, Recur Object内に保持される次のループに使われる環境を作っている.

  r, ok := car.(*Recur)
  if ok {
   xs := make([]interface{}, 0)
   for _, v := range List2Arr(Cdr(expr)) {
    xs = append(xs, Eval(env, v))
   }
   r.Update(xs)
   return r
  }
  

closureとの兼ね合い

loopのなかでclosureを作ったときループ変数を捕捉したらどうなるか?ということだが, recurのUpdateで新たに環境が作られているので問題ない. 次のコードは, 2, 1, 0を出力する. recurによって作られたが参照されていない環境はGarbage Collectされるので 環境が青天井に生成されてメモリが圧迫される心配はない.

(define xs (loop [i 0 xs '()]
             (if (< i 3)
               (recur (+ i 1) (cons (fn [x] i) xs))
               xs)))
((car xs) 'a)
((cadr xs) 'a)
((caddr xs) 'a)
  

さいごに

Clojureのloop/recurの説明は山ほどありますが, わかりにくいことが多いと思います. ここでの実装のようなとらえ方でいればイメージが湧くかと思いますがどうでしょう? closureのある言語でのforって裏でいろいろやってる想像ができますね. loop/recur構文を使った, 末尾再帰呼び出しの手動最適化は, 処理系側の実装コストが小さいので lisp処理系を実装するときは作ってみるといいと思います. ではでは〜

文献

• [SICP] "計算機プログラムの構造と解釈第二版" 1.2.1 線形再帰と反復, 4.1.1 評価器の中核
• [R5RS] Revised^5 Report on the Algorithmic Language
• [R6RS] Revised^6 Report on the Algorithmic Language. 日本語ユーザにとってありがたいのはこの辺.
• [SRFI-1] SRFI-1 リストライブラリ日本語訳
• [clj] clojure.org
• [stu] "プログラミングClojure" Stuart Halloway (著), 川合史朗 (翻訳) Amazon