Basic basic_string String Utils

Vários programadores C++ devem concordar que a interface do template std::basic_string [1] não é das mais ricas. Provavelmente, muitos já até criaram suas próprias funções utilitárias para lidar com strings. Eu resolvi publicar as minhas.

A pequena coleção de algoritmos em string não é tão poderosa e completa como a Boost String Algorithms Library. Também não é tão genérica quanto a da Boost. Isso, por que eu assumo que todos os tipos devem ser instâncias do template std::basic_string. Mesmo assim, ainda podem ter situações que compensem seu uso.

• Se você está trabalhando com ASCII [2], há versões das funções que aceitam qualquer tipo que seja uma instância do template std::basic_string parametrizado com char e std::char_traits<char> como sendo os dois primeiros argumentos template (o alocador não importa). Essas versões não utilizam os mecanismos de localização/internacionalização de C++, mas apenas uma tabela de conversões. Normalmente, isso permite um processamento mais rápido, já que não são realizadas chamadas de métodos virtuais das classes de facets [3]. Naturalmente, para outros encodings existem versões que aceitam um std::locale.
• Caso não esteja usando a Boost em sua aplicação, pode ser que não queira adicioná-la apenas por necessitar de algumas funções utilitárias para strings.

Bom, uma pequena introdução sobre minha Basic basic_string String Utils (que na verdade é uma versão em inglês deste texto) e o download estão disponíveis em meu site.

[1] Para os que ainda não sabem, ambos os tipos std::string e std::wstring são instâncias do template std::basic_string.

[2] Refiro-me ao ASCII convencional de 7 bits, e não extensões como ISO-8859-x.

[3] O mecanismo de internacionalização em C++ (locales) é constituído por uma coleção de templates e classes especiais chamadas de facets.

Read Full Post »

Entendendo o papel de std::iterator_traits

Um dos fóruns de desenvolvimento C++ que mais gosto é o Codeguru. De vez em quando participo de umas discussões por lá. Semana passada, por exemplo, surgiu um assunto que costuma gerar certas dúvidas. Principalmente, para quem não é muito por dentro do design da STL.

• Quais os requisitos que tornam uma classe de iteração (um iterator) compatível com os algoritmos da STL?
• Quais devem ser os cuidados ao implementar um algoritmo para que ele seja compatível com os iteradores da STL?

Bom, as respostas são relativamente simples. Nada mirabolante. Explicações breves seguem abaixo. Mas se alguém quiser ler a discussão original do Codeguru para entender melhor o contexto, os links são este e este.

Vamos para a primeira pergunta. Talvez você tenha criado uma nova estrutura de dados e esteja implementando um iterador para ela. Ou talvez tenha apenas inventado um mecanismo de iteração específico. Por qualquer que seja o motivo, se você tem uma classe de iteração e precisa fazê-la funcionar na STL é necessário seguir algumas diretrizes.

Como sabemos, os iteradores da STL são responsáveis por fazer a “cola” entre os contêineres e os algoritmos. Logo, a definição dos tipos de dados sobre os quais as operações são realizadas é de responsabilidade do iterador. A STL se apoia em um template, std::iterator_traits, para encapsular essa informação. Sua definição é a seguinte:

template<class iterator_t> 
struct iterator_traits 
{
  typedef typename iterator_t::difference_type difference_type;
  typedef typename iterator_t::value_type value_type;
  typedef typename iterator_t::pointer pointer;
  typedef typename iterator_t::reference reference;
  typedef typename iterator_t::iterator_category iterator_category;
};

O template std::iterator_traits deve possuir uma instanciação válida para todas as classes que representam iteradores, pois os algoritmos dependem dos tipos inferidos para que possam funcionar corretamente. Existem duas maneiras de fazer isso. Uma delas (normalmente recomendada) é definir os tipos acima através de typedefs dentro da própria classe.

class smart_iterator
{
public:
  typedef something value_type;
  typedef something * pointer;
  //...
};

A maneira alternativa é especializar o template std::iterator_traits e lá fazer a definição dos tipos. Essa é exatamente a abordagem que o próprio padrão C++ adota para que ponteiros comuns funcionem como iteradores. Portanto, a especialização de std::iterator_traits para ponteiros já vem de fábrica.

//Especialização para ponteiros (existe uma similar para ponteiros de constantes).
template<class T> 
struct iterator_traits<T*> 
{
  typedef ptrdiff_t difference_type; 
  typedef T value_type;
  typedef T* pointer;
  typedef T& reference;
  typedef random_access_iterator_tag iterator_category;
};

//Especialização para sua classe.
template <>
struct iterator_traits<smart_iterator>
{
  typedef something value_type;
  typedef something * pointer;
  //...
};

Ainda não acabou. Tendo estabelecido os tipos, você precisa se certificar de que a classe de iteração satisfaz as expressões válidas do conceito de iterador que se deseja modelar. Todos os iteradores devem suportar, por exemplo, o operador de dereferenciação (operator*) e o operador de acesso a membro (operator->). Mas alguns conceitos como Bidirectional Iterator ou Random Access Iterator adicionam novos requisitos.

