Open Recursion in scala もしくは関数型もオブジェクト指向も仲良くしようよぉのお話

追記：これの完全版みたいなのが comfrk vol3 に載ってます。「今夜はお前と俺でマルチパラダイムだからな」とかいうのです。

あまりにもアウトプットしなさすぎなので適当に何か書きます。

フィボナッチ関数を scala で object-oriented な感じで書いてみます。

class Fib {
  def fib(n : Int) : Int = if (n <= 1) 1 else fib(n - 1) + fib(n - 2)
}

簡単ですね。しかし、簡単すぎます。というわけで、お決まりのメモ化を「Fib クラスに手を加えず」に行ってましょう。

class FibMemo extends Fib {
  import collection.mutable.Map
  private val table : Map[Int, Int] = Map()
  override def fib(n : Int) : Int =
    if (table.contains(n)) {
      table(n)
    } else {
      val result = super.fib(n)
      table(n) = result
      result
    } 
}

簡単ですね。折角なのでトレースとかもしてみましょう。今度も矢張り FibMemo クラスには手を加えずに。

class TraceFibMemo extends FibMemo {
  override def fib(n : Int) : Int = {
    println("Entering fib(" + n + ")")
    val result = super.fib(n)
    println("Exiting fib(" + n + ") = " + result)
    result
  }
}

簡単ですね。

このような外部からの新たな機能の埋め込みは、OOP のどのような性質によって実現されているのでしょうか？

Fib クラスの定義を見直してみましょう。

class Fib {
  def fib(n : Int) : Int = if (n <= 1) 1 else fib(n - 1) + fib(n - 2)
}

fib メソッドは単純な再帰を行っているように見えますが、定義内の unqualified な fib メソッド呼び出しは、実際には this を介したメソッド呼び出しになっています。。

class Fib {
  def fib(n : Int) : Int = if (n <= 1) 1 else this.fib(n - 1) + this.fib(n - 2)
}

this を介した late-bind なメソッド呼び出しとメソッドのオーバーライドによって、Fib クラスの fib メソッドの定義は外部に「開かれて」いるわけです。

このような性質のことを "Open Recursion" といったりします。

Open Recursion は実際強力です。この性質を関数型言語でも利用したい…しかし多くの関数型言語は OOP のための言語機能を提供してくれない！どうしましょう。

とりあえず Fib クラスの定義を、少しずつ functional な形に書き換えてみましょう。

まずは "this" を引数として明示的に取るようにします。

class Fib {
  def fib(self : Fib, n : Int) : Int = if (n <= 1) 1 else self.fib(n - 1) + self.fib(n - 2)
}

引数 self に対しては fib メソッドの呼び出ししか行っていないのだから、もうメソッド、より正確には関数をそのままもらってしまえばいいですよね。そうします。

class Fib {
  def fib(proceed : Int => Int)(n : Int) : Int = if (n <= 1) 1 else proceed(n - 1) + proceed(n - 2)
}

もう Fib クラスは要りませんね。

def fib(proceed : Int => Int)(n : Int) : Int = if (n <= 1) 1 else proceed(n - 1) + proceed(n - 2)

あとは fib 関数の第一引数を満たしてやれば、つまり「開いた」fib 関数の定義を「閉じて」やれば、Fib クラスの fib メソッドと同様の振る舞いをする関数を定義できたことになります。

しかしここで問題が生じます。fib 関数の型は (Int => Int) => Int => Int です。第一引数に自分自身を渡せば、当然型があわず、コンパイルエラーになってしまいます。

val slowFib = fib(fib)(_) // ダメ

fib 関数が要求するのは「閉じた」関数ですが、fib 関数自体は「開いて」います。fib 関数を fib 関数で「閉じる」ためには、まずは fib 関数を「閉じ」なければならない…

