UNIVERSIDADE FEDERAL DE SANTA CATARINA GRADUAÇÃO SISTEMAS DE INFORMAÇÃO DISCIPLINA – DESENV. SISTEMAS OO II ALUNOS – DANIEL T. CARDOSO, LEANDRO AMANCIO, EDUARDO B. HADLICH

PROGRAMAÇÃO GENÉRICA

Florianópolis, 20 de Março de 2002.

1. Programação Genérica

O presente texto visa apresentar o paradigma de programação genérica, abordando aspectos como utilização, funcionalidades, vantagens e desvantagens. Ela foi introduzida por David R. Musser e Alexander A. Stepanov com o objetivo de desenvolver uma biblioteca baseada em algoritmos genéricos.

Programação genérica é uma sub-disciplina da ciência da computação que lida com a criação de representações abstratas de algoritmos concretos, estruturas de dados e outros conceitos de software. Alguns objetivos comuns são listados, dentre eles citamos a facilidade de expressar algoritmos sem se procupar com abstrações de dados e migrar de um algoritmo concreto para um nível mais elevado de abstração – nível genérico – sem perder eficiência, por exemplo, quando a forma mais abstrata de um determinado algoritmo é especialidada em tempo de compilação resulta em um algortimo de igual eficiência ao algoritmo concreto do qual ele foi abstraído.

Os tipos de abstrações são definidos basicamente em dois: as abstrações de dados, que são basicamente abstrações de tipos de dados e conjuntos de operações definidas sobre eles e as abstrações de algoritmos, que são famílias de abstrações de dados as quais possuem um conjunto de algoritmos concretos em comum - estes são os chamados algoritmos genéricos.

Hoje em dia diversas linguagens de programação suportam a programação genérica, a mais usada é C++, através da biblioteca STL. Seu uso no desenvolvimento de software vai ao encontro dos benefícios pregados pela programação orientada a objetos, os dois assuntos visam a reusabilidade como uma meta a ser alcançada. Programação genérica visa quase que exclusivamente isso: utilizar uma classe genericamente implementada em diversas aplicações que necessitem de um artefato com caracteristicas semelhantes, variando apenas no tipo de dado que é manipulado, como uma lista de números, uma lista de pessoas ou uma lista de livros.

2. Templates

Achamos por bem falar sobre STL (biblioteca padrão de C++ - Standard Template Library) pois é, atualmente, o melhor exemplo de programação genérica que temos. Porém, antes de falarmos sobre STL devemos primeiro falar sobre o mecanismo utilizado para seu desenvolvimento: os Templates.

Templates são uma abordagem para programação genérica, uma estratégia de programação na qual conjuntos de algoritmos são parametrizados por uma variedade de tipos de dados/estruturas de dados adequadas. O mecanismo de Templates em C++ permite que um tipo seja uma parâmetro na definição de uma classe ou função. Seu uso abre novas possibilidades na linguagem, tais como a descrição de algoritmos que se executam em tempo de compilação, a geração otimizada de códigos, mais fácil compreensão e manutenção de software. Além disso promove principalmente a reutilização de código: o desenvolvedor escreve o código uma única vez e a linguagem que existe dentro da linguagem de compilação (em tempo de compilação) copia e compila o código quantas vezes forem necessárias com cada tipo de dado diferente. Em tempo de compilação é que é visto a necessidade de se criar o código com determinado tipo de dado.

O uso de Templates se mostrou essencial no projeto da biblioteca padrão de C++ (STL), uma vez que as estruturas e algoritmos lá definidos devem ser de uso geral sem comprometer sua eficiência. Assim, vários algoritmos podem ser usados com várias estruturas de dados.

