•  03-07-2019
  •  | 
  •  

質問

C ++には、遅延評価のネイティブサポートがありません（Haskellにはあります）。

C ++で遅延評価を合理的な方法で実装できるかどうか疑問に思っています。はいの場合、どうしますか？

編集：Konrad Rudolphの答えが好きです。

たとえば、matrix_addがmatrixに対して機能するように、Tに対して基本的に機能するパラメータ化されたクラスlazyを使用するなど、より一般的な方法で実装できるかどうか疑問に思っています。

Tを操作すると、代わりに遅延が返されます。唯一の問題は、引数と操作コードを怠zyな内部に保存することです。誰もこれを改善する方法を見ることができますか？

役に立ちましたか？

解決

  

C ++で遅延評価を合理的な方法で実装できるかどうか疑問に思っています。はいの場合、どうしますか？

はい、これは可能であり、非常に頻繁に行われます。マトリックス計算用。これを容易にする主なメカニズムは、オペレーターのオーバーロードです。行列加算の場合を考えます。関数の署名は通常、次のようになります。

matrix operator +(matrix const& a, matrix const& b);

今、この関数を遅延させるには、実際の結果の代わりにプロキシを返すだけで十分です：

struct matrix_add;

matrix_add operator +(matrix const& a, matrix const& b) {
    return matrix_add(a, b);
}

今やるべきことはこのプロキシを書くことだけです：

struct matrix_add {
    matrix_add(matrix const& a, matrix const& b) : a(a), b(b) { }

    operator matrix() const {
        matrix result;
        // Do the addition.
        return result;
    }
private:
    matrix const& a, b;
};

魔法は、 matrix_add から単純な matrix への暗黙的な変換演算子である operator matrix（）メソッドにあります。このようにして、複数の操作を連鎖させることができます（もちろん、適切なオーバーロードを提供することにより）。評価は、最終結果が matrix インスタンスに割り当てられた場合にのみ行われます。

編集より明確にすべきでした。そのままでは、評価は遅延して行われますが、同じ式で行われるため、コードは意味がありません。特に、 matrix_add 構造が連鎖追加を許可するように変更されない限り、別の追加がこのコードを評価します。 C ++ 0xは、可変長テンプレート（つまり、可変長のテンプレートリスト）を許可することにより、これを非常に容易にします。

ただし、このコードが実際に直接的なメリットをもたらす非常に単純なケースは次のとおりです。

int value = (A + B)(2, 3);

ここでは、 A と B は2次元行列であり、逆参照はFortran表記法で行われる、つまり上記では one 要素。もちろん、マトリックス全体を追加するのは無駄です。 matrix_add の助け：

struct matrix_add {
    // … yadda, yadda, yadda …

    int operator ()(unsigned int x, unsigned int y) {
        // Calculate *just one* element:
        return a(x, y) + b(x, y);
    }
};

他の例もたくさんあります。少し前に関連するものを実装したことを思い出しました。基本的に、固定の事前定義されたインターフェイスに準拠する文字列クラスを実装する必要がありました。ただし、特定の文字列クラスは、実際にはメモリに保存されていない巨大な文字列を処理しました。通常、ユーザーは関数 infix を使用して、元の文字列から小さな部分文字列にアクセスするだけです。文字列型のこの関数をオーバーロードして、文字列への参照を保持するプロキシを、目的の開始位置と終了位置とともに返すようにしました。この部分文字列が実際に使用されたときのみ、C APIにクエリを実行して文字列のこの部分を取得しました。

他のヒント

Boost.Lambdaは非常に優れていますが、 Boost.Proto は、まさにあなたが探しているものです。既に all C ++演算子のオーバーロードがあり、デフォルトでは proto :: eval（）が呼び出されたときに通常の機能を実行しますが、変更できます。

