カテゴリー: programming

プログラミング言語を形式的に取り扱う

 型なしの算術式と型付きの算術式を例に、計算がどのように体系付けられていくのか、その流れの一例をみていきます。これによりプログラミング言語の基本的な側面を形式的に取り扱うことができます。

 ちなみにこの記事は型システム入門とプログラム意味論という本を参考にして書いてます。厳密でないところや間違ったところがたくさんあると思いますが、気になる箇所はこちらの本をあたると良いと思います。間違いなどはこっそりコメントを頂けたりすると嬉しいです。

言語構文の定義付けについて考える

 次のように、真理値true, false、条件式、数値定数0、後者関数 succ、前者関数 pred、ゼロ判定の演算子iszero の簡単な構文からなる小さな言語を考えてみましょう。

これと同じことを次のように帰納的な形で定義することもできます。

また以下のように推論規則による定義の仕方もあります。

[推論規則による項の定義] 項の集合は次の規則によって定義される
rule
 この推論規則は、上段を前提として下段を導けるというものです。とくに上段がない、つまり前提を必要としない規則のことを特に公理と呼びます。また以下のように項の要素を生成する具体的手続きを書き下すことによる定義の仕方もあります。

[具体的な項の定義] 自然数 i について、集合T_i、 項の集合 T をそれぞれ以下のように定義する。
rule2

項の評価について考える

 以上のように色々な方法で言語の構文を定式化できました。さてプログラミング言語を考えるときには各項がどのように評価されるということも考えなければなりません。この評価がどのようにされるかという議論を意味論と呼びます。意味論の形式化にも様々なバリエーションがあります。

 さて、手始めにブール値の評価について考えてみましょう。すると次の3つの評価関係が成り立つと一般的な言語機能として良さそうだということはなんとなく分かるかと思います。

 このように項の状態に対して遷移規則を定めることにより、項の評価を定義していく方法を操作的意味論と言います(そのなかでもスモールステップ意味論というスタイルになります)。なお表記の都合上、推論規則は (上段) => (下段) という書き方をしています。

 この3つの規則が何を言っているのかと同じくらい、何を言っていないのかということも重要です。たとえばこれらの規則から「if全体が評価される前にthen節やelse節が評価されることはない」という評価戦略が読み取れます。

 この3つの評価関係から例えばif false then false else true という項は、(2) を適用して true という値に評価することができます。true はこれ以上適用できる規則がありません。このような項を正規形と呼びます。

評価できない項

 ブール値の評価について定めましたが数値についてはまだでした。まとめて評価規則を定義しましょう。まずは構文と値の再確認をしておきます。

つづいて評価規則についてみてみます。

 このように言語の操作的意味論を形式化すると、例えば succ true のようにこれ以上評価できない、つまり正規形であるが、値ではないというようなパターンが生まれてしまいます。こういうような項を行き詰まり状態と呼びます。

 プログラミング言語の機能としてこの行き詰まり状態をどう扱うかということはひとつ大きな課題となります。エラーを表す新しい項を導入したり、型を導入してこの手のエラーを予め防ぐなどいくつかのアプローチがあります。

型の導入による行き詰まり状態の回避の試み

 項を実際には評価せずとも succ true のような行き詰まり状態にならないことが分かると便利です。このような仕組みのひとつとして型を導入することを考えましょう。前述の言語では、値として数値とブール値を扱っていたためそれらに対応する型 Nat と Bool を導入します。

 以上のような型付け規則により、項 t が評価したときにある型の値になることを静的に、つまり評価することなく判断することができるようになります。項 t に対してある型 T が存在して、t: T となるとき t は型付け可能と言います。

安全性を支える型システム

 行き詰まり状態を回避する手段のひとつとして型を導入したことからも何となく分かるように、型システムの最も基本的な性質は「安全性」です。正しく型付けされた項は行き詰まり状態にならない「安全性」は少し難しい話になりますが、型の進行定理と保存定理というものによって保証されます。証明はしませんが、それぞれ以下のような内容になります。

 これら2つの定理によって、正しく型付けされた項は最終的に値として評価でき、行き詰まり状態に陥らないということがわかります。

Javaでオートマトンを作ろう

