2012年3月5日月曜日

「ツイッターStorm:オープンソースのリアルタイムHadoop」のマインドマップとクラス図

2月18日(土)に横浜モデリング勉強会を行いました。また、会場には(株)アットウェア様の会議室をお借りしました。参加された皆さん、アットウェア様、どうもありがとうございました。

この勉強会で、浅海が作成したモデルを紹介します。モデルはMindmapModelingの手法で作成しました。(勉強会で使用したチュートリアル)

モデリングの対象は、InfoQ誌に掲載されたBienvenido David III氏の記事「ツイッターStorm:オープンソースのリアルタイムHadoop」です。今回は、今話題の分散フレームワークTwitter Stormをテーマにしてみました。

単語を抜き出す

まず、最初の作業で記事中から単語を抜き出します。単語を抜き出しながら、登場人物、道具、出来事を中心にMindmapModelingの定めた分類に従って仕分けしていきます。

この結果、できた最初のマインドマップが以下のものです。(図をクリックすると拡大します。)


関係の洗練

次の段階では、抽出した、登場人物、道具、出来事の洗練を行います。用語の名寄せ、用語の種類(generalization)や部品構成(aggregation)を整理していきます。また、この段階で区分(powertype)の抽出を開始します。

以上の作業を行った結果のマインドマップは以下のものです。分散計算システムの共通性質の抽出をターゲットにすることにしました。


さらに、共通性質の精度を高め、区分と部品として整理をすすめました。この結果のマインドマップ配下のものです。


以下の図は最後にできあがったマインドマップ・モデルをクラス図に変換したものです。分散計算システムを区分、機能、データ処理、外部部品の観点から整理することができました。


出来事と物語

今回のテーマはstormに興味があったので取り上げました。

オブジェクト・モデリングの観点からは、出来事(イベント)や物語(協調、ユースケース)が面白い所なのですが、製品の機能説明の記事だとなかなかこのあたりのモデリングができませんね。次回以降は、記事の選択を工夫したいと思います。

圏論デザインパターン

要求開発アライアンスのセッション『Object-Functional Analysis and Design: 次世代モデリングパラダイムへの道標』で使用するスライドについて背景説明を行ってきました。

今回は背景説明第4弾で、「圏論デザインパターン」として用意した以下の図を説明します。


圏論デザインパターン

関数型言語の技術マップで説明したように、型クラスの導入によって代数的構造や圏論の理論をプログラミング言語で直接利用できるようになりました。

代数構造的デザインパターンは、基本中の基本概念であるので、モノイド以外のパターンもいずれ広く使われるようになることが予想されますが、今の所広く使われているのは圏論デザインパターンの方です。

代表的な圏論デザインパターンは以下のものです。

圏(category)
対象と射(対象間の構造を保つ対応関係)によって表現される代数的構造
射(arrow,morphism)
圏で対象間の対応関係を表現
関手(functor)
2つの圏間の構造保持するマッピング
Applicative functor
関手の一種。関手とモナドの中間に位置する性質を持つ。
モナド(monad)
関手の一種。計算を表現するプログラミング構造 。

以下では、Scalaプログラミングの観点で説明します。

圏と射

圏は対象と射(対象間の構造を保つ対応関係)によって表現される代数的構造です。

圏論の基本概念(圏と射)は檜山さんの『はじめての圏論 その第1歩:しりとりの圏』が分かりやすいと思います。

圏論的には、HaskellプログラムはHask圏という圏の中で動いていることになりますが、海の中で泳いでいる魚が海を見れないように、自分自身(つまりHaskellプログラム)は圏を意識することはありません。「Scala圏」という用語はまだ聞いたことがありませんが、Scalaでも事情は同じでScalaプログラムが一種の圏になっていると考えるとよいでしょう。

Scalaと圏論の関係については『 Scalaで圏論入門』が参考になります。

圏を意識する必要があるのは、別世界の圏を操作することになった時です。

関数型プログラミングの中では、今の所、圏の一種であるクライスリ圏(kleisli category)が多く使用されています。クライスリ圏はモナドの合成に使用することができます。

逆にいうと、モナドの合成を行わない場合には登場してこないので、使用頻度は低いです。

ただし、いずれ並行プログラミングでモナドの合成などを行うようになると、かなり重要なデザインパターンになるのではないかと考えています。

関手

関手(functor)は圏内の対象と射の関係を保存する2つの圏間でのマッピングです。

Scalaでは、Listなどmapメソッドを持っているオブジェクトが関手ということになります。(ただ単にmapメソッドを持っているだけではなくて、いくつかの規則を守る必要があります。)

このブログでは以下の記事が参考になるかもしれません。

Applicative functor

Applicative functorは、関手の一種で、関手の上に持ち上げた関数を適用する機能を提供します。(普通の関手は、関手の上に持ち上げていない関数を内部的に持ち上げて適用します。)引数が2つ以上の関数を、(関手的な)コンテナに適用することができるのが特徴です。(この機能が便利だと思えるには、一定の関数型プログラミングの経験が必要なので、この説明で意味が分からなくても大丈夫です。)

