Y combinator

勉強

最近は残業と休日出勤ばかりでうんざりの KrdLab です．
今回はちょっと毛色の違う話題を．内容はいつの間にか自分用のまとめになってしまいましたが．．．

Y combinator とは？

不動点コンビネータの一種．
不動点とは，ある関数 F を定義したとき，F(p) = p となる p のことを指す．ここで p を関数にまで拡張して考えてみる．すなわち関数 F は高階関数となる．この関数 F の不動点 p を返すような関数 g を考えると，p = g(F) の様に表すことができる．このとき関数 g を不動点コンビネータと呼ぶ．

特にラムダ計算では，

g := λf. (λx. f(x x)) (λx. f(x x))

と表される Y combinator がよく知られている．

なお，combinator については Combinatory logic - Wikipedia, the free encyclopedia にて以下のように説明されている．

A combinator is a higher-order function that uses only function application and earlier defined combinators to define a result from its arguments. [引用]

combinator は，自身の定義に自由識別子 (自由変数と呼ばれる場合もある) が含まれていないため，実行時の環境に因らず，引数 (束縛された識別子) のみから自身の出力が決まる．

性質

不動点の関係を表しているのだから，g(F) = YF = p，かつ F(p) = p より，F(YF) = YF となるはず．実際に適用を進めると，確かにその性質が認められる．

YF = (λf. (λx. f(x x)) (λx. f(x x)))F
   =   (λx. F(x x)) (λx. F(x x))
   = F((λx. F(x x)) (λx. F(x x)))
   = F(YF)