コンラッドがすでに説明したことをさらに入れて、すべての演算子が遅延して実行されるネストされた呼び出しをサポートできます。 Konradの例では、1つの操作の2つのオペランドに対して、2つの引数を正確に格納できる式オブジェクトがあります。問題は、 one 部分式を遅延して実行するだけであるため、単純な用語で言えば遅延評価の概念をうまく説明できますが、パフォーマンスは大幅には向上しません。他の例は、 operator（）を適用して、その式オブジェクトを使用して一部の要素のみを追加する方法も示しています。しかし、任意の複雑な式を評価するには、その構造も保存できるメカニズムが必要です。そのためにテンプレートを回避することはできません。そしてその名前は expression templates です。アイデアは、テンプレート化された1つの式オブジェクトが、操作がノードで、オペランドが子ノードであるツリーのような任意のサブ式の構造を再帰的に格納できるということです。今日見つけた非常に良い説明については（以下のコードを書いてから数日後）こちら。

template<typename Lhs, typename Rhs>
struct AddOp {
    Lhs const& lhs;
    Rhs const& rhs;

    AddOp(Lhs const& lhs, Rhs const& rhs):lhs(lhs), rhs(rhs) {
        // empty body
    }

    Lhs const& get_lhs() const { return lhs; }
    Rhs const& get_rhs() const { return rhs; }
};

これは、次の単純なポイントタイプのoperator +の定義からわかるように、追加操作（ネストされた操作も含む）を格納します。

struct Point { int x, y; };

// add expression template with point at the right
template<typename Lhs, typename Rhs> AddOp<AddOp<Lhs, Rhs>, Point> 
operator+(AddOp<Lhs, Rhs> const& lhs, Point const& p) {
    return AddOp<AddOp<Lhs, Rhs>, Point>(lhs, p);
} 

// add expression template with point at the left
template<typename Lhs, typename Rhs> AddOp< Point, AddOp<Lhs, Rhs> > 
operator+(Point const& p, AddOp<Lhs, Rhs> const& rhs) {
    return AddOp< Point, AddOp<Lhs, Rhs> >(p, rhs);
}

// add two points, yield a expression template    
AddOp< Point, Point > 
operator+(Point const& lhs, Point const& rhs) {
    return AddOp<Point, Point>(lhs, rhs);
}

今、お持ちの場合

Point p1 = { 1, 2 }, p2 = { 3, 4 }, p3 = { 5, 6 };
p1 + (p2 + p3); // returns AddOp< Point, AddOp<Point, Point> >

ここで、operator =をオーバーロードし、Pointタイプに適切なコンストラクターを追加して、AddOpを受け入れるだけです。定義を次のように変更します。

struct Point { 
    int x, y; 

    Point(int x = 0, int y = 0):x(x), y(y) { }

    template<typename Lhs, typename Rhs>
    Point(AddOp<Lhs, Rhs> const& op) {
        x = op.get_x();
        y = op.get_y();
    }

    template<typename Lhs, typename Rhs>
    Point& operator=(AddOp<Lhs, Rhs> const& op) {
        x = op.get_x();
        y = op.get_y();
        return *this;
    }

    int get_x() const { return x; }
    int get_y() const { return y; }
};

そして、適切なget_xおよびget_yをメンバー関数としてAddOpに追加します。

int get_x() const {
    return lhs.get_x() + rhs.get_x();
}

int get_y() const {
    return lhs.get_y() + rhs.get_y();
}

ポイント型の一時ファイルを作成していないことに注意してください。それは多くのフィールドを持つ大きな行列であったかもしれません。しかし、結果が必要なときに、怠emに計算します。

std :: function を使用するテンプレートクラスの実装を考えています。クラスは多かれ少なかれ、次のようになります。

template <typename Value>
class Lazy
{
public:
    Lazy(std::function<Value()> function) : _function(function), _evaluated(false) {}

    Value &operator*()  { Evaluate(); return  _value; }
    Value *operator->() { Evaluate(); return &_value; }

private:
    void Evaluate()
    {
        if (!_evaluated)
        {
            _value = _function();
            _evaluated = true;
        }
    }