Applicative functorは、Scalaの型クラスライブラリScalazで使用できます。

ScalaにおけるApplicative functorは『Applicatives are generalized functors』が参考になります。

このブログでは以下の記事が参考になるかもしれません。

モナド

モナド(monad)は、計算を表現するプログラミング構造で、モナド内に格納されたオブジェクトに対する計算文脈を提供します。そういう意味で、モナドはコンテナという意味合いと、計算文脈という意味合いの両方を持つ関数オブジェクトとして考えることができます。

Scalaでは、ざっくり言うと、ListなどflatMapメソッドを持っているオブジェクトがモナドということになります。(ただ単にflatMapメソッドを持っているだけではなくて、いくつかの規則を守る必要があります。)

Scalaではモナドは非常に重要な構成要素になっており、for式はモナドを扱う文法糖衣になっています。(一見Javaなどのfor文と同じものに見えますが、中ではモナドが動いている、という構造になっています。)

このブログでは以下の記事が参考になるかもしれません。

ノート

圏論の定義(圏、射、関手の基本定義ぐらいまで)そのものは、それほど難しいものではありませんが、圏論の教科書は初学者向けを謳っているものでも非常に難解です。

これは、将棋や囲碁で、ルールそのものは簡単であるにもかかわらず、実際に試合に勝つためには、序盤の定跡から、手筋、定石、大局観、詰将棋(詰碁)といった膨大な知識と運用能力を持っていなければならないことに似ています。

そういう意味で、ボクも圏論の触りのところは少し分かってきたとは思うのですが、圏論の全体像や具体的な活用方法については全く霧の中です。将棋に例えると圏論10級ぐらいですね。初段(数学科学部卒?)ぐらいになると客観的に見て形になってくるのではないかと思います。初段はハードルが高そうですが、関数型プログラマとしては、5級とか3級といった級の上位になってくると、十分に面白さが分かってきて、実用的に使えるようになってくるのではないかと推測しています。

ただ、圏論由来の関数型プログラミングのデザインパターンとしての関手、Applicative Functor、モナドについては、それなりにうまく使えるようになってきました。

ボクがテーマとして追いかけているモデル駆動のメタモデルやモデルコンパイラのような技術は圏論の知識が役に立ちそうなので、圏論の勉強は続けていきたいと思っていますが、一般的なアプリケーションプログラミングという意味では、関手、Applicative Functor、モナドの使い方をデザインパターンやイディオムという形で知っていれば十分で、圏論そのものの知識はあまり関係ないという印象です。

モナド

ボクが圏論を調べる時に使っている教科書の一つ『圏論による論理学 高階論理とトポス』では、モナドは出てきません。(少なくても索引には載っていません)

その他いろいろな状況証拠から、モナドは圏論の中では特殊な応用の一つ、ではないかという印象を持っています。

もちろん、圏論を修めた後、その一理論であるモナドを理解し、その全体像の中でのモナドを意識しつつ、プログラミングに応用するのは、理想的ではあるのですが、関数型プログラミングを習得するという目的にはかなり遠回りではないかと思われます。

Applicative Functor

この所、関数型プログラミングでは関手とモナドの中間の性質を持つApplicative Functorが注目されていますが、これは関数型プログラミングという「圏」で有効なメカニズムで、恐らく圏論そのものには(重要な理論の一つとしては)登場してこないのではないかと推測します。

このように関数型プログラミングの圏でのみ有用な技法というものはこれからもたくさん登場することが予想されます。こういった技法の習得は圏論を勉強しても直接は役に立たなさそうです。

Applicative Functorのようなアイデアを考案し理論として記述したり、そのようにして書かれた原著論文を解読するには圏論の知識が必要ですが、原著論文の内容をアプリケーションプログラムに必要なデザインパターンとして仕立て直した後は、関数型プログラミングの知識で技術を習得することは可能です。

以上のようなこともあり、関数型プログラミングの普及には、難しい理論を知らなくても使えるデザインパターンやイディオムが重要ではないかと考えています。

そういった観点から、このブログでは、デザインパターンやイディオムの整理を行っています。

2012年3月2日金曜日

代数的構造デザインパターン

要求開発アライアンスのセッション『Object-Functional Analysis and Design: 次世代モデリングパラダイムへの道標』で使用するスライドの背景説明第3弾です。

「代数構造的デザインパターン」として用意した以下の図を説明します。

デザインパターン

関数型プログラミングでは、数学由来の手法を駆使してプログラミングしていきます。このため元になった数学理論に対する本質的な理解は重要ではあるのですが、数学理論上では重要ではあるもののプログラミング的にはほとんど使われない概念や、数学理論上では枝葉の議論がプログラミング的には重要ということもありそうです。そういう意味で、プログラミングのために元になる数学理論を学ぶのは、プログラミングテクニックの習得という意味では遠回りです。