A resposta para a segunda pergunta é bem intuitiva tendo-se em vista os comentários acima. Quando quiser implementar um algoritmo no estilo STL, lembre-se de dois pontos importantes:

• Algoritmos operam através de iteradores. Acesso aos tipos de dados devem ser sempre feitos com o auxílio de std::iterator_traits. Nunca acesse o tipo diretamente através do parâmetro template correspondente ao iterador.

template <class input_iterator_t>
void cool_algorithm(input_iterator first, input_iterator last)
{
  //Não faça assim!
  typename input_iterator_t::value_type a; 

  //Faça assim!
  typename std::iterator_traits<input_iterator_t>::value_type b;
  
  //...
}

• Deixe claro na documentação qual o conceito esperado que o iterador modele. Obviamente, utilize apenas as expressões desse conceito (ou de conceitos que ele refina). Não utilize, por exemplo, a expressão --i (assumindo que i seja um iterador) em uma implementação que espera um Forward Iterator, já que ela só é válida para um Bidirectional Iterator.

Read Full Post »

Conceitos no C++ – Tipos Associados

Continuando a série de posts sobre conceitos (concepts) no C++0x, agora é hora de apresentar outro elemento importante. No último post, expliquei como especificar um contexto restrito no qual apenas tipos LessThanComparable (comparáveis por menor) são permitidos. Tais tipos devem suportar o operator< que recebe dois parâmetros e retorna um bool. Porém, nem sempre trabalhamos com funções associadas que operam somente sobre tipos primitivos. Inclusive, em muitos casos nem sequer sabemos exatamente quais os tipos dos dados em questão. Para resolver esses e outros problemas existem os tipos associados.

O objetivo dos tipos associados é justamente introduzir abstrações pelas quais podemos suportar funções associadas de maneira natural. Para ilustrar, considere o exemplo do post anterior no qual criei uma classe chamada book. Suponha que essa classe faça parte de uma aplicação que modela o sistema de uma livraria. Nela, todos os itens como livros, revistas, jornais ou similares são caracterizados como sendo materias de leitura.

A aplicação da livraria, assim como qualquer outra, possui regras de negócio que devem ser aplicadas a todos os materiais de leitura. Mas como estamos no mundo da programação genérica, ao invés de fazer com que todos eles herdem de uma classe base comum farei com que todos modelem um conceito comum, chamado ReadableMaterial.

Para que um item seja considerado um ReadableMaterial ele precisa satisfazer alguns requisitos como, por exemplo, saber o seu número de páginas. No caso da classe book do post anterior assumi que essa informação era armazenada em um membro do tipo int. No entanto, para promover um tratamento uniforme entre os variados materiais de leitura é necessário adotar uma abstração genérica que represente o tipo de dados que cada um deles utiliza para armazenar seu número de páginas. Afinal de contas, nessa aplicação hipotética, enquanto os livros utilizam um int os jornais e revistas utilizam um short. Já as enciclopédias utilizam um std::size_t. Além disso, pode aparecer um novo material de leitura que utilize um tipo de dados personalizado, definido pelo próprio usuário. (Lembre que isso é apenas um exemplo de caráter didático.) Portanto, a solução é especificar, além da função associada, um tipo associado ao conceito ReadableMaterial.

Uma outra informação que gostaria de ter sobre os materiais de leitura é se determinada página contém alguma ilustração. Assim como o número de páginas, esse requisito pode ser introduzido no conceito através de uma função associada. Com isso, a definição de ReadableMaterial fica conforme o código abaixo.

concept ReadableMaterial <typename T>
{
  typename page_size_type;

  page_size_type num_pages(T const&);
  bool is_illustrated_page(T const&, page_size_type);
}

Agora, a próxima etapa é justamente criar mapas de conceito entre ReadableMaterial e as classes que o modelam, como book, magazine, newspaper, entre outras. Abaixo, mostro apenas para book, mas os outros seriam similares. Note que o conceito não requer as funções associadas num_pages e is_illustrated_page como membros do tipo modelo (que, de fato, pode ser feito). Logo, preciso realizar o mapeamento explícito dessas funções (no caso, utilizando as próprias funções membro de book).

class book
{
public:
  int num_pages() const { return num_pages_; }
  bool is_illustrated_page(int page_num) const { /*...*/ }

private:
  int num_pages_;
};

concept_map ReadableMaterial<book>
{
  typedef int page_size_type;

  int num_pages(book const& b)
  { return b.num_pages(); }
 
  bool is_illustrated_page(book const& b, int page_num)
  { return b.is_illustrated_page(page_num); }
}

Tendo o conceito e seus respectivos modelos definidos, posso implementar uma função genérica simples que conta o número de páginas com ilustrações de um ReadableMaterial. Preste atenção no código e tente identificar se ainda está faltando algo nesta abordagem.

