Tipo de classe

Da Wikipédia, a enciclopédia livre
Ir para a navegação Saltar para pesquisar

Em ciência da computação , uma classe de tipos é uma construção de sistema de tipos que suporta polimorfismo ad hoc . Isso é obtido adicionando restrições a variáveis ​​de tipo em tipos parametricamente polimórficos . Essa restrição normalmente envolve uma classe de tipo Te uma variável a de tipo e significa que asó pode ser instanciada para um tipo cujos membros dão suporte às operações sobrecarregadas associadas ao T.

As classes de tipo foram implementadas pela primeira vez na linguagem de programação Haskell depois de terem sido propostas por Philip Wadler e Stephen Blott como uma extensão para "eqtypes" no Standard ML , [1] [2] e foram originalmente concebidas como uma maneira de implementar aritmética e igualdade sobrecarregadas operadores de uma forma baseada em princípios. [3] [2] Em contraste com os "eqtypes" do Standard ML, sobrecarregar o operador de igualdade através do uso de classes de tipo em Haskell não requer modificação extensiva do frontend do compilador ou do sistema de tipos subjacente. [4]

Desde sua criação, muitas outras aplicações de classes de tipos foram descobertas.

Visão geral

As classes de tipo são definidas especificando um conjunto de nomes de funções ou constantes, juntamente com seus respectivos tipos, que devem existir para cada tipo que pertence à classe. Em Haskell, os tipos podem ser parametrizados; uma classe de tipo Eqdestinada a conter tipos que admitem igualdade seria declarada da seguinte maneira:

class  Eq  a  where 
  ( == )  ::  a  ->  a  ->  Bool 
  ( /= )  ::  a  ->  a  ->  Bool

onde aé uma instância da classe de tipo Eqe adefine as assinaturas de função para 2 funções (as funções de igualdade e desigualdade), cada uma recebendo 2 argumentos do tipo ae retornando um booleano.

A variável tipo atem tipo (também é conhecido como Typena versão mais recente do GHC ), [5] significando que o tipo Eqde

Eq  ::  Tipo  ->  Restrição

A declaração pode ser lida como afirmando que um "tipo apertence à classe de tipo Eqse houver funções chamadas (==), e (/=), dos tipos apropriados, definidos nela". Um programador pode então definir uma função elem(que determina se um elemento está em uma lista) da seguinte maneira:

elem  ::  Eq  a  =>  a  ->  [ a ]  ​​->  Bool 
elem  y  []      =  False 
elem  y  ( x : xs )  =  ( x  ==  y )  ||  elem  y  xs

A função elemtem o tipo a -> [a] -> Boolcom o contexto Eq a, que restringe os tipos que apodem variar para aqueles aque pertencem à Eqclasse de tipos. ( Nota : Haskell => pode ser chamado de 'restrição de classe'.)

Um programador pode tornar qualquer tipo tum membro de uma determinada classe Cde tipo usando uma declaração de instância que define implementações de todos Cos métodos de um determinado tipo t. Por exemplo, se um programador define um novo tipo de dados t, ele pode então tornar esse novo tipo uma instância de Eqfornecendo uma função de igualdade sobre os valores do tipo tda maneira que achar melhor. Feito isso, eles podem usar a função elemon [t], ou seja, listas de elementos do tipo t.

Observe que as classes de tipo são diferentes das classes em linguagens de programação orientadas a objetos. Em particular, Eqnão é um tipo: não existe um valor de tipo Eq.

As classes de tipos estão intimamente relacionadas ao polimorfismo paramétrico. Por exemplo, observe que o tipo de elemconforme especificado acima seria o tipo parametricamente polimórfico a -> [a] -> Boolse não fosse a restrição de classe de tipo " Eq a =>".

Polimorfismo de tipo superior

Uma classe de tipo não precisa receber uma variável de tipo Type de tipo, mas pode receber uma de qualquer tipo. Essas classes de tipo com tipos mais altos às vezes são chamadas de classes de construtor (os construtores mencionados são construtores de tipo como Maybe, em vez de construtores de dados como Just). Um exemplo é a Monadclasse:

class  Monad  m  where 
  return  ::  a  ->  m  a 
  ( >>= )   ::  m  a  ->  ( a  ->  m  b )  ->  m  b

