Evaluación diferida en C++

lazy-evaluation

Question

C ++ no tiene soporte nativo para la evaluación perezosa (como lo hace Haskell).

Me pregunto si es posible implementar la evaluación diferida en C ++ de manera razonable. Si es así, ¿cómo lo harías?

EDITAR: Me gusta la respuesta de Konrad Rudolph.

Me pregunto si es posible implementarlo de una manera más genérica, por ejemplo, utilizando un perezoso de clase parametrizado que esencialmente funciona para T de la misma forma que matrix_add funciona para la matriz.

Cualquier operación en T devolvería flojo en su lugar. El único problema es almacenar los argumentos y el código de operación dentro de perezosos. ¿Alguien puede ver cómo mejorar esto?

Answer 1

C ++ 0x es agradable y todo ... pero para aquellos de nosotros que vivimos en el presente, tenemos la biblioteca Boost lambda y Boost Phoenix. Ambos con la intención de traer grandes cantidades de programación funcional a C ++.

Answer 2

Como se va a hacer en C ++ 0x , por expresiones lambda.

Answer 3

Es bastante fácil crear su propia clase de "contenedor" que toma un objeto de función de generación y expone iteradores.

Answer 4

No tengo nada que agregar a la publicación de Konrad, pero puedes mirar a Eigen para ver un ejemplo de evaluación perezosa realizada correctamente, en una aplicación del mundo real. Es bastante inspirador.

Answer 5

Boost.Lambda es muy agradable, pero Boost.Proto es exactamente lo que estás buscando. Ya tiene sobrecargas de todos los operadores de C ++, que de forma predeterminada realizan su función habitual cuando se llama a proto::eval() , pero se puede modificar.

Answer 6

Estoy pensando en implementar una clase de plantilla, que usa std::function . La clase debería, más o menos, verse así:

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;
};

Por ejemplo uso:

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();
}

El código anterior debe producir el siguiente mensaje en la consola:

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

Tenga en cuenta que el constructor que imprime Noisy(10) no se invocará hasta que se acceda a la variable.

Sin embargo, esta clase está lejos de ser perfecta. Lo primero sería que el constructor predeterminado de Value tendrá que invocarse en la inicialización del miembro (impresión de Noisy(0) en este caso). En su lugar, podemos usar el puntero para _value , pero no estoy seguro de si afectaría el rendimiento.

Answer 7

Me pregunto si es posible implementar la evaluación diferida en C ++ de manera razonable. Si es así, ¿cómo lo harías?

Sí, esto es posible y muy a menudo, por ejemplo, para cálculos matriciales. El mecanismo principal para facilitar esto es la sobrecarga del operador. Considere el caso de la adición de la matriz. La firma de la función generalmente se vería así:

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

Ahora, para hacer que esta función sea floja, es suficiente devolver un proxy en lugar del resultado real:

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

Ahora todo lo que se necesita hacer es escribir este proxy:

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;
};

La magia se encuentra en la operator matrix() método operator matrix() que es un operador de conversión implícita de matrix_add a plain matrix . De esta forma, puede encadenar múltiples operaciones (proporcionando sobrecargas apropiadas, por supuesto). La evaluación tiene lugar solo cuando el resultado final se asigna a una instancia de matrix .

EDITAR debería haber sido más explícito. Tal como están las cosas, el código no tiene sentido porque, aunque la evaluación se realiza de forma lenta, todavía ocurre en la misma expresión. En particular, otra adición evaluará este código a menos que la estructura matrix_add se cambie para permitir la adición encadenada. C ++ 0x facilita enormemente esto al permitir plantillas variadas (es decir, listas de plantillas de longitud variable).

Sin embargo, un caso muy simple en el que este código realmente tendría un beneficio real y directo es el siguiente:

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

Aquí, se supone que A y B son matrices bidimensionales y que la eliminación de referencias se realiza en notación de Fortran, es decir, lo anterior calcula un elemento a partir de una suma de matriz. Por supuesto, es un desperdicio agregar todas las matrices. matrix_add al rescate:

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);
}
};

