Subscribed unsubscribe Subscribe Subscribe

The Expression Problem

Haskell

この記事はHaskell Advent Calendar jp 2010 : ATND向けに書いたものです。

最近、ふらふらとネットの波をさまよっていたら、Channel 9でRalf LaemmelさんがHaskellの型クラスを解説する動画を見つけました。これです。

The Expression Problemと呼ばれるプログラミングにおける古典的な問題をネタに、型クラスの基本的な使い方からfundepsの必要性まで、とてもわかりやすく解説しているのでお勧めです。今回は、このくそ忙しい師走に2時間も動画を見ていられないあなたのために、内容を抜粋して紹介したいと思います。

The Expression Problemとは何か

まあ慌てずに、まずはジミーウェールズに聞いてみましょう。

Philip Wadler coined the term:

The Expression Problem is a new name for an old problem. The goal is to define a datatype by cases, where one can add new cases to the datatype and new functions over the datatype, without recompiling existing code, and while retaining static type safety (e.g., no casts).

Expression problem - Wikipedia, the free encyclopedia

ニホンゴにすると、静的型付き言語で、再コンパイルなしで、新しいデータ型を追加したり、新しい関数を追加できるようにするにはどうしたらよいかということです。

動画の中では非常に基本的なインタプリタを例に解説しています。それでは実際に見ていきましょう。対象のインタプリタは次のように振る舞うことを想定します。

> let x = Const 40
> let y = Const 2
> let z = Add x y
> prettyPrint z
"40 + 2"
> evaluate z
42

ConstやAddというデータ構成子を使って値を作り、prettyPrintで文字列に、evaluateで実際に計算した値を返します。このインタプリタはどう実装すればよいのでしょうか。たいていの関数型言語に備わる代数的データ型(algebraic data types)を使えば簡単に実装できます。

module Data where

data Expr = Const Int
          | Add Expr Expr

プリティプリンタは次のように定義できます。

module PrettyPrinter where
import Data

prettyPrint :: Expr -> String
prettyPrint (Const i) = show i
prettyPrint (Add l r) = prettyPrint l ++ " + " ++ prettyPrint r

データ型はそのままに、さらに関数を追加してみます。実際に計算するevaluateは次のように定義できます。

module Evaluator where
import Data

evaluate :: Expr -> Int
evaluate (Const i) = i
evaluate (Add l r) = evaluate l + evaluate r

簡単ですね。

では、今度はデータ型(動画中ではdata variantsと呼ばれている)を追加してみましょう。Exprの正負を反転するNeg Exprを追加するにはどうしたらよいでしょうか?もちろんExprの定義に追加することになります。

data Expr = Const Int
          | Add Expr Expr
          | Neg Expr

プリティプリンタはどうなるでしょうか。prettyPrintはExprの各データ構成子でパターンマッチしているので、新しく追加したNegにもマッチするように定義を修正する必要があります。

prettyPrint :: Expr -> String
prettyPrint (Const i) = show i
prettyPrint (Add l r) = prettyPrint l ++ " + " ++ prettyPrint r
prettyPrint (Neg e)   = "- " ++ prettyPrint e

評価器evaluateも同様です。

関数型言語(代数的データ型)ではデータ型を追加するのが難しい

何が言いたいかというと、Exprにvariantを一つ追加するだけで、各所を変更する必要がある、ということです。これでは新しいvariantを追加するたびにモジュール全体を再コンパイルする必要があり、柔軟性に欠けているといえます。

オブジェクト指向では…

