implementacao.org

Implementação de Tipos

1 Implementação de Tipos

Tipos Primitivos

• Geralmente suportados pelo hardware
• Operações e valores possíveis predefinidos
• Elementos de primeira ordem
  • Inteiro
  • Ponto Flutuante
  • Caractere
  • …

\pause Tipos definidos pelo usuário

• Manipular estruturas não suportadas pela linguagem
• Tornar o programa mais legível
• Mais propenso a detecção de erros
• \pause Projeto da linguagem deve prever “construtores de tipo”
  • Restrição
  • Enumeração
  • Composição (Tipos Estruturados)

2 Tipo Inteiro

Java

byte, short, int, long

C, C++, Objective-C

int, long, long long
unsigned int, unsigned long, unsigned long long

Ada

Integer, Long_Integer, Long_Long_Integer
Modular Types (mod) : Last + 1 == 0 == First

O caso do tipo \texttt{long} do Python

243487532863295237631293218657236152427355863621263L

\pause Tamanho ocupado por um inteiro?
Vejamos os códigos em Ada e C: \texttt{size.adb} e \texttt{size.c}

\pause Como implementar o sinal (negativo ou não)?

• Complemento para dois

3 Tipo Ponto Flutuante

Aproximação para números reais

Representação binária de tamanho finito

float = 4 bytes, double = 8 bytes /* em C */

Representação mais encontrada: mantissa e expoente

Quantos bits para mantissa e expoente?

• \pause IEEE Floting-Point Standard 754
  • float: 1 bit + 8 bits + 23 bits
  • double: 1 bit + 11 bits + 52 bits

\pause Cálculo/Análise numérica

• Aplicações de simulação física
• Precisa de mais precisão ainda

4 Tipo Caractere

Quanto espaço ocupa cada caractere?

Qual a codificação utilizada?

• ASCII (no máximo 128 caracteres)
• ISO 8859-1 (no máximo 256 caracteres)
• Unicode → UTF-8

Maioria das linguagens tem um tipo caractere

char c;
sizeof(char) = 1 byte

5 Tipo Cadeia de Caracteres

Como definir o tamanho de uma cadeia?

\pause Abordagem estática, tamanho não muda

• Python, Java (class String), C++, Ruby, C#

\pause Abordagem dinâmica limitada

• C

  char str[10];
      

\pause Abordagem dinâmica

• JavaScript, Perl

\pause Ada95 suporta os três tipos

Standard.String
Ada.Strings.Bounded.Bounded_String
Ada.Strings.Unbounded.Unbounded_String

\pause Como implementar essas diferentes abordagens?

• Estática e Dinâmica Limitada são simples (uma alocação)
• Dinâmica (Listas encadeadas, Vetor de ponteiros, Células adjacentes de memória)

6 Tipos de usuário por restrição

Subsequência de um tipo existente

Exemplos em Pascal

type maiusculas = 'A'..'Z';
type dias = 1..31;

Ada

type Dias is (Seg, Ter, Qua, Qui, Sex, Sab, Dom);
subtype DiasUteis is Dias range Seg..Sex;
subtype Indice is Integer range 1..100;

7 Tipos de usuário por enumeração 1

Valores desejados são explicitados

Exemplos em C/C++/Objective-C

• Associação implícita

  enum Cores {Vermelho, Verde, Azul};
      

• \pause Associação explícita

  enum Romanos {I=1, V=5, X=10, L=50,
                C=100, D=500, M=1000};
  enum Cartas {dois=2, tres, quatro, cinco, seis,
               sete, oito, nove, dez, valete,
               dama, reis, as};
      

\pause Implementação com inteiros em C/C++/Objective-C

\pause Problemas

Cores minhaCor = Azul;
minhaCor++; /* qual cor agora? */
minhaCor = 4; /* C++ dá erro */

8 Tipos de usuário por enumeração 2

Ada permite literais sobrecarregados

type Primary_Color is (Red, Green, Blue);
type Traffic_Light is (Red, Yellow, Green);

\pause Java 5.0 (suporte a partir de 2004)

• Tipos por enumeração são subclasses de \texttt{enum}

  public Enum Dia { Seg, Ter, Qua, Qui, Sex, Sab, Dom };
      

• \pause Campos são instâncias

\pause C#

• Nunca são transformados para inteiros
• Restrições que permitem boa detecção de erros

\pause Nenhuma das linguagens de script recentes suporta

• Python, PHP, JavaScript, Perl, Ruby

9 Tipos de usuários por composição

Restrição e enumeração nem sempre são suficientes

Tipos Compostos

• Define um novo tipo de dado dito estruturado
• Utiliza tipos primitivos
• Pode ser homogêneo ou heterogêneo

Homogêneo – todos os membros do mesmo tipo

Heterogêneo – membros de tipos diferentes

\pause Métodos de composição

• Produto cartesiano
• Mapeamento finito
• Sequência
• União
• Conjunto potência

10 Método de Composição versus Tipos

Método	Formato	Tipo Resultante
Produto cartesiano	Heterogêneo	registro, estrutura, classe
Mapeamento finito	Homogêneo	arranjo, mapa, vetor
Sequência		cadeia, arquivo
União discriminada	Heterogêneo	variant, registro, união
Conjunto potência		conjunto

11 Estruturas – \texttt{struct}

Permite fazer uma união de diferentes tipos

• Cada componente é chamado de campo

struct element {
  char name[2];
  int atomic_number;
  double atomic_weight;
  _Booleano metallic;
};

\pause Pode-se aninhar definições

struct {
   char name[30];
   struct {
      char name[2];
      int atomic_number;
      double atomic_weight;
      _Booleano metallic;
   } element_yielded;
};

\pause Qual é o tamanho em memória da primeira estrutura?

• Vamos ver codigo \texttt{struct.c}

12 Estruturas – \texttt{union}

Permite economizar ocupação em memória

union {
   int i;
   double d;
   _Booleano b;
};

\pause Duas utilizações possíveis

• Programas de sistema (mesma região de memória deve ser tratada diferentemente em momentos distintos)
• \pause Representar campos alternativos em uma estrutura \scriptsize

  struct {
     char *lexema;
     int tipo_token;
     union {
        char *identificador;
        double flutuante;
        int inteiro;
        char *cadeia_literal;
     };
  };