template <typename T>
  requires ReadableMaterial<T>
ReadableMaterial<T>::page_size_type count_illustrated_pages(T const& t)
{
  ReadableMaterial<T>::page_size_type count = 0;
  for (ReadableMaterial<T>::page_size_type i = 0; i < num_pages(t); ++i)
    if (is_illustrated_page(t, i))
      ++count;
  return count;
}
&#91;/sourcecode&#93;

Provavelmente, os leitores que já captaram a essência da programação baseada em conceitos detectaram pequenos problemas. No <a href="https://0xc0de.wordpress.com/2008/10/16/conceitos-no-c-introducao/">primeiro post</a> da série, tentei deixar claro que uma grande vantagem desse paradigma é exatamente a imposição contratual de certas regras, tanto para o autor quanto para o usuário de templates. Eu, como autor de <code>count_illustrated_pages</code>, violei parte desse contrato. O motivo é o seguinte: Informei aos usuários que tipos que modelam <em>ReadableMaterial</em> poderiam ser utilizados na função acima. Porém, em sua implementação utilizei construções sintáticas que não são requisitos desse conceito. Ou seja, <code>count_illustrated_pages</code> depende que <code>page_size_type</code> satisfaça requisitos que não são exigidos em <em>ReadableMaterial</em>. São eles:

- Construção a partir de um inteiro;
- Comparação por menor;
- Operador de pré-incremento;
- Construtor de cópia;
- Destrutor.

Esses pequenos itens não são motivo de dores de cabeça. Há uma forma simples de fazer o exemplo funcionar. Basta adicionar os requisitos acima ao tipo associado<code> page_size_type</code> de <em>ReadableMaterial</em>. Felizmente, há um conceito chamado <em>ArithmeticLike</em> no novo padrão C++ que já os encapsula. Portanto, há basicamente duas formas de contornar a situação. A primeira delas consiste de adicionar a restrição de <em>ArithmeticLike</em> sobre <code>page_size_type</code> na função <code>count_illustrated_pages</code>, conforme mostrado abaixo. (Note a notação simplificada na qual especifico T como sendo um <em>ReadableMaterial</em> ao invés de um <code>typename</code> convencional.)


template <ReadableMaterial T>
  requires ArithmeticLike<T::page_size_type>
T::page_size_type count_illustrated_pages(T const& t)
{
  T::page_size_type count = 0;
  for (T::page_size_type i = 0; i < num_pages(t); ++i)
    if (is_illustrated_page(t, i))
      ++count;
  return count;
}
&#91;/sourcecode&#93;

A segunda delas, que considero a melhor opção, é adicionar a restrição de <em>ArithmeticLike</em> sobre <code>page_size_type</code> diretamente em <em>ReadableMaterial</em>. Nesse caso, não é necessário colocar a restrição de <em>ArithmeticLike</em> sobre a função, já que agora ela é parte integral do próprio conceito.


concept ReadableMaterial <typename T>
{
  typename page_size_type;
 
  page_size_type num_pages(T const&);
  bool is_illustrated_page(T const&, page_size_type);
 
  requires ArithmeticLike<page_size_type>; //Novo requisito!
}

Até a próxima!

Leandro T. C. Melo

Read Full Post »

Otimização de Classe Base Vazia (EBCO)

Começarei este post com trechos de código e, em seguida, farei uma pergunta. Considere o struct information abaixo.

struct information
{
  typedef int value_type;
  value_type get_info() const { /* ... */ }
};

Notem que ele simplesmente define um tipo e uma função membro não-virtual. Assim como membros estáticos, definições de tipo e funções não-virtuais não ocupam espaço em uma classe. Porém, ao declarar um membro do tipo information no template de classe simple, abaixo, observamos que 4 bytes adicionais são alocados. (Utilize sizeof para testar.)

template <class information_t>
class simple
{
public:
  simple(information_t const& info, int data) : 
    info_(info), data_(data)
  {}

private:
  information_t info_; //Gera 4 bytes extras em simple.
  int data_;
};

//...

simple<information> s(information(), 10);

Se simple tivesse apenas o inteiro data_ seu tamanho seria de 4 bytes (naturalmente, considerando o ambiente que estou compilando), mas com o membro info_ seu tamanho vai para 8 bytes. Qual a razão desse comportamento?

A resposta é a seguinte: O padrão C++ não permite a existência de tipos com tamanho zero, mesmo sendo classes vazias como o struct information. Se não acreditar, experimente criar uma classe sem absolutamente nenhum membro e verifique seu sizeof. Pode parecer contraditório, mas existem motivos importantes para essa restrição. Como seria, por exemplo, um array de tipos de tamanho zero? Imaginem as operações aritméticas de ponteiros sobre ele? Confuso, não?

Acontece que espaço desnecessário em memória é caro em determinadas aplicações. Neste mesmo blog, em um post anterior, mencionei como estratégias bem conhecidas de alinhamento e preenchimento podem resultar em uso mais eficiente de espaço. Portanto, o ideal é encontrar alguma forma de contornar essa situação. No paradigma de programação genérica, por exemplo, é bastante comum classes com caraterísticas bem similares as do struct information.