O fato de m ser aplicado a uma variável de tipo indica que ela possui kind Type -> Type, ou seja, pega um tipo e retorna um tipo, o tipo de Monadé assim:

Mônada  ::  ( Tipo  ->  Tipo )  ->  Restrição

Classes do tipo multiparâmetros

As classes de tipo permitem vários parâmetros de tipo e, portanto, as classes de tipo podem ser vistas como relações em tipos. [6] Por exemplo, na biblioteca padrão GHC , a classe IArrayexpressa uma interface de matriz imutável geral. Nesta classe, a restrição de classe de tipo IArray a esignifica que aé um tipo de matriz que contém elementos do tipo e. (Esta restrição de polimorfismo é usada para implementar tipos de array sem caixa, por exemplo. )

Como multimétodos [ citação necessária ] , classes de tipo multiparâmetros suportam a chamada de diferentes implementações de um método dependendo dos tipos de múltiplos argumentos e, de fato, tipos de retorno. As classes do tipo multiparâmetros não exigem a pesquisa do método a ser chamado em cada chamada em tempo de execução; [7] : minuto 25:12  em vez disso, o método a ser chamado é primeiro compilado e armazenado no dicionário da instância da classe de tipo, assim como nas classes de tipo de parâmetro único.

O código Haskell que usa classes do tipo multiparâmetros não é portátil, pois esse recurso não faz parte do padrão Haskell 98. As implementações populares de Haskell, GHC e Hugs , suportam classes do tipo multiparâmetros.

Dependências funcionais

Em Haskell, as classes de tipo foram refinadas para permitir que o programador declare dependências funcionais entre parâmetros de tipo — um conceito inspirado na teoria de banco de dados relacional . [8] [9] Ou seja, o programador pode afirmar que uma determinada atribuição de algum subconjunto dos parâmetros de tipo determina exclusivamente os parâmetros de tipo restantes. Por exemplo, uma mônada m geral que carrega um parâmetro de estado do tipo ssatisfaz a restrição de classe de tipo Monad.State s m. Nesta restrição, existe uma dependência funcional m -> s. Isso significa que, para uma determinada mônada mdo tipo class Monad.State, o tipo de estado acessível de mé determinado exclusivamente. Isso ajuda o compilador na inferência de tipos, além de auxiliar o programador na programação direcionada ao tipo .

Simon Peyton-Jones se opôs à introdução de dependências funcionais em Haskell por motivos de complexidade. [10]

Classes de tipo e parâmetros implícitos

As classes de tipo e os parâmetros implícitos são muito semelhantes por natureza, embora não sejam exatamente iguais. Uma função polimórfica com uma restrição de classe de tipo, como:

soma  ::  Num  a  =>  [ a ]  ​​->  a

pode ser tratado intuitivamente como uma função que aceita implicitamente uma instância de Num:

soma_  ::  Num_  a  ->  [ a ]  ​​->  a

A instância Num_ aé essencialmente um registro que contém a definição de instância de Num a. (Na verdade, é assim que as classes de tipo são implementadas sob o capô pelo Glasgow Haskell Compiler.)

No entanto, há uma diferença crucial: os parâmetros implícitos são mais flexíveis – você pode passar diferentes instâncias de Num Int. Em contraste, as classes de tipo impõem a chamada propriedade de coerência , que exige que haja apenas uma única escolha de instância para qualquer tipo. A propriedade de coerência torna as classes de tipo um tanto antimodulares, razão pela qual instâncias órfãs (instâncias que são definidas em um módulo que não contém a classe nem o tipo de interesse) são fortemente desencorajadas. Por outro lado, a coerência adiciona um nível adicional de segurança à linguagem, fornecendo ao programador a garantia de que duas partes disjuntas do mesmo código compartilharão a mesma instância. [11]

Como exemplo, um conjunto ordenado (do tipo Set a) requer uma ordenação total dos elementos (do tipo a) para funcionar. Isso pode ser evidenciado por uma restrição Ord a, que define um operador de comparação nos elementos. No entanto, pode haver várias maneiras de impor uma ordem total. Como os algoritmos de conjunto geralmente são intolerantes a mudanças na ordenação após a construção de um conjunto, passar uma instância incompatível de Ord apara funções que operam no conjunto pode levar a resultados incorretos (ou travamentos). Assim, impor a coerência de Ord aneste cenário específico é crucial.

