08.type systems

7-1

8Sistemas de Tipos

Polimorfismo de inclusão.

Polimorfismo paramétrico.

Sobrecarga.

Conversões de tipos.

Notas de implementação.

7-2

Polimorfismo de inclusão (1)

Polimorfismo de inclusão é um sistema de tipo no qual um tipo pode ter subtipos, que herdam as operações daquele tipo

• Conceito-chave das linguagem orientadas a objetos

Tipos e subtipos

• Um tipo T é um conjunto de valores equipado com operações

• Um subtipo de T é um subconjunto dos valores de T equipado com as mesmas operações de T

– Todo valor do subtipo também é valor do tipo T, podendo ser usado no contexto onde um valor do tipo T é esperado

– O conceito de subtipos é uma idéia útil e comum em programação

7-3

Exemplo: tipos primitivos e subtipos em Ada

Declarações em Ada definindo subtipos de Integer• subtype Natural is Integer range 0 .. Integer'last;

subtype Small is Integer range -3 .. +3;

• Conjuntos de valores correspondentes

– Natural = {0, 1, 2, 3, 4, 5, 6, ...}Small = {-3, -2, -1, 0, +1, +2, +3}

• Variáveis

– i: Integer; n: Natural; s: Small;

i := n;i := s;

n := i; n := s;s := i; s := n:

Requer verificação em tempo de execução

7-4

Exemplo: tipos e subtipo de registros discriminados em Ada (1)

Declaração de registro discriminado em Ada• type Form is (pointy, circular, rectangular);

type Figure (f: Form := pointy) is record x, y: Float; case f is when pointy => null; when circular => r: Float; when rectangular => h, w: Float; end case; end record;

subtype Point is Figure(pointy); subtype Circle is Figure(circular); subtype Rectangle is Figure(rectangular);

• Conjuntos de valores

– Form = {pointy, circular, rectangular}Figure = pointy(Float × Float) + circular(Float × Float × Float) + rectangular(Float × Float × Float × Float)

7-5

Exemplo: tipos e subtipo de registros discriminados em Ada (2)

Conjunto de valores dos subtipos– Point = pointy(Float × Float)

Circle = circular(Float × Float × Float)Rectangle = rectangular(Float × Float × Float × Float)

Exemplos de variáveis• diagram: array (...) of Figure;

frame: Rectangle; cursor: Point;

7-6


Em linguagens de programação que suportam subtipos, não é possível estabelecer univocamente o subtipo de um valor

Propriedades gerais dos subtipos• Condição necessária para S ser um subtipo de T: S ⊆ T

• O tipo T é equipado com operações que são aplicáveis a todos os valores do tipo T

• Todas essas operações também serão aplicáveis aos valores do subtipo S – S herda as perações de T

7-7


Compatibilidade de tipos na presença de subtipos• V := E

• T1 é compatível com T2 se e somente se T1 e T2 têm valores em comum

– Ou T1 é um subtipo de T2 ou T2 é um subtipo de T1 ou T1 e T2 são subtipos de outro tipo qualquer

• Casos de interesse quando T1 e T2 são compatíveis

– T1 é um subtipo de T2: T1 pode ser usado com segurança num contexto onde um valor de T2 é esperado – não precisa de verificação em tempo de execução

– T1 não é um subtipo de T2: valores do tipo T1 somente podem ser usados após verificação em tempo de execução para determinar se ele também é um valor do tipo T2

tipo = T1tipo = T2

7-8

Classes e subclasses

Uma classe C é um conjunto de objetos equipados com operações• Cada objeto da classe C tem uma ou mais variáveis componentes e

está equipada com métodos que acessam essas variáveis

• Cada objeto de uma subclasse S de C herda todas as variáveis componentes dos objetos da classe C, podendo ter variáveis componentes adicionais

• Cada objeto da classe S potencialmente herda todos os métodos dos objetos da classe C e pode ser equipada com métodos adicionais para acessar tais variáveis

• Qualquer objeto de uma subclasse pode ser usado no contexto onde um objeto da classe C é esperado

Subclasses não são o mesmo que subtipos em geral

7-9

Exemplo: subclasses de Java como subtipos (1)

Considere as classes• class Point {

protected double x, y;

public void draw () {...} }