Otros ejemplos abundan. Acabo de recordar que he implementado algo relacionado no hace mucho tiempo. Básicamente, tuve que implementar una clase de cadena que debería adherirse a una interfaz fija y predefinida. Sin embargo, mi clase de cuerda particular manejaba enormes cadenas que en realidad no estaban almacenadas en la memoria. Por lo general, el usuario simplemente accederá a pequeñas subcadenas de la cadena original utilizando un infix función. Sobrecargué esta función para mi tipo de cadena para devolver un proxy que contenía una referencia a mi cadena, junto con la posición inicial y final deseada. Solo cuando esta subcadena se usó realmente consultó una API C para recuperar esta porción de la cadena.

Answer 8

Todo es posible.

Depende de exactamente lo que quieres decir:

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

Aquí tenemos el efecto de una variable global que se evalúa perezosamente en el momento del primer uso.

Como se solicitó recientemente en la pregunta.
Y robando el diseño de Konrad Rudolph y ampliándolo.

El objeto 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;
};

Cómo usarlo:

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);
}
}

Answer 9

La respuesta de Johannes funciona. Pero cuando se trata de más paréntesis, no funciona como desees. Aquí hay un ejemplo.

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

Porque el operador + tres sobrecargado no cubrió el caso

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

Entonces el compilador tiene que convertir cualquiera (p1 + p2) o (p3 + p4) a Point, eso no es lo suficientemente flojo. Y cuando el compilador decide qué convertir, se queja. Porque ninguno es mejor que el otro. Aquí viene mi extensión: agrega otro operador sobrecargado +

 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);
}

Ahora, el compilador puede manejar el caso de arriba correctamente, y sin conversión implícita, volia!

Answer 10

Lo que Konrad ya explicó puede ampliarse para respaldar las invocaciones anidadas de los operadores, todas ejecutadas de forma perezosa. En el ejemplo de Konrad, tiene un objeto de expresión que puede almacenar exactamente dos argumentos, para exactamente dos operandos de una operación. El problema es que solo ejecutará una subexpresión de forma perezosa, lo que explica muy bien el concepto de evaluación perezosa en términos simples, pero no mejora sustancialmente el rendimiento. El otro ejemplo también muestra bien cómo se puede aplicar operator() para agregar solo algunos elementos usando ese objeto de expresión. Pero para evaluar expresiones complejas arbitrarias, necesitamos algún mecanismo que pueda almacenar la estructura de eso también. No podemos evitar las plantillas para hacer eso. Y el nombre para eso son expression templates . La idea es que un objeto de expresión con plantilla pueda almacenar la estructura de alguna sub-expresión arbitraria recursivamente, como un árbol, donde las operaciones son los nodos, y los operandos son los nodos secundarios. Para una muy buena explicación que acabo de encontrar hoy (algunos días después de que escribí el siguiente código), mira aquí .

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; }
};

Eso almacenará cualquier operación de adición, incluso anidada, como se puede ver en la siguiente definición de operador + para un tipo de punto simple:

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);
}

Ahora, si tienes

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

Ahora solo necesita sobrecargar operator = y agregar un constructor adecuado para el tipo Point y aceptar AddOp. Cambiar su definición a:

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; }
};

Y agregue los get_x y get_y apropiados en AddOp como funciones de miembro:

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

Tenga en cuenta que no hemos creado ningún temporario de tipo Point. Pudo haber sido una gran matriz con muchos campos. Pero en el momento en que se necesita el resultado, lo calculamos perezosamente .

Answer 11

En C ++ 11 se puede lograr una evaluación diferida similar a la respuesta de hiapay usando std :: shared_future. Todavía tiene que encapsular los cálculos en lambdas, pero la memorización se ocupa de:

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

Aquí hay un ejemplo completo:

#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;
}