Embed Size (px)
Citation preview
Tópicos
• Introdução• Tipos de Dados Primitivos• Tipos Cadeia de Caracteres• Tipos Definidos pelo Usuário• Tipos Matriz• Matrizes Associativas• Tipos Registro• Tipos União• Tipos Conjunto• Tipos Ponteiro
Introdução
• Um tipo de dado define uma coleção de dados e um conjunto de operações pré-definidas sobre esses dados
• Um descritor é um conjunto de atributos de uma variável
• Um objeto representa uma instância de um tipo de dado abstrato definido pelo usuário
• Uma questão fundamental de projeto:– Quais operações são fornecidas para variáveis do tipo e
como elas são especificadas?
Tipos de Dados Primitivos
• Tipos de dados não-definidos em termos de outros tipos são chamados tipos de dados primitivos
• Praticamente todas as linguagens de programação oferecem um conjunto de tipos de dados primitivos
• Alguns tipos de dados primitivos são reflexos do hardware– Por exemplo: os inteiros
• Outros exigem um pequeno suporte de software para sua implementação
Tipos de Dados Primitivos: Inteiro
• Quase sempre um reflexo do hardware– Assim, seu mapeamento é trivial
• Muitos computadores suportam diferentes tamanhos para inteiros
• Em Java, diferentes tamanhos para inteiros– byte, short, int, long
Tipos de Dados Primitivos: Ponto-flutuante
• Modelam os números reais, mas são aproximações
• Linguagens para fins científicos suportam pelo menos dois tipos ponto-flutuante (float e double)
• IEEE Floating-Point Standard 754
Tipos de Dados Primitivos: Ponto-flutuante
Tipos de Dados Primitivos: Decimal
• Para aplicações comerciais (moeda)– Essencial para COBOL– C# oferece um tipo de dado decimal
• Armazena um número fixo de dígitos decimais
• Vantagem– Precisão
• Desvantagens– Faixa de valores restrita– Desperdício de memória
Tipos de Dados Primitivos: Booleano
• Mais simples de todos
• Faixa de valores– Dois elementos, um para “true” e um para
“false”
• Pode ser implementado como bits, mas geralmente são como bytes– Vantagem: legibilidade
Tipos de Dados Primitivos: Caractere
• Armazenados como codificações numéricas
• O código mais usado: ASCII
• Uma alternativa, codificação de 16-bit: Unicode– Inclui caracteres da maioria das linguagens naturais– Usado em Java– C# e JavaScript também suportam Unicode
Tipos Cadeia de Caracteres
• Valores consistem em seqüências de caracteres
• Questões de projeto:– É um tipo primitivo ou apenas um tipo
especial de vetores de caracteres?
– As cadeias devem ter tamanho estático ou dinâmico?
As Cadeias e Suas Operações
• Operações típicas:– Atribuição e cópia
– Comparação (=, >, etc.) – Concatenação
– Referências a subcadeias– Pattern matching
Cadeias nas Linguagens
• C e C++– Não primitivo– Usam vetores char e uma biblioteca de funções que
oferecem operações (string.h)
• SNOBOL4 (uma linguagem de manipulação de cadeias)– Primitivo– Muitas operações, incluindo pattern matching elaborados
• Java
– Primitivo através da classe String
Opções de Tamanho da Cadeia
• Estático– COBOL, FORTRAN 90, Pascal, Ada e Java classe String
• Tamanho dinâmico limitado: C e C++– Um caractere especial é usado para indicar o final da cadeia,
em vez de manter seu tamanho
• Dinâmico (sem máximo): SNOBOL4, Perl, JavaScript
• Ada suporta todas as opções acima
Tipos Cadeia de Caracteres:Avaliação
• São importantes para a capacidade de escrita de uma linguagem
• Como um tipo primitivo com tamanho estático, não é caro– Por que não usá-las?
• Tamanho dinâmico é mais flexível– Mas o custo compensa?
Implementação dos Tipos Cadeias de Caracteres
• Tamanho estático– descritor em tempo de compilação
• Tamanho dinâmico limitado– Podem exigir um descritor em tempo de execução
para armazenar tanto o tamanho máximo como o tamanho atual (mas não em C e C++)
• Tamanho dinâmico– Exigem um descritor em tempo de execução– Exigem um gerenciamento de armazenagem mais
complexo• Alocação e desalocação
Implementação dos Tipos Cadeias de Caracteres
Implementação dos Tipos Cadeias de Caracteres
Tipos ordinais definidos pelo usuário
• Um tipo ordinário é aquele cuja faixa de valores possíveis pode ser associada ao conjunto dos números inteiros positivos– Tipos Enumeração– Tipos Subfaixa
• Exemplos de tipos ordinários em Java– integer
– char
– boolean
Tipos Enumeração
• Todos os valores possíveis, os quais se tornam constantes simbólicas, são enumerados na definição
• Exemplo C# enum days {mon, tue, wed, thu, fri,
sat, sun};
Tipos Enumeração
• Questões de projeto
– Deve-se permitir que um literal constante apareça em mais de uma definição de tipo e, se assim for, como o tipo de uma ocorrência desse literal é verificado no programa?
– É possível fazer coerção de valores de enumeração para inteiros?
Tipos Enumeração: Avaliação
• Vantagens em termos de legibilidade– Não é necessário codificar uma cor como
um número
• Vantagens em termos de confiabilidade– Operações (não permite adicionar cores) – Nenhum variável de enumeração será
assinalada para valores fora de sua faixa
Tipos Subfaixa
• É uma subsequência de um ordinal– Exemplo: 12..18 é uma subfaixa dos inteiros
• Projeto em Adatype Days is (mon, tue, wed, thu, fri, sat, sun);
subtype Weekdays is Days range mon..fri;
subtype Index is Integer range 1..100;
Day1: Days;
Day2: Weekday;
Day2 := Day1;
Tipos Subfaixa: Avaliação
• Legibilidade– Informam ao leitor que as variáveis podem
armazenar apenas uma faixa de valores
• Confiabilidade– A atribuição de um valor a uma variável fora
de sua faixa pode ser detectado pelo compilador como sendo um erro
Tipos Matriz
• Uma matriz é um agregado homogêneo de dados cujo elemento individual é identificado por sua posição no agregado em relação ao primeiro.
Questões de Projeto
• Quais tipos são legais para os subscritos?• As expressões de subscrito nas referências a
elementos são verificados quanto à faixa?• Quando as faixas de subscrito são vinculadas?• Quando a alocação da matriz se desenvolve?• Quantos subscritos são permitidos?• Matrizes podem ser inicializadas quando têm seu
armazenamento alocado?• Quais tipos de fatias são permitidos, se for o caso?
Matrizes e Índices
• Índices (ou subscritos) fazem mapeamento para elementosarray_name(index_value_list) → element
• Sintaxe do Índice– FORTRAN, PL/I e Ada usam parênteses
• Ada usa parênteses para mostrar uma uniformidade entre matrizes e chamadas de funções, pois ambos são mapeamentos
– Outras linguagens usam colchetes
Tipos dos Índices
• FORTRAN, C: apenas inteiros
• Pascal: qualquer tipo ordinário– inteiro, Boolean, Char, enumeração
• Ada: inteiro ou enumeração (incluindo Boolean e Char)
• Java: apenas inteiros
• C, C++, Perl e Fortran não especificam faixa para checagem
• Java, ML e C# especificam a checagem da faixa
Vinculações de Subscritos e Categorias de Matrizes
• Matriz Estática– As faixas de subscrito estão estaticamente
vinculadas e a alocação de armazenamento é estática (feita antes da execução)
– Vantagem: eficiência (em alocação dinâmica)
• Matriz Fixa Dinâmica na Pilha– Faixas de subscrito estão estaticamente
vinculadas, mas a alocação é feita no momento da declaração durante a execução
– Vantagem: eficiência de espaço
• Matriz Dinâmica na Pilha– Faixas de subscritos estão dinamicamente
vinculadas e a alocação de armazenamento é dinâmica (feita durante a execução)
– Vantagem: flexibilidade (o tamanho de uma matriz não precisa ser conhecido antes da sua utilização)
• Matriz Dinâmica no Monte– A vinculação das faixas dos índices e a alocação
são dinâmicas e podem mudar várias vezes– Vantagem: flexibilidade (matrizes podem crescer
ou encolher durante a execução do programa)
Vinculações de Subscritos e Categorias de Matrizes
• Matrizes C e C++ que incluem static são estáticas
• Matrizes C e C++ sem static são fixas dinâmicas na pilha
• Matrizes Ada podem ser dinâmicas na pilha• C e C++ também oferecem matrizes dinâmicas
(malloc e free)• Perl e JavaScript suportam matrizes dinâmicas
Vinculações de Subscritos e Categorias de Matrizes
Inicialização de Matrizes
• Algumas linguagens permitem a inicializaçãono momento em que o armazenamento é alocado– Exemplos: C, C++, Java e C#
• int list [] = {4, 5, 7, 83}
– Cadeias de caracteres em C e C++• char name [] = “freddie”;
– Matrizes de strings em C e C++• char *names [] = {“Bob”,“Jake”,“Joe”];
– Java inicialização de objetos String• String[] names = {“Bob”, “Jake”, “Joe”};
Operações com Matrizes
• APL permite poderosas operações para matrizes, como também operadores unários– Exemplo: inverte os elementos das colunas
• Ada permite atribuição e concatenação de matrizes
• FORTRAN oferece operações elementarespois são operações entre pares de elementos de matriz– Exemplo: operador + entre duas matrizes resulta em
uma matriz que é a soma dos pares de elementos das duas matrizes
Fatias
• Uma fatia (slice) de uma matriz é alguma subestrutura desta
• Fatias são úteis em linguagens que possuem operadores sobre matrizes
Fatias: Exemplos
• Fortran 95Integer, Dimension (10) :: Vector
Integer, Dimension (3,3) :: Mat
Integer, Dimension (3,3,3) :: Cube
Vector (3:6) é um vetor de 4 elementos
Fatias: Exemplos
Acessando Matrizes (multidimensionais)
• Duas maneiras comumente usadas
– Ordem da linha maior (por linhas)• Usado na maioria das linguagens
– Ordem da coluna maior (por colunas)• Usando em Fortran
Acessando Matrizes (multidimensionais)
• Exemplo de matriz3 4 76 2 51 3 8
• Ordem da linha maior (por linhas)– 3,4,7,6,2,5,1,3,8
• Ordem da coluna maior– 3,6,1,4,2,3,7,5,8
Localizando um elemento em uma matriz multidimensional
Formato geral
location (a[i,j]) = address of a[row_lb,col_lb] +
(((I - row_lb)*n) + (j - col_lb)) * element_size
Matrizes Associativas
• Uma matriz associativa é um conjunto não-ordenado de elementos indexados por um número igual de valores chamados chaves– Chaves definidas pelos usuários devem ser
armazenadas
• Questões de projeto– Qual é a forma de referência dos elementos?– O tamanho de uma matriz associativa é estático
ou dinâmico?
Matrizes associativas em Perl
• Nomes começam com %; literais são delimitados por parênteses%hi_temps = ("Mon"=>77, "Tue"=>79,
“Wed”=>65, …);
• Os nomes de variáveis escalares iniciam-se com $$hi_temps{"Wed"} = 83;
– Elementos podem ser removidosdelete $hi_temps{"Tue"};
Tipos Registro
• Um registro é um agregado possivelmente homogêneo de elementos de dados
• Cada elemento individual é identificado por seu nome
• Questões de projeto– Qual é a forma sintática das referências a campos? – São permitidas referências elípticas?
Definições de Registros
COBOL usa números para aninhar registros; outras linguagens usam definições recursivas
01 EMP-REGISTER.
02 EMP-NAME.
05 FIRST PIC X(20).
05 MID PIC X(10).
05 LAST PIC X(20).
02 HOURLY-RATE PIC 99V99.
Definição de Registros em Ada
type Emp_Rec_Type is record
First: String (1..20);
Mid: String (1..10);
Last: String (1..20);
Hourly_Rate: Float;
end record;
Emp_Rec: Emp_Rec_Type;
Referências a Campos do Registro
• A maioria das linguagens usam um ponto na notação– Emp_Rec.Name
• Referências elípticas (exemplo em Pascal)empregado.nome := ‘Bob’;empregado.idade := 42;empregado.salario := 23750.0;
with empregado dobegin
nome := ‘Bob’;idade := 42;salario := 23750.0;
end;
Avaliação e comparação com matrizes
• O projeto de registros é direto e, seu uso, seguro
• Registros são usados quando os dados formam uma coleção heterogênea
• Acesso aos elementos das matrizes são mais lentos do que para registros, pois os índices são dinâmicos (nomes de campos são estáticos)
• Índices dinâmicos podem ser usados para acessar campos dos registros, mas rejeitaria a verificação de tipos e também seria mais lento
Implementação de Tipos Registro
Tipos União
• Uma união é um tipo que pode armazenar diferentes valores de tipo durante a execução do programa
• Questões de projeto– A verificação de tipos deve ser exigida?
• Note que qualquer verificação de tipos deve ser dinâmica.
Discriminantes vs. Uniões Livres
• Fortran, C e C++ oferecem construções de união que não há nenhum suporte na linguagem para verificação de tipos– A união nessas linguagens são chamadas de
uniões livres
• A verificação de tipos em uniões exige que cada construtor de união inclua um indicador de tipo, chamado discriminante
– Suportado por Pascal e por Ada
Uniões em Ada
type Shape is (Circle, Triangle, Rectangle);
type Colors is (Red, Green, Blue);
type Figure (Form: Shape) is record
Filled: Boolean;
Color: Colors;
case Form is
when Circle => Diameter: Float;
when Triangle =>
Leftside, Rightside: Integer;
Angle: Float;
when Rectangle => Side1, Side2: Integer;
end case;
end record;
Estrutura de um registro variante
Uma união discriminada de três variáveis de forma
Avaliação de Uniões
• Construções potencialmente inseguras– Não permitem verificação de tipos das
referências a uniões– Um dos motivos pelos quais FORTRAN,
Pascal, C e C++ não são fortemente tipificadas
• Java e C# não suportam uniões– Reflexo da crescente motivação por
linguagens de programação mais seguras
Tipos Ponteiro
• Um tipo ponteiro é aquele em que as variáveis têm uma faixa de valores que consistem em endereços de memória e um valor especial, nil
• Oferece o poder de endereçamento indireto
• Oferece uma alternativa para gerenciar endereçamento dinamicamente
Questões de projeto de ponteiros
• Quais são o escopo e o tempo de vida de uma variável de ponteiro?
• Qual é o tempo de vida de uma variável dinâmica no monte?
• Os ponteiros são restritos quanto ao tipo de valor para o qual eles apontam?
Operações com Ponteiros
• Duas operações fundamentais– Atribuição e desreferenciamento
• Atribuição é usada para fixar o valor de uma variável de ponteiro em um endereço útil
• Desreferenciamento referencia o valor da célula de memória (não apenas o endereço)– Dereferenciamento pode ser implícito ou explícito– C++ usa uma operação explícita *j = *ptr
fixará j ao valor ao valor alocado em ptr
Ilustração de atribuição de ponteiro
A operação de atribuição j = *ptr
Problemas com Ponteiros
• Ponteiros Pendurados (Dangling pointers)– Um ponteiro que contém o endereço de uma variável dinâmica
no monte desalocada
• Variáveis dinâmicas no monte perdidas– Uma variável dinâmica no monte alocada não mais acessível
ao programa usuário (geralmente chamada de lixo)• Ponteiro p1 é ajustado para apontar para uma variável dinâmica
no monte recém-criada• Mais tarde, ponteiro p1 é ajustado para outra variável dinâmica no
monte recém-criada
• Vazamento de memória
Sumário
• Os tipos de dados de uma linguagem são uma grande parte daquilo que determina o seu estilo e seu uso
• Os tipos de dados primitivos da maioria das linguagens imperativas incluem os tipos numérico, caractere e booleano
• Os tipos enumeração e a subfaixa definidos pelo usuário são convenientes e aumentam a legibilidade e a confiabilidade dos programas
• Matrizes e registros estão presentes na maioria das linguagens de programação
• Ponteiros são usados para dar flexibilidade de endereçamento e para controlar o gerenciamento de armazenamento dinâmica