「機械」は何をしているのだろうか

 たとえば照明のスイッチについて、消えている状態に対してOFFボタンを押しても何も起こりません。ONボタンを押すと点灯状態になります。逆に照明がついている状態に対して、OFFボタンを押すと消え、ONボタンを押しても何も起こりません。図にまとめるとこんな感じです。

automaton

 このように「ある状態に対して入力を与えたとき、どんなふうに振る舞うかということ」は、様々な機械のしていることの本質のひとつであると言うことができると思います。このモデルのことを状態機械(State Machine)、あるいはオートマトン(automaton)と呼びます。

 現在私たちが用いているパソコンやモバイル端末などは、尋常でない数のシステムがくみ合わさって実現されています。しかしながら上記の図くらい機械というものを抽象化すれば、人間の脳みそでも全容を理解しながら追っていくことができます。

機械とオートマトン

 様々な機械は、ほとんどの場合ある目的のために作られていると思います。その目的に達した状態を終了状態(end state)、あるいは受容状態(accept state)と呼ぶことにしましょう。逆に機械を動かす前の状態を開始状態(start state)と呼ぶことにしましょう。機械は、開始状態か受容状態を区別できる1ビットの出力を生成できるものとします。

 たとえば先ほどの照明の例では、最初の状態は消灯している状態でしょう。機械になんらかの入力を与えて、照明が点灯している状態が終了状態になると思います。これを図で表現すると以下のようになります。開始状態には矢印をつけ、終了状態には二重の円を用います。

automaton-1

 さて、このオートマトンは有限個の状態と遷移の組み合わせからなっていることは分かると思います。この場合、有限オートマトン(Finite Automaton)と呼ぶことができます。さらに次にどの状態になるか確実に決まっていることもわかります。これを決定性有限オートマトン(DFA: Deterministic Finite Automaton)と言います。

Javaで決定性有限オートマトン

 まずはこの決定性有限オートマトンをJavaで書いてみましょう。今回作るオートマトンが取りうる状態は {ON, OFF} の2つ、受け付ける入力は {0, 1} の2つにします。0 が入力されたら必ず OFF に 1 が入力されたら必ず ON の状態に遷移することにします。まとめると次の図のようになります。

automaton-2

 このオートマトンは 1 が入力されると受容状態に達する、つまり受理されて、 0 が入力されると受理されないという代物です。

 さてコーディングにとりかかります。今回は凝ったことはやらずに、状態を列挙体State、状態から状態への遷移規則をRuleクラス、遷移規則をまとめたものをRuleBookクラス、オートマトンをDFAクラスとして以下のように書き下してみました。

 ここまでできたら利用側のコードを書いて動かしてみます。まずは状態の遷移規則を表すRuleをまとめたRuleBookのインスタンスを用意。次に受容状態を表すセットを準備します。最後にDFAクラスに開始状態と受容状態のセットと遷移規則集を渡してインスタンス生成をしたら、inputメソッドでいろんな入力を与えて挙動を確認できます。

 残念ながらこのコードは汎用的ではありませんが、何となく有限オートマトンの雰囲気はつかめたのではないでしょうか。

非決定性有限オートマトンの導入

 実際の機械は遷移が必ずしも成功するとは限りません。あるいは何も入力していなくても遷移してしまうことがあるかもしれません。こうしたことをモデルに組み込むためには、「次にどの状態に遷移するか確実に決まっている性質」である決定性を捨てる必要があります。これを非決定性有限オートマトン(NFA: Nondeterministic Finite Automaton)と言います。

 たとえば先ほどの照明の例に対して、消灯状態から 1 を与えたとき、点灯するかもしれないし、しないかもしれないということが表現できるようになります。図にすると以下のような具合です。

automaton-3

 このとき、受理状態になるなんらかのパスがあれば、その入力は受理されると考えることにしましょう。つまり、1 や 11 や 011 などは全て受理されます。 0 や 000 や 000000 は受理されません。

 これができると何が嬉しいのか、少し考えてみることにします。今回は「最後から2番目の入力が 1 である数字の列を受理する機械」を考えてみましょう。これを決定性有限オートマトンの枠組みで考えるのは難しいと思います(実際に考えてみてください)。これがもし「最初から2番目の入力が 1 である数字の列を受理する機械」であれば以下のように決定性有限オートマトンとして簡単に表現が思いつくでしょう。

