BLOG C++

Expressões Lambda

Para criarmos uma expressão que retorne um functor iremos usar templates. Para isso precisaremos redefinir todos os operadores – aritméticos, lógicos, relacionais etc. Por exemplo, para podermos escrever uma expressão “2*x + 1” precisamos redefinir “*” e “+”. No entanto, embora possamos redefinir “*” para Var e int, o operador “+” precisa ser redefinido para o functor retornado por “2*x” e int. Como a princípio a expressão do lado esquerdo pode ser qualquer coisa (a do lado direito também), não temos como saber a priori qual o seu tipo. Por outro lado, não podemos redefinir o operador “+” para tipos genéricos sob o risco de fazer parar de funcionar outras templates. Assim, precisamos distinguir o que é uma expressão lambda de outros tipos do programa. A melhor forma de fazer isso é criar uma template Lambda que apenas encapsula um functor qualquer, e redefine o operador “()” para um parâmetro qualquer. Pensando dessa forma, a própria variável x pode ser do tipo Lambda, sob a forma de especialização de templates. O tipo Lambda será então apenas um envelope para expressões/functores, repassando para a expressão/functor a tarefa de executar a operação desejada.

template <class Functor>
struct Lambda {
  const Functor f;

  Lambda( const Functor& f ): f(f) {}

  template <class T>
  T operator()( const T& x ) const { return f( x ); }
};

struct Var {
  template <class T>
  T operator()( const T& x ) const { return x; }
};

template <>
struct Lambda< Var > {
  Var f;

  template <class T>
  T operator()( const T& x ) const { return x; }
};

typedef Lambda< Var > ParamX;

ParamX x;

Assim podemos redefinir os operadores para atuarem apenas em tipos Lambda< T >.

Para podermos encadear os operadores devemos primeiro transformá-los em functores com uma interface única, de modo que a chamada a um operador possa ser capturada em uma template (a STL usa essa técnica). Para tanto, criaremos uma struct com uma template para uma função estática (que pode ser chamada sem um objeto) que recebe dois parâmetros e retorna a aplicação do operador a estes parâmetros.

struct Adicao {
  template <class A, class B>
  static A aplica( A a, B b ) { return a + b; }
};

struct Multiplicacao {
  template <class A, class B>
  static A aplica( A a, B b ) { return a * b; }
};

struct Subtracao {
  template <class A, class B>
  static A aplica( A a, B b ) { return a - b; }
};

struct Divisao {
  template <class A, class B>
  static A aplica( A a, B b ) { return a / b; }
};

Dessa forma, com uma única template, que chamaremos de Oper, podemos encadear os operadores:

template <class O, class A, class B>
class Oper {
    private:
      const A a;
      const B b;

    public:
      Oper( const A& a, const B& b ): a(a), b(b) {}

      template <class T>
      T operator()( const T& x ) const { return O::aplica( a(x), b(x) ); }
};

Essa template possui dois campos, a e b, que são eles mesmos functores – e é exatamente isso que irá permitir que uma expressão seja representada por functores encadeados. Por exemplo, para representar x + x podemos escrever o seguinte código:

int main(int argc, char *argv[]) {
  Oper< Adicao, ParamX, ParamX > expr( x, x );

  cout << expr( 10 ) << endl;

  return EXIT_SUCCESS;
}

Esse código produz como saída 20. Mas o que queremos é poder realmente escrever x + x. Para tanto basta escrever uma template para o operador + com parâmetros Lambda< T >.

template <class A, class B>
inline Lambda< Oper< Adicao, A, B > > operator + ( const Lambda<A>& a, const Lambda<B>& b ) {
  return Oper< Adicao, A, B  >( a.f, b.f );
}

template <class A, class B>
inline Lambda< Oper< Multiplicacao, A, B > > operator * ( const Lambda<A>& a, const Lambda<B>& b ) {
  return Oper< Multiplicacao, A, B  >( a.f, b.f );
}

template <class A, class B>
inline Lambda< Oper< Subtracao, A, B > > operator - ( const Lambda<A>& a, const Lambda<B>& b ) {
  return Oper< Subtracao, A, B  >( a.f, b.f );
}

template <class A, class B>
inline Lambda< Oper< Divisao, A, B > > operator / ( const Lambda<A>& a, const Lambda<B>& b ) {
  return Oper< Divisao, A, B  >( a.f, b.f );
}