Um template não causa perda de desempenho: a transformação de um template "abstrato" em uma classe "concreta" é feita em tempo de compilação. E também não implica na redução da quantidade de código gerado: se em um projeto existem duas classes derivadas de um template, o código será gerado de forma equivalente à definição direta de duas classes não relacionadas, em outras palavras, o compilador gera duas classes distintas e que não têm relação alguma. Seria como se o desenvolvedor tivesse escrito o código de duas classes e as compilasse, porém o código é escrito uma só vez mas compilado duas vezes com tipos de dados diferentes formando duas classes diferentes que foram compiladas. Inclusive, por isso deve-se ter o cuidado de evitar inundar a memória com muitas definições quase iguais geradas a partir de um template, ou seja, sempre que possível deve-se chamar pela mesma definição de template para não deixar o código muito grande. Por exemplo se já existe uma definição de uma classe a partir de um template que trabalha com reais, talvez, não seja necessário definir uma nova classe para operar sobre inteiros, mas sim fazer uma conversão de inteiros para reais e chamar a classe já definida.

Templates são usados tanto para definição de classes genéricas como de funções genéricas. No caso de funções geradas a partir de um template todas terão o mesmo nome, de modo que o compilador usa o conceito de sobrecarga para invocar a função apropriada. O processo de correspondência para achar qual função foi invocada se dá da seguinte maneira: Primeiro o compilador tenta achar uma função na qual o nome da função e os tipos de parâmetros coincidem exatamente com aqueles da chamada de função para poder utilizar a função. Se isto falha o compilador verifica se está disponível um template com nome e parâmetros correspondentes para gerar uma nova função e então utilizá-la. Caso também não encontre é gerado um erro de compilação.

Para concluir e entender a real necessidade de Templates é exposto o seguinte exemplo genérico: conhecemos o conceito e o comportamento de uma pilha (“último a entrar é o primeiro a sair”) sem mesmo saber dos tipos de itens que estão inseridos nela. Mas quando chega no momento de efetivamente instanciar uma pilha, um tipo de dados deve ser especificado. Isso cria uma excelente oportunidade para reutilização de software. Necessitamos de meios de descrever a noção de pilha genericamente e instanciar classes que são versões desta classe genérica de pilha para tipos específicos de pilha. Este recurso é fornecido por Templates.

3. STL

Nos anos 70, os componentes utilizados eram estruturas de controle e funções. Já nos anos 80, usava-se classes de diversas bibliotecas dependentes de plataformas. No final da década de 90, com a STL, surge um novo passo no uso de componentes – as bibliotecas de classes independentes de plataformas.

Na reunião da ANSI/ISO em julho 1994, o comitê de padrões C++ realizou votação para adotar a STL como parte da biblioteca de padrões C++. Desenvolvida por Alexander Stepanov, Meng Lee, e David Musser, na Hewlett-Packard, a STL (Standard Template Library) está entre as mais conceituadas bibliotecas de componentes.

Para entender melhor como funciona a STL é necessário conhecer três elementos chaves que a compõem – conteineres, algoritmos e iteradores.

Conteineres podem ser entendidos como estruturas de dados comuns (listas, pilhas, filas...), implementadas de forma que sejam adaptáveis para conter o tipo de dado relevante para a aplicação. Já os algoritmos, que também são genéricos, são utilizados para manipular os conteineres, ou seja, ações como inserir, deletar, procurar, classificar são obtidas através de algoritmos. Iteradores tem por objetivo servir como elo de ligação entre algoritmos e conteineres.

Um fator chave na STL está no fato de diversos conteineres poderem estar associados a diferentes algoritmos. Isto so é permitido com o uso correto de iteradores que apontam para elementos de um contêiner, e evitam erros que poderiam ocorrer com a manipulação de ponteiros. O código baseado em ponteiros é complexo, e a menor omissão, ou desatenção pode conduzir a sérias violações de acesso e erros de “perda de memória” sem reclamações do compilador.