Pensando nisso, os envolvidos na padronização do C++ deixaram uma “brecha” interessante. Apesar de todos os tipos serem obrigados a terem tamanho maior que zero, quando classes vazias são utilizadas como classes bases não é necessário que nenhum espaço seja alocado para elas. Obviamente, a condição vale desde que haja a garantia que a classe base vazia não seja alocada em um mesmo endereço de outros objetos, inclusive derivados da própria hierarquia. Essa estratégia é conhecida como otimização de classe base vazia, do inglês Empty Base Class Optimization (EBCO).

Creio que a maioria dos compiladores profissionais implementam essa otimização. Se não me engano, tanto o Microsoft Visual C++ quanto o GCC já a fazem há bastante tempo. Logo, desenvolvedores de bibliotecas C++ ricas em templates (o que não é nada raro atualmente) devem ficar atentos para as oportunidades de otimização. No caso do exemplo deste post, como poderíamos usufruir desse recurso?

O primeiro passo é garantir que o struct information seja uma classe base, eliminando, assim, o espaço desnecessário em memória. Uma alternativa é fornecer um template de classe que agregue tanto a classe vazia quanto um dado qualquer. Tal template deve herdar da classe vazia conforme o código abaixo.

template <class base_t, class data_t>
struct ebco : base_t
{
  data_t data_;
  ebco(base_t const& base, data_t const& data) : 
    base_t(base), data_(data)
  {}
};

Agora, ao invés de declarar o membro info_ e o membro data_, declararamos apenas o template ebco parametrizado com information e o inteiro que representa o dado. O template de classe optimized_simple faz exatamente isso.

template <class information_t>
class optimized_simple
{
public:
  optimized_simple(information_t const& info, int data) : 
    optimization_(info, data)
  {}

private:
  ebco<information_t, int> optimization_ ;
};

Pronto! Comparando os retornos de sizeof(simple) e sizeof(optimized_simple) obtemos 8 bytes para o primeiro e 4 bytes para o segundo. Ou seja, para esse caso específico reduzimos o tamanho de um tipo pela metade.

Read Full Post »

Manipuladores sem Parâmetros em C++

Creio que a maioria dos programadores C++ saiba que o std::cout é um objeto do tipo std::ostream. Sendo que std::ostream é nada mais do que uma definição do template de classe std::basic_ostream com o tipo char. Ou seja:

typedef basic_ostream<char> ostream;

Por outro lado, já não é qualquer programador que sabe o que é o std::endl que comumente acompanha um std::cout. Um objeto? Uma função? Afinal, o que acontece exatamente quando o compilador encontra um std::endl?

std::cout << "Invocando um manipulador..." << std::endl;
&#91;/code&#93;

Tecnicamente, o <code>std::endl</code> é um <strong>manipulador</strong> (<em>manipulator</em>). Manipuladores são "componentes" que podem ser utilizados em conjunto com os operadores de entrada e saída de stream afim de... ora, manipular o stream. Provavelmente, você conhece outros manipuladores como, por exemplo, o <code>std::boolalpha</code> ou o <code>std::flush</code>.

Como é implementado um manipulador? Bom, isso depende. Manipuladores que não possuem parâmetros, como os descritos no parágrafo acima, são ponteiros de funções (<em>function pointers</em>). Já os manipuladores que possuem parâmetros, como <code>std::setw()</code> e <code>std::setfill()</code>, entre outros, são simplesmente objetos de determinada classe. Nesse post, mostrarei a implementação de um manipulador simples e sem parâmetros.

O padrão C++ disponibiliza quatro tipos de ponteiros de funções a serem utilizados pelos manipuladores de streams. Eles são membros dos templates <code>basic_istream</code> e <code>basic_ostream</code> e são invocados por uma sobrecarga convencional dos operadores de deslocamento (<em>shift</em>): <code>operator&lt;&lt;</code> e <code>operator&gt;&gt;</code>. Lembre que a hierarquia de classes da biblioteca C++ de IOStreams começa com a classe <code>ios_base</code>. Em seguida, aparece a classe <code>basic_ios</code>, que na verdade é um template de classe parametrizado pelo tipo do caractere e <em>traits</em> de caracteres. Herdando diretamente de <code>basic_ios</code> e igualmente parametrizadas, estão os templates de classe <code>basic_istream</code> e <code>basic_ostream</code>. Abaixo, na definição parcial de <code>basic_istream</code>,  <code>charT</code> e <code>traits</code> são, respectivamente, os parâmetros correspondentes ao tipo de caractere e ao traits.


//Namespace std naturalmente.
template <class charT, class traits = char_traits<charT> >
class basic_istream : virtual public basic_ios<charT, traits>
{
public:
  //...
  
  //Para manipuladores que acessam apenas ios_base.
  basic_istream<charT,traits>&
  operator>> 
  (ios_base& (*pf)(ios_base&));