    std::function<Value()> _function;
    Value _value;
    bool _evaluated;
};

使用例：

class Noisy
{
public:
    Noisy(int i = 0) : _i(i)
    {
        std::cout << "Noisy(" << _i << ")"  << std::endl;
    }
    Noisy(const Noisy &that) : _i(that._i)
    {
        std::cout << "Noisy(const Noisy &)" << std::endl;
    }
    ~Noisy()
    {
        std::cout << "~Noisy(" << _i << ")" << std::endl;
    }

    void MakeNoise()
    {
        std::cout << "MakeNoise(" << _i << ")" << std::endl;
    }
private:
    int _i;
};  

int main()
{
    Lazy<Noisy> n = [] () { return Noisy(10); };

    std::cout << "about to make noise" << std::endl;

    n->MakeNoise();
    (*n).MakeNoise();
    auto &nn = *n;
    nn.MakeNoise();
}

上記のコードは、コンソールに次のメッセージを生成するはずです：

Noisy(0)
about to make noise
Noisy(10)
~Noisy(10)
MakeNoise(10)
MakeNoise(10)
MakeNoise(10)
~Noisy(10)

Noisy（10）を出力するコンストラクターは、変数にアクセスするまで呼び出されないことに注意してください。

ただし、このクラスは完璧にはほど遠いです。最初のことは、メンバーの初期化時に Value のデフォルトコンストラクターを呼び出す必要があることです（この場合は Noisy（0）を出力します）。代わりに _value にポインターを使用できますが、パフォーマンスに影響するかどうかはわかりません。

ヨハネスの答えは機能しますが、括弧の数が増えると、期待どおりに機能しません。以下に例を示します。

Point p1 = { 1, 2 }, p2 = { 3, 4 }, p3 = { 5, 6 }, p4 = { 7, 8 };
(p1 + p2) + (p3+p4)// it works ,but not lazy enough

3つのオーバーロードされた+演算子がケースをカバーしなかったため

AddOp<Llhs,Lrhs>+AddOp<Rlhs,Rrhs>

したがって、コンパイラーは（p1 + p2）または（p3 + p4）のいずれかをPointに変換する必要がありますが、これは十分に怠notではありません。なぜなら他のものより良いものはないからです。 ここに私の拡張機能があります：オーバーロードされた演算子をもう1つ追加します+ 

    template <typename LLhs, typename LRhs, typename RLhs, typename RRhs>
AddOp<AddOp<LLhs, LRhs>, AddOp<RLhs, RRhs>> operator+(const AddOp<LLhs, LRhs> & leftOperandconst, const AddOp<RLhs, RRhs> & rightOperand)
{
    return  AddOp<AddOp<LLhs, LRhs>, AddOp<RLhs, RRhs>>(leftOperandconst, rightOperand);

}

現在、コンパイラは上記のケースを正しく処理でき、暗黙の変換はありません、volia！

C ++ 0xはすべてが素晴らしく、...。しかし、現在の私たちにとっては、Boost lambdaライブラリとBoost Phoenixがあります。両方とも、大量の関数型プログラミングをC ++にもたらすことを目的としています。

何でも可能です。

それはあなたが何を意味するかによって異なります：

class X
{
     public: static X& getObjectA()
     {
          static X instanceA;

          return instanceA;
     }
};

ここでは、最初の使用時に遅延評価されるグローバル変数の影響があります。

質問で新たにリクエストされたとおり。
Konrad Rudolphのデザインを盗んで拡張します。

遅延オブジェクト：

template<typename O,typename T1,typename T2>
struct Lazy
{
    Lazy(T1 const& l,T2 const& r)
        :lhs(l),rhs(r) {}

    typedef typename O::Result  Result;
    operator Result() const
    {
        O   op;
        return op(lhs,rhs);
    }
    private:
        T1 const&   lhs;
        T2 const&   rhs;
};

使用方法：