Com isso podemos já escrever uma expressão mais complexa, como por exemplo x*x + x.

Para um mínimo de funcionalidade, precisamos lidar com constantes nas expressões lambda. Para tanto precisamos de uma classe que guarde o valor de uma constante de qualquer tipo e funcione como um functor para um parâmetro, retornando o valor dessa constante qualquer que seja o valor desse parâmetro. Além disso, precisamos de templates para os operadores lidarem com constantes e variáveis, para todos os operadores (abaixo fizemos apenas para “+”).

template <class C>
class Constante {
  private:
    const C n;

  public:
    Constante( const C& n ): n(n) {}

    template <class T>
    C operator()( const T& ) const { return n; }
};

template <class A, class B>
inline Lambda< Oper< Adicao, A, Constante<B> > > operator + ( const Lambda<A>& a, const B& b ) {
  return Oper< Adicao, A, Constante<B> >( a.f, b );
}

template <class A, class B>
inline Lambda< Oper< Adicao, Constante<B>, A > > operator + ( const A& a, const Lambda<B>& b ) {
  return Oper< Adicao, Constante<B>, A >( a, b.f );
}

Assim, já podemos escrever o seguinte código passando uma expressão lambda para uma função:

template <class Functor>
void imprime( int a, int b, Functor f ) {
  for( int i = a; i <= b; i++ )
    cout << f(i) << " ";

  cout << endl;
}

int main(int argc, char *argv[]) {
  imprime( 0, 10, x*x + x + 1 );

  return EXIT_SUCCESS;
}

Esse programa produz como saída o seguinte: 1 3 7 13 21 31 43 57 73 91 111

Na Parte 3 dessa série veremos como lidar com atribuições. Nesse link aqui você pode baixar o código completo desse post.

“I left alone my mind was blank/I needed time to think to get the memories from my mind”

Criando funções on-the-fly

Expressões lambda e cálculo lambda são abstrações muito utilizadas em teoria da computação. E são uma ótima forma de se definir funções on-the-fly, ou seja, no meio do código. Aqui vou mostrar uma pequena introdução sobre como fazer isso em C++, e em outros posts irei aperfeiçoar a idéia. Na biblioteca Boost existe uma boa implementação de expressões lambda, mas ela é pouco didática para se estudar. Melhor a gente ter uma idéia de como implementar primeiro e depois usar a biblioteca.

Um exemplo de uma expressão lambda é dado a seguir:

λxy.x+y
(λxy.x+y)( 2, 4 )

Na linha 1 está uma expressão que define uma função (sem nome e sem tipos) que recebe dois parâmetros x e y e retorna a soma deles. A idéia central aqui é função sem nome e sem tipos. Na linha 2 essa expressão é avaliada para os argumentos 2 e 4, do tipo int, retornando 6.

A principal utilidade de expressões lambda é para substituir functores nas funções da STL, por exemplo for_each, permitindo que a função a ser passada como parâmetro seja definida on-the-fly. As vantagens desse tipo de definição são duas: a definição da função fica perto do seu uso, e desempenho, pois tudo é expandido inline.

Para se criar expressões lambda em C++ podemos fazer algumas simplificações. A primeira delas é abolir a letra λ e a segunda é fixar os nomes dos parâmetros. Nessa primeira parte do post, irei criar apenas expressões lambda de um parâmetro, que se chamará x. Além disso, as expressões lambda não terão tipo – o que nos indica que serão templates. Uma expressão lambda “x + 1″ deve retornar um functor que soma 1 ao argumento passado na chamada dele. Assim, (x + 1)( 10 ) deve retornar 11. O código a seguir ilustra onde queremos chegar.

#include <iostream>
#include <vector>
#include <lambda>

using namespace std;

struct Imprime {
  ostream& o;

  Imprime( ostream& o ): o(o) {}

  template <class T>
  void operator () ( T n ) {
    o << n << " ";
  }
};

int main(int argc, char *argv[]) {
  vector<int> a;

  a.push_back( 1 );
  a.push_back( 2 );
  a.push_back( 3 );
  a.push_back( 4 );
  a.push_back( 5 );

  for_each( a.begin(), a.end(), x = x*x+1 );

  for_each( a.begin(), a.end(), Imprime( cout ) );
}

Saída:

2 5 10 17 26

