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.”