Avaliação Preguiçosa em C ++

C ++ não tem suporte nativo para avaliação lenta (como Haskell faz).

Eu estou querendo saber se é possível implementar avaliação preguiçosa em C ++ de uma maneira razoável. Se sim, como você faria isso?

EDIT: Eu gosto da resposta de Konrad Rudolph.

Eu estou querendo saber se é possível implementá-lo de uma forma mais genérica, por exemplo, usando uma class parametrizada preguiçosa que essencialmente funciona para T a maneira matrix_add funciona para matriz.

Qualquer operação em T retornaria preguiçosa. O único problema é armazenar os argumentos e o código de operação dentro do próprio preguiçoso. Alguém pode ver como melhorar isso?

Eu estou querendo saber se é possível implementar avaliação preguiçosa em C ++ de uma maneira razoável. Se sim, como você faria isso?

Sim, isso é possível e muitas vezes feito, por exemplo, para cálculos matriciais. O principal mecanismo para facilitar isso é a sobrecarga do operador. Considere o caso da adição de matriz. A assinatura da function normalmente seria algo como isto:

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

Agora, para tornar essa function preguiçosa, basta retornar um proxy em vez do resultado real:

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

Agora tudo o que precisa ser feito é escrever 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; }; 

A mágica está na operator matrix() do método operator matrix() que é um operador de conversão implícito de matrix_add para plain matrix . Dessa forma, você pode encadear várias operações (fornecendo sobrecargas apropriadas, é claro). A avaliação ocorre somente quando o resultado final é atribuído a uma instância de matrix .

EDIT Eu deveria ter sido mais explícito. Como é, o código não faz sentido porque, embora a avaliação ocorra preguiçosamente, ainda acontece na mesma expressão. Em particular, outra adição avaliará esse código, a menos que a estrutura matrix_add seja alterada para permitir adição encadeada. C ++ 0x facilita muito isso, permitindo modelos variadic (ou seja, listas de modelo de comprimento variável).

No entanto, um caso muito simples em que esse código realmente teria um benefício real e direto é o seguinte:

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

Aqui, assume-se que A e B são matrizes bidimensionais e que a desreferenciação é feita na notação de Fortran, isto é, o acima calcula um elemento a partir de uma sum de matriz. É claro que é um desperdício adicionar as matrizes inteiras. matrix_add para o resgate:

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

Outros exemplos são abundantes. Acabei de lembrar que implementei algo relacionado há não muito tempo atrás. Basicamente, eu tive que implementar uma class de string que deveria aderir a uma interface fixa e pré-definida. No entanto, minha class de string específica lidava com strings enormes que na verdade não eram armazenadas na memory. Normalmente, o usuário apenas acessa pequenas substrings da string original usando uma function infix . Eu sobrecarreguei esta function para o meu tipo de string para retornar um proxy que continha uma referência à minha string, juntamente com a posição inicial e final desejada. Somente quando essa substring foi realmente usada, ela consultou uma API C para recuperar essa parte da string.

Boost.Lambda é muito bom, mas o Boost.Proto é exatamente o que você está procurando. Ele já possui sobrecargas de todos os operadores C ++, que por padrão executam sua function usual quando proto::eval() é chamado, mas pode ser alterado.

O que Konrad já explicou pode ser melhorado para suportar invocações aninhadas de operadores, todas executadas preguiçosamente. No exemplo de Konrad, ele possui um object de expressão que pode armazenar exatamente dois argumentos, exatamente para dois operandos de uma operação. O problema é que ele executará apenas uma subexpressão preguiçosamente, o que explica bem o conceito em avaliação preguiçosa em termos simples, mas não melhora substancialmente o desempenho. O outro exemplo mostra também como se pode aplicar operator() para adicionar apenas alguns elementos usando esse object de expressão. Mas para avaliar expressões complexas arbitrárias, precisamos de algum mecanismo que possa armazenar a estrutura disso também. Não podemos contornar modelos para fazer isso. E o nome para isso é expression templates . A ideia é que um object de expressão de modelo possa armazenar a estrutura de alguma subexpressão arbitrária recursivamente, como uma tree, em que as operações são os nós e os operandos são os nós-filhos. Para uma explicação muito boa que eu encontrei hoje (alguns dias depois que eu escrevi o código abaixo) veja aqui .

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