namespace M
{
    class Matrix
    {
    };
    struct MatrixAdd
    {
        typedef Matrix  Result;
        Result operator()(Matrix const& lhs,Matrix const& rhs) const
        {
            Result  r;
            return r;
        }
    };
    struct MatrixSub
    {
        typedef Matrix  Result;
        Result operator()(Matrix const& lhs,Matrix const& rhs) const
        {
            Result  r;
            return r;
        }
    };
    template<typename T1,typename T2>
    Lazy<MatrixAdd,T1,T2> operator+(T1 const& lhs,T2 const& rhs)
    {
        return Lazy<MatrixAdd,T1,T2>(lhs,rhs);
    }
    template<typename T1,typename T2>
    Lazy<MatrixSub,T1,T2> operator-(T1 const& lhs,T2 const& rhs)
    {
        return Lazy<MatrixSub,T1,T2>(lhs,rhs);
    }
}

C ++ 0x で行われます、ラムダ式による。

C ++ 11では、stap :: shared_futureを使用して、hiapayの答えに似た遅延評価を実現できます。計算をラムダでカプセル化する必要がありますが、メモ化は次のように処理されます。

std::shared_future<int> a = std::async(std::launch::deferred, [](){ return 1+1; });

完全な例は次のとおりです。

#include <iostream>
#include <future>

#define LAZY(EXPR, ...) std::async(std::launch::deferred, [__VA_ARGS__](){ std::cout << "evaluating "#EXPR << std::endl; return EXPR; })

int main() {
    std::shared_future<int> f1 = LAZY(8);
    std::shared_future<int> f2 = LAZY(2);
    std::shared_future<int> f3 = LAZY(f1.get() * f2.get(), f1, f2);

    std::cout << "f3 = " << f3.get() << std::endl;
    std::cout << "f2 = " << f2.get() << std::endl;
    std::cout << "f1 = " << f1.get() << std::endl;
    return 0;
}

Haskellを私たちのインスピレーションとしてとらえましょう-それはコアに対して怠beingです。 また、C＃のLinqがどのようにEnumeratorsをモナド的な方法で使用するかを念頭に置いてみましょう（これは単語です-ごめんなさい）。 最後に、プログラマーに提供するコルーチンが何であるかを念頭に置いてください。つまり、計算ステップ（生産者と消費者など）の相互分離です。 そして、コルーチンが遅延評価にどのように関係するかを考えてみましょう。

上記のすべては何らかの形で関連しているようです。

次に、「怠lazな」ものの個人的な定義を抽出してみましょう。になります。

1つの解釈は次のとおりです。計算を実行可能な前に、構成可能な方法で記述したい。 完全なソリューションを構成するために使用する一部のパーツは、巨大な（場合によっては無限の）データソースを非常によく利用し、完全な計算でも有限または無限の結果を生成します。

具体化して、いくつかのコードを作成します。そのための例が必要です！ここでは、fizzbuzz「問題」を選択します。例として、それに対するいくつかの素晴らしい、怠zyな解決策があるという理由だけのために。

Haskellでは、次のようになります。     

module FizzBuzz
( fb
)
where
fb n =
    fmap merge fizzBuzzAndNumbers
    where
        fizz = cycle ["","","fizz"]
        buzz = cycle ["","","","","buzz"]
        fizzBuzz = zipWith (++) fizz buzz
        fizzBuzzAndNumbers = zip [1..n] fizzBuzz
        merge (x,s) = if length s == 0 then show x else s

Haskell関数 cycle は、有限リスト内の値を永久に繰り返すことにより、有限リストから無限リスト（もちろん遅延）を作成します。熱心なプログラミングスタイルでは、そのようなものを書くと警告音が鳴ります（メモリオーバーフロー、無限ループ！）。しかし、怠zyな言語ではそうではありません。秘trickは、遅延リストはすぐには計算されないということです。たぶん決して。通常、後続のコードで必要な場合のみ。