そこで、こういった数学由来の手法をオブジェクト指向プログラマに馴染みの深いデザインパターンとして整備して、プログラミングテクニック、デザインテクニックとして効率よく学び、コミュケーションのためのボキャブラリとしても活用できるようにしていくのが得策ではないかと考えています。

本来のデザインパターンはパターン言語で使用する文脈や動機、解法といったものを定めていきますが、きちんとしたものを書くのはかなりの労力が必要なので、ここではアイデアレベルのラフスケッチにとどめます。

代数的構造

代数的構造(algebraic structure)は代数学の基本概念です。

HaskellやScalaでは、型クラスの導入によってこの代数的構造のメカニズムをプログラミング言語の自然な拡張として使用できるようになりました。関数型プログラミングにおける型クラスの導入と代数的構造の適用はごく最近のことなので、まだ端緒についたばかりですが、いずれ広範囲に深く利用されることになるのではないかと思います。

結合律(associative law)、交換律(commutative law)、分配率(distributive law)というと難しそうに感じますが、「Commutative, Associative and Distributive Laws」を見て頂ければ分かるとおり、法則そのものは小学校の算数に登場するもので誰でも知っていることです。

代数学で重要なのは、算数で使用するこれらの基本概念が数値計算以外の任意のドメインに対して適用することができるように抽象化を行っていることです。これらの基本概念を適用するための条件や計算方法を定めています。

このため、代数構造的デザインパターンをアプリケーションが定義した任意の代数的データ型に適用することによって、代数が提供する理論体系を適用することができるようになります。

現在のところ、代数的構造デザインパターンの中で関数型プログラミングに本格的に活用されているデザインパターンはモノイド(monoid)だけではないかと思います。

しかし、本格的な並行プログラミングが必要になってくるとより広範囲に活用されることになるのではないかと考えています。

結合律パターン

結合律(associative law)は、二項演算に与えられる以下の性質です。

(a + b) + c = a + (b + c)
半群(semigroup)
結合律を持つ二項演算から構成される代数的構造
モノイド(monoid)
半群に単位元を加えた代数的構造
群(group)
モノイドに逆元を加えた代数構造

結合律を満たした代数的構造を半群と呼びます。半群に単位元を追加したものがモノイド、モノイドに逆元を追加したものが群という関係になっています。

Scalaz

関数型プログラミングでは、モノイドが頻繁に利用されます。(半群の範囲で使用されるケースも多いですが、一般的にはモノイドとして認識して使用しています。)

関数型プログラミングでは、モノイドの二項演算として加算的な演算を割り当てることが一般的のようです。

Scalazでは、モノイドによる二項演算の(加算的な)演算子 |+| を提供しており、1|+|2 やList(1, 2, 3)|+|List(4, 5, 6) といった演算が可能になっています。(半群側で実現されているので半群でも利用可)

scala> 1 |+| 2
res10: Int = 3

scala> List(1, 2, 3) |+| List(4, 5, 6)
res11: List[Int] = List(1, 2, 3, 4, 5, 6)

また、Scalazの比較演算を行う型クラスOrderはモノイド的な動きをするようになっており:

scala> 1 ?|? 1 |+| 2 ?|? 2
res7: scalaz.Ordering = EQ

scala> 1 ?|? 1 |+| 2 ?|? 3
res8: scalaz.Ordering = LT

scala> 2 ?|? 1 |+| 2 ?|? 3
res9: scalaz.Ordering = GT

といったように、単位元を利用した比較演算の合成ができるようになっています。?|? は比較演算子、 |+| がモノイドの(加算的な)演算子です。EQが単位元になっています。

可換律パターン

可換律(commutative law)は、二項演算に与えられる以下の性質です。

a + b = b + a

結合律を満たした上で、可換律を満たした代数的構造として以下のものがあります。

可換半群
可換の性質を追加した半群
可換モノイド
可換の性質を追加したモノイド
可換群
可換の性質を追加した群。アーベル群ともいいます。

可換半群、可換モノイド、可換群はそれぞれ半群、モノイド、群に可換律を追加したものです。

分配律パターン

分配律(distributive law)は、以下の2つの二項演算(この場合は乗法*と加法+)に与えられる以下の性質です。

a * (b + c) = a * b + a * c

結合律、可換律は二項演算が一組(上の例では+)のパターンでしたが、二項演算が二組(上の例では+と*)では、分配律が加わってきます。

以下の性質を考えます。

  • 1. 加法に関して可換群
  • 2. 加法と乗法の間に分配法則が成り立つ。
  • 3. 乗法に関して半群
  • 4. 加法に関する単位元を除いて、乗法に関して群をなす。
環(ring)
上記性質で1, 2, 3を満たす代数的構造
体(field)
上記性質で1, 2, 4を満たす代数的構造

ざっくりと分配律が成立する代数的構造を環、環の制約を強めたものが体という感じと理解しています。

環と体の定義は「環・体とは」を参考にしました。

Scala