class Circle extends Point { private double r;


class Rectangle extends Point { private double w, h;


7-10


Conjuntos de valores das classes– Point = Point(Double × Double)

Circle = Circle(Double × Double × Double)Rectangle = Rectangle(Double × Double × Double × Double)

• Nota-se que Circle e Rectangle não são subtipos de Point• Mas são subtipos do tipo Point$ abaixo

– Point$ = Point(Double × Double) + Circle(Double × Double × Double) + Rectangle(Double × Double × Double × Double)

Point$

7-11


Java permite que objetos de qualquer subclasse sejam

tratados como objetos da superclasse• Point p;

...

p= new Point(3.0, 4.0);

...

p= new Circle(3.0, 4.0, 5.0);

– Variáveis do classe Point podem referenciar quaisquer valores do

tipo Point$

• Em geral, se C é uma classe, então C$ inclui não apenas os objetos

da classe C, mas também os objetos de todas as subclasses de C

– C$ é denominada de tipo de classe estendido (class-wide type)

7-12

Exemplo: extensibilidade em Java (1)

Sejam as declarações considerando o exemplo anterior• class Line extends Point {

private double length, orientation;

public void draw () { ... } }

class Textbox extends Rectangle { private String text;

public void draw () { ... } }

• As definições acima não apenas definem os conjuntos de objetos das novas classes

– Line = Line(Double × Double × Double)Textbox = Textbox(Double × Double × String)

7-13

Exemplo: extensibilidade em Java (2)

• como também definem os tipos de classe estendidos abaixo

– Point$ = Point(Double × Double) +

Circle(Double × Double × Double) +

Rectangle(Double × Double × Double × Double) +

Line(Double × Double × Double) +

Textbox(Double × Double × String)

– Rectangle$ = Rectangle(Double × Double × Double × Double) +

Textbox(Double × Double × String)

7-14

Polimorfismo paramétrico (1)

Polimorfismo paramétrico é um sistema de tipos que

permite que se escrevam procedimentos polimórficos

• Um procedimento polimórfico é aquele que pode operar

uniformemente sobre argumentos de toda uma família de tipos

• Um procedimento monomórfico é aquele que somente pode

operar sobre argumentos de um tipo fixo

– Uma função que computar o tamanho de uma lista de caracteres não

pode ser aplicada a listas de inteiros, por exemplo

7-15


Procedimentos polimórficos

• Suportado naturalmente em Haskell

– Basta que se declare o tipo da função utilizando variáveis de tipo, em

vez de tipos específicos

Uma variável de tipo é um identificador que denota um tipo de uma

família de tipos

» Letras romanas minúsculas em Haskell

» Letras gregas nos exemplos do livro-texto (α, β, γ, ...)

7-16

Exemplo: função polimórfica em Haskell (1)

Função monomórfica em Haskell• second (x: Int, y: Int) = y

• Tipo da função

– Integer × Integer → Integer– second(13, 21) resulta no valor 21, mas a chamada

second(13, true) é ilegal, pois os tipos não casam

A versão polimórfica desta função resolve este problema• second (x: σ, y: τ) = y

• Tipo da função

– σ × τ → τ

– σ e τ são variáveis de tipo, cada uma representação de um tipo arbitrário

7-17

Exemplo: função polimórfica em Haskell (2)

• Agora, a chamada da função abaixo é legal

– second(13, true) resulta no valor true

– O tipo da função determinado pelo casamento de tipos é o seguinte

σ Integer e τ Boolean

Substituíndo ambos no tipo σ × τ → τ, tem-se o tipo resultante da aplicação da função

Integer × Boolean → Boolean

Esta função polimórfica aceitas argumentos de muitos tipos, mas não quaisquer argumentos• Apenas pares da forma σ × τ• As chamadas abaixo são ilegais

– second(13)

– second(1978, 5, 5)

7-18


Um politipo deriva uma família de tipos e sempre possui uma ou mais variáveis de tipo∀ σ × τ e σ × τ → τ são exemplos de politipos

• Politipos derivam uma família de tipos pela substituição sistemática das variáveis de tipo por tipos

– A família de tipos derivada por σ × τ → τ , incluem

Integer × Boolean → Boolean String × String → String

– mas não incluem

Integer × Boolean → Integer Integer → Integer String × String × String → String

7-19

Exemplo: função polimórfica em Haskell

Considere a seguinte função monomórfica em Haskell• either (b: Bool) (x1: Char) (x2: Char) =

if b then x1 else x2

• O tipo dessa função é Boolean → Character → Character → Character• translate (x: Char) =

either (isspace x) x '*'

• Nota-se que o tipo do primeiro argumento deve ser Boolean, mas os tipos do segundo e terceiro argumentos não precisão ser!

• either (b: Bool) (x1: τ) (x2: τ) = if b then x1 else x2

• O tipo da função para Boolean → τ → τ → τ

• translate (x: Char) = either (isspace x) x '*'

• max (m: Int, n: Int) = either (m > n) m n'

Aplicação legal da função either

7-20

Tipos parametrizados

Um tipo parametrizado é um tipo que toma outros tipos

como parâmetros

• Pode-se imaginar o τ[] como um tipo parametrizado de C, que pode

ser especializado num tipo ordinário, como char[], ou float[], ou

float[][], pela substituição da variável τ por um tipo real

• Todas as linguagens de programação têm tipos parametrizados pré-

definidos

– C, C++ e Java têm τ[]

– Ada tem array (σ) of e access τ

• Poucas linguagens de programação, como ML e Haskell permitem que

o programador defina seus próprios tipos parametrizados

7-21

Exemplo: tipo parametrizado em Haskell

Definição de um tipo de pares homogêneos• type Pair τ =(τ, τ)

• τ é um parâmetro do tipo e denota um tipo arbitrário

• Uma especialização deste tipo poderia ser

– Pair Int

– com o tipo resultante Integer × Integer, ou seja valores pares de números

inteiros

– ou

– Pair Float

– com o tipo resultante Real × Real, ou seja valores pares de números reais

7-22

Exemplo: tipo parametrizado recursivo em Haskell

Definição de listas homogêneas• data List τ = Nil | Cons (τ, List τ)

• Agora, List Int é um tipo cujos valores são listas de inteiros• head (l: List τ)=

case l of Nil -> ... -- error Cons(x,xs) -> x

tail (l: List τ)= case l of Nil -> ... -- error Cons(x,xs) -> xs

length (l: List τ)= case l of Nil -> 0 Cons(x,xs) -> 1 + length(xs)

List<τ> = Unit + (τ × List<τ>)

head : List<τ> → τ

tail : List<τ> → List<τ>

length: List<τ> → Integer

7-23

Inferência de tipos

A maioria das linguagens estaticamente tipadas requerem que o programador declare explicitamente os tipos usados em toda entidade declarada num programa

• I: constant T := E; I: T; function I (I': T') return T;

Em Haskell, os tipos não precisam ser explicitados – são inferidos do contexto

Inferência de tipos é um processo pelo qual o tipo de uma entidade declarada é inferido, quando não foi explicitamente estabelecido

7-24

Exemplo: inferência de tipos monomórficos em Haskell

Considere a seguinte definição de função• even n = (n 'mod' 2 = 0)

• Sabe-se que o operador mod tem tipo Integer × Integer → Integer

• A partir da subexpressão n 'mod' 2 pode-se inferir que o tipo de n

é Integer

• De forma similar, pode-se inferir que o corpo da função tem o tipo Boolean

• Logo, a função even tem o monotipo Integer → Boolean

• Nem sempre pode inferir um monotipo!

7-25

Exemplo: inferência de tipos polimórficos em Haskell

Considere a seguinte função• f . g =

\x -> f(g(x))

• Nota-se que f e g são funções, que o tipo resultante de g deve ser o mesmo tipo do parâmetro de f, mas nada se pode inferir que tipo é este, ele é um politipo β qualquer

• Nada se pode afirmar dos tipos do parâmetro de g e do valor resultante de f, que podem ser diferentes, eles podem ter os politipos α e γ , respectivamente

• Neste caso, o tipo de x obrigatoriamente é α• Logo, o tipo da função acima é

– (β → γ) → (α → β) → (α → γ)

7-26

Sobrecarga (1)

Um identificador está sobrecarregado se ele denota dois

ou mais procedimentos num mesmo escopo

• Aceitável apenas quando a chamada do procedimento pode ser

feita sem ambigüidade

Pode ser definida pelo programador em Java, C++, Ada,

dentre outras linguagens

7-27

Exemplo: funções sobrecarregadas em C

O operador "–" em C denota simultaneamente quatro

funções pré-definidas

• Negação de inteiros (função com tipo Integer → Integer)

• Negação de ponto-flutuante (função com tipo Float → Float)

• Subtração de inteiro (função com tipo Integer × Integer → Integer)

• Subtração de ponto-flutuante (função com tipo Float × Float → Float)

Nota-se que não há ambigüidade, pois o número e os tipos

dos operandos determinam a função a chamar

7-28

Exemplo: funções sobrecarregadas em Ada

O operador "/" denota duas funções pré-definidas em Ada• Divisão de inteiros (função com tipo Integer × Integer → Integer)• Divisão de ponto-flutuante (função com tipo Float × Float → Float)

Pode-se declarar a função sobrecarregada abaixo• function "/" (m, n: Integer) return Float;

-- Return the quotient of m and n as a real number.

• cujo tipo é (função com tipo Integer × Integer → Float)• Neste caso, a função a chamar vai depender do contexto onde é

aplicada e não apenas dos parâmetros reais• n: Integer; x: Float;

...

• x := 7.0/2.0; - computes 7.0/2.0 = 3.5x := 7/2; - computes 7/2 = 3.5n := 7/2; - computes 7/2 = 3n := (7/2)/(5/2); - computes (7/2)/(5/2) = 3/2 = 1

• Algumas chamadas são ambíguas e ilegais– x := (7/2)/(5/2); - computes (7/2)/(5/2) = 3/2 = 1.5 ou

(7/2)/(5/2) = 3.5/2.5 = 1.5

7-29

Sobrecarga (2)

Suponha um identificador F denotando simultaneamente duas funções f1: S1 → T1 e f2: S2 → T2

• Sobrecarga independente de contexto: requer que S1 e S2 sejam

não equivalentes

– A função a ser chamada sempre pode ser univocamente identificada pelo tipo do parâmetro real

• Sobrecarga dependente de contexto: requer apenas que S1 e S2

sejam não equivalentes ou que T1 e T2 sejam não equivalentes

– Quando S1 e S2 são equivalentes, o contexto onde o F é utilizado deve

ser levado em conta para identificar a função a ser chamada

– Possibilita a formulação de expressões nas quais a função a ser

chamada não pode ser determinada univocamente – tais construções

ambíguas devem ser proibidas

7-30

Sobrecarga (3)

Advertência!

• Não confundir sobrecarga – também conhecido como

polimorfismo ad hoc – com polimorfismo paramétrico

– A sobrecarga não aumenta o poder de expressividade da linguagem

de programação, visto que a quantidade de funções sobrecarregadas

sempre é limitada

– Por outro lado, o polimorfismo paramétrico permite que um

procedimento opere sobre um número potencialmente ilimitado de

variedade de tipos

7-31

Conversão de tipos (1)

Uma conversão de tipos é um mapeamento de valores de

um tipo para valores correspondentes de outro tipo

• Exemplos:

– Mapeamento natural de números inteiros para reais

{..., −2 → −2.0, −1 → −1.0, 0 → 0.0, +1 → +1.0, +2 → +2.0, ...}

– Truncamento e o arredondamento são opções de conversão de tipos

de real para inteiros

– Mapeamento de caracteres para strings de tamanho 1

7-32


Conversões de tipos podem ser mapeamentos totais

• Caracteres para códigos de caracteres, inteiros para reais, ...

Conversões de tipos podem ser mapeamentos parciais

• Códigos de caracteres para caracteres, reais para inteiros, ...

• Mapeamentos parciais podem provocar falhas em programas

7-33


Conversões de tipos podem ser explícitas ou implícitas• Um cast é uma conversão de tipos explícita

– Em C, C++ e Java, um cast tem a forma (T)E

– Em Ada e em Object Pascal, um cast tem a forma T(E)

Caso a subexpressão E é do tipo S – não equivalente a T – e se a

linguagem de programação define uma conversão de tipo de S para T,

então o cast mapeia o valor de E para o valor correspondente de T

• Uma coerção é uma conversão de tipos implícita, realizada automaticamente sempre que o contexto sintático exigir

– Considere a expressão E no contexto do tipo T

Se o tipo de E é S – não equivalente a T – e se a linguagem permite a

coerção de S para T nesse contexto, então a coerção mapeia o valor de E

para o valor correspondente de T

7-34

Exemplo: coerções e Pascal e casts em Ada

Pascal• var n: Integer; x : Real;

...x := n; -- converte o valor de n para um número realn := x; -- ilegal!n := round(x) -- converte o valor de x para um inteiro por arredondamento

Ada• Ada não prover nenhum tipo de coerção• n: Integer; x : Float;

...x := n; -- ilegal! n := x; -- ilegal!x := Float(n) -- converte o valor de n para um número real n := Integer(x) -- converte o valor de x para um inteiro por arredondamento

Algumas linguagens de programação são muitos permissivas em relação às coerções, e. g. C, Java

A tendência é reduzir ou mesmo eliminar coerções nas linguagens de programação mais modernas

7-35

Notas de Implementação (1)

Implementação do polimorfismo paramétrico

• Procedimento polimórficos operam uniformemente sobre argumento de

uma família de tipos

• Opções de implementação

– Gera uma instância separada de procedimento para cada tipo distinto de

argumento

Inviável na prática!

– Representar os valores de todos os tipos de tal modo que eles pareçam

similar para o procedimento polimórfico

Representar cada valor através de um apontador para o objeto na memória

heap

7-36

Notas de Implementação (2)

Considere as funções polimórficas

• Estas funções somente copia valores do tipo τ e isto é implementado

copiando-se os ponteiros para estes valores

– either: Boolean → τ → τ → τ

– second: σ × τ → τ

– head : List<τ> → τ

• Esta implementação de funções paramétricas é simples e uniforme, porém de

alto custo

– Todos os valores – incluindo valores primitivos – devem ser armazenados na

memória heap e acessados através de apontadores

– Espaço na memória deve ser alocado quando eles são usados da primeira vez e

desalocado pelo gerenciador de memória quando não são mais necessários

Documents

08.type systems