Novos mecanismos de programação genérica em C++0x (PedroLamarao)
De ccppbrasil.org
Tabela de conteúdo |
Introdução
Neste artigo apresentamos alguns dos novos mecanismos integrados ao working paper do comitê de padronização do C++ no ISO. Os mecanismos apresentados foram escolhidos por oferecerem soluções para certos problemas de projeto de bibliotecas genéricas.
Stepanov e Musser definem a programação genérica como “a idéia de abstrair de algoritmos concretos e eficientes para obter algoritmos genéricos que possam ser combinados com diferentes representações de dados para produzir uma variedade de programas úteis”.
Um das características típicas dos algoritmos genéricos é lidar com uma quantidade indeterminado de objetos de tipos desconhecidos que cumpram um conjunto mínimo de requisitos.
Apesar de C++ possuir um número de mecanismos para suportar a programação genérica ainda restam muitas pontas soltas. C++0x propõe novos mecanismos para resolver inúmeros problemas encontrados pela indústria após dez anos de experiência.
O primeiro padrão C++ foi publicado pelo ISO em Setembro de 1998. Uma série de modificações para solucionar problemas encontrados posteriormente foi reunida em um Technical Corrigendum e incorporada no padrão em 2003. Às vezes as diferentes “versões” do padrão C++ são chamadas C++98 e C++03 de acordo com as datas de publicação; hoje falamos em um C++0x porque a expectativa é de que o novo padrão C++ seja publicado antes do final desta década. A meta atual do grupo de trabalho é finalizar os trabalhos em 2009.
Este artigo recebeu valiosas contribuições de Alexandre Moreira, que revisou a primeira versão.
Alguns Problemas da Programação Genérica em C++03
Distinguir rvalues de lvalues
Um dos utilitários da biblioteca padrão é o adaptador de função std::bind2nd, que vincula um valor a um dos argumentos de um objeto função, produzindo outro objeto função com um argumento livre apenas.
template <typename Operation, typename T> não-especificado bind2nd (Operation const& o, T const& t);
Um adaptador como este é de grande valor quando se necessita reunir diferentes bibliotecas em um programa cujas expectativas sobre os tipos sejam ligeiramente diferentes.
Podemos usar std::bind2nd para implementar uma operação que atribui um valor fixo a todos os elementos de um vetor.
template <typename T>
void
assign (T& t1, T const& t2) { t1 = t2; }
template <typename ForwardIterator, typename T>
void
assign_to_each (ForwardIterator begin, ForwardIterator end, T const& t) {
for_each(
begin,
end,
bind2nd(
fun_ptr(assign<T>),
t
)
);
}
Em C++03, instanciar assign_to_each sempre falha. A explicação está na implementação do tipo do objeto função adaptador retornado por bin2nd.
template <typename Operation>
class binder2nd : public unary_function<não-especificado> {
public:
typename Operation::result_type
operator() (typename Operation::first_argument_type const&);
};
Este adaptador produz um objeto função que recebe seu argumento como referência const. Isto garante que todo tipo de valores possam se prender ali, sejam lvalues ou rvalues.
Porém, como consequência, a qualidade original do valor é perdida: o objeto função adaptado por std::binder2nd receberá invariavelmente um valor de tipo referência const.
A solução é sobrecarregar este operator() em duas versões, uma cujo tipo do parâmetro seja declarado por referência a const e outro por referência a não-const.
Porém, quando projetamos adaptador mais complexos, cuja lista de argumentos é N, esta solução requer 2^N diferentes sobrecargas deste operador. Isto torna a implementação de adaptadores genéricos muito custosa.
Não há em C++03 uma maneira simples de distinguir e retransmitir argumentos lvalue e rvalue.
A Lista Indeterminada de argumentos
Utilitários como std::bind2nd são, por baixo dos panos, geradores ou factories para classes de suporte responsáveis por adaptar o objeto original a uma nova forma.
Um problema compartilhado por todos os utilitários deste tipo é como lidar com todo tipo de objetos de forma genérica; no caso de bind2nd, como lidar com objetos função com uma lista indeterminada de argumentos.
Note que bind2n é um adaptador específico para objetos função com dois argumentos.
Um utilitário mais básico que std::bind2nd é std::ptr_fun, que adapta um ponteiro para função em um objeto função.
template <typename Arg, typename Result> pointer_to_unary_function<Arg, Result> ptr_fun (Result (*)(Arg)); template <typename Arg1, typename Arg2, typename Result> pointer_to_binary_function<Arg1, Arg2, Result> ptr_fun (Result (*)(Arg1, Arg2));
Observe que para suportar funções com até N argumentos é necessário N sobrecargas de std::ptr_fun e N classes adaptadores de suporte.
Adaptadores como std::bind1st e std::bind2nd tem dificuldades ainda piores: para suportar objetos função de N argumentos são necessários N geradores distintos e N classes adaptadoras distintas cada uma com 2^N sobrecargas do operator() como vimos anteriormente.
Suportar funções com N + 1 argumentos demandariam outros N + 1 geradores e assim por diante.
Um caso particular da dificuldade dos geradores com listas indeterminadas de argumentos é exibido pela função membro construct da classe std::allocator.
template <typename T>
class allocator {
public:
void
construct (T* ptr, T const& val);
};
A função construct tem o propósito de construir um objeto do tipo T na memória apontada pelo argumento ptr. Para inicializar o valor do objeto construído copia-se o valor, previamente construído, do argumento val.
Para suportar a construção do objeto a partir de qualquer um dos seus construtores seria necessário oferecer sobrecargas template de construct recebendo N, N +1, N + 2 etc. argumentos.
Em C++03 a única maneira de suportar listas de parâmetros “genéricas” é duplicar o código para diferentes números de parâmetros, possivelmente usando truques com o pré-processador.
O Tipo de uma Expressão Genérica
Consideremos uma das sobrecargas de ptr_fun.
template <typename Arg, typename Result> pointer_to_unary_function<Arg, Result> ptr_fun (Result (*)(Arg));
A dedução do tipo do argumento de template permite obter, do tipo de ponteiro para função, o tipo dos argumentos e o tipo do retorno. Esses tipos são repassados à classe adaptadora para compor seu operator().
Prestando mais atenção à assinatura do operator() do adaptador std::binder2nd repare em seu valor de retorno.
typename Operation::result_type operator() (typename Operation::first_argument_type const&);
O adaptador std::binder2nd somente é capaz de adaptar objetos função cujo tipo cumpra os requisitos de uma BinaryFunction; esses requisitos incluem typedef membros que declaram os tipos dos argumentos e do valor de retorno.
(Ignoramos nesta discussão o problema dos tipos dos argumentos, que é diferente.)
std::ptr_fun gera sempre objetos função que cumprem esses requisitos.
std::binder2nd é incapaz de adaptar objetos função de tipos simples como o seguinte:
template <typename T1, typename T2>
struct assigner {
void
operator() (T1& t1, T2 const& t2) { t1 = t2; }
};
Este problema é compartilhado por todos os adaptadores de objeto função.
Outra classe de exemplos são operações genéricas como a seguinte:
template <typename A, typename B>
indeterminado
add (A const& a, B const& B) { return a + b; }
O tipo da expressão a + b acima pode ser A, ou B, ou qualquer outra coisa.
Em C++03 não é possível deduzir o tipo de uma expressão genérica, de modo que é necessário o uso de traits ou outro mecanismo de anúncio explícito de tipos.
Performance e o Custo da Abstração
Todos os problemas apresentados acima são, de certa maneira, problemas de inconveniência; problemas cuja solução é multiplicar indefinidamente o número de variantes dos utilitários para suportar todo (ou quase todo) tipo de objeto.
Assim, esses problemas são resolvíveis, e versões genéricas dos utilitários apresentados aparecem no TR1 da biblioteca padrão como tr1::function e tr1::mem_fn, tr1::bind, e outros.
A implementação destes utilitários impõe duras penas ao pré-processador e ao compilador, incorrendo um incremento indesejável no tempo de compilação dos projetos.
Além disso, o número de camadas de classes intermediárias de suporte necessárias exige do compilador toda a sua habilidade de otimização, sob pena de incorrer chamadas de função e objetos temporários extras.
As técnicas de inlining em geral contém o crescimento das chamadas extra de função; mas a criação de objetos temporários extra pode ser difícil de controlar implícita ou explicitamente.
Por que não há maneira simples de distinguir rvalues de lvalues a eliminação ou reaproveitamento de temporários pode ser impossível. Um caso simples é o operator+ de uma classe como string.
string TOKEN(“!”); string hw = “Hello” + string(“ “) + “World” + TOKEN;
Fora os objetos construídos por conversão de usuário, a expressão do lado direito da atribuição gera três objetos temporários para armazenar o valor intermediário das três sub-expressões. Cada um desses realiza a construção completa, incluindo alocação de memória, e posterior realocação para lidar com o operador propriamente dito.
Este operator+ é declarado da única maneira sensata.
template <não-especificado> basic_string<não-especificado> operator+ (basic_string<não-especificado> const& s1, basic_string<não-especificado> const& s2);
Como este operador nunca deve modificar um argumento lvalue não podemos sobrecarregá-lo em referências a const e a não-const para distinguir os lvalues dos rvalues.
Este problema é compartilhado em geral por todas as bibliotecas de templates de expressão, cujos adaptadores se valem da sobrecarga de operadores para oferecer “extensões” da sintaxe de C++.
A dificuldade de se produzir um gerador genérico como a função membro construct de std::allocator leva os projetos a se contentar com a necessidade de construção por cópia. Outro exemplo dessa necessidade é o acréscimo de um elemento a um Container.
void push_back (value_type const& v);
Não é possível construir um objeto dentro do Container; é preciso construí-lo fora e copiá-lo para lá.
Novos Mecanismos de Linguagem em C++0x
Alguns dos novos mecanismos de linguagem propostos para o C++0x vêm para resolver esses problemas.
Combinados, eles nos permitem escrever utilitários genéricos de forma concisa, que podem ser combinados e recombinados em expressões complicadas incorrendo um mínimo de penalidades por abstração.
Rvalue References
A proposta “rvalue references” acrescenta ao C++ um novo conceito: a distinção entre referências a lvalue e referências a rvalue, com o acréscimo de um novo token para distinguir os dois tipos de declarator.
pair<int, int> p1(3, 14); pair<int, int>& r1 = p1; // referência a lvalue pair<int, int>&& r2 = make_pair(3, 14); // referência a rvalue
O exemplo acima demonstra a diferença fundamental entre os dois tipos de referência. As referências a lvalue apresentam as mesmas regras das referências atuais, mantendo a compatibilidade com o passado; já as referências a rvalue permitem que se prenda um objeto temporário a uma referência não-const.
Em termos mais gerais, referências a lvalue preferem os lvalues e referências a rvalue preferem os rvalues.
Esta distinção é valiosa na resolução de sobrecarga.
void push_back (value_type const& v); void push_back (value_type&& v);
Por que nós sabemos que argumentos lvalue selecionarão a primeira sobrecarga e argumentos rvalue selecionarão a segunda sobrecarga, é possível, na implementação da segunda sobrecarga, reaproveitar a memória do rvalue dentro do Container.
De fato, a sobrecarga entre referência const lvalue e referência a rvalue permite que se diferencie funções “que copiam” de funções “que movem”; construtores de cópia e construtores de “mover”. Esta distinção oferece a oportunidade de economizar o custo de uma cópia completa quando ela não é necessária.
Este custo pode ser alto quando o objeto aloca memória internamente, por exemplo.
A dedução dos tipos dos argumentos de template nas funções template e a sintetização de tipos a partir dos argumentos de template foi modificada para dar conta dos novos conceitos.
Quando o tipo de um parâmetro de template é uma referência e o tipo do argumento de template também é uma referência ocorre um colapso das referências produzindo o tipo final.
Quando o parâmetro de template é um tipo de referência a rvalue a dedução e sintetização desse tipo mantém perfeitamente o tipo original do argumento de template.
Esta regra é valiosa para os adaptadores genéricos que redirecionam argumentos em chamadas de objeto função.
template <typename Operation>
class binder2nd : public unary_function<não-especificado> {
public:
typename Operation::result_type
operator() (typename Operation::first_argument_type&&);
};
O operator() acima sempre redirecionará seu argumento corretamente para a operação adaptada; se o argumento passado ao adaptador for um lvalue (const ou não) o tipo deduzido será também um lvalue (const ou não respectivamente); se for um rvalue o tipo deduzido será um rvalue.
Isto significa que suportar objetos função de N argumentos neste adaptador requer apenas N sobrecargas deste mecanismo.
Decltype
A proposta “decltype” acrescenta uma nova palavra-chave decltype funcionando como um operador e como um simple type specifier.
O significado da expressão:
decltype(expressão)
é o tipo da expressão entre parênteses.
Como decltype é um simple type specifier é possível declarar nomes cujo tipo é deduzido de uma expressão:
template <typename A, typename B>
void
foo (A a, B b) {
(...)
decltype(a + b) tmp = a + b;
(...)
}
Uma extensão da sintaxe de assinatura de função permite a declaração de funções cujo tipo de retorno é deduzido:
template <typename A, typename B>
auto
add (A const& a, B const& b) -> decltype(a + b) {
return a + b;
}
A palavra-chave auto no tipo de retorno da função indica que este tipo será deduzido após a lista de parâmetros for conhecida.
Com decltype é possível declarar adaptadores de objeto função que deduzem o tipo de retorno do objeto função adaptado:
template <typename Operation>
class binder2nd : public unary_function<não-especificado> {
private:
Operation op;
typename Operation::first_argument_type bound_arg;
public:
auto
operator() (typename Operation::first_argument_type&& arg) -> decltype(op(arg, bound_arg));
};
Variadic Templates
A proposta “variadic templates” acrescenta um elemento análogo aos “varargs” do C: um pack de parâmetros e um correspondente pack de argumentos.
Um template é declarado como aceitando um pack de parâmetros da seguinte forma:
template <typename... Args> struct foo; template <typename... Args> foo<Args...> bar (Args... args);
Um template que recebe um pack de parâmetros é chamado um template variádico.
Um pack de parâmetros é uma seqüência de zero ou mais tipos; um pack de argumentos é uma seqüência de zero ou mais argumentos correspondentes.
A única operação definida para um pack de parâmetros está exibida no tipo de retorno do template de função foo: a expansão de pack.
Quando o operador ... é aplicado a um pack o compilador o trata como se fosse uma seqüência normal de tipos.
O mesmo se aplica a um pack de argumentos.
template <typename... Args>
foo<Args...>
bar (Args... args) {
return foo<Args...>(args...);
}
Neste exemplo construímos um novo objeto expandindo o pack de argumentos para selecionar um construtor de foo.
Desta forma podemos construir geradores genéricos que inicializam o valor do objeto diretamente através do construtor apropriado:
template <typename T>
class allocator {
template <typename... Args>
void
construct (T* ptr, Args&&... args)
{ new (ptr)(static_cast<Args&&...>(args...)); }
};
A construção in-place com new acima seleciona um construtor apropriado para a seqüência de tipos expandida do pack de parâmetros e redireciona os argumentos diretamente a esse construtor, sem a necessidade de uma cópia intermediária.
O exemplo acima exibe uma propriedade dos packs de parâmetros: é possível aplicar declarators ao pack que se aplicarão em seqüência a todos os tipos do pack.
No exemplo acima recebemos os argumentos de construct por referência a rvalue para realizar o encaminhamento dos argumentos com o tipo correto, distinguindo corretamente lvalues de rvalues.
Como o compilador expande um pack de parâmetros no que, de outro modo, é apenas uma seqüência de tipos, podemos trabalhar cada elemento da seqüência recursivamente através da especialização do template variádico.
template <typename... Args>
struct accumulate_sizeof;
template <>
struct accumulate_sizeof<> {
static const int sum = 0;
};
template <typename T, typename... Args>
struct accumulate_sizeof {
static const int sum = sizeof(T) + accumulate_sizeof<Args...>::sum;
}
A meta-função acima calcula a soma dos sizeof dos seus tipos argumento de template.
Quando a meta-função é instanciada com um ou mais argumentos, a segunda especialização é selecionada. Esta especialização separa o primeiro argumento e calcula seu sizeof; então instancia a si mesma novamente com o restante dos argumentos.
Quando (eventualmente) a meta-função é instanciada com zero argumentos, a primeira especialização é selecionada, retornando zero.
Desta forma é possível implementar utilitários e adaptadores verdadeiramente genéricos. Exemplos mais interessantes podem ser encontrados no documento “Variadic templates (revision 3)”, disponível na URL dada na bibliografia.
Bibliografia
David R. Musser and Alexander A. Stepanov: Generic Programming. ISSAC 1988, pages 13-25. http://www.stepanovpapers.com/genprog.pdf
Hinnant, Howard. A Proposal to Add an Rvalue Reference to the C++ Language. Technical Report N1690=04-0130, ISO/IEC JTC1, Information Technology, Subcommittee SC 22, Programming Language C++, September 2004. http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2004/n1690.html
Technical Report on C++ Performance. TR 18015:2006, ISO/IEC JTC 1, Information Technology, Subcommittee SC 22, Programming Language C++, February 2006. http://www.open-std.org/jtc1/sc22/wg21/docs/TR18015.pdf
Jaakko. Järvi, Bjarne Stroustrup, and Gabriel Dos Reis. Decltype (revision 5). Technical Report N1978=06- 0048, ISO/IEC JTC 1, Information Technology, Subcommittee SC 22, Programming Language C++, April 2006. http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2006/n1978.pdf
D. Gregor, J. Järvi, and G. Powell. Variadic templates (revision 3). Number N2080=06-0150, ISO/IEC JTC 1, Information Technology, Subcommittee SC 22, Programming Language C++, October 2006. http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2006/n2080.pdf
Working Draft, Standard for Programming Language C++. Number N2461=07-0331, ISO/IEC JTC 1, Information Technology, Subcommittee SC 22, Programming Language C++, October 2007. http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2007/n2461.pdf