automaton3-1

 では、先ほど導入した非決定性有限オートマトンの枠組みで「最後から2番目の入力が 1 である数字の列を受理する機械」を表現するとどうなるのでしょうか。以下の図のようになります。

automaton4-2

 例えば 10, 00010, 01010101010 などは受理される(=受容状態へのパスが存在する)ことがわかります。 01 や 1001 などは受理されないことも分かります。

Javaで非決定性オートマトン

 さて、実際にJavaで実装してみましょう。先ほどよりやや汎用的に使えるように、状態をState、遷移規則をRule、遷移規則集をRuleBookとして以下のようなコードを用意します。

 そして非決定性有限オートマトンをNFAクラスとして次のように定義します。isAcceptableメソッドは入力から得られる可能性のある全ての状態のSetを作って、その中に受容状態があるかどうかを返します。こうすることにより、受容状態へのパスがあるかどうかを調べています。

 最後に利用側のクラスの例として、テストコードを掲載しておきます。

 実装的に雑な部分は目立つと思いますが、おおむね非決定性有限オートマトンと入力を受容するかどうかを判定するアルゴリズムについては理解頂けたかと思います。

自由移動

 長さが2の倍数の文字列を受理する機械は次のように簡単に表現できます。

automaton4-4

 では、長さが2か3の倍数の文字列を受理する機械は果たしてどうしたら良いでしょうか。ここで自由移動(free move)という規則を導入すると簡単に表現ができます。これは何の入力もなしに従うことができる規則です。これを用いると以下のように表現できます。

automaton4-3

 図中の1 -> 2,1 -> 3 は何の入力もなしに遷移が可能です。こうすることにより 00, 000, 0000, 000000 などは受理され、0, 00000などは受理されないことが分かると思います。

 一見、オートマトンは単純で何の役にも立たなそうにみえますが、身近でかつ重要なところでは正規表現などに使われています。また、生物や人工知能の分野では神経系をオートマトンを応用した形でモデル化して様々な研究が行われていたりします。

JJUG ナイトセミナー 機械学習・自然言語処理のおはなしを聞きにいった

雑なまとめですが一応公開します.速記なので内容の正確性は保証できません.スライドを見ると良いと思います.

Javaでカジュアルに機械学習

機械学習を始める前に知っておきたいこと

機械学習とは,経験(データ)によって賢くなるアルゴリズムの研究.分類・識別,パターンマイニング・アソシエーションルール,予測・回帰,クラスタリングなどができる.これらは正解があってモデルを作っていく教師あり学習と,正解がない教師なし学習に分類できるそうです.

入力データとしては原則として数値列しか扱えないため,非構造データはそのままでは扱えない.そういった場合はそのデータを表現するなにがしかの「特徴量」を抽出することによって機械学習を実現している.得られた結果が正しいかどうかについて確かめる方法として,k分割交差検証や適合率,再現率,相関係数,決定係数などを用いるものがある.また線形分離という,データを一本の線を轢くことによってデータを分類する方法もある.

Javaで機械学習

機械学習アルゴリズムのテストはかなり辛く,時間・空間効率の良い実装はさらに難しい.したがって車輪の再発名はなるべく避け既存のライブラリをなるべく使うようにした方がよい.Javaで機械学習を用いたアドホック分析はだいぶ辛いので,そういったことであればPythonを使うと良いとのこと.

Javaで使える機械学習ライブラリのなかで発表者がおすすめなものがliblinear-java.線形分類・回帰可能な問題へ特化している. Wekaは多種多様な機械学習アルゴリズムが提供されているため最初に触るには向いているらしい.MLib(Spark)は分散処理フレームワークSpark上での利用を前提としていて,アドホック分析の環境としてもScalaを用いて利用できる.MahoutはHadoop上の機械学習ライブラリ.Sparkのほうが出てきてから若干オワコン感があるらしい.SAMOAはStomなどの分散ストリーミングフレームワーク上で利用できる機械学習ライブラリだが最近開発があまり活発ではない?Jubatusはリアルタイム性が要求されるときに用いると良い.h2oはディープラーニングをJavaでやりたいときに使うことになるそうです.