ScalaでのモノイドについてScala Tips / Option (8)とScala Tips / Either (13) - 二項演算, AND, Monoidで取り上げました。

並行プログラミングでの期待

今の所、広く利用されているのはモノイドですが、いずれ可換群、環、体といったものが活用されるようになるのではないかと予測しています。

というのは、モノイドが満たす結合律に加えて、可換律、分配律は並行プログラミングにおける処理の最適化で重要な役割を担うことになると考えるからです。

具体的には、モノイドや、可換群、体といった型クラスに準拠した代数的データをドメイン・モデルで定義しておけば、このデータ型に対する演算はフレームワーク側で自動的に並列実行してくれるようなイメージを考えています。

現在の実装では、まだまだそのような所までは至っていませんが、いずれメニーコアが普通になってくると、関数型プログラミングもその方向に伸びてくるのではないかと思います。

そして、OFADにおけるドメイン・モデルの構築もこの性質を織り込んだものになるでしょう。 

Scala Tips / Either (15) - 二項演算, OR

Rightを成功とする、成功/失敗文脈におけるEitherに対する二項演算です。(Scala Tips / Either (9) - 二項演算)

前回までは、「Either:AND」について「Either:AND」×「値:任意の関数で計算」、「Either:AND」×「値:Monoid」、「Either:AND」×「値:Plus」についてみてきました。

今回は、「Either:OR」×「値:任意の関数で計算」を考えます。

EitherのORは以下の演算になります。

EitherのOR
lhsrhs結果Rightの値Leftの値
RightRightRight二項演算-
RightLeftRightlhs-
LeftRightRightrhs-
LeftLeftLeft-二項演算

lhsとrhsの両方がLeft(失敗)でない場合は、Right(成功)となります。

値に対する二項演算は、lhs/rhsともRightだった場合と、Leftだった場合があります。

値に対する二項演算は、以下のものが考えられます。

lhs
lhs側を使う
rhs
rhs側を使う
  • f(lhs, rhs) :: 任意の関数で計算
  • lhs |+| rhs :: Monoidで計算
  • lhs <+> rhs :: Plusで計算

値に対する二項演算は以下の組合せとします。

lhs/rhsともRight
任意の関数で計算
lhs/rhsともLeft
lhs側を使う

(分類の基準)

Java風

if式を使って、4つの場合を記述します。

def f(e1: Either[Throwable, Int], e2: Either[Throwable, Int], f: (Int, Int) => Int): Either[Throwable, Int] = {
  if (e1.isRight && e2.isRight) {
    Right(f(e1.right.get, e2.right.get)) // Rightの二項計算
  } else if (e1.isRight && e2.isLeft) {
    e1
  } else if (e1.isLeft && e2.isRight) {
    e2
  } else { // e1.is Left && e2.isLeft
    e1 // Leftの二項演算
  }
}

Scala風

match式を使って、4つの場合を記述します。

def f(e1: Either[Throwable, Int], e2: Either[Throwable, Int], f: (Int, Int) => Int): Either[Throwable, Int] = {
  e1 match {
    case Right(e1r) => e2 match {
      case Right(e2r) => Right(f(e1r, e2r)) // Rightの二項計算
      case Left(_) => e1
    }
    case Left(_) => e2 match {
      case Right(_) => e2
      case Left(_) => e1 // Leftの二項演算
    }
  }
}

match式のネストが気に入らない場合は以下のようにすればネストしない方式で記述することもできます。

def f(e1: Either[Throwable, Int], e2: Either[Throwable, Int], f: (Int, Int) => Int): Either[Throwable, Int] = {
  (e1, e2) match {
    case (Right(e1r), Right(e2r)) => Right(f(e1r, e2r)) // Rightの二項計算
    case (Right(_), Left(_)) => e1
    case (Left(_), Right(_)) => e2
    case (Left(_), Left(_)) => e1 // Leftの二項計算
  }
}

後者(Tuple方式)は、Tupleを導入しているのとパターンマッチングの回数が増えるので性能的には不利ですが、プログラムの見通しはよくなります。フレームワークで使う場合には性能重視で前者(ネスト方式)、アプリケーションで使う場合には可読性重視で後者(Tuple方式)という選択も考えられます。

Scala

Eitherに対するORを行うScalaらしい関数合成、Monadic演算による方式を見つけることができませんでした。Scala風で説明した方法を用いることになります。

Scalaz

Scalazでも、Eitherに対するORを行うScalaらしい関数合成、Monadic演算による方式を見つけることができませんでした。Scala風で説明した方法を用いることになります。

ノート

Scala Tips / Either (10) - 二項演算, AND、Scala Tips / Either (13) - 二項演算, AND, Monoid、Scala Tips / Either (14) - 二項演算, AND, Plusの3つはflatMapを使った関数合成やApplicative Functorの利用がぴったりとはまりました。

一方、今回はEitherに対するORを行おうとしたわけですが、ぴったりはまるよい方法を見つけることができませんでした。