  //Para manipuladores que acessam basic_ios.
  basic_istream<charT,traits>&
  operator>> 
  (basic_ios<charT,traits>& (*pf)(basic_ios<charT,traits>&));

  //Para manipuladores que dependem de istream.
  basic_istream<charT,traits>&
  operator>> 
  (basic_istream<charT,traits>& (*pf)(basic_istream<charT,traits>&));
};

No parágrafo anterior eu disse que são disponibilizadas sobrecargas para quatros tipos de ponteiros de função. A quarta sobrecarca é equivalente à terceira de basic_istream mostrada acima. Porém, ela está diponível em basic_ostream e é voltada para streams de saída. O importante de ser observado é que todos os tipos de ponteiros de funções recebem e retornam um stream. Portanto, qualquer função que tenha uma assinatura consistente com uma das definições pode ser usada como um manipulador. Simples, não?

Aqui vai, então, a implementação e utilização do meu super manipulator. Ele não faz grandes coisas. Basicamente, é um std::endl incrementado que, além do caractere de fim de linha, também adiciona um caractere de tab para a próxima linha. Seu nome é endlplacet (end line and place tab). Ainda não consegui nenhuma utilidade prática para ele...

#include

template
inline std::basic_ostream&
endlplacet(std::basic_ostream& os)
{
os.put(os.widen('\n'));
os.put(os.widen('\t'));
os.flush();

return os;
}

int main()
{
std::cout << "Feliz 2009," << endlplacet << "Leandro Melo."; return 0; } [/code]

Leandro T. C. Melo

Read Full Post »

Conceitos no C++ – Funções Associadas

Os conceitos (concepts) já estão aprovados para o novo C++ e foram o tema do primeiro post desta série. Nele, apresentei uma introdução básica sobre assunto. Em particular, quais são as motivações para o formalismo estabelecido pelos conceitos. Agora, é hora de entender melhor como eles funcionam.

Deve estar claro para você que os conceitos representam a interface pela qual estruturas de dados são acessadas e/ou manipuladas. Seus principais componentes são os tipos associados e funções associadas. (Outros itens que podem fazer parte da especificação de um conceito serão discutidos em breve.) Inicialmente, vamos nos concentrar na estrutura básica de um programa baseado em conceitos. Para isso, será utilizado o exemplo clássico: LessThanComparable.

Se você tem experiência com a STL é bem provável que tenha passado pela especificação desse conceito no site da SGI¹. Porém, se você não tem experiência com programação genérica, mesmo tendo esbarrado na especificação da SGI também é bastante provável que não tenha dado muito atenção ao conteúdo lá descrito. Mas não importa! O que você precisa saber neste momento é que para que determinado tipo modele ou satisfaça o conceito LessThanComparable (“comparável por menor”) é necessário que um operator< compatível esteja disponível. Consequentemente, a definição desse conceito deve incorporar tal requisito.

concept LessThanComparable<typename T>
{
  bool operator<(T const& x, T const& y);
}
&#91;/sourcecode&#93;

O trecho de código acima é simples. Ele diz a compilador que existe um conceito chamado <em>LessThanComparable</em> e que esse conceito exige uma <em>função associada</em>, um <code>operator&lt;</code> para o tipo <code>T</code>. Ou seja, para que um tipo <code>T</code> seja considerado <em>LessThanComparable</em> deve ser possível utilizá-lo em um <code>operator&lt;</code> com dois parâmetros.

Com o conceito definido, podemos, então, criar <em>mapas de conceitos</em> que mapeam estruturas de dados diversas em conceitos específicos. No nosso caso, os tipos primitivos <code>int</code> e <code>double</code> podem ser comparados por menor com o próprio <code>operator&lt;</code> built-in da linguagem C++. Logo, basta dizer ao compilador que tais tipos <em>satisfazem</em> o conceito <em>LessThanComparable</em>. Isso é feito com a palavra-chave <code>concept_map</code>.


concept_map LessThanComparable<int>{ }
concept_map LessThanComparable<double> { }

Neste momento, é bem provável que você esteja se perguntando: Já que int e double são naturalmente comparáveis com o operator<, por quê preciso mapeá-los explicitamente? A resposta é que você não precisa! Mas para isso é necessário modificar ligeiramente a definição do conceito LessThanComparable. A idéia é deixar claro para o compilador que esse conceito é automático. Portanto, os mapeados podem ser inferidos implicitamente. O compilador está livre para procurar definições compatíveis do operator< ou de qualquer outra função associada ao conceito em determinado escopo.

auto concept LessThanComparable<typename T> //Note o auto.
{
  bool operator<(T const& x, T const& y);
}
&#91;/sourcecode&#93;

A definição de um conceito como automático libera o programador de ter que indicar explicitamente quais os tipos de dados que o satisfazem. Isso inclui tantos os tipos primitivos quanto os tipos definidos pelo usuário. Por exemplo, se você criou uma classe <code>book</code> e também criou um <code>operator&lt;</code> que compara <code>book</code>s, esta classe é considerada um modelo de <em>LessThanComparable</em> sem a necessidade de um mapeamento explícito.