さらに適用を続けると，以下のように再帰構造が現れる．

   = F(F(YF))
   = F(F(F...

つまり不動点 YF は，「関数を引数にとって関数を返す」関数 F による再帰を表しているとも解釈できる．

何ができるのか？

ラムダ式で再帰を表現することができる (つまり繰り返しを表現できる)．このような再帰を無名再帰と呼ぶ．
ここでは階乗計算を例に説明する．プログラムでフツーに書けば以下のようになる．

fact 0       = 1
fact (n + 1) = (n + 1) * fact n

これをラムダ式のみで表すために Y を用いる．前述の性質から，「F の繰り返し適用 (再帰) の結果得られる関数」を表す YF に n を渡したものが，fact n と等しくなるような F を定義すればよい．

イメージとしては fact(n) := YFn = F(YF)n より，F は関数と数値を引数にとればよいことがわかる．

コードで書くと以下のような感じになる (大文字始まりなのは気にしないでください)．

F = \f n -> case n of
              0       -> 1
              (m + 1) -> n * f m

上記 F に Y を適用することで引数 f は YF となり，再帰構造が生まれる．

よって，目的の fact は以下のようになる (大文字始まりなのは気にしないでください)．

fact = Y F
--       ↓
       Y (\f n -> case n of
                    0       -> 1
                    (m + 1) -> n * f m)


実際に引数を与えると以下のように関数適用が進み，階乗計算が実現される (ラムダ式は長いので便宜上 F と表記しています)．

(Y F) 3 -> F (Y F) 3
        -> 3 * (Y F) 2
        -> 3 * (F (Y F) 2)
        -> 3 * (2 * (Y F) 1)
        -> 3 * (2 * (F (Y F) 1))
        -> 3 * (2 * (1 * (Y F) 0))
        -> 3 * (2 * (1 * (F (Y F) 0)))
        -> 3 * (2 * (1 * (1)))
        -> 6

以上により，Y combinator を用いることで無名再帰を実現できたことがわかる．

補足

haskell で Y combinator を定義する方法は，ググるといくつか紹介されています．ちなみに fix = \f -> f (fix f) は反則 (？) なので悪しからず．
また，正格評価を基礎とする言語で Y combinator を記述した場合，展開が無限に進んでエラーとなってしまいます．こちらについてはここやここで対応版が紹介されています．

OutOfMemoryError を分析する

Java

最近仕事で Java ばかりの KrdLab です．そんな中，Eclipse の Memory Analyzer (MAT) が素晴らしかったので紹介．
http://www.eclipse.org/mat/

はじめに

Java ではメモリリークによって OutOfMemoryError (OOME) が発生する．このリークを特定する作業はなかなか困難な作業になることが多い (特に，誰が作ったのかわからない古いコードの保守で発生すると大変！)．
今回はその作業コストを軽減するツールとして Memory Analyzer (MAT) を紹介する．

Eclipse Memory Analyzer とは？

JVM のヒープダンプを解析するツール．どのオブジェクトがリーク候補なのか，どこから参照されていたものだったのか，といった情報がグラフィカルに表示される．
他にもダンプ分析のための様々な機能があり，非常に強力なツールである．

ヒープダンプを取得するには？

OutOfMemoryError 発生時に取得する場合
以下のように HeapDump* オプションを JVM に指定する．

>java -Xmx128m -XX:+HeapDumpOnOutOfMemoryError -XX:HeapDumpPath=./dump.hprof -cp ...

上記であれば，128 MB を超えたところでヒープダンプ dump.hprof が出力される．
参考：http://blogs.sun.com/watt/resource/jvm-options-list.html


任意のタイミングで取得する場合
jmap で取得する．(他にもいくつか方法があるけど割愛)

>jmap -dump:format=b,file=test.hprof 5624

これで PID=5624 のヒープダンプが test.hprof として出力される．
参考：jmap - Memory Map


ただしサーバ系 OS の場合，実行権限の関係上 jmap が正常に実行できない場合がある．そのような場合は PsTools の PsExec を使用すると良い．"-s" オプションをつけることで，jmap を System アカウントで実行できる．

>PsExec.exe -s jmap -dump:format=b,file=test.hprof 5624

参考：PsExec | Microsoft Docs

Memory Analyzer を使ってみる

以下のようなシンプルなコードを用意した．あからさまなリークについてはあしからず．

package com.example.test.mat;
import java.util.ArrayList;
import java.util.List;

public class Main {
    public static void main(String[] args) throws Exception {
        final Thread th = new Thread(new Leaker(), "leak-thread");
        th.start();
        th.join();
    }
}

class Leaker implements Runnable {
    private final List<Integer[]> list = new ArrayList<Integer[]>();

    public void run() {
        for (int i = 0; i < 1024; ++i) {
            list.add(new Integer[1024 * 1024]);
            try {
                Thread.sleep(1000);
            } catch (InterruptedException _ignore_) {
            }
        }
    }
}
// コンパイル：javac -d ./bin -cp ./src -encoding utf-8 src/com/example/test/mat/Main.java

前述した方法でヒープダンプを取得し，MAT で「Leak Suspects」を開く．

(※この円グラフで「ここヤバそう」というのがわかる)
「Details」リンクから詳細画面に移動すれば，個々のオブジェクトについて詳細な情報を得ることができる．

画面から，Leaker の ArrayList でリークしていることがわかる．実行スレッドの名前は "leak-thread" である．
各要素のリンクを選択することでさらに分析を進めていくことができる．

最後に

Eclipse Memory Analyzer はヒープダンプを分析するツールです．機能・操作性ともに素晴らしい．
実際に以下のようなことに使ってみて，とても便利でした．

  • OutOfMemoryError 発生箇所の特定と確認
  • メモリ使用量の推測値を検証

まぁ，機能は紹介しきれないため，実際にさわってみることをおすすめします．(＾_＾)

DataMapper 0.10.2 Reading (その 4: dm-core/core_ext/)

ruby

このディレクトリに配置されたコードは，ruby の標準クラス (モジュール) を拡張するためのもの．具体的には以下の 3 つが拡張されている．

  • Enumerable
  • Kernel
  • Symbol

それぞれは小さなコードだが，影響範囲は広い．

Enumerable

empty?/one?/first/size メソッドを定義している．標準メソッドについては こちら を参照されたし．
Enumerable の規約に従い，全て each により定義されている．これらの内，ここでは one? メソッドを取り上げようと思う．one? メソッドは文字通り「1 つだけ？」かどうかを判定するわけだが，この判定基準にブロックを用いる．

module Enumerable
  def one?
    return one? { |entry| entry } unless block_given?

    matches = 0
    each do |entry|
      matches += 1 if yield(entry)
      return false if matches > 1
    end
    matches == 1
  end

与えられたブロックで各要素を評価し，true を返した要素の個数をカウントしていく．カウントが 1 であれば true を返すし，そうでなければ false を返す．

Kernel

Kernel では，DataMapper モジュールの repository メソッドを呼び出すためのメソッドが定義されている．

module Kernel
  private
  def repository(*args, &block)
    DataMapper.repository(*args, &block)
  end
end

ここで定義されているということは，self.repository の形であれば (self 以外に対して .repository としなければ) どこでも呼び出せる．
簡単な例を示すと，以下のような感じ．

module Kernel
  private
  def hoge
    puts "hogeっていうな"
  end
end

hoge
# => hogeっていうな

class A; end
a = A.new
a.hoge
# => NoMethodError

class A
  def call_hoge
    hoge
  end
end
a.call_hoge
# => hogeっていうな

Symbol

コードは短いが，検索に広く影響する条件用の Symbol を定義している．

class Symbol
  (DataMapper::Query::Conditions::Comparison.slugs | [ :not, :asc, :desc ]).each do |sym|
    class_eval <<-RUBY, __FILE__, __LINE__ + 1
      def #{sym}
        #{"warn \"explicit use of '#{sym}' operator is deprecated (#{caller[0]})\"" if sym == :eql || sym == :in}
        DataMapper::Query::Operator.new(self, #{sym.inspect})
      end
    RUBY
  end
end

例えば，

class MyModel
  include DataMapper::Resource
  property :id, Serial
  property :name, String
end

というモデルを定義したとき，

m = MyModel.all(:name.like => 'Krd%')

という呼び出しの ".like" にあたる部分を定義していることになる．
この定義により，".like" と呼び出すことで，条件演算を表す Operator インスタンスが得られる．

なお，"Comparison.slugs" については後ほど．ここでは「条件記述用に定義された Symbol を配列で返す」ぐらいの認識でよいかと．

Pocket WiFi

生活

Pocket WiFi なるものを購入してみた．

思ってたよりも小さい．スゲーつるつるしてる．

プランは「新にねん」で「スーパーライトデータ」にした．これだと本体価格は 15,580 円になる．「にねん M」だと 5,980 円になるが，差額の 9,600 円は 24ヶ月で分割され，月々の基本料金に上乗せされる．まぁ，つまるところ，2 年間使い続ければ差は無くなる．2 年より多く使うのであれば，多少は「新にねん」の方がお得になる．


これからいろいろ持ち運んでみる予定．

追記：2010/02/02
http://speedtest.goo.ne.jp/ で計測してみたら 0.51 Mbps だった．．．あれ？

DataMapper 0.10.2 Reading (その 3: dm-core/)

ruby

今回からは dm-core/ 以下のコードを見ていきます．

配置確認

うーん，かなり変更されている．．．

dm-core/
  adapters/
    abstract_adapter.rb
    data_objects_adapter.rb
    in_memory_adapter.rb
    mysql_adapter.rb
    oracle_adapter.rb
    postgres_adapter.rb
    sqlite3_adapter.rb
    sqlserver_adapter.rb
    yaml_adapter.rb
  associations/
    many_to_many.rb
    many_to_one.rb
    one_to_many.rb
    one_to_one.rb
    relationship.rb
  core_ext/
    enumerable.rb
    kernel.rb
    symbol.rb
  model/
    descendant_set.rb
    hook.rb
    is.rb
    property.rb
    relationship.rb
    scope.rb
  query/
    conditions/
      comparison.rb
      operation.rb
    direction.rb
    operator.rb
    path.rb
    sort.rb
  spec/
    adapter_shared_spec.rb
    data_objects_adapter_shared_spec.rb
  support/
    chainable.rb
    deprecate.rb
    equalizer.rb
    logger.rb
    naming_conventions.rb
  types/
    boolean.rb
    discriminator.rb
    object.rb
    paranoid_boolean.rb
    paranoid_datetime.rb
    serial.rb
    text.rb
  adapters.rb
  collection.rb
  identity_map.rb
  migrations.rb
  model.rb
  property.rb
  property_set.rb
  query.rb
  repository.rb
  resource.rb
  transaction.rb
  type.rb
  version.rb