Lambda Calculus – Parte 2
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”