F 代数と C++

「F 代数は Proto で役立つと思います。」 このようにして Bartosz Milewski が私の頭の中に種を蒔き、それが今ではこのブログ記事へと成熟しました。 Bartosz は F 代数に関するブログ記事を書いていたので、私にそれを復習してもらうために、Proto ニンジンをぶら下げました。かみました。

F 代数では、式の評価は再帰とは別のものです。代数は、あるレベルの式ツリーがどのように評価されるかを指定し、残りは カタモルフィズム によって処理されます 、一度書かれ、すべての代数で共有されます。私は怠惰なプログラマーです。私はかなりの数学の吸盤でもあります。だから私は夢中になりました.

Bartosz のコードは Haskell で書かれているので、最初のステップは C++ に移植することでした。この投稿の残りの部分では、私の F 代数コードの C++11 への移植を紹介します。最初に Bartosz の投稿をお読みください。すべてが理解できたら、ここに戻って、これがすべて C++ にどのようにマップされるかを確認してください。

免責事項:これは、F 代数の読みやすい紹介を意図したものではありません。それについては Bartosz のブログを読んでください。

Haskell の ExprF 型

Bartosz は、運転例として単純な式ツリーを使用します。次のようになります:

data ExprF a = Const Int
             | Add a a
             | Mul a a

type Expr = Fix ExprF

注目すべきは、06 という事実です。 ではない 再帰的;つまり、19 それ自体では実装されていません。それでも彼は、これはツリー データ構造であり、ツリーは再帰的であると主張しています。

答えは、再帰が 26 と呼ばれる型コンストラクターによって外部から提供されることです。 . 37 の場合 は 1 レベルのツリーで、42 は 2 レベルのツリーで、50 無限レベルのツリーです。無限に到達したことをどのように知ることができますか?もう1つがあなたが始めた場所に戻るとき。それは定点です 、および 69 は定点です。パラメータ 78 のアプリケーションを無限に偽装します。 .任意の型コンストラクタ 82 の場合 、タイプ 91 106 の別のアプリケーション 開始した場所に戻ります。 110 の方法を見てみましょう が定義されています。

修正タイプ

124 非再帰シェルから再帰データ構造を作成できます。ハスケルはこちら。 136 を含めます ここでも機能します。

newtype Fix f = Fx (f (Fix f))

unFix :: Fix f -> f (Fix f)
unFix (Fx x) = x

ここでは、145 は単項型コンストラクタであり、 157 168 を取るデータコンストラクタです 171 を返します . C++ では、単項型コンストラクターは、1 つのパラメーターを受け取るクラス テンプレートです。 185 の場合、単項クラス テンプレートをパラメーターとして受け取るテンプレートであり、195 207 を返す関数です :

template<template<typename> class F>
struct Fix
  : F<Fix<F>>
{
    explicit Fix(F<Fix<F>> f)
      : F<Fix<F>>(f)
    {}
};

template<template<typename> class F>
Fix<F> Fx(F<Fix<F>> f)
{
    return Fix<F>{f};
}

template<template<typename> class F>
F<Fix<F>> unFix(Fix<F> f)
{
    return f;
}    

C++ から、219 であることがわかります。 本当に定点です。 228 233 から継承 .継承は IS-A です 関係なので、246 本当に 250 です . (逆を真と見なすかどうか — つまり、264 278 です —あなたがどれだけ文字通りの精神を持っているかによって異なります。私の目的では、286 関数はそうします。)

ハスケルに戻ります。 Bartosz の 294 の定義で および 301 、次のやや冗長な例のように、任意の深さの式ツリーを作成できます:

testExpr = Fx $ 
               (Fx $ (Fx $ Const 2) `Add` (Fx $ Const 3))
                `Mul` (Fx $ Const 4)

しかし、312 を表現する最良の方法は何ですか? C ++で?それは明らかではありません。

C++ の ExprF 型

322 の定義をもう一度見てみましょう

data ExprF a = Const Int
             | Add a a
             | Mul a a

これは次のように読むことができます:もし誰かが 332 を与えた場合 、 343 のいずれかを含むことができます 、 350 、または 369 .このどちらかまたは両方の演説は、組合のように聞こえます。 C++11 の無制限共用体を使ってこのようなものをハックすることもできますが、Boost はもっと良い方法を提供してくれます:370 .これ以上苦労することなく、これが 386 をどのように移植したかです C++ へ:

struct Const_
{
    int value;
};

template<typename A>
struct Add_
{
    A left;
    A right;
};

template<typename A>
struct Mul_
{
    A left;
    A right;
};