scalaz.Traverseあたりを使うと何とかなりそうな気もしていたのですが、TraverseもflatMapと同様にANDのセマンティクスのようです。Optionに変換する方法はLeftの情報がなくなってしまうのでダメです。

Eitherに対するOR演算は、今後の研究課題にしたいと思います。

諸元

  • Scala 2.9.1
  • Scalaz 6.0.3

2012年3月1日木曜日

オブジェクト・モデリングのボトルネック

要求開発アライアンスのセッション『Object-Functional Analysis and Design: 次世代モデリングパラダイムへの道標』で使用するスライドの背景説明第2弾です。

「オブジェクトモデリング」として用意した以下の図を説明します。



オブジェクト・モデルの構成

オブジェクト指向分析/設計ではシステムを色々な観点のモデルを組み合わせて記述します。

ここでは、静的構造モデル、状態機械モデル、協調モデルの3種類のモデルによる軸について考えます。(これとは別の軸で、ドメイン・モデル/アプリケーション・モデルの軸、論理モデル/物理モデルの軸、もあります。)

静的構造モデルは、モデルの静的構造をクラス図やコンポーネント図などを用いて記述します。ドメイン・モデルや配備モデルの中核モデルとして用いられます。

状態機械モデルは、オブジェクトの状態遷移モデルを状態機械図や状態遷移表で記述します。オブジェクトモデリングの動的モデルの基盤となります。

協調モデルは、システムを構成するオブジェクト群の協調動作をメッセージパッシングによるオブジェクト間の相互作用として記述します。相互作用は、相互作用図(interaction diagram) であるシーケンス図(sequence diagram)とコミュニケーション図(commnunication diagram) (旧コラボレーション図, collaboration diagram)で記述します。

また、協調モデルの中で抽象的な位置付けのモデルとしてユースケースモデルがあります。ユースケースを現実化(realization)するとコラボレーション、コラボレーションを抽象化するとユースケースになるという関係です。ユースケースはUML的にはユースケース図で記述しますが、これはユースケース・モデルの目次みたいなもので、ユースケース記述、シナリオがユースケースの肝となる情報です。

ユースケースは、要求モデルの中軸モデルです。ユースケースによって記述された要求モデルを、ユースケースをコラボレーションに落とし込むことで、システムの静的構造モデル、状態機械モデルに反映させていくことになります。

オブジェクトモデリングの問題点

静的構造モデルと状態機械モデルは、プログラムに落とし込めるレベルのものを宣言的に記述することが可能です。

しかし、協調モデルについては、静的構造モデルや状態機械モデルとはモデルの練度が異なっていて、直接プログラムに落とし込むレベルのものは記述することができません。インスタンス(実例)ベース、帰納的に記述したモデルを、手動でプログラムに落とし込むことになります。

オブジェクトモデリングの問題点は、協調モデルが不完全なためにモデル駆動開発で使えるレベルのプラットフォーム独立な動的モデルを記述できない点にあります。さらに、協調モデルは要求モデルとシステムをつなぐ重要な役割も担っているので、このモデルが機能不全を起こしていることの影響は深刻です。

また、協調モデルが取り持つことになっている静的構造モデルと状態機械モデルの連携も不完全になり、結果として静的構造モデルのみの運用になってしまいます。静的構造モデルのメインの用途はドメイン・モデルの構造記述ですから、事実上、クラス図を使ってデータモデリングをしているのと変わらないことになってしまいがちです。

Object-Functional Analysis and Design (OFAD)での論点

OOADに関数型を編み込んでOFADに昇華させるための論点として、色々あると思いますが、今の所、以下のものを中心に考えています。

  • 状態機械と関数の関係
  • 要求モデルの記述方法と関数型との関係
  • 協調モデルの問題点を関数型で緩和できるのか
  • データフローモデルの使いどころ

特に、オブジェクトモデリングの欠点を埋める「協調モデルの問題点を関数型で緩和できるのか」という論点が重要ではないかと考えています。他の項目は、OOADに対してFPで何を足すのかということですが、この項目は、OOADのボトルネックをFPが緩和(理想的には解消)できるのかという切り口なので、うまく適用できれば、OOADからOFADに移行する大きな誘因になるからです。

Scala Tips / Either (14) - 二項演算, AND, Plus

Rightを成功とする、成功/失敗文脈におけるEitherに対する二項演算です。

今回は「Either:AND」×「値:Plus」を考えます。

前々回は「Either:AND」×「値:任意の関数で計算」、前回は「Either:AND」×「値:Monoidで計算」でしたが、値の計算方法を「任意の関数で計算」や「Monoidで計算」から「Plusで計算」に変えたものになります。Plusはちょっと謎な性質なのですが、Scalazで用意されているので、動作確認という意味もあり試してみました。

EitherのANDは以下の演算になります。

EitherのAND
lhsrhs結果Rightの値Leftの値
RightRightRight二項演算-
RightLeftLeft-rhs
LeftRightLeft-lhs
LeftLeftLeft-二項演算