A expressão “x = x*x+1” retornou um functor que calcula esse valor, e ele foi passado como parâmetro para a função for_each, produzindo o efeito desejado nos elementos do vetor. O functor Imprime na verdade não está ali por acaso: ele servirá de idéia base para a construção de expressões lambda. Seu operador de chamada de função é uma template, e pode ser utilizado para qualquer tipo que possa ser passado para um ostream através do operador “<<”. Ou seja, ele é um functor que encapsula a expressão cout << x << ” “.

Se fizermos um operador “<<” para ostream e um tipo novo para representar x (Var por exemplo) e se esse operador ao invés de imprimir retornar um objeto do tipo Imprime, poderemos criar uma expressão lambda.

Primeira Expressão Lambda:

#include <iostream>
#include <vector>
#include <lambda>

using namespace std;

struct Imprime {
  ostream& o;

  Imprime( ostream& o ): o(o) {}

  template <class T>
  void operator () ( T n ) {
    o << n << " ";
  }
};

struct Var {};
Var x;

Imprime operator << ( ostream& o, Var ) {
  return Imprime( o );
}

int main(int argc, char *argv[]) {
  vector<int> a;

  a.push_back( 1 );
  a.push_back( 2 );
  a.push_back( 3 );
  a.push_back( 4 );
  a.push_back( 5 );

  for_each( a.begin(), a.end(), x = x*x+1 );

  for_each( a.begin(), a.end(), cout << x );
}

É essa a idéia central: representar através de functores sem tipo as operações que compõem uma expressão lambda. A expressão é montada através de operadores
redefinidos, conforme podemos ver nas linhas 21 e 36.

No próximo post, mostro como encadear as expressões.

“Se a experiência funcionou na primeira tentativa, tem algo errado.”

Adiando a definição de uma template interna a uma classe template

Às vezes devido às dependências do código precisamos adiar a definição de uma template até um determinado ponto do programa fonte – por exemplo se no código dessa template for necessário uma declaração feita mais a frente. Outro motivo seria simplesmente manter a declaração da classe pequena, deixando a definição em outra parte do código – sem contar que qualquer declaração dentro de uma classe será automaticamente considerada inline sempre que possível.

A sintaxe para isto é estranha. Veja os trechos de código a seguir.

Declaração:

#include <cstdlib>
#include <iostream>
#include <string>

using namespace std;

template <class T>
class Estado {
  private:
    string nome;
    T t;

  public:
    Estado( string nome );

    template <class U> class Municipio {
      private:
        string nome;

      public:
        Municipio( string nome );

        int praias();

        template <class V> void hotel( V v );
    };

    template <class W> void cobertura( W w );

};

A classe Estado é uma template com um construtor e um método template (cobertura), e a classe Municipio é uma template interna à classe Estado, e possui um método comum (praias) e um outro método template (hotel). O método hotel depende de três parâmetros template: T, U e V.

Não há mistério na definição fora da classe do construtor Estado. A coisa começa a ficar estranha para o método cobertura, pois este precisa de dois parâmetros.

template <class T>
Estado<T>::Estado( string nome ): nome(nome), t(0) {
  // Um código qualquer aqui
}

template <class T, class W>
void Estado<T>::cobertura( W w ) {
  t = w;
  // Um código qualquer aqui
}

A saída para esta compilação é:

