54

たとえば、Javaで記述されたプログラムは、動的ディスパッチに大きく依存しています。

そのようなプログラムはHaskellのような関数型言語でどのように表現されていますか？

言い換えれば、「ダイナミックディスパッチャ」の下でアイデアを表現するハスケルの方法は何ですか？

4

4 に答える 4

78

答えは一見単純です：高階関数。オブジェクト指向言語の仮想メソッドを持つオブジェクトは、いくつかのローカル状態を伴う関数の栄光の記録にすぎません。Haskellでは、関数のレコードを直接使用して、ローカル状態をクロージャに格納できます。

より具体的には、OOオブジェクトは次のもので構成されます。

  • オブジェクトのクラスの仮想メソッドの実装を含むvtable（仮想メソッドテーブル）へのポインター（vptr）。言い換えれば、関数ポインタの束。機能の記録。特に、各関数には、暗黙的に渡されるオブジェクト自体である非表示のパラメーターがあります。
  • オブジェクトのデータメンバー（ローカル状態）

多くの場合、オブジェクトと仮想関数の建物全体は、クロージャのサポートがないための手の込んだ回避策のように感じます。

たとえば、JavaのComparatorインターフェースについて考えてみます。

public interface Comparator<T> {
    int compare(T o1, T o2); // virtual (per default)
}

また、これを使用して、文字列のN番目の文字に基づいて文字列のリストを並べ替えるとします（十分な長さがあると想定します）。クラスを定義します。

public class MyComparator implements Comparator<String> {
    private final int _n;

    MyComparator(int n) {
        _n = n;
    }

    int compare(String s1, String s2) {
        return s1.charAt(_n) - s2.charAt(_n);
    }
}

そして、あなたはそれを使用します：

Collections.sort(myList, new MyComparator(5));

Haskellでは次のようにします：

sortBy :: (a -> a -> Ordering) -> [a] -> [a]

myComparator :: Int -> (String -> String -> Ordering)
myComparator n = \s1 s2 -> (s1 !! n) `compare` (s2 !! n)
-- n is implicitly stored in the closure of the function we return

foo = sortBy (myComparator 5) myList

Haskellに慣れていない場合は、一種の疑似Javaで大まかにどのように見えるかを次に示します（これは1回だけ行います）。

public void <T> sortBy(List<T> list, Ordering FUNCTION(T, T) comparator) { ... }

public (Ordering FUNCTION(String, String)) myComparator(int n) {
    return FUNCTION(String s1, String s2) {
        return s1[n].compare(s2[n]);
    }
}

public void foo() {
    sortBy(myList, myComparator(5));
}

タイプを定義していないことに注意してください。使用したのは関数だけです。どちらの場合も、sort関数に渡した「ペイロード」は、2つの要素を受け取り、それらの相対的な順序を与える関数でした。あるケースでは、これは、インターフェースを実装するタイプを定義し、その仮想関数を適切な方法で実装し、そのタイプのオブジェクトを渡すことによって達成されました。それ以外の場合は、関数を直接渡しました。どちらの場合も、sort関数に渡したものに内部整数を格納しました。1つのケースでは、これはプライベートデータメンバーを型に追加することによって行われ、もう1つのケースでは、関数でそれを参照するだけで、関数のクロージャーに保持されます。

イベントハンドラーを備えたウィジェットのより複雑な例を考えてみましょう。

public class Widget {
    public void onMouseClick(int x, int y) { }
    public void onKeyPress(Key key) { }
    public void paint() { }
    ...
}

public class MyWidget extends Widget {
    private Foo _foo;
    private Bar _bar;
    MyWidget(...) {
        _foo = something;
        _bar = something; 
    }
    public void onMouseClick(int x, int y) {
        ...do stuff with _foo and _bar...
    }
}

Haskellでは次のように行うことができます：

data Widget = Widget {
    onMouseClick :: Int -> Int -> IO (),
    onKeyPress   :: Key -> IO (),
    paint        :: IO (),
    ...
}

constructMyWidget :: ... -> IO Widget
constructMyWidget = do
    foo <- newIORef someFoo
    bar <- newIORef someBar
    return $ Widget {
        onMouseClick = \x y -> do
            ... do stuff with foo and bar ...,
        onKeyPress = \key -> do ...,
        paint = do ...
    }

