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