template<typename A>
using ExprF_ =
    boost::variant<
        Const_
      , boost::recursive_wrapper<Add_<A> >
      , boost::recursive_wrapper<Mul_<A> >
    >;

template<typename A>
struct ExprF
  : ExprF_<A>
{
    typedef ExprF<A> tag;
    ExprF(Const_ c) : ExprF_<A>(c) {}
    ExprF(Add_<A> c) : ExprF_<A>(c) {}
    ExprF(Mul_<A> c) : ExprF_<A>(c) {}
};

using Expr = Fix<ExprF>;

これは冗長ですが、ほとんど簡単です。でも待って、398 はどうなっているの? ? 408 じゃないですか 非再帰的であるべきですか?そうです、技術的には、今でもそうです。しかし、木を作り始めると、それはできあがる 411 による再帰 . Haskell では、再帰型は問題ありません。ただし、C++ では、構造体 422 タイプ 433 のメンバーを持つことはできません . できます タイプ 441 のメンバーを持つ しかし、それは基本的に 456

469 を構築するためのいくつかのユーティリティ関数 オブジェクトは後で役に立ちます:

template<typename A = Expr>
ExprF<A> Const(int val) {return Const_{val};}

template<typename A>
ExprF<A> Add(A a, A b) {return Add_<A>{a, b};}

template<typename A>
ExprF<A> Mul(A a, A b) {return Mul_<A>{a, b};}

カタ関数

データ型の再帰は 477 によって外部で行われます 、アルゴリズムの再帰は、カタモルフィズムと呼ばれる非常に一般的な関数によって外部で行われます 、または 484 . Bartosz による 491 の派生 関数は非常に興味深いので、ぜひお読みください。結果はこちら:

cata :: Functor f => (f a -> a) -> Fix f -> a
cata alg o = alg . fmap (cata alg) . unFix o

すべての数学関数合成を右から左に行うように、これを読みます。 501 再帰的な固定小数点データ構造の 1 つのレベルをアンパックする効果があります。これにより、515 できる Functor が生成されます 以上。 521の方法を知らなくても 私たちの型に実装されているので、532 を呼び出すことがわかります。 再帰的に。 (この時点では、再帰がどのように終了するかは明確ではありません。後で説明します。)

これは 544 です C++で。短くて甘い…ほぼ。

template<typename Alg, template<typename> class F>
???? cata(Alg alg, Fix<F> o)
{
    using std::placeholders::_1;
    return alg(fmap(std::bind(&cata<Alg, F>, alg, _1),
                    unFix(o)));
}

Haskell では、2 つを期待する関数に 1 つの引数を渡すと、1 つの引数を取る関数が得られます。涼しい。 C++ でこれを行うと、コンパイラ エラーが発生します。 😛 代わりに、非常に便利な 556 を使用します .ラムダの方がファッショナブルですが、私は少し時代遅れです.

唯一の問題は、戻り値の型を宣言しようとするときです。 560 573 を返します 渡されたときに戻ります…何?まあ、どんな 580 でも 戻り値。しかし、598 によって返される型 603 への再帰呼び出しに依存します 、そしてそれを計算しようとして Catch-22 に行き詰まります。 617 の戻り値の型について言えること 一部になるということです テンプレート 627 のインスタンス 、しかしどれかはわかりません .だから、私はごまかします:

// A horrible hack for the purpose of computing
// cata's return type. AnyF<F> stands in for a F<T>
// when T is unknown.
template<template<typename> class F>
struct AnyF
{
    template<typename T>
    operator F<T> &() const;
};

template<typename Alg, template<typename> class F>
typename std::result_of<Alg(AnyF<F>)>::type
cata(Alg alg, Fix<F> o)
{
    using std::placeholders::_1;
    return alg(fmap(std::bind(&cata<Alg, F>, alg, _1),
                    unFix(o)));
}

このハッキングの恐ろしさ、なぜ機能するのか、なぜ機能しないのかについては詳しく説明しません。言わないほうがいい。

fmap

あなたが Haskeller なら、633 を知っているでしょう ファンクターを意味します。 (これは、大文字の「F」が付いた数学的な「ファンクター」であり、おなじみの C++ のものとはおそらく異なるものです。) もしあなたが Haskeller でないなら、ここにスキニーがあります:>649 652 からマッピングされる関数 660 まで 、それはあなたに 670 を与えます 何かをすることによって . 685 ごとに何かが違うということ -可能なタイプ。