上の where ブロックの3行目は、別の遅延を作成します!!リスト、無限のリスト fizz と buzz を、単一の2要素レシピ＆quot;いずれかの入力リストの文字列要素を単一の文字列に連結する＆quot;を組み合わせて組み合わせます。繰り返しますが、これをすぐに評価する場合、コンピューターのリソースがなくなるまで待つ必要があります。

4行目では、無限レイジーリスト fizzbuzz を使用して、有限レイジーリスト [1..n] のメンバーのタプルを作成します。結果はまだ怠laです。

fb 関数の本体でも、熱心になる必要はありません。関数全体がソリューションを含むリストを返しますが、それ自体もまた怠laです。 fb 50 の結果は、後で（部分的に）評価できる計算と考えることもできます。または、他のものと組み合わせて、さらに大きな（遅延）評価を導きます。

したがって、「fizzbuzz」のC ++バージョンを開始するには、必要に応じて各ステップのデータを前のステップから描画して、計算の部分的なステップをより大きな計算のビットに結合する方法を考える必要があります。

私の要点で詳細をご覧いただけます。

コードの背後にある基本的な考え方：

C＃とLinqから借用して、「発明」します。ステートフルなジェネリック型 Enumerator で、
  -部分計算の現在の値
  -部分的な計算の状態（したがって、後続の値を生成できます）
  -次の状態、次の値、さらにデータがあるか、列挙が終了したかどうかを示すブール値を生成するワーカー関数。

。（ドット）の力を使用して Enumerator＆lt; T、S＆gt; インスタンスを作成できるように、このクラスには借用した関数も含まれています Functor や Applicative などのHaskell型クラスから。

列挙子のワーカー関数は、常に次の形式です： S-＆gt; std :: tuple＆lt; bool、S、T S は状態を表すジェネリック型変数で、 T は遺伝子です

遅延評価の非常に簡単な定義を使用すると、値は必要になるまで評価されないため、ポインターとマクロ（構文シュガー用）を使用してこれを実装できます。

#include <stdatomic.h>

#define lazy(var_type) lazy_ ## var_type

#define def_lazy_type( var_type ) \
    typedef _Atomic var_type _atomic_ ## var_type; \
    typedef _atomic_ ## var_type * lazy(var_type);  //pointer to atomic type

#define def_lazy_variable(var_type, var_name ) \
    _atomic_ ## var_type _ ## var_name; \
    lazy_ ## var_type var_name = & _ ## var_name;

#define assign_lazy( var_name, val ) atomic_store( & _ ## var_name, val )
#define eval_lazy(var_name) atomic_load( &(*var_name) )

#include <stdio.h>

def_lazy_type(int)

void print_power2 ( lazy(int) i )
{
      printf( "%d\n", eval_lazy(i) * eval_lazy(i) );
}

typedef struct {
    int a;
} simple;

def_lazy_type(simple)

void print_simple ( lazy(simple) s )
{
    simple temp = eval_lazy(s);
    printf("%d\n", temp.a );
}


#define def_lazy_array1( var_type, nElements, var_name ) \
    _atomic_ ## var_type  _ ## var_name [ nElements ]; \
    lazy(var_type) var_name = _ ## var_name; 

int main ( )
{
    //declarations
    def_lazy_variable( int, X )
    def_lazy_variable( simple, Y)
    def_lazy_array1(int,10,Z)
    simple new_simple;

    //first the lazy int
    assign_lazy(X,111);
    print_power2(X);

    //second the lazy struct
    new_simple.a = 555;
    assign_lazy(Y,new_simple);
    print_simple ( Y );

    //third the array of lazy ints
    for(int i=0; i < 10; i++)
    {
        assign_lazy( Z[i], i );
    }

    for(int i=0; i < 10; i++)
    {
        int r = eval_lazy( &Z[i] ); //must pass with &
        printf("%d\n", r );
    }

    return 0;
}

関数 print_power2 には、 eval_lazy というマクロがあり、実際に必要になる直前に値を取得するためにポインターを逆参照するだけです。 。遅延型はアトミックにアクセスされるため、完全にスレッドセーフです。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top