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

要求開発アライアンスのセッション『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におけるドメイン・モデルの構築もこの性質を織り込んだものになるでしょう。