38 main.cpp: prototype for `void Estado<T>::cobertura(W)' does not match any in class `Estado<T>'
38 main.cpp: template<class T> template<class W> void Estado::cobertura(W)
38 main.cpp: template definition of non-template `void Estado<T>::cobertura(W)'
[Build Error] [main.o] Error 1

A linha 2  já nos indica qual a solução: template <class T> template<class W>

A sintaxe para a declaração de templates aninhadas é essa. Com qualquer nível de aninhamento. Assim, o código final para a declaração das templates externamente à classe é mostrado a seguir.

Código final:

#include <cstdlib>
#include <iostream>
#include <string>

using namespace std;

template <class T>
class Estado {
  private:
    string nome;
    T t;

  public:
    Estado( string nome );

    template <class U> class Municipio {
      private:
        string nome;

      public:
        Municipio( string nome );

        int praias();

        template <class V> void hotel( V v );
    };

    template <class W> void cobertura( W w );

};

template <class T>
Estado<T>::Estado( string nome ): nome(nome), t(0) {
  // Um código qualquer aqui
}

template <class T> template <class W>
void Estado<T>::cobertura( W w ) {
  t = w;
  // Um código qualquer aqui
}

template <class T> template <class U>
Estado<T>::Municipio<U>::Municipio( string nome ): nome(nome) {
  // Um código qualquer aqui
}

template <class T> template <class U>
int Estado<T>::Municipio<U>::praias() {
  // Um código qualquer aqui
  return 0;
}

template <class T> template <class U> template <class V>
inline void Estado<T>::Municipio<U>::hotel( V v ) {
  // Um código qualquer aqui
}

int main(int argc, char *argv[])
{
  Estado<int> rio("Rio de Janeiro");
  Estado<int>::Municipio<double> buzios("Búzios");

  rio.cobertura( 4 );
  buzios.hotel( 5 );
  cout << buzios.praias() << endl;

  return EXIT_SUCCESS;
}

Dessa forma, além de podermos contornar as possíveis dependências do código também podemos manter a declaração de uma classe template enxuta – sem comprometer o desempenho, pois nada impede que usemos a opção inline (linha 55).

“All the world’s a stage…”

Soluções simples quase sempre são as melhores

Outro dia estava com um problema onde precisa de um map que pudesse ser indexado por mais de um tipo de dado diferente. Chamei isso de map heterogêneo.

Pra quem não sabe, a template map da stl recebe dois tipos de dados e faz um dicionário. A hash_map faz a mesma coisa, porém mais rápido – mas o meu principal problema não era velocidade.

Exemplo de uso da map em C++

#include <iostream>
#include <map>

using namespace std;

int main(int argc, char *argv[])
{
  map<string,int> dic;

  dic["abacate"] = 3;
  dic["maçã"] = 2;

  cout << dic["abacate"] << endl;
  cout << dic["maçã"] << endl;
  cout << dic["banana"] << endl;

  return 0;
}

(Gostei dessa formatação acima!)

O caso é que o tipo do índice do map tem de ser um só, e eu queria misturar int, double, char* e string. Lógico que poderia usar quatro maps diferentes, mas isso significaria passar quatro parâmetros a mais para várias funções. Antes de partir pra fazer uma classe com quatro maps diferentes (ou mais, veio logo essa dúvida!) e sobrecarregar o operador [], me ocorreu a seguinte idéia: e se um campo membro da classe pudesse ser template? Bom, isso não funciona – apenas métodos podem ser templates. Mas consegui um workaround que, se não é a coisa mais linda nem eficiente do mundo, resolveu bem o problema com um mínimo de esforço.

Um método pode ser template, e um método pode ter uma variável local do tipo do parâmetro da template. O problema é que uma variável local morre quando se sai do método. Mas e se essa variável fosse estática? Nesse caso surgiria outro problema – teria apenas uma instância da variável para todos os objetos da classe. O código abaixo ilustra isso.

Versão 0.1 da solução para map heterogêneo

#include <iostream>
#include <map>

using namespace std;

template <class T>
struct Map {
  template <class I>
  int& operator [] ( I i ) {
    static map<I,int> m;

    return m[i];
  }
};

int main(int argc, char *argv[])
{
  Map<int> dic, outroDic;

  dic["abacate"] = 3;
  dic["maçã"] = 2;
  dic[0] = 1;
  dic[0.0] = 5;

  cout << dic["abacate"] << endl;
  cout << outroDic["maçã"] << endl;
  cout << dic["banana"] << endl;
  cout << dic[0] << endl;
  cout << dic[0.0] << endl;

  return 0;
}

Saída:

3
2
0
1
5

Na linha 26, embora esteja usando a variável outroDic, o resultado não foi zero: as duas variáveis, dic e outroDic, copartilham o mesmo map, pois ele é estático. Daí veio a seguinte idéia: e se tivesse um map para o próprio objeto, ou seja, this? Bingo! resolvido o problema (já disse, é apenas uma solução simples – para ser eficiente teria de usar hash_map, e para ser elegante… bem, aí é outra estória…).

Versão 0.2 da solução para map heterogêneo

#include <iostream>
#include <map>

using namespace std;

template <class T>
struct Map {
  template <class I>
  int& operator [] ( I i ) {
    static map<Map*, map<I,int> > m;

    return m[this][i];
  }
};

int main(int argc, char *argv[])
{
  Map<int> dic, outroDic;

  dic["abacate"] = 3;
  dic["maçã"] = 2;
  dic[0] = 1;
  dic[0.0] = 5;

  cout << dic["abacate"] << endl;
  cout << outroDic["maçã"] << endl;
  cout << dic["banana"] << endl;
  cout << dic[0] << endl;
  cout << dic[0.0] << endl;

  return 0;
}

Saída:

3
0
0
1
5

Dessa vez a linha 26 corretamente produziu zero como saída, pois o dado foi armazenado associado ao ponteiro this, ou seja, ao próprio objeto. O que me deixou surpreso e satisfeito foi realmente a simplicidade da solução – apenas 6 linhas de código. E muito fácil de adaptar para hash_map para não ficar tão ineficiente…

Resolvi o meu problema imediato. Mas é a versão 0.2 ainda porque não tem iteradores… não parei ainda para pensar em uma forma de fazer um iterador único para cada variável, na verdade me ocorreu que somente seria possível ter um iterador para cada tipo de índice por causa do campo first. Uma pena… mas pelo menos para o meu problema o código acima já serve.

E para quem for mais atento, falta um destrutor para remover da variável estática m (linha 10) os Maps locais quando eles forem destruídos… é, talvez versão 0.2–

“Veni, vidi, vici”

Esse é o verdadeiro Fibonacci em C++…

Lógico que no post anterior sobre o desempenho do Java o objetivo não era calcular Fibonacci, mas mostrar que em chamadas recursivas o otimizador do Java leva a melhor. Uma implementação de Fibonacci em C++ usando este algoritmo recursivo,  sem passar para outros algoritmos mais óbvios como manter os dois últimos valores ou somar em um vetor, deve usar uma característica funcional da linguagem C++: a metaprogramação.

Este é o primeiro  post sobre metaprogramação que faço, mas é o exemplo clássico, muito simples e que causa um impacto enorme…

#include <iostream>;

using namespace std;

template<int n>
struct Fib {
  enum X { value = Fib<n-1>::value + Fib<n-2>::value };
};
template <>
struct Fib<1> {
  enum X { value = 1 };
};

template <>
struct Fib<0> {
  enum X { value = 0 };
};

int main(int argc, char *argv[]) {
  cout << Fib<45>::value << endl;
  return 0;
}

Tempo de execução: 0.01 segundo!

Às vezes 0.00 segundo (o sistema não conseguiu medir…). E o tempo de compilação foi normal, 0.58 segundos. Bom, esse programa não é genérico o suficiente para calcular para n, apenas para uma constante conhecida a tempo de compilação. Mas é um recurso do C++, e a gente programa em C++ para usar todos os recursos que a linguagem oferece.  É rápido por que é calculado em tempo de compilação. Não torna a compilação mais lenta pois o compilador instancia Fib<x> apenas uma vez e reaproveita o valor nas vezes seguintes.

Mas também é possível fazer um Fibonacci recursivo para qualquer n mesmo que ele não seja conhecido durante a compilação.

using namespace std;

template <int n>
struct FIB {
  enum X { value = FIB<n-1>::value + FIB<n-2>::value };

  static int generico( int k ) {
    return k > n ? FIB<n>::generico( k-1 ) + FIB<n>::generico( k-2 ) : especifico( k );
  }

  static int especifico( int k ) {
    return k == n ? value : FIB<n-1>::especifico( k );
  }
};

template <>
struct FIB<0> {
  enum X { value = 0 };

  static int especifico( int k ) { return 0; }
};

template <>
struct FIB<1> {
  enum X { value = 1 };

  static int especifico( int k ) {return k == 1 ? value : FIB<0>::especifico( k ); }
};

inline int fib( const int n ) {
  return FIB<15>::generico( n );
}

int main(int argc, char *argv[])
{
  cout << fib( 45 ) << endl;
  return 0;
}

No exemplo acima o tempo de execução foi de 0.03 segundo. O pulo do gato é o 15 na função fib. Ele instancia a série para os 15 primeiros elementos. Detalhe que esse número é configurável durante a compilação somente. Mas de qualquer forma o programa funciona usando o mesmo algoritmo original – só que muito mais rápido.

Foi uma mistura de metaprogramação com programação. Uma possibilidade do C++, que a gente usa de acordo com o problema em questão…

“Nunca diga nunca!”