Instâncias (ou "dicionários") em classes do tipo Scala são apenas valores comuns na linguagem, em vez de um tipo de entidade completamente separado. [12] [13] Embora essas instâncias sejam fornecidas por padrão ao encontrar instâncias apropriadas no escopo para serem usadas como parâmetros reais implícitos para parâmetros formais implícitos explicitamente declarados, o fato de serem valores comuns significa que podem ser fornecidos explicitamente, para resolver a ambiguidade. Como resultado, as classes do tipo Scala não satisfazem a propriedade de coerência e são efetivamente um açúcar sintático para parâmetros implícitos.

Este é um exemplo retirado da documentação do Cats [14] :

// Uma classe de tipo para fornecer o 
traço de representação textual  Show [ A ]  { 
  def  show ( f :  A ):  String 
}

// Uma função polimórfica que funciona apenas quando há uma 
// instância implícita de Show[A] disponível 
def  log [ A ]( a :  A )( implicit  s :  Show [ A ])  =  println ( s . show ( a ) )

// Uma instância para String 
implícita  val  stringShow  =  new  Show [ String ]  { 
  def  show ( s :  String )  =  s 
}

// O parâmetro stringShow foi inserido pelo compilador. 
scala >  log ( "uma string" ) 
uma  string

Coq (versão 8.2 em diante) também suporta classes de tipo inferindo as instâncias apropriadas. [15] Versões recentes do Agda 2 também fornecem um recurso semelhante, chamado "argumentos de instância". [16]

Outras abordagens para sobrecarga de operadores

No Standard ML , o mecanismo de "tipos de igualdade" corresponde aproximadamente ao tipo interno de Haskell Eq, mas todos os operadores de igualdade são derivados automaticamente pelo compilador. O controle do processo do programador é limitado a designar quais componentes de tipo em uma estrutura são tipos de igualdade e quais variáveis ​​de tipo em um intervalo de tipos polimórficos sobre tipos de igualdade.

Os módulos e functores de SML e OCaml podem desempenhar um papel semelhante ao das classes de tipos de Haskell, sendo a principal diferença o papel de inferência de tipos, que torna as classes de tipos adequadas para polimorfismo ad hoc . [17] O subconjunto orientado a objetos do OCaml é outra abordagem que é um pouco comparável à das classes de tipos.

Noções relacionadas

Uma noção análoga para dados sobrecarregados (implementada no GHC ) é a de tipo family . [18]

Em C++ , notavelmente o C++20 tem suporte para classes de tipo usando o Concepts (C++) . Como ilustração, o exemplo Haskell mencionado acima de typeclass Eq seria escrito como

modelo < nome do tipo T >  
conceito  igual = 
      requer ( T a , T b ) {     
            { a == b } -> std :: convertible_to < bool > ;      
            { a != b } -> std :: convertible_to < bool > ;      
};

No tipo Clean , as classes são semelhantes ao Haskell, mas têm uma sintaxe ligeiramente diferente.

Rust suporta traits , que são uma forma limitada de classes de tipo com coerência. [19]

Mercury tem classes de tipos, embora não sejam exatamente as mesmas que em Haskell. [ explicações adicionais necessárias ]

Em Scala , as classes de tipo são um idioma de programação que pode ser implementado com recursos de linguagem existentes, como parâmetros implícitos, não um recurso de linguagem separado em si. Por causa da maneira como eles são implementados em Scala, é possível especificar explicitamente qual instância de classe de tipo usar para um tipo em um local específico no código, em caso de ambiguidade. No entanto, isso não é necessariamente um benefício, pois as instâncias de classe de tipo ambíguo podem ser propensas a erros.

O assistente de prova Coq também oferece suporte a classes de tipo em versões recentes. Ao contrário das linguagens de programação comuns, no Coq, quaisquer leis de uma classe de tipo (como as leis da mônada) que são declaradas dentro da definição de classe de tipo, devem ser matematicamente provadas de cada instância de classe de tipo antes de usá-las.