struct book
{
  int num_pages_;
  //...
};

bool operator<(book const& b1, book const& b2)
{
  return b1.num_pages_ < b2.num_pages_;
}

//O mapeamento abaixo não é necessário!
//concept_map LessThanComparable<book> { }

Por outro lado, se não existe um operator< para books, mas ainda sim é desejável que a classe seja LessThanComparable, o mapeamento explícito deve ser fornecido. No próprio mapa de conceito é possível especificar como a comparação de menor é realizada para a classe book.

struct book
{
int num_pages_;
//…
};

//Não há operator<. Logo, o mapeamento é necessário. concept_map LessThanComparable
{
bool operator<(book const& b1, book const& b2) { return b1.num_pages_ < b2.num_pages_; } } [/sourcecode] Seja através de conceitos automáticos (com a palavra-chave auto) ou não, a moral da história é que o compilador deve ser capaz de encontrar implementações concretas que satisfaçam os requisitos associados ao conceito. Não faz diferença se o mapeamento é feito implicitamente ou explicitamente por um mapa de conceito, como ilustram, respectivamente, os dois últimos trechos de código acima. Durante a compilação determinados tipos (primitivos ou definidos pelo usuário) serão considerados como modelos de conceitos e outros não.

Se você leu a primeira parte deste texto deve se lembrar que o problema da função print era o fato de não haver uma garantia de que o tipo T parametrizado possuísse um operator<< válido. Trazendo o problema para o contexto deste post e fazendo uma analogia, gostaríamos de implementar uma função minimum, por exemplo, na qual houvesse a garantia de que para o tipo T parametrizado sempre existisse um operator< compatível. Exatamente para esse propósito que os conceitos são extremamente úteis.

O template de função minimum abaixo impõe uma restrição sobre T. Tecnicamente, ela cria um contexto restrito no qual os requisitos do conceito especificado devem ser obrigatoriamente satisfeitos para o tipo de dado parametrizado. Neste caso, apenas modelos de LessThanComparable são aceitos em minimum.

template
requires LessThanComparable
T const& minimum(T const& a, T const& b)
{
return a < b ? a : b; } [/sourcecode] A definição de minimum é muito parecida com a forma tradicional que estamos acostumados. No entanto, há um pequeno detalhe que faz uma enorme diferença: Sob o parâmetro T é aplicada uma cláusula de restrição dizendo que apenas tipos que satisfazem LessThanComparable são considerados válidos. Um template restrito de função como minimum traz duas grandes vantagens para programadores:

• Contrato para autores de templates: Em um template restrito os autores de templates não podem utilizar expressões, tipos associados ou qualquer relação de dependência sobre o tipo parametrizado que não esteja especificada no conceito em questão. Isso quer dizer que se o autor de minimum tivesse a brilhante idéia de implementar o corpo do template de função com a expressão !(a >= b) ao invés de a < b ele receberia um erro de compilação. Portanto, autores de templates estão agora mais seguros e apoiados em um mecanismo formal para poderem estabelecer os requisitos de suas obras-primas.
• Contrato para usuários de templates: O grande benefício para os usuários de templates é que eles têm uma maneira clara e objetiva para conhecerem os requisitos mínimos a serem oferecidos por tipos de dados submetidos como argumentos a templates de classes e/ou funções. Se mesmo assim ainda forem cometidos erros, o compilador gerará mensagens de erro sucintas e diretas a respeito de qual requisito do conceito não foi satisfeito. A detecção do erro não mais acontecerá na etapa de compilação que realiza a instanciação de templates. Agora, a detecção do erro será imediata.

O programa abaixo exemplifica a discussão deste texto.

struct book
int num_pages_;
//…
};