Widgetイニシャルの後、タイプを定義しなかったことに再度注意してください。関数のレコードを作成し、クロージャに格納する関数のみを記述しました。ほとんどの場合、これがオブジェクト指向言語でサブクラスを定義する唯一の理由でもあります。前の例との唯一の違いは、1つの関数の代わりに複数の関数があることです。これは、Javaの場合、インターフェイス（およびその実装）に複数の関数を配置するだけでエンコードされ、Haskellでは関数のレコードを渡す代わりにエンコードされます。単一の機能。（前の例では、単一の関数を含むレコードを渡すこともできましたが、そのようには感じませんでした。）

（多くの場合、動的ディスパッチは必要ないことに注意してください。タイプのデフォルトの順序に基づいてリストを並べ替えるだけの場合は、指定されたインスタンスに対して定義されsort :: Ord a => [a] -> [a]たインスタンスを使用するを使用します。タイプ。静的に選択されます。）Orda

タイプベースの動的ディスパッチ

上記のJavaアプローチとHaskellアプローチの違いの1つは、Javaアプローチでは、オブジェクトの動作（ローカル状態を除く）がそのタイプによって決定されることです（または、それほど慈善的ではありませんが、各実装には新しいタイプが必要です）。Haskellでは、関数の記録を好きなように作成しています。ほとんどの場合、これは純粋な勝利です（柔軟性が得られ、何も失われません）が、何らかの理由でJavaの方法が必要だとします。その場合、他の回答で述べられているように、進むべき道は型クラスと実存主義です。

この例を続けるためWidgetに、aの実装をWidgetその型から追跡したいとします（実装ごとに新しい型を必要とします）。型クラスを定義して、型をその実装にマップします。

-- the same record as before, we just gave it a different name
data WidgetImpl = WidgetImpl {
    onMouseClick :: Int -> Int -> IO (),
    onKeyPress   :: Key -> IO (),
    paint        :: IO (),
    ...
}

class IsWidget a where
    widgetImpl :: a -> WidgetImpl

data Widget = forall a. IsWidget a => Widget a

sendClick :: Int -> Int -> Widget -> IO ()
sendClick x y (Widget a) = onMouseClick (widgetImpl a) x y

data MyWidget = MyWidget {
    foo :: IORef Foo,
    bar :: IORef Bar
}

constructMyWidget :: ... -> IO MyWidget
constructMyWidget = do
    foo_ <- newIORef someFoo
    bar_ <- newIORef someBar
    return $ MyWidget {
        foo = foo_,
        bar = bar_
    }

instance IsWidget MyWidget where
    widgetImpl myWidget = WidgetImpl {
            onMouseClick = \x y -> do
                ... do stuff with (foo myWidget) and (bar myWidget) ...,
            onKeyPress = \key -> do ...,
            paint = do ...
        }

関数のレコードを取得するためだけのクラスがあり、関数を個別に取り出す必要があるのは少し厄介です。私はこの方法で型クラスの個別の側面を説明するだけでした。それらは関数の栄光の記録（以下で使用）と、コンパイラが推測された型（上記で使用）に基づいて適切なレコードを挿入する魔法です。 、および以下を使用し続けます）。単純化しましょう：

class IsWidget a where
    onMouseClick :: Int -> Int -> a -> IO ()
    onKeyPress   :: Key -> a -> IO ()
    paint        :: a -> IO ()
    ...

instance IsWidget MyWidget where
    onMouseClick x y myWidget = ... do stuff with (foo myWidget) and (bar myWidget) ...
    onKeyPress key myWidget = ...
    paint myWidget = ...

sendClick :: Int -> Int -> Widget -> IO ()
sendClick x y (Widget a) = onMouseClick x y a

-- the rest is unchanged from above

このスタイルは、オブジェクト指向言語の方法からより親しみやすく、1対1のマッピングに近いため、オブジェクト指向言語から来る人々によく採用されます。ただし、ほとんどの場合、最初のセクションで説明したアプローチよりも複雑で柔軟性がありません。その理由は、さまざまなウィジェットの唯一の重要な点がウィジェット関数の実装方法である場合、型、それらの型のインターフェイスのインスタンスを作成し、それらを入れて基になる型を再び抽象化することにほとんど意味がないためです。実存的なラッパー：関数を直接渡す方が簡単です。

私が考えることができる利点の1つは、Haskellにはサブタイピングがない一方で、「サブクラス化」（おそらくサブインターフェースまたはサブ制約と呼ばれる方がよい）があることです。たとえば、次のことができます。

class IsWidget a => IsWidgetExtra a where
    ...additional methods to implement...

