BLOG C++

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