UCI Machine Learnigというところで色々なデータが提供されている.だいたいがCSVファイルで提供されている.そのなかでもIrisというのは機械学習の世界でのHello worldにあたるくらい常識的なデータセットらしいです.

Wekaの入力形式はCSVの先頭にちょっとおまけがついているものだが,CSVLoaderというクラスがあるので問題はない.k分割交差検証を実施するweka.classifiers.Evaluation,ロジスティック回帰による分類はweka.classifiers.functions.Logisticあたりを用いる.実際のコードはGitHubにあがっている.

SparkとMLlibのはなし

機械学習でモデルの制度を高めたいがデータが増えると計算量やIO量が増えるし,そのデータをどこに置いておくのかという点が問題で,かつ従来の機械学習ライブラリは,単一のマシンで計算を行うことが前提としてつくられていた.したがって計算処理の効率は単一のマシンの性能に制約されていた.Hadoopはオープンソースの大規模分散処理基盤で特別な聞きを用いずコモディティなサーバ機器を複数束ねてクラスタを形成して,並列分散処理を可能にするものだそうです.

HDFSは複数のスレーブを束ね,大きなファイルシステムに見せる仕組み,故障することが前提の設計.MapReduceは大規模分散処理向けのフレームワークでこちらも故障が前提.これらを連携させることにより真価を発揮する.HadoopとMahoutの登場で機械学習はある側面でスケーラブルになったそうな.MapReduceを前提としていると反復処理の回数を増やすほど,モデルが作られるまでのレイテンシが大きくなる.Hadoopはスループットを最大にすることを目的にしているため,ジョブが多段になったときにもオーバーヘッドが問題となっていく.

Apache Sparkとはスループットとレイテンシの両方が必要な問題領域にアプローチするために開発されたOSSのインメモリ分散処理基盤.HadoopはMapReduceという単一の処理パラダイムであるが,RDDという異なる処理モデルがとられている.

HadoopはMapとReduceでジョブを構成している.SparkはRDDで処理をしたデータをチェーンでつなげた全体を単一ジョブとして構成する. Sparkの目標の一つはコアとなる分散処理エンジンを中心に据え,それを活用するためのライブラリを充実させることで,そのひとつがMLlibになる.Scala/Java/Pythonでコードを書ける.

自然言語処理のはなし

このあたりで動画あがってるのに気付いたのでメモしてない

感想

ElasticSarchとKibanaとMLlibあたり面白そうなので、それらを使って何か作ってみようと思いました

ラムダ計算について調べた(前編)

関数プログラミングとその背景にある数学的なお話を理解する上でラムダ計算の知識が必要そうなので,確認していきます. というかなんかよくよく調べていくと,「計算機科学の理論としては常識」とか書いてあったりするので,あせって基礎をさらいました. まずは型なしのラムダ計算まで. 間違ったところがあったらご指摘頂けると嬉しいです.

ラムダ計算とは何か?

Wikipediaによるとラムダ計算とは次のようなものとされています.

ラムダ計算(lambda calculus)は、計算模型のひとつで、計算の実行を関数への引数の評価(evaluation)と適用(apply)としてモデル化・抽象化した計算体系である。ラムダ算法とも言う。

ラムダ計算では,関数をラムダ抽象を使って記述します. たとえば f(x)=2x+1 なる関数は f=λx.2x+1 というように書きます. こうすることにより,関数を返す関数などを定義することができるようになります. また名前をつけずに値のように関数を取り扱えるようになりました.

たとえば, g(x,y)=x+2y+1 は g=λx.(λy.x+2y+1) といったように 2変数関数は,1変数を返す関数として定義することができます.このような変換をカリー化(currying)とよびます. また関数を値として受け取ったり,返したりする関数のことを高階関数(higher-order function)とよびます.

関数に値を適用したい場合はラムダ抽象の後ろに値を書けば良いです. たとえば f(x)=2x+1 に x=2 を適用するときは ((λx.2x+1)2) と書きます. これを関数適用といいます.

またλx.x+y についてx は束縛されているといい y は自由であるといいます.

型なしラムダ計算(lambda calculus)