Haskell の Functor は型クラスです。型クラスとインスタンスは、C++ の概念と概念マップのようなものです。では、Haskell の Functor 型クラスのようなものはどのように C++ に変換すればよいのでしょうか?興味深い質問です。今のところ、単純化するための仮定を立てます:all C++ で「ファンクター」の概念をモデル化する型は、690 として実装されます。 . (明らかに、これは 703 の場合です。 .)

711 はこちら C++ で:

template<typename Fun, typename Tag>
struct functor_visitor;

template<typename Fun, typename Fa>
typename
    functor_visitor<Fun, typename Fa::tag>::result_type
fmap(Fun f, Fa fa)
{
    return boost::apply_visitor(
        functor_visitor<Fun, typename Fa::tag>{f}, fa);
}

725 バリアントでどのスロットが占有されているかを確認し、734 で適切なハンドラーにディスパッチする単純なラッパーです。 .そこに 749 を入れます あなたのタイプのロジック。これが 753 の方法です 768 用に実装されています :

template<typename Fun, typename A>
struct functor_visitor<Fun, ExprF<A>>
  : boost::static_visitor<
        ExprF<typename std::result_of<Fun(A)>::type>>
{
    typedef typename std::result_of<Fun(A)>::type B;

    explicit functor_visitor(Fun f)
      : f_(f)
    {}

    ExprF<B> operator()(Const_ i) const
    {
        return Const<B>(i.value);
    }

    ExprF<B> operator()(Add_<A> e) const
    {
        return Add(f_(e.left), f_(e.right));
    }

    ExprF<B> operator()(Mul_<A> e) const
    {
        return Mul(f_(e.left), f_(e.right));
    }
private:
    Fun f_;
};

つまり、776 関数と 785 を使用 798 の内容に応じて、3 つのいずれかを行います .各 801 オーバーロードは考えられる 1 つのケースを処理し、それらはすべて 814 を返します 、ここで 828 836 とは 847 が渡されると戻ります .

852 を見る 、関数は 861 になります -ing over は 877 になります . 887 の場合 893 を含む または 907 、その後、再帰的に 918 を呼び出すことになります .しかし、920 に到達すると 、私たちはしません 再帰。そうでなければ 938 二度と戻らない!

F代数

944 とは ?それが最良の部分です:あなたが決めます!それは代数です。シンボルから式を作成して評価する方法。以下は、955 を引き起こす Haskell の単純な代数です。 意味のある方法で式ツリーを評価するには:

alg :: ExprF Int -> Int

alg (Const i)   = i
alg (x `Add` y) = x + y
alg (x `Mul` y) = x * y

C++ では次のようになります:

struct alg_visitor
  : boost::static_visitor<int>
{
    int operator()(Const_ i) const
    {
        return i.value;
    }

    int operator()(Add_<int> e) const
    {
        return e.left + e.right;
    }

    int operator()(Mul_<int> e) const
    {
        return e.left * e.right;
    }
};

int alg(ExprF<int> e)
{
    return boost::apply_visitor(alg_visitor{}, e);
}

966 の例を次に示します。 と 975 式ツリーの評価:

// (2+3)*4 == 20
Expr testExpr =
    Fx(Mul(
        Fx(Add(
            Fx(Const(2)),
            Fx(Const(3))
        )),
        Fx(Const(4))
    ));
int z = cata(alg, testExpr);
std::cout << z << std::endl;

これは 986 を出力します あなたが期待するように。同じ式ツリーを異なる方法で評価させる他の代数を簡単に定義できます。

まとめ

991 に注意してください 再帰的ではありません。ここで本当に素晴らしいことが起こりました。 1 つのレベルのツリーを処理する方法を指定するだけで済み、任意の のツリーを無料で評価できます。 深さ。他のすべては 1002 によって処理されます および 1013 .

楽しくてかっこいいという事実以外に、なぜ私は気にするのですか? C++ で組み込みのドメイン固有言語を構築するための私のライブラリである Boost.Proto には、式の評価方法を指定するための小さな DSL があります。その DSL では、ツリー トラバーサル ロジックが残りのアルゴリズムと混合されます。これにより、Proto アルゴリズムを作成するのが難しくなります。興味深いビットのみを指定しながら、再帰的な評価を無料で取得する方法があれば…。それゆえ、F 代数に興味があります。

Bartosz と私は、これを拡張して私のユース ケースで動作させる方法について話し合ってきました。 State モナドと組み合わせると、1029 関数は、多くの式評価スキームの重要な部分である折り畳みを行うことができます。でも、それは後で取っておこうと思います。

このコードは、私の github リポジトリで少し一般化された形で見つけることができます。そこでは、State モナドの私の実装も見つけることができます。