A STL foi cuidadosamente planejada para que os conteineres forneçam funcionalidades similares, de forma que existam operações genéricas e outras operações que se aplicam a subconjuntos de conteineres similares. Esta separação torna mais fácil escrever algoritmos genéricos consistentes, aplicáveis a muitas outras classes de conteineres. Como exemplos pode-se citar a função size (retorna o número de elementos presentes no contêiner), que pode ser aplicada em qualquer contêiner e a função eraser (apaga um ou mais elementos de um contêiner) que so é utilizada por um subconjunto de conteineres.

Antes da STL, as bibliotecas de classe de conteineres e algoritmos de diferentes fornecedores eram essencialmente incompatíveis. As bibliotecas de contêiner antigas geralmente usavam herança e polimorfismo e os algoritmos eram construídos nas classes de conteineres, como comportamento das classes. A STL separa algoritmos dos conteineres, permitindo assim, que diferentes algoritmos se associem a diferentes conteineres através de iteradores.

Buscar soluções para determinados problemas no desenvolvimento de softwares na STL permite uma economia de tempo e esforço consideráveis de programação além de obter, como resultado final, softwares de maior qualidade. O desenvolvedor não perde tempo na construção de componentes que já existem na biblioteca, algoritmos e estruturas de dados, que já estão implementados e otimizados ao máximo, são reutilizados.

4. Conclusão

Como foi visto a programação Genérica se propõe a geração de código independente de tipos específicos, porém para isso, a principal dificuldade está relacionada com tempo despendido e a complexidade para se fazer estruturas e algoritmos genéricos. É menos trabalhoso pensar e fazer um software pensando nos problemas específicos desse software (gerando código específico e não reutilizável) do que analisar e descobrir pontos genéricos (gerando códigos genéricos) para reuso tanto dentro do próprio software quanto para reuso em outros software’s.

Outra dificuldade é com relação ao fato de que nem toda linguagem promove mecanismos para se realizar códigos genéricos como por exemplo C++ ou Ada. Isso faz com que desenvolvedores de outras linguagens muitas vezes não conheçam a programação genérica ou então não a utiliza devido a complexidade de ter de migrar seu software para uma linguagem que permita a programação genérica.

Também pode ser considerada uma dificuldade na sua utilização o fato de que não existem meios adequados de modelagem para programação genérica, fazendo com que código e especificação se tornem diferentes, o que pode dificultar a compreensão das pessoas que desenvolverão sobre esses termos.

Apesar disso a Programação Genérica vem se difundindo cada vez mais, visto que após a trabalhosa conclusão da elaboração dos códigos genéricos, tem-se como resultado algoritmos e estruturas genéricas que podem ser usados em várias aplicações diferentes, e vários algoritmos genéricos que podem interagir com várias estruturas genéricas e vice-versa. Com isso as vantagens adquiridas são muitas, tais como a descrição de algoritmos que se executam em tempo de compilação, a geração otimizada de códigos, aumento de algoritmo e estruturas concretas para um nível mais genérico sem perder a eficiência, mais fácil compreensão, manutenção e principalmente a reutilização de código, economia de tempo e esforço, maximização do desempenho e produção de software de maior qualidade, a medida que se usa algoritmos e estruturas já testadas e depuradas. Prova disso são as facilidades que os desenvolvedores ganham ao programar em C++ devido à STL, a maior e melhor biblioteca genérica de que se tem notícia até hoje.

Todas essas vantagens que se obtém como consequências em se utilizar a programação genérica são um importante atrativo que faz com que cada vez mais desenvolvedores procurem a generalização de seu código.

5. Bibliografia

- C++: como programar/ H.M. Deitel e P.J Deitel; trad. Carlos Arthur Lang Lisbôa, 3.ed. – Porto Alegre : Bookman, 2001

- Followup to a Dagstuhl Seminar Held April 27 – May 1, 1998 Schlob Dagstuhl, Wadern, Germany.

- David R. Musser, Alexander A Stepanov, Generic Programming – Rome, Italy, July 4-8, 1988.