ラムダ式の構文

型なしラムダ計算の抽象構文は e::=x|λx.e|e1e2 のように定義されます. 単純にいうとラムダ式は,変数か,ラムダ抽象か,関数適用から構成されるということです.

ラムダ計算の実行

ラムダ計算の実行はα-変換,β-簡約,η-変換の3つの操作に抽象化できます.

  • α-変換(α-conversion)
    • λx.M→αλy.M[x:=y]
    • 束縛変数の名前はMの中に自由なyがなければ置き換えられる:λx.f⇒λy.f[x→y]
  • β-簡約(β-reduction)
    • (λx.M)N→βM[x:=N]
    • 関数適用そのものを指す:λx.fy⇒f[x→y]
  • η-変換(η-conversion)
    • λx.Mx→ηM
    • 関数の外延性を表す:λx.fx⇒λy.f

ラムダによるデータの表現

自然数

以下のように自然数をラムダ式で表せる.このようなラムダ式をチャーチ数(Church Number)とよびます.

  • 0 を λs.λz.z
  • 1 を λs.λz.sz
  • 2 を λs.λz.s(sz)

これは足し算を plus=λg1.λg2.λs.λz.g2sg1z を定義して, plus 1 2 などを計算してみると納得がいくと思います

論理値

論理値 true は λt,λf.t ,false は λt.λf.f とすると, if e1 then e2 else e3 を e1e2e3 としてうまい具合にif-elseの構造を表せる. これは if true then e1 else e2 = true e1 e2 = (λt.λf.t)e2e3 →(λt.e2)e3→e2 かつ if false then e1 else e2 = false e1 e2 = (λt.λf.f)e2e3 →(λf.g)e3→e3 となることから納得がいくと思います.

その他 この資料 が結構良い感じにまとまっています

他クラスに依存しないテストを支える仕組み:スタブ・モック・スパイ

手元にはあったが長らく積んでいたJUnit実践入門の11章:テストダブルの章を読んでまとめを書きました.実際のところMockitoってなんだかいままでよく分からない存在だったけど,手をつけてみるとかなりお手軽&便利なものでした.学習コストもそれほど高くないので,何となく敬遠していたり,テストってどう書けば良いのかよくわかっていない私のような人がいたら是非,Mockitoを使ったテストコードを実際に書いてみることをお勧めします.

テスト対象クラスが依存するクラス・モジュール問題

理想的なユニットテストは,依存するすべてのクラスや外部システムを使用したもの  
* なぜなら,実際に動くコードはそういう状況で動くのだから
* しかし依存する本物のオブジェクトを常に使用できるとは限らないし,ユニットテストで扱いにくいオブジェクトもある
* このようなときにテストしやすいようにリファクタリングしたり,本物のオブジェクトの代役となるオブジェクトに置き換えてテストを行うという手法が用いられる

テスタビリティを高めるリファクタリング

  • JavaのDateの精度はミリ秒であるため次のコードは,テストに成功したり失敗したりする
  • 乱数を使ったコードは当然ながらテストが書きにくい
  • このようにインスタンス生成のタイミングや環境に依存してしまう部分が含まれるコードのテストは難しい

インスタンス生成の部分を抽出してファクトリメソッドを作ると,ここをOverrideして振る舞いを変えることができ,依存度を下げることができる

今回の例に対してはやや過剰な実装とはなるが,振る舞いの複雑なメソッドをオブジェクトに切り出し,委譲を使って差し替え可能にするという方法もある

テストダブル:スタブ/モック/スパイ

  • テスト対象となるクラスが他クラスに依存していないケースはほとんどない
  • 依存しているクラスもまた他のクラスに依存している
  • この状態でテストを行うメリットは実行時に近い状態でテストができること
  • デメリットはテスト対象以外の問題を原因としてテストが失敗する可能性があること
  • このとき依存しているオブジェクトの代役(スタブ・モック)を使うことをテストダブルという