値に対する二項演算は以下の組合せとします。

lhs/rhsともRight
Plus
lhs/rhsともLeft
lhs側を使う

Scala標準ライブラリではPlusは提供されていないので、この組み合わせが可能なのはScalazの場合です。Java風、Scala風、ScalaはMonoidの場合と同じになるので省略して、ScalazでPlusを使った実装を行います。

Scalaz

引数の型を型クラスPlusに対応する型パラメータMとします。また型パラメータMは高カインド型で、型パラメータAを取ります。この場合、型パラメータMは、コンテキスト・バウンドを使って「M[_]: Plus」と指定します。

ScalazではPlus同士の加算演算として、演算子 <+> を用意しているので、これを使います。

Scalazでは、RightProjectionだけではなくEitherも成功/失敗文脈のモナドとして使えるのと、flatMapメソッドとして>>=メソッドを使うことができるので、以下のようになります。

def f[M[_]: Plus, A](e1: Either[Throwable, M[A]], e2: Either[Throwable, M[A]]): Either[Throwable, M[A]] = {
  e1 >>= (e1r => e2.map(e2r => e1r <+> e2r))
}

試してみたところ、型クラスPlusはコンテナ同士のOR演算を行うようです。

Scalazでは、ListやOptionなどコンテナ的に使用できるオブジェクトの多くが型クラスPlus型として定義されているので、Plusに対するロジックをそのまま適用することができます。以下は実際に動いている様子です。

scala> f(List(1, 2).right, List(3, 4).right)
res100: Either[Throwable,List[Int]] = Right(List(1, 2, 3, 4))
scala> f(Map(1 -> 10, 2 -> 20).right, Map(3 -> 30, 4 -> 40).right)
res103: Either[Throwable,scala.collection.immutable.Iterable[(Int, Int)]] = Right(List((1,10), (2,20), (3,30), (4,40)))
scala> f(1.some.right, 2.some.right)
res104: Either[Throwable,Option[Int]] = Right(Some(1))
scala> f(none.right, 2.some.right)
res106: Either[Throwable,Option[Int]] = Right(Some(2))

ListとMapは、コンテナが自然に結合されています。

Optionについては、コンテナ内に格納できる要素が一つしかありません。そこで、短絡評価ORの計算が行われるようです。モノイドの場合は、格納される値に対する二項演算が行われるので、その点が違いとなります。

for

for式でもrightメソッドでRightProjectionを取り出す処理は省略できます。

Plus同士の加算演算として、オペレータ <+> を使います。

def f[M[_]: Plus, A](e1: Either[Throwable, M[A]], e2: Either[Throwable, M[A]]): Either[Throwable, M[A]] = {
  for {
    e1r <- e1
    e2r <- e2
  } yield e1r <+> e2r
}
Applicative Functor

Scalazでは、Applicative Functorを使って、2つ(またはそれ以上)のEitherに対して二項演算(N項演算)することができます。

Plus同士の加算演算として、演算子 <+> を使います。演算子 <+> を使う場合には、「(e1|@|e2)(f)」といった形でメソッド名のみを指定する省略形は使えないので、引数を指定する必要があります。

def f[M[_]: Plus, A](e1: Either[Throwable, M[A]], e2: Either[Throwable, M[A]]): Either[Throwable, M[A]] = {
  (e1 |@| e2)(_ <+> _)
}

e1とe2が共にRightの場合、関数fの第1引数にe1(Right)の値、第2引数e2(Right)の値を適用して評価し、その結果をRightに詰めて返すという動作をします。

ノート

型クラスPlusを用いて、コンテナ・オブジェクトに対して演算子 <+> による共通のロジックを適用することができました。

型クラスMonoidは、オブジェクトに対する二項演算なので、演算子 |+| はscalaz.Identityに定義されていますが、型クラスPlusは、コンテナ・オブジェクトに対する二項演算なので、演算子 <+> はscalaz.MAに定義されています。

型クラスMonoidと型クラスPlusの使い分けは、このあたりのメカニズムも意識しておくとよいでしょう。

型クラスとコンテキスト・バウンド

PlusバージョンのプログラムでもMonoidバージョンと同様に、Int型ではなくて、コンテキスト・バウンドの記述方法[T: Plus]を用いてPlus型のオブジェクトを処理対象として宣言しました。

コンテキスト・バウンドを使わず、暗黙パラメタを使って、本文の処理を定義すると以下のようになります。

def f[M[_], A](e1: Either[Throwable, M[A]], e2: Either[Throwable, M[A]])(implicit p: Plus[M]): Either[Throwable, M[A]] = {
  (e1 |@| e2)(_ <+> _)
}

Monoidでは、型パラメータTに対するコンテキスト・バウンドでしたが、Plusでは、高カインド型の型パラメータMに対するコンテキスト・バウンドを使用しました。高カインド型の型パラメータでは、引数となる型パラメータは並置して宣言して、メソッド引数などで組合せを指定します。高カインド型の型パラメータを扱うときは、ちょっとコツが必要なので注意が必要です。

