Y combinator - コードの恵み

Y combinator について分かった(気がする)範囲のメモ

『Scheme 手習い』 9章

この章が難しくて悩んでいたのだけど理由が分かった。

Learning Programming Languages with Koans によると*1『Scheme 手習い』は Koan の元になっているようだ。
各章はあるテーマに沿った演習を行っているのだが Koan と違って『Scheme手習い』では何の演習をしているのかぼかして記述してある。9章では何の演習を行っているか？と考えてみると再帰や lambda だ。
演習を行うために Y combinator を用いているだけなのにそれを理解しようとしていたのが間違いだった。6章の最後と同じでおそらく友情出演みたいなものだろう。

lambda を操作する理由を考えてしまうと分からなくなるが、操作自体はついていける。

関数名がないので再帰関数を入れ子で表現する

  static def length_0   = { l ->
    null_(l) ? 0 :
               add1(eternity(l.tail()))
  }

  static def length_le1 = { l ->
    null_(l) ? 0 :
               add1({ l1 ->
                      null_(l1) ? 0 :
                                  add1(eternity(l1.tail()))
                    }(l.tail()))
  }

  static def length_le2 = { l ->
    null_(l) ? 0 :
               add1({ l1 ->
                      null_(l1) ? 0 :
                                  add1({ l2 ->
                                         null_(l2) ? 0 :
                                                     add1(eternity(l2.tail()))
                                       }(l1.tail()))
                    }(l.tail()))
  }

length を引数に取るクロージャで表現する

  static def length_0 = {
    { length ->
      { l -> null_(l) ? 0 : add1(length(l.tail())) }
    }(eternity)
  }()

  static def length_le1 = {
    { length ->
      { l -> null_(l) ? 0 : add1(length(l.tail())) }
    }({ length ->
      { l -> null_(l) ? 0 : add1(length(l.tail())) }
    }(eternity))
  }()

  static def length_le2 = {
    { length ->
      { l -> null_(l) ? 0 : add1(length(l.tail())) }
    }({ length ->
      { l -> null_(l) ? 0 : add1(length(l.tail())) }
    }({ length ->
      { l -> null_(l) ? 0 : add1(length(l.tail())) }
    }(eternity)))
  }()

length を引数に取るクロージャを引数に取るクロージャで表現する

{ length -> { l -> null_(l) ? 0 : add1(length(l.tail())) } } を mk-length と呼ぶ

  static def length_0 = { mk_length ->
    mk_length(eternity)
  }({ length ->
    { l -> null_(l) ? 0 : add1(length(l.tail())) }
  })

  static def length_le1 = { mk_length ->
    mk_length(mk_length(eternity))
  }({ length ->
    { l -> null_(l) ? 0 : add1(length(l.tail())) }
  })

  static def length_le2 = { mk_length ->
    mk_length(mk_length(mk_length(eternity)))
  }({ length ->
    { l -> null_(l) ? 0 : add1(length(l.tail())) }
  })

mk-length の中の length を mk-length に置き換える

mk-length の中で mk-length を評価してしまうと無限ループしてしまうのでクロージャで囲って遅延評価する

  static def length = { mk_length ->
    mk_length(mk_length)
  }({ mk_length ->
    { l -> null_(l) ? 0 : add1({ x -> mk_length(mk_length)(x) }(l.tail())) }
  })

遅延評価するためのクロージャを外に出すと mk-length が再び現れる

  static def length = { mk_length ->
    mk_length(mk_length)
  }({ mk_length ->
    { length ->
      { l -> null_(l) ? 0 : add1(length(l.tail())) }
    }({ x -> mk_length(mk_length)(x) })
  })

mk-length を外に出す

  static def length = { le ->
    { mk_length ->
      mk_length(mk_length)
    }({ mk_length ->
      le({ x -> mk_length(mk_length)(x) })
    })
  }({ length ->
    { l -> null_(l) ? 0 : add1(length(l.tail())) }
  })

mk-length を除いた部分は Y コンビネータと呼ばれる

  static def Y = { le ->
    { f ->
      f(f)
    }({ f ->
      le({ x -> f(f)(x) })
    })
  }

  static def length = Y({ length ->
    { l -> null_(l) ? 0 : add1(length(l.tail())) }
  })

Y combinator - Rosetta Code のコードと同じになった。

Y combinator を使う

6年前に流行ったらしい。

元となった k.inaba 氏のエントリは発想にはついていけないが易しい言葉で書かれている*2ので追いかけて読むことはできた。
読んだのはもっと前でそのときのメモに「Y Combinator を理解したい」と書いてあった。その fix こそが Y Combinator だったことに今ごろ気づいた。

JavaScript では一回書いたので今度は Groovy に書き直してみる*3。

def fix
fix = { G ->
  return G({ x -> fix(G)(x) })
}

def fib_maker = { f ->
  // fib の再帰部分を f に置き換えたクロージャ
  return { x -> return x <= 1 ? 1 : f(x-1) + f(x-2) }
}

// fix は fib_maker を渡すと fib を返す
// fib を fib_maker の最小不動点というらしい
def fib = fix(fib_maker)
(1..10).each { println fib(it) }

// 関数をメモ化して返す
def memo = { cache -> { f ->
  return { x ->
    x in cache ? cache[x] : (cache[x] = f(x))
  }
}}

// 関数にデバッグプリントを埋め込んで返す
def debug = { f ->
  return { x ->
    println("call-" + x)
    def r = f(x)
    println("retn-" + r)
    return r
  }
}

// maker に memo を適用するフィルター
def memo_filter = { G ->
  // 戻り値のクロージャは再帰の度に呼び出されるので外側で memo を用意する
  def m = memo([:])
  return { f -> G(m(f)) }
}

// maker に debug を適用するフィルター
def debug_filter = { G ->
  return { f -> G(debug(f)) }
}

// 実行
fib = fix(debug_filter(memo_filter(fib_maker)))
(1..10).each { println fib(it) }


// filter を共通化する
def filter = { F -> { G ->
  return { f -> G(F(f)) }
}}

// 実行
fib = fix(filter(debug)(filter(memo([:]))(fib_maker)))
(1..10).each { println fib(it) }

fix と maker に分かれていると間にいろいろ処理を挟むことができる。

dankogai 氏のこのエントリによるとラムダ計算では fix の中で fix を使うのはだめらしい。でも fix で再帰すると分かり易いし不動点コンビネータ - Wikipedia の動作確認で Y で再帰する形にもっていっているのでプログラムでは使用しても問題はないと思う。

さらに Haskell の話がリンク先にはあるのでいつか読む。

$ と関係している?
状態を持たない Haskell でメモ化をどうするのか?

Wikipedia で「貧乏人のクロージャ (poor man's closures) 」と書かれていたので検索してみたらこんなのが Hit したのでこれもメモしておく。

"Object is a poor man's closure." Norman Adams
"Closure is a poor man's object." Christian Queinnec

「鶏が先か、卵が先か」みたいなことを言っているのだろうか?

2011-05-27 追記

static になっているのは『Scheme 手習い』の関数をすべて定義したクラスの中だから。

  static def null_ = { l -> assert l in List; l.empty }
  static def add1 = { int n -> assert n >= 0; n + 1 }
  static def eternity = { x -> eternity(x) }

遅延評価するものは Y combinator ではないらしい。
きしだなおき氏の 2009-04-09 が Groovy だしわかりやすいかも。

*1:読んでないけど

*2:内容が易しかったわけではない

*3:メモ化の部分はオリジナルとは変えてある