Isso armazenará qualquer operação de adição, mesmo aninhada, como pode ser visto pela seguinte definição de um operador + para um tipo de ponto simples:

 struct Point { int x, y; }; // add expression template with point at the right template AddOp, Point> operator+(AddOp const& lhs, Point const& p) { return AddOp, Point>(lhs, p); } // add expression template with point at the left template AddOp< Point, AddOp > operator+(Point const& p, AddOp const& rhs) { return AddOp< Point, AddOp >(p, rhs); } // add two points, yield a expression template AddOp< Point, Point > operator+(Point const& lhs, Point const& rhs) { return AddOp(lhs, rhs); } 

Agora, se você tem

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

Agora você só precisa sobrecarregar operator = e adicionar um construtor adequado para o tipo Point e aceitar AddOp. Altere sua definição para:

 struct Point { int x, y; Point(int x = 0, int y = 0):x(x), y(y) { } template Point(AddOp const& op) { x = op.get_x(); y = op.get_y(); } template Point& operator=(AddOp const& op) { x = op.get_x(); y = op.get_y(); return *this; } int get_x() const { return x; } int get_y() const { return y; } }; 

E adicione o get_x e get_y apropriados ao AddOp como funções de membro:

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

Note como não criamos nenhum temporário do tipo Point. Poderia ter sido uma grande matriz com muitos campos. Mas no momento em que o resultado é necessário, calculamos isso preguiçosamente .

Eu não tenho nada a acrescentar ao post de Konrad, mas você pode olhar para a Eigen como um exemplo de avaliação preguiçosa feita corretamente, em um aplicativo do mundo real. É muito inspirador.

Estou pensando em implementar uma class de modelo, que usa std::function . A class deve, mais ou menos, ser assim:

 template  class Lazy { public: Lazy(std::function 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 _function; Value _value; bool _evaluated; }; 

Por exemplo, 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 n = [] () { return Noisy(10); }; std::cout << "about to make noise" << std::endl; n->MakeNoise(); (*n).MakeNoise(); auto &nn = *n; nn.MakeNoise(); } 

O código acima deve produzir a seguinte mensagem no console:

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

Note que o construtor imprimindo Noisy(10) não será chamado até que a variável seja acessada.

Esta class está longe de ser perfeita, no entanto. A primeira coisa que seria o construtor padrão de Value teria que ser chamado na boot do membro (impressão Noisy(0) neste caso). Podemos usar o ponteiro para _value , mas não tenho certeza se isso afetaria o desempenho.

A resposta de Johannes funciona. Mas quando se trata de mais parênteses, não funciona como o desejo. Aqui está um exemplo.

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

Porque os três operadores + sobrecarregados não cobriram o case

 AddOp+AddOp 

Portanto, o compilador deve converter (p1 + p2) ou (p3 + p4) em Point, o que não é preguiçoso. E quando o compilador decide qual converter, ele reclama. Porque nenhum é melhor que o outro. Aqui vem o meu ramal: adicione mais um operador sobrecarregado +

  template  AddOp, AddOp> operator+(const AddOp & leftOperandconst, const AddOp & rightOperand) { return AddOp, AddOp>(leftOperandconst, rightOperand); } 

Agora, o compilador pode manipular o caso acima corretamente, e nenhuma conversão implícita, volia!

C + + 0x é bom e tudo …. mas para aqueles de nós que vivem no presente você tem biblioteca Boost lambda e Boost Phoenix. Ambos com a intenção de trazer grandes quantidades de functional programming para o C ++.

Tudo é possível.

Depende exatamente do que você quer dizer:

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

Aqui temos o efeito de uma variável global que é avaliada preguiçosamente no ponto do primeiro uso.

Conforme solicitado recentemente na pergunta.
E roubar o design de Konrad Rudolph e estendê-lo.

O object preguiçoso:

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

Como usá-lo:

 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 Lazy operator+(T1 const& lhs,T2 const& rhs) { return Lazy(lhs,rhs); } template Lazy operator-(T1 const& lhs,T2 const& rhs) { return Lazy(lhs,rhs); } } 

Como isso será feito em C ++ 0x , por expressões lambda.

Em C ++ 11, uma avaliação preguiçosa similar à resposta do hiapay pode ser obtida usando std :: shared_future. Você ainda tem que encapsular cálculos em lambdas, mas a memoização é cuidada:

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

Aqui está um exemplo completo:

 #include  #include  #define LAZY(EXPR, ...) std::async(std::launch::deferred, [__VA_ARGS__](){ std::cout << "evaluating "#EXPR << std::endl; return EXPR; }) int main() { std::shared_future f1 = LAZY(8); std::shared_future f2 = LAZY(2); std::shared_future 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; } 

É fácil criar sua própria class “contêiner”, que recebe um object de function de geração e expõe os iteradores.