LP_ResumoPolimorfismo

Prévia do material em texto

Pontif́ıcia Universidade Católica de Minas Gerais
PUC-MG
Trabalho prático I
Pedro Igor Martins dos Reis
Belo Horizonte
2022
Pedro Igor Martins dos Reis
Trabalho prático I
Orientador:
Marco Rodrigo Costa
Belo Horizonte
2022
O texto a seguir é um breve resumo do artigo On understanding types, data
abstraction, and polymorphism de Luca Cardelli e Peter Wegner, de 1985, que aborda
extensamente a respeito dos conceitos de polimorfismo, abstração e tipagem nas
linguagens de programação. O resumo foi complementado com outras fontes que
apresentam pontos de vista diferentes dos autores originais, a ver referências no
final do texto.
1 De universos não tipados para universos tipados
1.1 Universos não tipados
• Apenas um tipo para todos os objetos;
• Sequências de bits na memória do computador;
• Expressões-S em LISP puro;
• Expressões-λ no Cálculo-λ;
• Conjuntos em teoria definida.
1.2 Organização de objetos
Classificação de uso ou comportamento, caracteres, inteiros, listas, pares, funções e
programas.
2 Tipagem forte e estática
2.1 Tipos impõem restrições para aplicar correção
• Proteção da representação subjacente sem tipo definido;
• Limita a interação de objetos.
2.2 Estrutura de programas de tipagem estática
• Pouca ou nenhuma informação de tipo é fornecida explicitamente;
• Tipos associados às constantes/śımbolos de funções;
• O sistema de inferência de tipos infere tipos de expressões por meio de análise
estática.
2.3 Sistema de forte tipagem
• As expressões têm a garantia de consistência de tipo;
• Tipo em si pode ser estaticamente desconhecido;
• Introduz a verificação do tipo de tempo de execução.
1
3 Tipos de polimorfismo
3.1 Linguagens monomórficas
Nas linguagens monomórficas, todas as funções e procedimentos possuem um tipo
único, da mesma forma, todos os valores e variáveis também tem um tipo apenas.
3.2 Linguagens polimórficas
Valores e variáveis podem possuir mais de um tipo e funções polimórficas admitem
operandos de mais de um tipo.
3.3 Polimorfismo universal
• Funções trabalham uniformemente em vários tipos;
• Polimorfismo paramétrico e de inclusão.
3.4 Polimorfismo Ad-hoc
• A função funciona em vários tipos não relacionados;
• Sobrecarga e coerção.
4 Polimorfismo universal
4.1 Polimorfismo paramétrico
• O tipo real é uma função dos parâmetros de tipo;
• Cada aplicação de função polimórfica substitui os parâmetros de tipo;
4.2 Polimorfismo de inclusão
• O valor pertence a vários tipos relacionados por relação de inclusão;
• Sistemas de tipos orientados a objetos.
4.3 Funções genéricas
Em funções genéricas temos funções de comprimento sobre listas e o mesmo trabalho
é realizado para argumentos de diferentes tipos.
2
5 Polimorfismo Ad-hoc
5.1 Sobrecarga
• Mesmo nome denota diferentes funções;
• O contexto decide qual função é denotada pela ocorrência particular de um
nome;
• O pré-processamento pode eliminar a sobrecarga dando nomes diferentes a
funções diferentes.
5.2 Coerção
• As conversões de tipo convertem um argumento em um tipo esperado por uma
função;
• Pode ser fornecido estaticamente em tempo de compilação;
• Pode ser determinado dinamicamente por testes em tempo de execução.
5.3 Polimorfismo aparente
• Operadores e funções possuem apenas um tipo;
• Apenas a sintaxe faz parecer o polimorfismo;
6 Prévia da linguagem FUN
6.1 Linguagem baseada no Cálculo-λ
• Base é o Cálculo-λ de primeira ordem.
• Enriquecido por recursos de segunda ordem para modelagem polimórfica de
linguagens orientadas a objetos.
6.2 Tipos de primeira ordem
Os tipos são: booleanos, inteiros, flutuantes e strings.
6.3 Formas diferentes de quantificadores de tipos
• Quantificação universal: QuantifiedType ::= ∀ A. Type
• Quantificação existencial: QuantifiedType ::= ∃ A. Type
• Quantificação limitada: QuantifiedType ::= ∀ A ⊆ Type. Type | ∃ A ⊆
Type. Type
3
6.4 Modelagem de tipos de sistemas avançados
• Quantificação Universal: tipos parametrizados.
• Quantificadores Existenciais: tipos de dados abstratos.
• Quantificação Limitada: herança.
7 Cálculo-λ não tipado
7.1 Expressões
e ::= x
e ::= fun(x)e
e ::= e(e)
7.2 Introdução de nomes
valueid = fun(x)x
valuesucc = fun(x)x+ 1
valuetwice = fun(f)fun(y)f(f(y))
8 Cálculo-λ tipado
8.1 Extensão do Cálculo-λ não tipado
• Cada variável deve ser explicitamente tipada quando introduzida.
• Os tipos de resultado podem ser deduzidos do corpo da função.
8.2 Exemplos
valuesucc = fun(x : int)x+ 1
valuetwice = fun(f : Int → Int)fun(y : Int)f(f(y))
8.3 Declarações de tipos
typeIntPair = IntxInt
typeIntFun = Int → Int
8.4 Tipos de anotações ou afirmações
(3, 4) : IntPair
valueIntPair : IntPair = (3, 4)
4
8.5 Variáveis locais
let a = 3 in a+ 1
let a : Int = 3 in a+ 1
9 Tipos básicos e estruturados
9.1 Tipos básicos
• Unitário, tipo trivial, apenas elemento ();
• Bool, com if-then-else;
• Int, com aritmética e comparação;
• Real, com aritmética e comparação;
• String, com concatenação infixa.
9.2 Tipos construtores
• Função espacial: ⇒;
• Produto cartesiano: x;
• Tipos registradores;
• Tipos variantes;
9.3 Exemplos
value p : Int x Bool = 3, true
fst(p), snd(p)
10 Tipos registradores
10.1 Exemplos
type ARec = {a : Int, b : Bool}
value r : ARec = {a = 3, b = true}
r.b
10.2 Funções como componentes
type FunRec = {f1 : Int ⇒ Int, f2 : Real ⇒ Real}
value funRec : FunRec = {f1 = succ, f2 = sin}
5
10.3 Concatenação de tipos registradores
type NewRec = FunRec & {f3 : Bool ⇒ Bool}
10.4 Estrutura de dados privados
1 value counter =
2 let count = ref(0) in {
3 inc = fun(n:Int) count := count+n
4 total = fun() count
5 }
6 counter.inc (3), counter.total()
7
11 Tipos de variantes e recursão
11.1 Exemplo
1 type AVar = [a: Int , b: String]
2 value v1: AVar = [a = 3]
3 value v2: AVar = [b = "abcd"]
4 value f = fun(x: AVar)
5 case x of
6 [a = anInt] "int"
7 [b = aString] "string" ^ aString
8 otherwise "error"
9
11.2 Definição de funções recursivas
1 rec value fact =
2 fun(n: Int) if n=0 then 1 else n*fact(n-1)
3
11.3 Definição de tipo recursivo
1 rec type IntList =
2 [nil: Unit
3 cons: {head: Int , tail: IntList} ]
4
12 Quantificação universal
12.1 Cálculo-λ descreve funções monomórficas
Insuficiente para descrever funções que se comportam da mesma forma para argu-
mentos de diferentes tipos.
6
12.2 Tipos como parâmetros
1 value id = all[a] fun(x:a) x
2 id[Int ](3)}
3
12.3 Capaz de omitir informação
1 value id = fun(x:a) x
2 id(3)
3
Verificador de tipos introduz all[a] e [Int].
12.4 Tipos polimórficos
1 type GenericId = forall a. a -> a
2 id: GenericId
3 value inst = fun(f: forall a. a -> a)(f[Int], f[Bool])
4 value intid: Int -> Int = fst(inst(id))
5 value boolid: Bool -> Bool = snd(inst(id))
13 Definições recursivas
13.1 Operadores definidos recursivamente
1 rec type List[Item] =
2 [nil: Unit
3 cons: {head: Item , tail: List[Item]} ]
4 value nil: forall Item.List[Item] = all[Item]. [nil = ()]
5 value intNil: List[Int] = nil[Int]
6 value cons:
7 forall Item. (Item x List[Intem]) -> List[Item] =
8 all[Item].
9 fun(h Item , t: List[Item])
10 [cons = {head = h, tail = t}]
Cons podem ser usados apenas para construir listas homogêneas.
14 Quantificação existencial
p : ∃a. t(a)
14.1 Exemplos
(3, 4) : ∃ a. a x a
(3, 4) : ∃ a. a
No exemplo acima, a constante pode satisfazer diferentes tipos existenciais.
7
14.2 Exemplos de tipos existenciais
• Tipo para qualquer valor: type Top = ∃ a. a
• Tipo para qualquer par: ∃a. ∃ b. a x b
15 Ocultamento de informações
15.1 Tipos abstratos
• Tipos desconhecidos de representação.
• Em conjunto com operações que podem ser aplicadas à representação.
15.2 Uso restrito de tipos de dados
1 value p: exists a. a x (a -> Int)
2 = pack[a = Int in a x (a -> Int)](3,succ)
Sendo que:
• p é um pacote;
• Type a x (a ⇒ Int) seria a interface;
• a=Int seria a representação do tipo.
15.3 Forma geral
1 pack [a = typerep in interface ]( contents)
16 Uso de pacotes
• Pacotes devem ser abertos antes de serem utilizados:
1 value p = pack[a = Int in
2 a x (a -> Int)](3, succ)
3 open p as x in (snd(x))(fst(x))
4 value p = pack[a = Int in
5 {arg: a, op: a -> Int}](3, succ)
• Referência para tipos ocultos:
1 open p as x[b] in ... fun(y:b) (snd(x))(y) ...
8
17 Pacotes e tipos de dados abstratos
17.1 Modelagem de sistema do tipo Ada
• Registros com componentes de função modelam pacotes Ada;
• Quantificação existencial modela tipo abstrato em Ada.
18 Pacotes ADA
1 package point1 is
2 function makepoint(x: Real , y: Real) return Point;
3 function x_coord(P: Point) return Real;
4 function y_coord(P: Point) return Real;
5 end point1;
6
7 package body point1 is
8 function makepoint(x: Real , y: Real) return Point;
9 - - implementation of makepoint
10 function x_coord(P: Point) return Real;
11 - - implementation of x_coord
12 function y_coord(P: Point) return Real;
13 - - implementation of y_coord
14 end point1
A especificação do pacote e o corpo fazem parte da especificação de valor.
19 Estrutura de dados ocultos
19.1 ADA
1 package body localpoint is
2 point: Point;
3 procedure makePoint(x, y: Real); ...
4 function x_coord return Real; ...
5 function y_coord return Real; ...
6 end localpoint
19.2 FUN
1 value localpoint =
2 let p: Point = ref((0,0)) in
3 {makepoint = fun(x: Real , y: Real) p := (x, y),
4 x_coord = fun() fst(p)
5 y_coord = fun() snd(p)}
19.3 Ocultação de informações de primeira ordem
Utiliza construtor let para restringir o escopo no ńıvel de valor (ocultar componentes
de registro).
9
19.4 Ocultação de informações de segunda ordem
Utiliza a quantificação existencial para restringir o escopo no ńıvel do tipo.
1 package point2
2 type Point is private;
3 function makepoint(x: Real , y: Real) return Point;
4 ...
5 private
6 - - hidden local definition of type Point
7 end point2;
8
9 type Point2 =
10 exists Point.
11 {makepoint: (Real x Real) -> Point ,
12 ...}
13 type Point2WRT[Point] =
14 {makepoint: (Real x Real) -> Point ,
15 ...}
16 value point2: Point2 = pack[Point = (Real x Real) in
17 Point2WRT[Point ]] point1
20 Combinando quantificação universal e existen-
cial
20.1 Combinações
• Quantificação universal: tipos genéricos.
• Quantificação existencial: tipos de dados abstratos.
• Combinação: abstrações de dados paramétricos.
1 nil: forall a. List[a]
2 cons: forall a. (a x List[a]) -> List[a]
3 hd: forall a. List[a] -> a
4 tl: forall a. List[a] -> List[a]
5 Null: forall a. List[a] -> Bool
6
7 array: forall a. Int -> Array[a]
8 index: forall a. (Array[a] x Int) -> a
9 update: forall a. (Array[a] x Int x a) -> Unit
21 Pilhas concretas
1 type IntListStack =
2 {emptyStack: List[Int],
3 push: (Int x List[Int]) -> List[Int]
4 pop: List[Int] x List[Int],
5 top:List[Int] -> Int}
6
10
7 value intListStack: IntListStack =
8 {emptyStack = nil[Int],
9 push = fun(a: Int , s: List[Int]) cons[Int](a,s),
10 pop = fun(s: List[Int]) tl[Int](s)
11 top = fun(s: List[Int]) hd[Int](s)}
12
13 type IntArrayStack =
14 {emptyStack: (Array[Int] x Int),
15 push: (Int x (Array[Int] x Int)) -> (Array[Int] x Int),
16 pop: (Array[Int] x Int) x (Array[Int] x Int),
17 top:( Array[Int] x Int) -> Int}
18
19 value intArrayStack: IntArrayStack =
20 {emptyStack = (Array[Int ](100) , -1) ...}
22 Tipos de elementos genéricos
1 type GenericListStack =
2 forall Item.
3 {emptyStack: List[Item],
4 push: (Item x List[Item]) -> List[Item]
5 pop: List[Item] x List[Item],
6 top:List[Item] -> Item}
7
8 value genericListStack: GenericListStack =
9 all[Item]
10 {emptyStack = nil[Item],
11 push = fun(a: Item , s: List[Item]) cons[Item](a,s),
12 pop = fun(s: List[Item]) tl[Item](s)
13 top = fun(s: List[Item]) hd[Item](s)}
14
15 type GenericArrayStack =
16 ...
17
18 value genericArrayStack: GenericArrayStack =
19 ...
23 Ocultando a representação
1 type GenericStack =
2 forall Item. exists Stack. GenericStackWRT[Item][ Stack]
3
4 type GenericStackWRT[Item][ Stack] =
5 {emptyStack = nil[Item],
6 push = fun(a: Item , s: List[Item]) cons[Item](a,s),
7 pop = fun(s: List[Item]) tl[Item](s)
8 top = fun(s: List[Item]) hd[Item](s)}
9
10 value listStackPackage: GenericStack =
11 all[Item]
12 pack[Stack = List[Item]
11
13 in GenericStackWRT[Item][ Stack]]
14 genericListStack[Item]
15 value useStack =
16 fun(stackPackage: GenericStack)
17 open stackPackage[Int] as p[stackRep]
18 in p.top(p.push(3, p.emptystack))
19
20 useStack(listStackPackage)
24 Quantificação e módulos
• Tipo de dados abstrato em conjunto com operadores.
• Pode importar outros módulos conhecidos.
• Pode ser parametrizado com módulos desconhecidos.
• Funções sobre tipos existenciais.
25 Módulos paramétricos
1 type ExtendedPointWRT[PointRep] =
2 PointWRT[PointRep] &
3 {add: (PointRep x PointRep) -> PointRep}
4
5 value ExtendedPoint =
6 exists PointRep. ExtendedPointWRT[PointRep]
7
8 value extendPointPackage =
9 fun(pointPackage: Point)
10 open pointPackage as p[PointRep] in
11 pack[PointRep ’ = PointRep
12 in ExtendedPointWRT[PointRep ’]]
13 p &
14 {add = fun(a: PointRep , b: PointRep)
15 p.mkpoint(p.x-coord(a)+p.x-coord(b),
16 p.y-coord(a)+p.x-coord(b))}
17
18 value extendedCartesianPointPackage =
19 extendPointPackage(cartesianPointPackage)
26 Exemplo de pacotes
26.1 Ćırculos
1 type CircleWRT2[CircleRep , PointRep] =
2 {pointPackage: PointWRT[PointRep],
3 mkcircle: (PointRep x Real) -> CircleRep ,
4 center: CircleRep -> PointRep , ...}
5 type CircleWRT1[PointRep] =
12
6 exists CircleRep. CircleWRT2[CircleRep , PointRep]
7 type Circle = exists PointRep. CircleWRT1[PointRep]
8 value circleModule: CircleModule =
9 all[PointRep]
10 fun(p: PointWRT[PointRep ])
11 pack[CircleRep = PointRep x Real
12 in CircleWRT2[CircleRep ,PointRep ]]
13 {pointPackage = p,
14 mkcircle = fun(m: PointRep , r: Real)(m, r) ...}
15 value cartesianCirclePackage =
16 openCartesianPointPackage as p[Rep] in
17 pack[PointRep = Rep in CircleWRT1[PointRep ]]
18 circleModule[Rep](p)
19 open cartesian CirclePackage as c[PointRep ][ CircleRep]
20 in ...c.mkcircle(c.pointPackage.mkpoint(3, 4), 5) ...
26.2 Retângulos
1 type RectWRT2[RectRep , PointRep] =
2 {pointPackage: PointWRT[PointRep],
3 mkrect: (PointRep x PointRep) -> RectRep , ...}
4
5 type RectWRT1[PointRep] =
6 exists RectRep. RectWRT2[RectRep , PointRep]
7 type Rect = exists PointRep. RectWRT1[PointRep]
8 type RectModule = forall PointRep.
9 PointWRT[PointRep] -> RectWRT1[PointRep]
10
11 value rectModule: RectModule =
12 all[PointRep]
13 fun(p: PointWRT[PointRep ])
14 pack[PointRep ’ = PointRep
15 in RectWRT1[PointRep ’]]
16 {pointPackage = p,
17 mkrect = fun(tl: PointRep , br: PointRep) ...}
26.3 Figuras
1 type FiguresWRT3[RectRep , CircleRep , PointRep] -
2 {circlePackage: CircleWRT[CircleRep , PointRep],
3 rectPackage: RectWRT[RectRep , PointRep],
4 boundingRect: CircleRep -> RectRep}
5
6 type FIguresWRT1[PointRep] =
7 exists RectRep. exists CircleRep.
8 FigureWRT3[RectRep , CircleRep , PointRep]
9 type Figures = exists PointRep. FIgureWRT1[PointRep]
10 type FiguresModule = forall PointRep.
11 PointWRT[PointRep] -> FiguresWRT1[PointRep]
12
13 value figuresModule: FIguresModule =
14 all[PointRep]
15 fun(p: PointWRT[PointRep ])
13
16 pack[PointRep ’ = PointRep
17 in FiguresWRT1[PointRep ]]
18 open circleModule[PointRep ](p) as c[CircleRep] in
19 open rectModule[PointRep ](p) as r[RectRep] in
20 {circlePackage = c, ...}
27 Quantificação delimitada
27.1 Inclusão de tipo
• O tipo A está inclúıdo no (subtipo) tipo B quando todos os valores de A
também são valores de B.
• Relação de inclusão em subfaixas, registros, variantes, função,tipos quantifi-
cados universal e existencialmente.
27.2 Tipo de subintervalo inteiro n . . . m
n...m ≤ n′ ≤ m′ iff n′ ≤ n and m ≤ m′
1 value f = fun(x: 2..5) x+1
2 f: 2..5 -> 3..6
3 f(3)
4 value g = fun(y: 3..4) f(y)
5
27.3 Tipo de função
s ⇒ t ≤ s′ ⇒ t′ iff s′ ⇐ s and t ≤ t′
Função do tipo 3 ...7 também pode ser considerada como função do tipo 4 ...6 ⇒ 6
...10
28 Tipos de registro e herança
28.1 Tipo de registro
{a1 : t1, ..., an : tn, ..., am : tm} ≤ {a1 : u1, ..., an : un}iff ti ≤ ui(foriin1...n)
A é subtipo de B se A tiver todos os campos de B e os tipos dos campos comuns
forem subtipos.
14
28.2 Conceito de herança ou subclasses
• Registros podem ter componentes funcionais;
• A instância de classe é registrada com funções e variáveis locais;
• A instância da subclasse é gravada com pelo menos essas funções e variáveis.
28.3 Tipos variantes
[a1 : t1, ..., an : tn] ≤ [a1 : u1, ..., an : un, ..., am : um]iff ti ≤ ui(foriin1...n)
29 Programação orientada a objetos
No código abaixo, moveX tem o valor do resultado equivalente ao tipo do argumento,
além disto, pode ser aplicado a objetos de tipo ainda desconhecidos.
1 type Point = {x: Int , y: Int}
2 value moveX0 =
3 fun(p: Point , dx: Int) p.x := p.x + dx; p
4 value moveX =
5 all[P <= Point] fun(p:P, dx: Int) p.x := p.x + dx; p
6
7 type Tile = {x: Int , y: Int , hor: Int , ver: Int}
8 moveX[Tile ]({x = 0, y = 0, hor - 1, ver = 1}, 1).hor
30 Quantificação Limitada e Abstração parcial
30.1 Quantificadores existenciais limitantes
∃ a ≤ t. t′
∃ a. t := ∃ a ≤ Top. t
• a é abstrato;
• Sabe que a é subtipo de t ;
• t é mais abstrato que a.
30.2 Construtor de empacotamento modificado
pack [a ≤ t = t′ in t”] e
15
31 Pontos e blocos
1 type Tile = exists P. exists T <= P. TileWRT2[P, T]
2
3 type TileWRT2[P, T] =
4 {mktile: (Int x Int x Int x Int) -> T,
5 origin: T -> P,
6 hor: T -> Int ,
7 ver: T -> Int}
8
9 type TileWRT[P] = exists T <= P. TileWRT2[P, T]
10 type Tile = exists P. TileWRT[P]
11
12 type PointRep = {x: Int , y: Int}
13 type TileRep = {x: Int , y: Int , hor: Int , ver: Int}
1 pack [P = PointRep in TileWRT[P]]
2
3 pack [T <= PointRep = TileRep in TileWRT2[P, T]]
4 {mktile = fun(x:Int , y: Int , hor: Int , ver: Int)
5 {x=x, y-y, hor=hor , ver=ver},
6 origin = fun(t: TileRep) t,
7 hor = fun(t: TileRep) t.hor ,
8 ver = fun(t: TileRep) t.ver}
9
10 fun(tilePack: Tile)
11 open tilePack as t[pointRep ][ tileRep]
12 let f = fun(p: pointRep) ...
13 in f(t.tile(0, 0, 1, 1))
16
32 Interpretação cŕıtica sobre o artigo
Antes de iniciar o resumo, foi realizada uma longa pesquisa em torno do artigo
e dos autores, em mı́dias especializadas e em comunidades focadas no assunto de
programação. Foi posśıvel observar muita discussão sobre o tema, onde não há uma
conclusão firme, apenas infinitos pontos levantados, isso porque o texto favorece
linguagens de programação fortemente tipadas.
O mais interessante do texto seria ver com diversos exemplos e como é posśıvel
relacionar com polimorfismo em Haskell, tópico este que não foi aprofundado no
seminário (TTP). O entendimento do tema foi complicado no ińıcio por se tratar de
elementos puramente abstratos e não tanǵıveis.
1 class Tipavel a where
2 nomeTipo :: a -> String
3 instance Tipavel Int where
4 nomeTipo _ = "Int"
5 instance Tipavel Float where
6 nomeTipo _ = "Float"
7 instance Tipavel Double where
8 nomeTipo _ = "Double"
9 instance Tipavel Char where
10 nomeTipo _ = "Char"
11
O artigo possui demasiadas informações e apresenta topos os pontos completa-
mente, porém como apresenta uma escrita rebuscada e requer uma familiaridade
com álgebra, o texto afastar novos leitores e alunos os quais desejam entender me-
lhor a respeito de abstração e polimorfismo fora da sala de aula. Desta forma, seria
interessante posteriormente realizar uma revisão, já que pode ser material didático
para disciplinas da área da computação.
17
Referências
[1] Cardelli, L., and Wegner, P. On understanding types, data abstraction,
and polymorphism. ACM Computing Surveys (CSUR) 17, 4 (1985), 471–523.
[2] Cook, W. On understanding data abstraction, revisited. Sigplan Notices -
SIGPLAN 44 (10 2009), 557–572.
[3] Reynolds, J. C. User-Defined Types and Procedural Data Structures as Com-
plementary Approaches to Data Abstraction. Springer New York, New York, NY,
1978, pp. 309–317.
18