//Mapeando book.
concept_map LessThanComparable {
bool operator<(book const& b1, book const& b2) { return b1.num_pages_ < b2.num_pages_; } } struct magazine { int num_pages_; }; //Nenhum mapeamento ou operator< para magazine. template
requires LessThanComparable
T const& minimum(T const& a, T const& b) {
return a < b ? a : b; } int main() { book b1, b2; //... bool rb = minimum(b1, b2); magazine m1, m2; //... bool rm = minimum(m1, m2); //Opa! Erro! //magazine não é LessThanComparable! return 0; } [/sourcecode] Os conceitos são um recurso poderoso do novo C++. O objetivo deste post é simplesmente introduzir os princípios básicos. Ao longo do tempo pretendo mostrar toda a riqueza sintática e semântica contida em um conceito. Você verá, por exemplo, como modificar indiretamente (através de mapas de conceitos) o comportamento de uma classe sem sequer tocá-la. No próximo post continuarei com os fundamentos dos conceitos C++. Para os mais apressados, o draft atual pode ser encontrado no site ISO.

Leandro T. C. Melo

(1) O novo padrão C++ incorpora um número enorme de especificações de conceitos. No entanto, há conceitos no site da SGI que não foram padronizados. Há também alguns conceitos não possuem exatamente os mesmos requisitos de seus correspondentes da SGI.

Read Full Post »

Conceitos no C++ – Introdução

Agora é oficial: Os conceitos (concepts) estão presentes no candidate draft do novo padrão C++0x (possivelmente C++09)!

O que são e para que servem os conceitos? Como eles estão relacionados aos templates C++ tradicionais? Quais são as vantagens e desvantagens de utilizá-los? Provavelmente, essas são perguntas bastante comuns para desenvolvedores que não são muito familiarizados com programação genérica. Se você, por acaso, é uma dessas pessoas e está interessado em entender um pouco mais sobre essa fantástica funcionalidade do novo C++, continue lendo.

Antes de falar sobre os conceitos é necessário falar sobre o paradigma da programação genérica. No mundo C++, a grande obra e referência desse paradigma, que vem crescendo a cada dia, é a STL (Standard Template Library). Outras referências importantes são a BGL (Boost Graph Library), a CGAL (Computational Geometry Algorithms Library) e a MTL (Matrix Template Library).

É relativamente comum escutar comentários negativos de programadores C++ pouco experientes em relação à STL. Particularmente, devido ao enorme número de templates de classes e de funções. No entanto, a arquitetura da STL é formulada propositalmente dessa forma com o intuito de promover um alto grau de genericidade (que no caso de C++, é obtida através do uso de templates). Adicionalmente, neste paradigma a flexibilidade e extensibilidade são os principais objetivos. Consequentemente, a “quebra” da orientação por objetos (OO) é inevitável em vários casos, o que contribui para o desconforto de certos programadores.

A grande idéia por trás da STL é a de trabalhar através de interfaces (no sentido abstrato) bem formuladas ao invés de trabalhar com tipos de dados (ou hierarquias de tipos de dados e polimorfismo dinâmico). Essas interfaces são descritas por tipos e operações que determinada implementação deve suportar. Tais interfaces são justamente os conceitos! Um conjunto de requisitos que estabelece os mecanismos pelos quais podemos manipular um tipo de dado específico. Se um tipo de dado satisfaz os requisitos de um conceito, ele representa um modelo para esse conceito.

Se você já visitou a página de documentação da STL no site da SGI, existem boas chances de já ter tido um primeiro contato com os conceitos. Lá estão descritos conceitos como Container, Forward Container, Sequence, Back Insertion Sequence, Trivial Iterator, Input Iterator, Random Access Iterator, entre outros. Clicando nos respectivos links a documentação do conceito em questão é acessada. Então, você irá descobrir quais são os requisitos ou “regras” necessárias para que um tipo de dados satisfaça ou modele o conceito. Por exemplo, o conceito Container determina que devem existir tipos associados chamados value_type, size_type, difference, entre outros. Também determina um conjunto de expressões válidas como begin(), end(), size(), empty(), considerando os retornos e inclusive a semântica.

A pergunta natural então é a seguinte: Os conceitos já existem… já estão documentados… então, o que é exatamente e qual o porque ou necessidade dessa nova funcionalidade?

A resposta é simples e o primeiro ponto é entender como funciona o mecanismo de templates C++. O que acontece quando o compilador encontra uma função template com nome print e que é parametrizada por um tipo T? Grosso modo, ele realiza uma validação sintática superficial, na qual são detectados erros simples como, por exemplo, um ponto e vírgula faltante. Mais tarde no processo de compilação, quando o tipo ticket que você passou para a função print estiver definido, o compilador volta nesta função, substitui T por ticket e realiza uma nova validação sintática, agora mais profunda, para que a função print possa ser instanciada. Somente nessa segunda validação, o compilador tenta encontrar corretamente os tipos que você declarou que T possui (utilizando typename), as chamadas de funções membro que você realizou sobre T, chamadas de funções globais que recebem T como argumento, etc. Ou seja, só na validação posterior o compilador pode, de fato, detectar se alguma operação esperada para o parâmetro T não pôde ser encontrada ou validada para o argumento ticket fornecido para a função.

struct ticket
{
int id;
};

template
void print(T const& t)
{
std::cout << t; } int main() { ticket obj; print(obj); return 0; } [/sourcecode] A parte chata de todo o processo é que você pode cometer um erro e se esquecer de fornecer um operator<< válido para o tipo ticket, como no código acima. Mas o compilador só descobrirá esse problema no momento em que fizer o parse de std::cout << t na função isntanciada (a que contém T substituído por ticket). Particularmente para esse o exemplo, a mensagem de erro é relativamente simples. Porém, em programas mais complexos e que envolvem um número grande de templates as mensagens de erro se tornam gigantescas e pouco inteligíveis. Inclusive, existe até uma ferramenta chamada STLFilt que objetiva “decifrar” as mensagens obscuras geradas por templates na STL.

Resumindo toda a história, o problema é que atualmente os requisitos esperados para um template estão no “papel”. Nós, programadores, trabalhamos com código-fonte. Obviamente, o compilador não conhece o papel e, consequentemente, não possui um mecanismo eficiente para nós auxiliar a escrever código-fonte de maneira consistente. Qual é a solução então? Colocar os conceitos dentro do código-fonte; Formalizá-los; Submetê-los ao compilador para que possamos trabalhar com templates de forma mais segura e menos sujeita a erros; Basicamente, gostaríamos de validar a função print mais ou menos conforme descrito abaixo.

template
/* Se e somente se existe um operator<< válido para T. */ void print(T const& t) { std::cout << t; } [/sourcecode] Apesar de ser uma das principais motivações para a introdução dos conceitos no C++, a idéia de validação sintática conforme no código acima é apenas de suas características. Através dos mapas de conceitos é possível transformar tipos de dados para se comportarem de acordo com os requisitos esperados sem que haja alterações em suas respectivas implementações. Também é possível a criação de axiomas que determinam a semântica esperada para funções associadas a um conceito. Resolução de sobrecarga de templates também levam em consideração os conceitos especificados. Enfim, há vários detalhes nessa nova funcionalidade que trazem um enorme poder de expressão para os templates C++. E tudo sem a necessidade de qualquer relação hierárquica entre os tipos de dados envolvidos. Em um próximo post mostrarei como está ficando a "cara" dos conceitos no novo C++. Para quem quiser sentir um gostinho, deixo um trecho que código que corresponde ao exemplo da função print.

auto concept OutputStreamable
{
std::ostream& operator<<(std::ostream&, const T&); } template
requires OutputStreamable
void print(T const& t)
{
std::cout << t; } struct ticket { int id; }; std::ostream& operator<<(std::ostream& out, ticket const& t) { out << "Id: " << t.id; return out; } int main() { ticket obj; print(obj); return 0; } [/sourcecode]

Leandro T. C. Melo

Read Full Post »

C++ Templates e Java Generics

O mecanismo de templates C++ é um recurso muito poderoso. Na minha opinião, o mais interessante de toda a linguagem de programação C++. Apesar dos exemplos de uso mais comuns nas aulas de programação serem utilizando coleções como std::list<MeuTipo> ou std::vector<MeuTipo>, os templates de C++ podem realizar tarefas muito mais fascinantes do que simples definições de contêineres.

Além de serem fundamentais para a programação genérica, o principal paradigma de desenvolvimento da STL (Standard Template Library) , os templates de C++ são instrumentos indispensáveis na arte da meta-programação. Em poucas palavras, a meta-programação consiste de código-fonte que é manipulado pelo compilador para gerar mais código-fonte. Ou seja, o compilador gerando código-fonte para a gente!

Um exemplo clássico de meta-programação é o cálculo do fatorial de uma constante (em se tratando de templates, é necessário que a informação esteja disponível estaticamente, por isso digo uma constante) em tempo de compilação [Wikipedia]. Mas há inúmeras situações interessantes onde a meta-programação é empregada. Muitas delas podem ser encontradas nas bibliotecas Boost. Considere, por exemplo, o seguinte código-fonte para converter uma constante entre a representação binária e decimal [D. Abrahams/A. Gurtovoy].

#include <iostream>

template <unsigned long N>
struct binary
{
	static unsigned const value =
		binary<N/10>::value * 2 + N%10;
};

template <>
struct binary<0> //Specialization.
{
	static unsigned const value = 0;
};

int main()
{
	std::cout << "1001 -> " << binary<1001>::value << std::endl;
	std::cout << "101001 -> " << binary<101001>::value << std::endl;
	return 0;
}
&#91;/sourcecode&#93;

Diferentemente do que acontece em C++, os generics de Java não definem tipos de verdade e são úteis, basicamente, para detecção de erros durante a compilação. Eles são implementados com uma técnica chamada <a href="http://java.sun.com/docs/books/tutorial/java/generics/erasure.html">Type Erasure</a> , a qual consiste da remoção dos parâmetros genéricos durante a geração do bytecode. Logo, não há informações disponíveis sobre eles em tempo de execução. Considere, por exemplo, a classe <code>Teste</code> abaixo e seu respectivo bytecode. Note que do ponto de vista de execução ambos os membros <code>a</code> e <code>b</code> são tipo <code>Object</code>.


public class Teste<T>
{
    public T a;
    public Object b;
}

Bytecode

Em Java é possível especificar restrições sobre os parâmetros genéricos através do uso de bounded types e wildcards. No padrão C++ atual não há um recurso equivalente. No entanto, qualquer quebra contratual em termos da interface esperada por um template resultará em um erro de compilação da mesma forma. Além disso, uma grande novidade esperada para o C++0x (provavelmente, C++09) são os conceitos (concepts), os quais contribuirão significativamente para o formalismo semântico e amigabilidade na utilização de templates.

Leandro T. C. Melo

Read Full Post »