fib(fib(fib(fib(fib(fib(fib( ...

勿論どこまでいこうと「閉じる」ことはできません。堂々巡りですね。

説明が面倒なので色々端折りますが（スイマセン…）こんなときは最小不動点の存在を仮定して、不動点演算子を適用してやればいいわけです。（追記：関数を取り関数を返す関数としての fib には不動点ないです。ここで言ってるのは関数と整数を取って整数を返す関数としての fib です。しかし fix を適用しているのは前者の fib なので、不動点の存在を仮定してみたいなのは、あまりよい説明じゃなかったですね…）

def fix[T](f : T => T) : T = f(fix(f)) // ダメ！

素朴に実装してしまうと、再帰呼び出しにより無限ループに陥ってしまいます。このような実装が許されるのは、非正格な評価を行う Haskell のような言語だけです。
ここでは fib 関数が関数を引数に取ることを利用して、以下のように定義することで無限ループを回避することができます。

def fix[T](f : (T => T) => T => T) : T => T = f((t : T) => fix(f)(t))
val slowFib = fix(fib)

ラムダ抽象が都合よく評価を遅延してくれています。
scala には引数の評価の遅延を行うための "By-Name Parameters" があるので、より素朴な実装に近い generic なシグネチャを持つ定義に書き換えることもできます。

def fib(proceed : => Int => Int)(n : Int) : Int = if (n <= 1) 1 else proceed(n - 1) + proceed(n - 2)
def fix[T](f : (=> T) => T) : T = f(fix(f))
val slowFib = fix(fib)

元の fib 関数のシグネチャに影響を与えてしまうのが、若干イマイチな感じですね。とりあえず今回は By-Name Parameters を利用しない定義を採用しましょう。

不動点演算子を用いることで「開いた」fib 関数から「閉じた」slowFib 関数を得ることができました。今度は FibMemo クラスの fib メソッド相当の「開いた」関数を定義してみましょう。

def fibMemo(table : collection.mutable.Map[Int, Int])(proceed : Int => Int)(n : Int) : Int = {
  if (table.contains(n)) {
    table(n)
  } else {
    val result = proceed(n)
    table(n) = result
    result
  }
}

さて、ここから FibMemo クラスの fib メソッドのように振舞う関数を定義するにはどうすればいいでしょうか？元の定義を見直してみます。

  override def fib(n : Int) : Int =
    if (table.contains(n)) {
      table(n)
    } else {
      val result = super.fib(n)
      table(n) = result
      result
    } 

proceed に対応しているのは "super.fib" です。これは Fib クラスの fib メソッドのことなので、fibMemo 関数の引数 proceed は「開いた」関数として定義された fib 関数になっていればよさそうです。

はい、大体そんな感じです。一々丁寧に説明してると終わらないので、もう定義してしまいます。

val t = collection.mutable.Map[Int, Int]()
val fastFib = fix(memo(t) _ compose fib)

できました。あまり関数合成などに慣れていない人からすると魔術めいているかもしれませんが、fix と compose を適当に展開してやれば、どんな風に memo(t) と fib が組み合わさっているかが分かると思います。これはちょっとやってみてください。トレースの追加も簡単にできると思います。

まとめとあとがきと参考文献の紹介

OOP の持つ強力な性質 Open Recursion と、それを functional に実現する手法を紹介しました。性質のことを指して Open Recursion と呼んでるものもあれば、手法を指して Open Recursion と呼んでるものもあって、正確なところは正直よくわかりませんが、まあそんな感じです。どんな感じ？？？
あまり詳しくないのですが、アスペクト指向なんかもこれでうまく表現可能らしいです。

今回は最も単純な例で紹介しましたが、実際には複数のメソッドが交わっているようなこともあると思います。つまり「開いた相互再帰」の場合ですね。これもレコードなんかを使えばうまくいくはずです。

紹介するのに都合がいいという理由で scala で書きましたが、scala なら素直にクラスを利用して書けばいいと思います。Haskell なんかで object-oriented なコードを書きたい、もしくは object-oriented なコードを元に移植的な何かをする、みたいな時には使えると思います。ただ Haskell だと、メモ化やトレースやロギングを挟み込む、みたいなことをしようとすると、どうしてもモナドが出てきてしまうので、ちょっとなあ…と思ってやめました。その代わり fix の定義が素直ではなくなってしまいましたが…

書籍では Types and Programming Languages…皆大好き（？）TAPL なんかで紹介されているっぽいです。グーグルブックスで載ってそうなことだけは確認しました。

元々は Functional Pearl の The Monad Zipper で利用されているのを見て初めて知りました。直和型に対する「閉じた」再帰関数を、個々のより小さい型に対する「開いた」関数で定義する…みたいな、ちょっとひねった形で利用されていました。しかし部分関数を張り合わせて循環させて全関数を作るという、その気持ちは多分同じです。多分ネ。
The Monad Zipper では単に利用されているだけだったので、詳細は "EffectiveAdvice: Disciplined Advice with Explicit Effects" で知りました。この論文にどうやってたどり着いたかは忘れてしまいました…

本当はもうちょっと続くはずだったのですが、本格的に疲れたのでこれでおしまいにします。