スタブ

  • スタブとは依存するクラスやモジュールとして代用できる仮のクラス・モジュール
  • 以下のようなときに用いられる
    • 依存オブジェクトが予想できない振る舞いを持つとき
    • 依存オブジェクトのクラスがまだ存在しないとき
    • 依存オブジェクトの実行コストが高く,簡単に利用できない
    • 依存オブジェクトが実行環境に強く依存している
  • 例えば乱数を用いるようなクラスのテストは,依存オブジェクトRandomが予想できない振る舞いを持つためスタブを使うと良い
  • コード的には次のようなものになる

モック

  • スタブと同様にテスト対象が依存するクラスやモジュールの代用として使用されるもの
  • スタブはメソッドの返り値を予想可能な値にすることにより、依存クラス・モジュールが正しく利用できているか確かめるもの
  • モックはメソッドが正しく呼び出されているかを検証するもの

スパイ

  • 基本的にテストはメソッドへの入力に対して出力を検証する
  • 従ってvoid型のメソッドの検証はやりにくい
  • そこでロガーに書き込まれた内容を検証に使うスパイという手法がある
  • 基本的にはロガーのロギング機構にStringBufferへのappendの処理を追加して,検証時にtoStringして文字列比較するという単純なもの

Mockitoでスタブ・モックを作る

  • mockitoが適当に使える状況にしておく
  • Mock.mock(モックを作りたい対象のクラス)でモックが作れる
  • `where(モックのインスタンス.メソッド()).thenReturn(期待する返り値)Pで振る舞いを持たせられる
  • その他,コードを見ればきっと分かる!
  • 基本的にmockitoの使い方自体は簡単だけれど,そもそもスタブ・モックとは何かを理解できていないところがmockitoを使う上での最大の壁になると感じた
  • 現に本を読んで自分はちゃんとスタブ・モックがなにかを理解できていなかったので反省した

Scalaのクエスチョンマーク3つは「Predef.???」

つい数日まえについにScalaでいろいろ書き始めました. コップ本のクラス定義の仕方とかそのあたりを適当に流し読みして, とりあえずいろいろ書いて分かんないところ読もうという方針のもと,コードを書いていくことにしました. わりと順調に進んで,型付きパターンマッチや, 変位指定アノテーションあたりなどちょくちょく分からないところをコップ本とググってでてきたページで解決してきました.

しかしながら,いろいろ調べものして出てきたScalaのコードにdef hoge = ???なる記述が…。とりあえずコップ本の索引を見てみるも載っておらず,?は記号なのでググっても引っかからない.「scala クエスチョンマーク」「scala 記号」で検索してもダメで,twitterでぼやいたところ,その正体がPredef.???だということを教えていただきました(ありがとうございました).

例えばdef hoge = ???としておくとコンパイルは通りますが,実行時にNotImplementedErrorをスローするという挙動をするもののようです.これはScala2.10から追加されたもののようで,追加に向けてForumでいろいろ議論がされていたようです.

すこしでも検索に引っかかりやすくなるようまとめてみました.
正確な話は公式のDocumentやソースコードを見て頂けると良いかと.

ちっと「???」はググって解決しにくいよなぁ…と,思いました(小並感).

以下最近調べたScalaまわりのことまとめ

型付きパターンマッチ

objがIdentifier[_]型のときマッチされ,値を以下の例だとthatという名前で扱える.別にthatじゃなくても良い.

全てのオブジェクトに実装されている##メソッドの実態

## は基底クラス(Any)に定義されているハッシュ値の取得メソッド

override def hashCode: Int = 31 * id.##

変位指定アノテーション:非変・反変・共変

[T]: 非変(nonvariant) => 指定した型変数のみを受け入れる
[-T]: 反変(contravariant) => 指定した型変数のスーパークラスを受け入れる
[+T]: 共変(covariant) => 指定した型変数のサブクラスを受け入れる

この場合,Indentifierトレイトの型変数には,Tとそのサブクラスを受け入れることができる.

Bridge Pattern

参考リンク

機能と実装の違い

ある数列[1,3,2,5,4]をソートしたいとします.このときソートの方法は何通りかあります.このとき「ソートをする」ということが機能にあたります.そして「ソートをする方法」,たとえばクイックソートやマージソートなどが実装にあたります.クラスを拡張しようとするときには,具体的には「機能の拡張」と「実装の拡張」のいずれかであることが多いです.

Bridge Patternが必要になる状況例

TECSCOREにわかりやすい例が載っていたので,それに添ってBridgeパターンが必要になるシチュエーションを見てみます.ソート機能を持つ抽象クラスSoterに対して,実装クラスQuickSorterBubbleSorterを以下のように作成したとします.機能はSoter,実装はQuickSorter, BubbleSorterに分離されていることに注意します.

現状のコードに新しい「実装」を増やすことは容易いです.単にSoterをextendsした実装クラスを書けば良いだけだからです.しかしながら新しい「機能」を増やすためにはどうしたら良いでしょうか.ためしにソートに加え,それにかかった時間を表示する機能を追加したい場合を考えてみます.するとコードは以下のようになります.

ソートの実装自体は先ほど実装してあるQucickSort, BubbleSortクラスを使いたいとします.しかしながらよくよく考えてみるとTimeSorterにそれらの実装を与えることができません(Java1.7以下での話?).そこで残念ながらそれらのTimeSorterに対応した実装クラスQuickTimeSorterBubbleTimeSorterを書かなければなりません.図で表すと以下のような具合になります.

l-1

このような状況に上手く対処するためにBridge Patternが用いられます.

Bridge Pattern

Bridge Patternでは実装の部分を別の階層に切り離すことによって,これまでに見てきた例のような問題を解決します.まずはコード例を見てみます.

このように機能を実現するための方法がSortImpl委譲されているため,実装の追加はもちろん,機能の追加は容易になります.まとめとしてBridge Patternのクラス図を示しておきます.

l-2

時間経過に伴って機能が拡張されていくバージョンアップの過程と,実装タイプのバリエーションを豊富に広げる品揃えの充実具合を,別個に分けて,整理して管理できる(GoFの23のデザインパターンを,Javaで活用するための一覧表より)

Java8での機能と実装の追加について考えてみた.

この部分については個人的に思いついた内容なので,実際に良い方法なのか微妙なところですが,とりあえず書いておきます.Java8ではインターフェースがデフォルト実装を持てるようになったため,先の例ででてきたSorterを抽象クラスではなくインターフェースとして定義しておけば,「実装の拡張」はもちろん,「機能の拡張」もすっきりおこなえるかなと思いました.ソートにかかる時間を表示するtimeSort機能を追加したあとのクラス的にはこんな具合になると思います.

l-3

現時点でこの方法が抱えている問題は,Sorterが抽象クラスではなくインターフェースになったので状態(プロパティ)を持てなくなってしまったという点だと考えていますが,どうでしょうか.

Strategy Pattern

状況・文脈(context)によって動的に振る舞いを変えたいときの定石がStrategy Patternです.
たとえば各OS向けに文字列を出力するTextPrinterクラスがあるとします.
ところが各OS標準で用いられる改行コードはことなるのでその部分についての振る舞いをOSによって変えなければなりません.
以下はこういう状況のときにありがちなコード例です.

往々にしてif文の嵐になります.そこで改行コード出力のふるまいだけを抜き出して,オブジェクトとして扱ってしまおうというのがStrategy Patternになります(言い過ぎ?).どの環境下でのふるまいも共通して「改行コードを出力する」という責務を持っているのでインターフェースを決めておくと便利です.今インターフェースCompositorを定義し,その後に各々の環境に応じた実装をしていくと良いです.

このようにスッキリしました.今やったことを抽象化したStrategy Patternのクラス図は以下のようになります.

l-4

【参考:GoF本での定義】アルゴリズムの集合を定義し、各アルゴリズムをカプセル化して、それらを交換可能にする。
Strategyパターンを利用することで、アルゴリズムを、それを利用するクライアントからは
独立に変更することができるようになる。

アルゴリズム実装のための専用オブジェクトを複数作っておき,その中から使うものだけを動的に選んで実行する。
ある程度複雑なアルゴリズムになると,ふつうのプログラマであれば,その部分を切り出して集約するだろう。また,他のアルゴリズムに置き変わった時に備えて,互換性も持たせておくだろう。なので,あまり新規性を感じないパターンに思えるかもしれない。とはいえ,アルゴリズムの交換可能性を増すために,共通の基底(または共通のインタフェース)を持たせているという点は注目。(GoFの23のデザインパターンを,Javaで活用するための一覧表より

Bridge PatternとStrategy Patternの違い

よくわからなかったので,GoF本の適用可能性の欄を参照しました.

  • Bridge Pattern(構造に関するパターン)
    • 抽出されたクラスとその実装を永続的に結合することを避けたい場合.
    • 抽出されたクラスとその実装の両方を,サブクラスの追加により拡張可能にすべき場合
    • 抽出されたクラスの実装における変更が,クライアントに影響を与えるべきではない場合
    • 複数オブジェクトの間で実装を共有したい場合
  • Strategy Pattern(振る舞いに関するパターン)
    • 関連する多くのクラスが振る舞いのみ異なっている場合
    • 複数の異なるアルゴリズムを必要とする場合.
    • アルゴリズムが,クライアントが知るべきではないデータを利用している場合.
    • クラスが多くの振る舞いを定義しており,これらがオペレーション内で複数の条件文として現れている場合.

ここから察するに,Bridge Patternは継承より委譲を使うことにより,インターフェースとその実装の結合を弱め,「機能」と「実装」を柔軟に拡張できる構造を作りたいときに使うパターン.そしてStrategy Patternは状況に応じ振る舞いが変わるような状況下でその振る舞いの部分を切り出し,クラスの肥大化・複雑化を避けたり,あるいはクラスと振る舞いの結合を弱めるために使われるのではないかと思いました.間違いがあったらご指摘いただけるとありがたいです.

参考リンク

Singletonパターンの罠

インスタンスが一個しか存在しないクラスを書くためのパターンがSingleton Patternです.登場するのはSingletonクラスひとつのみで以下のようなクラス図になります.

L

結城本には以下のような感じでサンプルコードが掲載されていました.

Double-checked locking 問題

参考ページ

概要

Fooクラスのインスタンスがただ一つだけするようにSingletonパターンを用いて以下のようなコードを書いたとします.

もし2つのスレッドが同時にgetHelper()を呼んだ場合,同時にインスタンスを生成しようとして,片方が完全に初期化されないままのインスタンスの参照を持ってしまうようなことが起こり得ます.これを防ぐためには,コストは大きいですが同期を取ってあげればよく,以下のようなコードに変更すれば良いです(from wikipedia).

よくよく考えてみるとsynchronizeが必要なのはgetHelper()内の最初のif文のみです.そこでDouble-checked lockingというイディオムが考えられました(from wikipedia).

Initialization-on-demand holder idiom

Double-checked lockingによりsynchronizedにより初回に正しくインタスタンス生成されたあとは同期を取らずにすみます.理論的には申し分ないのですが,これはJavaプラットフォームのメモリー・モデルが原因で,期待通りの動作が必ずしも保証されません.Javaではシングルトン実装のアンチパターンとされています.そこでInitialization-on-demand holder idiomというものが推奨されています(from wikipedi).

Template Method Pattern

だいたいの処理の流れが共通しているとき,それをテンプレートとしてスーパークラスに記述して,個々の具体的処理のみをサブクラスに記述するというパターンがTemplate Method Patternです.

このパターンに登場するクラスは主に2つあります.ひとつは,ひな形となるAbstractClassで,ここにはテンプレート内で行う個々の処理を抽象メソッドです.もうひとつは,それらを使った一連の処理の流れを実装したメソッドです.個々の処理はサブクラスで実装するためにprotectedかpublic修飾子を,それらを使った一連の流れを定義したメソッドは全サブクラスで共通化(テンプレート化)させたいのでfinal修飾子を付けます.クラス図は以下のような具合になります.

l

実際にファイルになにかを保存するための一連の流れを想定した例を以下のように書いてみました.

まとめ

  • Template Method Patternはabstract classの有用な使い方のひとつで,「似たような複数の処理の流れ」から共通の性質を見つけ出し,テンプレート化することにより,「似たような複数の処理の流れ」の数が増えたときでも,読みやすいコードが書けるのではないかと思った.
  • ただその「似たような複数の処理の流れ」の共通の性質をしっかりと見抜いて,良いテンプレートを作らないとかえって変更が難しいコードになってしまう危険性も持っているのではないかと思いました.
  • 事例で学ぶデザインパターン 第3回 Template Methodパターン