C++ には遅延評価のネイティブ サポートがありません (Haskell のように)。
C++ で合理的な方法で遅延評価を実装できるかどうか疑問に思っています。はいの場合、どのようにしますか？
編集：コンラッド・ルドルフの答えが好きです。
たとえば、matrix_add がマトリックスに対して機能するように、T に対して本質的に機能するパラメーター化されたクラス lazy を使用するなど、より一般的な方法で実装することが可能かどうか疑問に思っています。
T に対する操作はすべて、代わりに遅延を返します。唯一の問題は、引数と操作コードを lazy 自体に格納することです。誰でもこれを改善する方法を見ることができますか?
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;
};
魔法は、からプレーンoperator matrix()への暗黙的な変換演算子であるメソッドにあります。このようにして、複数の操作を連鎖させることができます (もちろん、適切なオーバーロードを提供することにより)。評価は、最終結果がインスタンスに割り当てられたときにのみ行われます。matrix_addmatrixmatrix
編集私はもっと明示的であるべきでした。このままでは、評価は遅延して行われますが、同じ式で行われるため、このコードは意味がありません。matrix_add特に、連鎖加算を許可するように構造が変更されない限り、別の加算はこのコードを評価します。C++0x では、可変長テンプレート (つまり、可変長のテンプレート リスト) を許可することで、これが大幅に容易になります。
ただし、このコードが実際に直接的な利益をもたらす非常に単純なケースの 1 つを次に示します。
int value = (A + B)(2, 3);
ここで、AとBは 2 次元の行列であり、逆参照は Fortran 表記法で行われると仮定します。つまり、上記は行列の合計から1 つの要素を計算します。もちろん、行列全体を追加するのは無駄です。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);
}
};
他の例はたくさんあります。少し前に関連するものを実装したことを思い出しました。基本的に、事前に定義された固定のインターフェイスに準拠する文字列クラスを実装する必要がありました。ただし、私の特定の文字列クラスは、実際にはメモリに格納されていない巨大な文字列を処理していました。通常、ユーザーは function を使用して元の文字列から小さな部分文字列にアクセスするだけですinfix。文字列型のこの関数をオーバーロードして、文字列への参照を目的の開始位置と終了位置と共に保持するプロキシを返しました。この部分文字列が実際に使用された場合にのみ、文字列のこの部分を取得するために C API を照会しました。
Boost.Lambda は非常に優れていますが、 Boost.Protoはまさにあなたが探しているものです。これには、すべてのC++ 演算子のオーバーロードが既にあります。既定では、呼び出されたときに通常の機能を実行しますが、proto::eval()変更することができます。
Konrad が既に説明したことは、すべて遅延実行されるオペレーターのネストされた呼び出しをサポートするためにさらに追加できます。Konrad の例では、1 つの演算の正確に 2 つのオペランドに対して、正確に 2 つの引数を格納できる式オブジェクトがあります。問題は、 1 つの部分式のみを遅延して実行することです。これは、遅延評価の概念を簡単に説明するとうまく説明できますが、パフォーマンスは大幅に向上しません。operator()もう 1 つの例は、その式オブジェクトを使用して一部の要素のみを追加する方法をよく示しています。しかし、任意の複雑な式を評価するには、その構造も格納できるメカニズムが必要です。それを行うためにテンプレートを回避することはできません。そしてその名前は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();
}
Point 型のテンポラリを作成していないことに注意してください。多くのフィールドを持つ大きなマトリックスである可能性があります。しかし、結果が必要なときは、遅延計算します。
Konrad の投稿に追加することは何もありませんが、実際のアプリで適切に行われた遅延評価の例として、Eigenを見ることができます。それはかなり畏敬の念を起こさせるものです。
ヨハネスの答えは機能しますが、括弧が増えると、希望どおりに機能しません。ここに例があります。
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 に変換する必要があります。他より優れているものはないからです。ここに私の拡張機能があります: さらに別のオーバーロードされた演算子を追加します +
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でラムダ式によって行われるように。
何でも可能です。
それはあなたが何を意味するかによって異なります：
class X
{
public: static X& getObjectA()
{
static X instanceA;
return instanceA;
}
};
ここでは、最初の使用時に遅延評価されるグローバル変数の影響があります。
質問で新しく要求されたとおり。
そしてコンラッド・ルドルフのデザインを盗んで拡張。
Lazy オブジェクト:
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++11 では、hiapay の回答に似た遅延評価は、std::shared_future を使用して実現できます。ラムダで計算をカプセル化する必要がありますが、メモ化は処理されます。
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;
}
C ++ 0xは素晴らしいものです....しかし、現在生きている私たちにとっては、BoostラムダライブラリとBoost Phoenixがあります。どちらも、大量の関数型プログラミングを C++ に持ち込むことを目的としています。
値が必要になるまで評価されないという非常に単純な遅延評価の定義を使用すると、ポインターとマクロ (構文シュガー用) を使用してこれを実装できると言えます。
#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遅延型はアトミックにアクセスされるため、完全にスレッドセーフです。