8 Sistemas de Tipos Polimorfismo de inclusão. Polimorfismo paramétrico. Sobrecarga. Conversões de tipos. Notas de implementação. 7-1 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-2 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; Requer verificação em tempo de execução n := i; n := s; s := i; s := n: 7-3 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-4 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-5 Polimorfismo de inclusão (2) 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-6 Polimorfismo de inclusão (3) Compatibilidade de tipos na presença de subtipos • V := E tipo = T2 tipo = T1 • 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 7-7 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-8 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; public void draw () {...} } class Rectangle extends Point { private double w, h; public void draw () {...} } 7-9 Exemplo: subclasses de Java como subtipos (2) 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-10 Exemplo: subclasses de Java como subtipos (3) 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-11 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-12 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-13 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-14 Polimorfismo paramétrico (2) 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-15 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) second(13, resulta no valor 21, mas a chamada 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-16 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-17 Polimorfismo paramétrico (3) 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-18 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 either legal da função 7-19 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-20 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-21 Exemplo: tipo parametrizado recursivo em Haskell List<> = Unit + ( List<>) 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 head : List<> tail : List<> List<> length: length (l: List )= case l of Nil -> 0 Cons(x,xs) -> 1 + length(xs) List<> Integer 7-22 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-23 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-24 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-25 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-26 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-27 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 x n n := := := := 7.0/2.0; 7/2; 7/2; (7/2)/(5/2); - computes computes computes computes 7.0/2.0 = 3.5 7/2 = 3.5 7/2 = 3 (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-28 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-29 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-30 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-31 Conversão de tipos (2) 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-32 Conversão de tipos (3) 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-33 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 real n := 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 7-34 linguagens de programação mais modernas 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-35 Notas de Implementação (2) Considere as funções polimórficas • Estas funções somente copia valores do tipo copiando-se os ponteiros para estes valores e isto é implementado – 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 7-36