諸元

  • Scala 2.9.1
  • Scalaz 6.0.3

2012年2月29日水曜日

関数型言語の技術マップ

要求開発アライアンスの定例会で『Object-Functional Analysis and Design: 次世代モデリングパラダイムへの道標』というタイトルでセッションを行うことになりました。

セッション時間が50分なので、かなり俯瞰した形での全体像の説明になりそうですが、関連する要素技術の数が多いのと、内容が込み入っているので、ブログで補足説明をすることにしました。

今回はその第一弾です。

「関数型言語の関連技術」として用意した以下の図を説明します。関数型プログラミング言語レベルの説明はScalaを対象にします。

Disclaimer

2008年にScalaをはじめて足掛け4年、関数型プログラミングとは、どうも数学を使ってプログラミングしていくことらしい、ということが分かってきました。

ScalaをBetter Javaとして使うのであれば、そこまで頑張らなくてもよいのですが、関数型言語のパワーを引き出すにはやはり関数型プログラミング、さらにいうと関数合成をベースとしたMonadicプログラミングをしていく必要があります。

ボク自身はにわか関数型プログラマですし、数学や計算機科学は門外漢なので関数型言語の背景技術を調べるのはなかなか辛いのですが、関数型プログラミングをする以上は避けて通れないので、牛歩のようなスピードですが、少しづつ調べています。

現時点で分かったことをまとめたのが上の図です。

計算機科学、数学の観点からは緩い点もあると思いますが、逆にオブジェクト指向プログラマの目から見た関数型言語という観点で見て頂けると、これから関数型言語にアプローチする人にはよいスタートポイントになるかもしれません。

Curry-Howard対応

プログラミング言語の中での関数型言語の位置付けを考える上で重要なのがCurry-Howard対応(Curry-Howard correspondence)です。

Curry-Howard対応の詳細は上記Wikiページやk.inabaさんのCurry-Howard Isomorphism も参考になります。

ざっくりいうと、「単純型付ラムダ計算」と「直感主義命題論理&自然演繹」がIsomorphism(同型)ですから文字通り相互変換が可能ということです。この枠組みの中では「型=命題」、「計算=証明」となり、コンパイルが成功すれば証明完了となります。まさにプログラミングが数学の証明と同じということです。凄いですね。

残念ながら「直感主義命題論理&自然演繹」で記述できる範囲は狭いので、汎用的に一般の問題を記述できるわけではありません。

しかし、同型という形で数学と直結している点が重要です。「直感主義命題論理&自然演繹」を軸に、数理論理学の膨大な理論体系をプログラミングに取り込む可能性がみえてきます。

純粋関数型言語

関数型言語は大きく純粋関数型言語と(純粋でない普通の)関数型言語に分類することができます。

純粋関数型言語は、副作用がないといった性質が有名?ですが、重要なのは「単純型付ラムダ計算」をプログラミング言語として実現した物ということであろうと思います。

「純粋関数型言語」=「単純型付ラムダ計算」であればさらに、「純粋関数型言語」=「直感主義命題論理&自然演繹」であるわけで、プログラミング言語と数理論理学が直結することになります。

ハードウェアの壁

純粋関数型言語は、「マッカーシーの5つの基本関数」 の時代から関数型言語の理想の姿でした。関数型言語における関数の評価は、ラムダ計算を基盤にしていて、数学的に記述して証明できることがそもそもの存在理由だったわけです。

しかし、ハードウェア性能の壁を乗り越えることは難しく、現在に至っています。関数型言語は実用性能を得るために、手続き型言語機能やオブジェクト指向言語機能を取り込んで、事実上関数型言語的な手続き型言語、関数型言語的なオブジェクト指向言語として使用されてきました。

いうまでもありませんが、ハードウェア性能の向上はこういった制約を取り払いつつあります。

Webアプリケーションなどのアプリケーションプログラムでは、RubyやPythonといったインタープリタ型のスクリプト言語が実用言語として十分機能することが明らかになってきました。コンパイル型の純粋関数型言語ではこの壁はすでに超えていることは容易に推測できます。

Scalaの立場

ハードウェア性能が純粋関数型言語を動作させるのに十分なレベルに向上してきたのではないかということを説明しました。しかし、それでは一足飛びに純粋関数型言語に切り替えてしまえばよいのかというと、そう簡単でもありません。

ハードウェア性能が向上したといっても、やはりぎりぎりの局面では副作用のあるプログラムにしたいケースは残りそうです。仮にそういう事は事実上は滅多にないにしても、いざという時のために保険の意味で機能は残しておきたいのが人情です。

もう一つは、純粋関数型言語で状態を扱う技術であるモナドの難易度が高いことです。習得コストがかなり高いので、すでにオブジェクト指向言語で普通にプログラミングできるエンジニアが、コストをかけて学ぶメリットがあるのかという問題が出てきます。モナドを習得してはじめてスタートラインに立てるというだけなので、習得のインセンティブはかなり小さくなります。