Veja também

Referências

  1. ^ Morris, John G. (2013). Classes de tipos e cadeias de instâncias: uma abordagem relacional (PDF) (PhD). Departamento de Ciência da Computação, Portland State University. doi : 10.15760/etd.1010 .
  2. ^ a b Wadler, P.; Blott, S. (1989). "Como tornar o polimorfismo ad-hoc menos ad hoc" . Anais do 16º Simpósio ACM SIGPLAN-SIGACT sobre Princípios de Linguagens de Programação (POPL '89) . Associação de Máquinas de Computação. págs. 60-76. doi : 10.1145/75277.75283 . ISBN 0897912942. S2CID  15327197 .
  3. ^ Kaes, Stefan (março de 1988). "Sobrecarga paramétrica em linguagens de programação polimórficas". Proc. 2º Simpósio Europeu de Linguagens de Programação . doi : 10.1007/3-540-19027-9_9 .
  4. ^ Recurso, AW; MacQueen, DB (1991). "Padrão ML de Nova Jersey" . Em Maluszyński, J.; Wirsing, M. (eds.). Implementação de Linguagem de Programação e Programação Lógica. PLILP 1991 . Notas de aula em Ciência da Computação. Vol. 528. Springer. págs. 1–13. CiteSeerX 10.1.1.55.9444 . doi : 10.1007/3-540-54444-5_83 . ISBN  3-540-54444-5.
  5. ^ Type deData.Kindapareceu na versão 8 do Glasgow Haskell Compiler
  6. ^ página Haskell' MultiParamTypeClasses .
  7. No GHC, o C Core usa as assinaturas de tipo System F da Girard & Reynold para identificar um caso tipado para processamento nas fases de otimização. -- Simon Peyton-Jones " Into the Core - Squeezing Haskell into Nine Constructors" Erlang User Conference, 14 de setembro de 2016
  8. ^ Jones, Mark P. (2000). "Classes de tipo com dependências funcionais" . Em Smolka, G. (ed.). Linguagens e Sistemas de Programação. ESOP 2000 . Notas de aula em Ciência da Computação. Vol. 1782. Springer. págs. 230–244. CiteSeerX 10.1.1.26.7153 . doi : 10.1007/3-540-46425-5_15 . ISBN  3-540-46425-5.
  9. ^ página Haskell' FunctionalDependencies .
  10. ^ Peyton-Jones, Simon (2006). "MPTCs e dependências funcionais" . Lista de discussão Haskell-prime .
  11. ^ Kmett, Eduardo. Classes de tipo contra o mundo . Encontro de Boston Haskell. Arquivado a partir do original em 21/12/2021.
  12. ^ Oliveira, Bruno CdS; Mouros, Adriano; Odersky, Martin (2010). "Classes de tipo como objetos e implícitos" (PDF) . Anais do ACM International Conference on Object Oriented Programming Systems Languages ​​and Applications (OOPSLA '10) . Associação de Máquinas de Computação. págs. 341-360. CiteSeerX 10.1.1.205.2737 . doi : 10.1145/1869459.1869489 . ISBN   9781450302036. S2CID  207183083 .
  13. ^ "Guia do Neófito para Scala Parte 12: Classes de tipos - Daniel Westheide" .
  14. ^ typelevel.org, Scala Cats
  15. ^ Castéran, P.; Sozeau, M. (2014). "Uma introdução suave às classes de tipos e relações em Coq" (PDF) . CiteSeerX 10.1.1.422.8091 .  
  16. ^ " Modelagem de classes de tipo com argumentos de instância ".
  17. ^ Dreyer, Derek; Harper, Robert; Chakravarty, Manuel MT (2007). "Classes de tipo modular". Anais do 34º Simpósio Anual ACM SIGPLAN-SIGACT sobre Princípios de Linguagens de Programação (POPL '07) . págs. 63-70. Veja pág. 63. doi : 10.1145/1190216.1190229 . ISBN 978-1595935755. S2CID  1828213 . TR-2006-03.
  18. ^ "Famílias GHC/Tipo - HaskellWiki" .
  19. ^ Turon, Aaron (2017). "Especialização, coerência e evolução da API" .

Links externos