そして、あなたが持っているどんなタイプでも、あなたはシームレスIsWidgetExtraにの方法を使うこともできます。IsWidgetレコードベースのアプローチの唯一の代替手段は、レコード内にレコードを作成することです。これには、内部レコードの手動によるラップとアンラップが含まれます。しかし、これは、オブジェクト指向言語の深いクラス階層を明示的にエミュレートしたい場合にのみ有利です。これは、自分の生活を困難にしたい場合にのみ行います。IsWidget（Haskellにはからに動的にダウンキャストする組み込みの方法がないことにも注意してくださいIsWidgetExtra。ただし、ifcxtがあります）

（レコードベースのアプローチの利点はどうですか？新しいことを行うたびに新しい型を定義する必要がないことに加えて、レコードは単純な値レベルのものであり、値は型よりもはるかに簡単に操作できます。たとえば、引数としてaを取り、それに基づいてWidget新しい関数を作成します。一部は異なり、その他は同じままです。これは、C ++のテンプレートパラメータからのサブクラス化のようなもので、混乱が少なくなります。）Widget

用語集

  • 高階関数：他の関数を引数として取る（または結果として返す）関数

  • レコード：構造体（パブリックデータメンバーのみを含むクラス）。辞書とも呼ばれます。

  • クロージャ：関数型言語（および他の多くの言語）を使用すると、定義サイトのスコープ内のもの（たとえば、外部関数の引数）を参照するローカル関数（関数内の関数、ラムダ）を定義できます。維持されますが、関数の「クロージャ」にあります。あるいは、2つのintを取り、intを返すような関数がある場合、plusそれを1つの引数、たとえばに適用できます。5その結果、intを取り、それに5を追加することにより、intを返す関数になります-その場合、5結果の関数のクロージャにも格納されます。（他のコンテキストでは、「クロージャ」は「クロージャのある関数」を意味するために使用されることもあります。）

  • 型クラス：オブジェクト指向言語のクラスと同じではありません。インターフェースのようなものですが、非常に異なります。ここを参照してください。

編集29-11-14：この答えの核心はまだ本質的に正しいと思いますが（HaskellのHOFはOOPの仮想メソッドに対応します）、私がそれを書いたときから私の価値判断は微妙になりました。特に、HaskellのアプローチもOOPのアプローチも、厳密には他のアプローチよりも「基本的」ではないと思います。このredditコメントを参照してください。

于 2012-10-28T16:14:27.213 に答える
13

実際に動的ディスパッチを必要とせず、ポリモーフィズムだけを必要とする頻度は驚くべきものです。

たとえば、リスト内のすべてのデータを並べ替える関数を作成する場合は、それを多態的にする必要があります。（つまり、この関数をすべてのタイプに対して手動で再実装する必要はありません。それは悪いことです。）しかし、実際には動的なものは必要ありません。コンパイル時に、ソートしたい1つまたは複数のリストに実際に何が含まれているかがわかります。したがって、この場合、実行時型ルックアップは実際にはまったく必要ありません。

Haskellでは、物事を移動したいだけで、それがどのタイプであるかを知る必要も気にする必要もない場合は、いわゆる「パラメトリックポリモーフィズム」を使用できます。これは、JavaジェネリックやC++テンプレートのようなものです。データに関数を適用できるようにする必要がある場合（たとえば、データを並べ替えるために順序の比較が必要な場合）、それを行う関数を引数として渡すことができます。あるいは、HaskellにはJavaインターフェースに少し似たものがあり、「このソート関数は、このインターフェースを実装するあらゆるタイプのデータを受け入れる」と言うことができます。

これまでのところ、動的ディスパッチはまったくなく、静的ディスパッチのみです。関数を引数として渡すことができるため、手動で「ディスパッチ」を実行できることにも注意してください。

実際の動的ディスパッチが本当に必要な場合は、「既存の型」を使用するか、ライブラリなどのトリックを使用できます。Data.Dynamic

于 2012-10-28T09:22:20.037 に答える
7

アドホック多相は型クラスを介して行われます。より多くのOOPのようなDDは、実存型でエミュレートされます。

于 2012-10-28T07:57:21.953 に答える
5

たぶんあなたはADTとパターンマッチングが必要ですか？

data Animal = Dog {dogName :: String}
            | Cat {catName :: String}
            | Unicorn

say :: Animal -> String
say (Dog {dogName = name}) = "Woof Woof, my name is " ++ name
say (Cat {catName = name}) = "Meow meow, my name is " ++ name
say Unicorn = "Unicorns do not talk"
于 2012-10-28T07:22:41.827 に答える