7-1
7Abstração Genérica
Unidades genéricas e instanciação.
Tipos e classes parâmetros.
Notas de implementação.
7-2
Unidades genéricas e instanciação (1)
Uma unidade genérica é uma unidade de programa que é parametrizada em relação às entidades das quais ela depende
A instanciação de uma unidade genérica cria uma unidade de programa ordinária, na qual, cada parâmetro formal da unidade é trocado por um argumento
• Gera sob demanda uma família de unidades de programas
similares, evitando a redundância de código
• Favorece a reusabilidade porque uma mesma unidade de programa
pode ser instanciada em diferentes programas
7-3
Unidades genéricas e instanciação (2)
Unidades genéricas seguem o princípio da abstração
• Uma unidade genérica é uma abstração sobre uma declaração
– Possui um corpo – a declaração – e uma instanciação genérica é uma
declaração que produzirá ligações pela elaboração do corpo da
unidade genérica
Unidades genéricas são suportadas por Ada, C++ e Java
em diferentes perspectivas
7-4
Exemplo: pacotes genéricos em Ada (1)
Ada suporta pacotes genéricos e procedimentos genéricos
generic capacity: Positive; package Queues is
type Queue is limited private; procedure clear (q: out Queue); procedure add (q: in out Queue; e: in Character); procedure remove (q: in out Queue; e: out Character);
private
type Queue is record length: Integer range 0 .. capacity; front, rear: Integer range 0 .. capacity-1; elems: array (0 .. capacity-1) of Character; end record;
end Queues;
Parâmetro formal baseado em valor
7-5
Exemplo: pacotes genéricos em Ada (2)
package body Queues is procedure clear (q: out Queue) is begin q.front := 0; q.rear := 0; q.length := 0; end; procedure add (q: in out Queue; e: in Character) is begin q.elems(q.rear) := e; q.rear := (q.rear + 1) mod capacity; q.length := q.length + 1; end; procedure remove (q: in out Queue; e: out Character) is begin e := q.elems(q.front); q.front := (q.front + 1) mod capacity; q.length := q.length - 1; end;
end Queues;
7-6
Exemplo: pacotes genéricos em Ada (3)
Pacotes genéricos em Ada são instanciados por uma forma
especial de declaração denominada instantiation
• package Line_Buffers is new Queues(120);
• package Input_Buffers is new Queues(80);
A instanciação resulta num pacote ordinário
• inbuf: Input_Buffers.Queue;
...
Input_Buffers.add(inbuf, '*');
Argumentos da instanciaçãoArgumentos da instanciação
7-7
Exemplo: pacotes genéricos em C++ (1)
C++ suporta funções genéricas (function templates) e classes genéricas (class templates)
template <int capacity> class Queue {
private: char elems[capacity]; int front, rear, length;
public:
Queue ();
void add (char e);
char remove ();
}
Parâmetro formal da classe genérica – denota um valor inteiro a ser conhecido durante a instanciação
7-8
Exemplo: pacotes genéricos em C++ (2)
Definição de construtores e métodos em separado
template <int capacity>Queue<capacity>::Queue () { front = rear = length = 0; }
template <int capacity> void Queue<capacity>::add (char e) { elems[rear] = e; rear = (rear + 1) % capacity; length++; }
template <int capacity> char Queue<capacity>::remove () { char e = elems[front]; front = (front + 1) % capacity; length--; return e; }
7-9
Exemplo: pacotes genéricos em C++ (3)
Instanciação de pacotes genéricos
• typedef Queue<80> Input_Buffer;
typedef Queue<120> Line_Buffer;
A instanciação resulta em classes nas quais os parâmetros
formais são substituídos pelo valor do argumento• Input_Buffer inbuf;
Line_Buffer outbuf;
Line_Buffer errbuf;
• ou
• Queue<80> inbuf;
Queue<120> outbuf;
Queue<120> errbuf;
7-10
Exemplo: pacotes genéricos em C++ (4)
A instanciação on the fly de classes genéricas resulta num problema conceitual e em outro de ordem pragmática• O problema conceitual diz respeito a equivalência de tipos
– Duas variáveis outbuf e errbuf declaradas com tipos Queue<120> e Queue<120> são equivalentes
– Mas se duas variáveis são declaradas com tipos Queue<m> e Queue<n-1>, o compilador não tem como decidir se os tipos são equivalentes
– instanciações em C++ devem obrigatoriamente poder avaliar seus argumentos em tempo de compilação
• O problema pragmático pode levar o programador a perder o controle sobre a expansão de código
– Se Queue<120> ocorre em vários locais do código, um compilador não profissional pode gerar várias instâncias de Queue, enquanto um profissional geraria apenas uma única instância
Estes problemas não ocorrem em Ada!
7-11
Tipos e classes parâmetros
Como uma unidade de programa usa um valor definido em qualquer lugar, a unidade de programa pode tornar-se genérica e parametrizada com relação a esse valor• Graças ao princípio da correspondência
Como uma unidade de programa usa um tipo (ou classe) definido em qualquer lugar, a unidade de programa pode tornar-se genérica e parametrizada com relação a esse tipo• Tem-se uma nova modalidade de parâmetro: o parâmetro que é um
tipo (ou uma classe)
Unidade genéricas em Ada, C++ e Java podem ter tipos como parâmetros
7-12
Exemplo: tipo parâmetro em Ada (1)
Uma unidade genérica em Ada pode ser parametrizada com respeito a qualquer tipo do qual ela dependa
generic type Element is private; package Lists is type List is limited private; procedure clear (l: out List); procedure add (l: in out List; e: in Element); ... private capacity: constant Integer := ...; type List is record length: Integer range 0 .. capacity; elems: array (1 .. capacity) of Element; end record; end Lists;
Parâmetro formal do pacote genérico – denota um tipo a ser conhecido durante a instanciação
7-13
Exemplo: tipo parâmetro em Ada (2)
O parâmetro formal Element é usado tanto da especificação do pacote, quanto no seu corpo
package body Lists is procedure clear (l: out List) is begin l.length := 0; end;
procedure add (l: in out List; e: in Element) is begin l.length := l.length + 1; l.elems(l.length) := e; end;
...
end Lists;
7-14
Exemplo: tipo parâmetro em Ada (3)
Instanciação do pacote genérico Lists– package Phrases is new Lists(Character);
• O parâmetro formal Element é ligado ao tipo Character (argumento na instanciação)
• Depois, a especificação e o corpo de Lists são elaborados, gerando um pacote que encapsula uma lista com elementos do tipo Character
– sentence: Phrases.List; ... Phrases.add(sentence, '.');
• Outra opção– type Transaction is record ... end record;
... package Transaction_Lists is new Lists(Transaction);
7-15
Exemplo: tipo e função parâmetro em Ada (1)
Se uma unidade genérica não sabe nada sobre o tipo
parâmetro – exceto o nome – ela ainda assim pode declarar
variáveis desse tipo, mas não pode aplicar nenhuma
operação sobre tais variáveis!
Unidades genéricas devem saber pelo menos algumas das
operações aplicáveis ao tipo parâmetro
– Tipicamente, as operações de atribuição e de teste de igualdade
7-16
Exemplo: tipo e função parâmetro em Ada (2)
generic type Element is private; with function precedes (x, y: Element) return Boolean; package Sequences is type Sequence is limited private; procedure clear (s: out Sequence); procedure append (s: in out Sequence; e: in Element); procedure sort (s: in out Sequence);
private
capacity: constant Integer := ...;
type Sequence is record length: Integer range 0 .. capacity; elems: array (1 .. capacity) of Element; end record; end Sequences;
Parâmetro formal que denota a uma função desconhecida que recebe dois argumentos do tipo Element e retorna um resultado do tipo Boolean
7-17
Exemplo: tipo e função parâmetro em Ada (3)
O corpo do pacote usa o tipo Element e a função precedes, parâmetros da unidade genérica
package body Sequences is ...
procedure sort (s: in out Sequence) is e: Element; begin ... if precedes(e, s.elems(i)) then ... ... end;
end Sequences;
7-18
Exemplo: tipo e função parâmetro em Ada (4)
Possível instanciação de Sequences type Transaction is record ... end record;
function earlier (t1, t2: Transaction) return Boolean; -- Return true if and only if t1 has an earlier timestamp than t2.
package Transaction_Sequences is new Sequences(Transaction, earlier);
que pode ser usada como um pacote comum audit_trail: Transaction_Sequences.Sequence;
... Transaction_Sequences.sort(audit_trail);
Outros exemplos package Ascending_Sequences is new Sequences(Float, "<");
readings: Ascending_Sequences.Sequence; ... Ascending_Sequences.sort(readings);
7-19
Exemplo: tipo e função parâmetro em Ada (5)
Em geral, se uma unidade genérica em Ada tem um tipo parâmetro T, ele é especificado pela cláusula• type T is especificação das operações que equipam T;
O compilador verifica a unidade genérica para assegurar que• operações usadas por T na unidade genérica nas operações com as
quais T está equipada
O compilador verifica separadamente cada instanciação da unidade genérica para assegurar que• operações com as quais T está equipada nas operações que equipam
o tipo que é passado como argumento
Uma vez implementada, as unidades genéricas em Ada podem ser reusada com segurança em relação a verificação de tipos
7-20
Exemplo: tipo parâmetro em C++ (1)
Unidades genéricas em C++ podem ser parametrizadas em relação a quaisquer tipos ou classes das quais elas dependam
template <class Element> class Sequence is
private:
const int capacity = ...; int length; Element elems[capacity];
public:
Sequence ();
void append (Element e);
void sort ();
}
Parâmetro formal que denota a um tipo qualquer desconhecido, e não apenas tipos que são classes
7-21
Exemplo: tipo parâmetro em C++ (2)
Implementação segue como usual
template
<class Element>
void Sequence<Element>::sort () {
Element e;
...
if (e < elems[i]) ...
...
}
• A utilização do operador "<" é perfeitamente legal, pois assume-se
que o tipo denotado por Element "estará" equipado com tal operador
– O compilador rejeitará instanciações para tipos argumentos que não
sejam equipados com o operador "<"
7-22
Exemplo: tipo parâmetro em C++ (3)
Exemplos de instanciações
typedef Sequence<float> Number_Sequence; Number_Sequence readings; ... readings.sort();
typedef char* String; typedef Sequence<String> String_Sequence;
struct Transaction { ... }; typedef Sequence<Transaction> Transaction_Sequence;
Esta instanciação será recusada pelo compilador, pois o operador "<" não equipa o tipo Transaction
O operador "<" será utilizado, mas o resultado não será o desejado! Por que?
7-23
Exemplo: tipo parâmetro em C++ (4)
Em geral, se uma unidade genérica em C++ tem um tipo parâmetro T, ele é especificado pela cláusula• <class T>
que não revela nada sobre as operações que equipam T. O compilador verifica cada instanciação da unidade genérica para assegurar que • operações usadas por T na unidade genérica nas operações que
equipam o tipo que é passado como argumento
As unidades genéricas de C++ não são uma fundação segura para reuso de software• O compilador não é capaz de verificar completamente os tipos numa
definição de unidade genérica, mas apenas instanciações individuais
7-24
Exemplo: classe genérica em Java com classe parâmetro (1)
Unidades genéricas foram introduzidas em Java com o lançamento da plataforma Java 2SE 5.0 em 2004• Classes genéricas – classes que podem ser parametrizadas em relação
a outras classes
class List <Element> { private int length; private Element[] elems;
public List () { ... }
public void append (Element e) { ... }...}
Parâmertro formal da classe genérica List e denota uma classe desconhecida a priori
7-25
Exemplo: classe genérica em Java com classe parâmetro (2)
Instanciação de classes genéricas
List<Character> sentence;
List<Transaction> transactions;
O argumento na instanciação deve ser uma classe – tipos
primitivos são proibidos
List<char> sentence;
Instanciação ilegal!
7-26
Exemplo: classe genérica em Java com classe parâmetro limitada pela interface (1)
Caso uma classe genérica assuma que a classe parâmetro está equipada com operações, a classe parâmetro deve ser especificada como implementando uma interface adequada
• Diz-se que tal classe parâmetro é limitada (bounded) pela interface
class Sequence <Element implements Comparable<Element>> { private int length; private Element[] elems;
public Sequence () { ... }
public void append (Element e) { ... }
public void sort () { Element e; ... if (e.compareTo(elems[i] < 0) ... ... }}
Element é um parâmetro formal que denota uma classe desconhecida, mas que deve implementar a interface Comparable, onde o método compareTo está especificado
7-27
Exemplo: classe genérica em Java com classe parâmetro limitada pela interface (2)
Possível instanciação da classe genérica Sequence
Sequence<Transaction> auditTrail;...auditTrail.sort();
assumindo que a classe Transaction é declarada assim
Class Transaction implements Comparable<Transaction> {
private ...;
public int compareTo(Transaction that) { ... }
...
}
7-28
Exemplo: classe genérica em Java com classe parâmetro limitada pela interface (3)
Em geral, se uma unidade genérica em Java tem uma classe parâmetro C, ela é especificada pela cláusula• C implements Interface;
O compilador verifica a unidade genérica para assegurar que• operações usadas por C na unidade genérica nas operações
declaradas em Interface
O compilador verifica separadamente cada instanciação da unidade genérica para assegurar que• operações declaradas na Interface nas operações que equipam a
classe passada como argumento
Uma vez implementada, as unidades genéricas em Java podem ser reusadas com segurança em relação a verificação de tipos
Desvantagens da classes genéricas em Java
• Somente classes podem ser parâmetros de classes
genéricas
• Tipos primitivos são proibidos – conseqüência da
incompletude de tipos em Java
• Não podem ser parametrizadas por valores dos quais
dependam
7-29
Notas de Implementação
Unidades genéricas com tipos parâmetros suscitam
interessantes problemas de implementação
• Como o tipo parâmetro denota um tipo desconhecido, o
compilador não pode determinar, apenas da unidade genérica,
como os valores do tipo serão representados
– Não há como saber o espaço de memória requerido, por exemplo
• Somente quando a unidade genérica é instanciada é que o
compilador pode saber essa informação
7-30
Exemplo: implementação de unidades genéricas em Ada (1)
7-31
Exemplo: implementação de unidades genéricas em Ada (2)
As três instanciações anteriores definem três tipos distintos
• A.List
• B.List
• C.List
Em geral, cada instanciação de um pacote genérico de Ada
é compilado, com a geração de código objeto
especializado para cada instanciação
• Em casos específicos, diferentes instanciações podem compartilhar
o mesmo código objeto – quando os tipos envolvido têm
representações similares
7-32
Exemplo: implementação de unidades genéricas em C++
Similar a implementação em Ada, mas com uma
complicação extra
• As classes genéricas de C++ podem ser instanciadas on the fly
– Um código de programa pode conter várias declarações de variáveis
do tipo
List<float>
– No sistema de tipos de C++, todas estas variáveis têm o mesmo tipo,
logo estão equipadas com as mesmas operações
– O desafio para o compilador é fazer com que todas estas variáveis
compartilhem o mesmo código objeto
7-33
Exemplo: implementação de unidades genéricas em Java (1)
A implementação de classes genéricas em Java é
simplificada porque elas só podem ser parametrizadas em
relação a classes, que sempre são acessadas através de
apontadores