続いて、動画ではOOPの例が出てくるのですが、

  • Haskell Advent Calendar的にちょっと。。。
  • やる気が(ry

ので省略します。一言でまとめるとOOPでは状況が逆で、データを追加するのは簡単ですが、操作を追加するのが難しくなります。詳しくは動画を見てね!

要するに

The Expression Problemとは

  1. 静的型を使っていて
  2. 再コンパイルすることなく
  3. データ型や
  4. 操作を増やすのが難しい

ということです。大事なことでもないのに2回言いました。ここまでが一つ目の動画です。

ではこの問題をHaskellでどう解決しますか?という話が次の動画で解説されています。

型クラスは魔法の道具?

今までみてきたインタプリタの実装は、代数的データ型で実装されたExprに新たなvariantを追加すると、すべての関数でパターンマッチを追加する必要がありました。これを動画中では、コンパイルなしでvariantを追加できないという意味で、閉じたデータ型(the closed datatype)と表現しています。
では開いたデータ型(the open datatype)はどのように実装できるでしょうか?それはHaskellでクールなものトップ3を挙げたら必ずランクインしそうな型クラスです。

型クラスとは

2つ目の動画では型クラスの基本について丁寧に説明されています。ので動画を見てください。Javaに慣れ親しんでいる方はインタフェースにちょっと似ている、型で多重ディスパッチする仕組みと考えてください。

The open datatype

それでは型クラスを使って開いたデータ型を実装します。ここでは発想を変えてConstとAddを別々のデータ型として定義し、それぞれをExprクラスのインスタンスにします。

data Const   = Const Int
data Add l r = Add l r

class Expr x

instance Expr Const

instance (Expr l, Expr r) => Expr (Add l r)

Exprクラスはメソッド一つも持ちません。これは与えられたデータ型がExprのインスタンスであることのみが重要ということです。

プリティプリンタは次のように定義されます。

-- クラス制約を使って、xには上で定義したExprのインスタンスのみ使えるようにしている
class Expr x => PrettyPrint x where
  prettyPrint :: x -> String

instance PrettyPrint Const where
  prettyPrint (Const i) = show i

instance (PrettyPrint l, PrettyPrint r) => PrettyPrint (Add l r) where
  prettyPrint (Add l r) = prettyPrint l ++ " + " ++ prettyPrint r

関数を追加するのもPrettyPrintクラスと同様、簡単です。

class Expr x => Evaluate x where
  evaluate :: x -> Int

instance Evaluate Const where
  evaluate (Const i) = i

instance (Evaluate l, Evaluate r) => Evaluate (Add l r) where
  evaluate (Add l r) = evaluate l + evaluate r

さらに新しくデータ型を追加するのも簡単です。代数的データ型ではうまくいかなかったNeg xを追加してみましょう。

data Neg x = Neg x

instance Expr x => Expr (Neg x)

instance PrettyPrint x => PrettyPrint (Neg x) where
  prettyPrint (Neg x) = "- " ++ prettyPrint x

instance Evaluate x => Evaluate (Neg x) where
  evaluate (Neg x) = negate $ evaluate x

今まで定義してきたデータ型・関数ともに変更することなくNeg xという新しい表現が使えるようになりました。重要なのはNegの定義自体はExprと同じモジュールである必要がないことです。これにより他のモジュールは再コンパイルなしで新しいデータ型を追加できるようになります。

Multi-parameter type classesを使う

動画ではさらに1歩進めて、複数の型の関係性を扱う場合も取り上げています。具体例として図形の重なりを判定することを考えます。

まずは閉じた代数的データ型で定義してみましょう。

data Shape = Square { x, y :: Int, length :: Int }
           | Rectangle { x, y :: Int, height, width :: Int }
           | Circle { x, y :: Int, radius :: Float }
           | Ellipse { x, y :: Int, major, minor :: Float }

重なりを判定する閉じた関数intersectは次のようになるでしょう。

intersect (Square x y l)      (Square x' y' l')       = ...
intersect (Rectangle x y h w) (Rectangle x' y' h' w') = ...
intersect (Circle x y r)      (Circle x' y' r')       = ...
intersect (Ellipse x y m n)   (Ellipse x' y' m' n')   = ...
intersect (Square x y l)      (Rectangle x' y' h w)   = ...
...

ここでShapeにvariantを追加したらどうなるでしょうか?先ほどと同じですね。intersectのパターンマッチを追加してやる必要があります。

では型クラスを使った開いたデータ型ではどうなるでしょうか?

data Square    = Square    Int Int Int
data Rectangle = Rectangle Int Int Int Int
data Circle    = Circle    Int Int Float
data Ellipse   = Ellipse   Int Int Float Float

class Shape x

instance Shape Square
instance Shape Rectangle
instance Shape Circle
instance Shape Ellipse

intersectもインタプリタと同様に次のように定義できます。

class Shape x

instance Shape Square
instance Shape Rectangle
instance Shape Circle
instance Shape Ellipse

class (Shape x, Shape y) => Intersect x y where
  intersect :: x -> y -> Bool

instance Intersect Square Square where
  intersect s s' = ...

instance Intersect Rectangle Rectangle where
  intersect s s' = ...

違いはIntersectクラスの定義でxとyという2つのパラメータを取っていることだけです。3つ以上のパラメータをとっても同じように適用できます。素晴らしいですね。

Functional dependencies (fundeps)

もう一つ例を考えてみましょう。今度は図形を正規化(normalize)します。面積と座標を保持したまま、RectangleはSquareに、EllipseはCircleに変換するようなものです。

閉じた型で定義してみます。

normalize :: Shape -> Shape
normalize s@(Square _ _ _)    = s
normalize (Rectangle x y h w) = Square ...
normalize s@(Circle _ _ _)    = s
normalize (Ellipse x y m n)   = Ellipse ...

簡単ですね。

開いた型ではどうなるでしょうか。

class Shape s => NormalShape s

instance NormalShape Square
instance NormalShape Circle

class (Shape s1, NormalShape s2) => Normalize s1 s2 where
  normalize :: s1 -> s2

instance Normalize Square Square where
  normalize = id

instance Normalize Circle Circle where
  normalize = id

instance Normalize Rectangle Square where
  normalize = ...

instance Normalize Ellipse Circle where
  normalize = ...

こちらも簡単です。

しかしこの定義は使うときになって問題が発覚します*1

Prelude> normalize (Square 1 2 3)   -- 型チェックを通らない

<interactive>:1:1:
    No instance for (Normalize Square s2)
      arising from a use of `normalize'
    Possible fix: add an instance declaration for (Normalize Square s2)
    In the expression: normalize (Square 1 2 3)
    In an equation for `it': it = normalize (Square 1 2 3)
(0.01 secs, 2654396 bytes)
Prelude> normalize (Square 1 2 3) :: Square -- 型を指定してやると通る
Square 1 2 3

これは型推論が意図したとおりには動かないことが原因です。何故このようなことが起こるのでしょうか?一見するとNomalize Square XXXというインスタンスは一つしかないので、型は一意に定まるように見えますが、Shapeは開かれていることを思い出してください。誰かが次のモジュールを追加すると何が起こるでしょうか?

instance Normalize Square Circle where ...

こうなると、もはやnormalize (Square 1 2 3)の型がSquareなのかCircleなのか判断がつきません。型システムはこのような問題を避けるように、型チェックで弾いてくれているのです。

しかし現実にはNormalize Square Circleという正規化は不要な時もあるでしょう。その場合はいつも結果の型を明示してやらなければならないのでしょうか?

これを解決するのがfunctional dependenciesです。

「Normalizeの1つ目のパラメータまで決まったら、2つ目のパラメータは一意に定まる」という意図を型に含めるには、ほんの少しNormalizeの定義をいじってやります。

class (Shape s1, NormalShape s2) => Normalize s1 s2 | s1 -> s2 where
  normalize :: s1 -> s2

この「| s1 -> s2」という部分が「1つ目のパラメータまで決まったら、2つ目のパラメータは一意に定まる」ことを表しています。使ってみましょう。

Prelude> normalize (Square 1 2 3)
Square 1 2 3

今度はうまく動きました。また、instance Normalize Square Circleを追加するとちゃんと型チェックで弾いてくれます。このようにfundepsは曖昧で一意に定まらない型に対して、制約を与えてやることで、型の表現力を増す働きをします。

最近ではfundepsの他にtype familiesという拡張もあって、fundepsをより関数的に書くために使うこともできます。こちらの紹介はまた別の機会に。

型クラスは銀の弾丸ではない

The Expression Problemの型クラスを用いた解法はシンプルで素晴らしいものですが、万能ではありません。

  • ボイラープレート(重複したコード)が多い
    • derivingしたい!みたいな
  • 開いた型に対する(==)ができない
  • 開いた型へのread :: Read a => String -> aができない
  • 厳密すぎる型
    • Add (Add (Const 1) (Const 1)) (Const 40) :: Add (Add Const Const) Constという具合
  • ヘテロなリスト
    • intersectMany :: [Shape] -> Boolはどうやって実装する?

これらの問題はHaskellのgeneric programmingのお話になるのでまた別の機会に!

動画はここまでですが、上に上げた以外にも、

  • instance宣言のスコープはグローバルにぶちまけられる
    • qualifiedインポートできない
    • hidingもできない
  • グローバルな故、複数のinstance宣言を使い分けることもできない
  • グローバルな故、衝突の可能性が常にある
    • cabal installで泣いた人も多いはず

などの問題があります。Scalaのimplict conversionはここら辺の問題をうまく扱っていたような気がします。Haskellでもいい方法ないかなあ。

追記: 発展

The Expression Problemとインタプリタというと、Oleg KiselyovさんのTyped tagless-final interpretations: Lecture notesの前半で取り上げられています。興味のある方は是非。

*1:Square型をderiving Showしています