これらのニーズを満たす解として考えらられるのがScalaが採用しているハイブリッド方式です。

Scalaでは、キーワードval、mutable/immutableの2種類がパラレルに用意されているコレクションライブラリ、代数的データ型を実装するのに適したcase classとキーワードsealed、といった形で副作用のない純粋関数型的なプログラミングを行うための仕掛けが多数用意されています。

この範囲でプログラミングしておけば、純粋関数型言語に近しい効果を得ることができます。

Scalaでは不変オブジェクトであるListは何も設定しなくても使えるのに対して、オブジェクト指向プログラミングに必須のArrayBufferは、importしなければ使えないようになっています。これは、純粋関数型的な利用方法を推奨するのがScalaのスタンスということの現れだと思われます。もちろん「純粋」では対処できない問題に対して(Javaと同等以上の)通常のオブジェクト指向プログラミングも可能になっています。

また、アルゴリズムのコアの部分は純粋関数型的に記述するとしても、それを取り囲む周辺機能は普通のオブジェクト指向プログラミングで記述するのも可能です。このため、関数型プログラマとオブジェクト指向プログラマが同一言語で協業するような運用も可能になります。

もちろん、不慮のバグで副作用が発生する可能性もあるので、純粋関数型言語のように安全というわけではありませんが、プログラマが気をつければ、純粋関数型プログラミングのメリットを享受できるようになっているわけです。

新しい要素技術

純粋関数型言語と相性のよい色々な要素技術が追加されています。

  • 代数的データ型
  • 永続データ構造
  • 型クラス

代数的データ構造は、代数的な計算に適したデータ型です。Scalaでの実装は不変オブジェクトであることに加えてキーワードsealedを用いることで、開いた形での継承によるポリモーフィズムを使わないようにします。

永続データ構造は、副作用を持たないデータ構造です。純粋関数型データ構造(pure functional data structure)という用語もあり、同じ意味を持つと思われます。一度作ったデータ構造は、二度と変更されることがなくメモリ上に残り続けるので「永続」と呼ばれています。(不揮発性のストレージに格納するという意味の「永続」ではありません。)不変オブジェクトのみで木構造やグラフ構造といったものを実現します。関数型プログラミングでは永続データ構造を使うスキルが重要になってきます。

型クラスは、「アドホック・ポリモーフィズムを提供する型システム」と定義されています。

オブジェクト指向的にいうと、アルゴリズムを実現したフレームワークと処理対象のデータオブジェクトを、それぞれ相互に依存しない形で実装したものを、どちらも変更することなく後付で接続するためのメカニズムです。

Scalaでは暗黙パラメタを使ったConceptパターンという手法で実現します。暗黙パラメタに対する文脈として型クラス・インスタンスをバインドすることで、フレームワークとデータオブジェクトをプログラム上は疎結合のままコンパイル時に接続できるのがミソです。

群論と圏論

型クラス導入前から、Scalaでもモナドを使うことはできましたが、コンベンションを使用した決め打ちの実装で、拡張性に乏しいものでした。

モナド以外にも、関数型プログラミングに有用な抽象代数学の概念はたくさんあるので、これらを必要に応じて取り入れていきたいニーズがあります。この目的に適したメカニズムが型クラスです。

型クラスは純粋関数型言語であるHaskellが導入した言語機能で、Haskellのクラスライブラリで代数的なメカニズムを構築するのに使用されています。

Scalaでは、型クラスを実現するクラスライブラリScalazを用いると、群論(モノイドなど)や圏論(モナドなど)が定義しているさまざまな代数的な処理をプログラミングテクニックとして利用することが可能になります。

代数的な計算メカニズムのサポートは、当然ながら型付ラムダ計算とも相性がよく、さらに他の数学分野との連携でも有効に機能すると思われます。

発展の方向

数理論理学では、命題論理は基本中の基本ですが、述語論理や様相論理といった形で、よる複雑で応用範囲の広い理論が存在しています。

現段階では、ボクの調べた範囲では、述語論理や様相論理を関数型プログラミングの基本テクニックとして活用できるようにはなっていないようです。

とはいえ、最近話題の証明駆動という形になるのか、論理型言語に昇華していくのか、着地点は分かりませんが長い目で見ればいずれそういう方向に進むのではないかと思います。

圏論の上に論理学の圏を載せたものとしてトポスという理論体系があるようです。また、論理学と代数の裏側には常に集合論が見え隠れしています。このあたりの相互に関連を持つ数学の理論群がいろいろな形で関数型プログラミングにも取り入れられていくことが期待できます。

プログラミング言語が数学と直結することで、数学の理論体系がある意味、プログラムから利用できる具体的な機能となるわけです。実際にモナドやモノイドといった数学上の概念が型クラスという形で利用可能になりました。このポテンシャルはかなり大きく、今後プログラミング技術が大発展するホットスポットになるのではないかと思います。