O sistema de tipos de Haskell é formalmente equivalente ao de Java? [fechadas]

66

Sei que algumas coisas são mais fáceis / difíceis em um idioma que no outro, mas estou interessado apenas em recursos relacionados ao tipo que são possíveis em um e impossíveis / irrelevantes no outro. Para torná-lo mais específico, vamos ignorar as extensões do tipo Haskell, já que existem muitas por aí que fazem todo tipo de coisas loucas / legais.

GlenPeterson
fonte
4
Também estou curioso para ouvir os teóricos da categoria há muito tempo respondendo a essa pergunta; embora duvide que o entenda particularmente, ainda estou interessado em um detalhamento disso. Minha inclinação a partir de coisas que eu li é que o sistema de tipos HM permite que o compilador para conhecer uma tonelada sobre o que seu código faz é por isso que ele é capaz de inferir tipos muito bem como dar tantas garantias sobre o comportamento. Mas esse é apenas o meu instinto e tenho certeza de que há outras coisas das quais não tenho consciência.
Jimmy Hoffa
11
Essa é uma ótima pergunta - é hora de twittar para os seguidores do grande debate Haskell / JVM!
Martijn Verburg
6
@ m3th0dman: O Scala tem exatamente o mesmo suporte para funções de ordem superior que o Java. No Scala, funções de primeira classe são simplesmente representadas como instâncias de classes abstratas com um único método abstrato, assim como Java. Certamente, o Scala possui um açúcar sintático para definir essas funções e possui uma rica biblioteca padrão de tipos de funções e métodos predefinidos que aceitam funções, mas, de uma perspectiva do sistema de tipos , que é essa a questão, não há diferença. . Portanto, se o Scala pode fazer isso, o Java também pode e, de fato, existem bibliotecas FP para Java inspiradas em Haskell.
Jörg W Mittag
2
@ m3th0dman: Não é sobre isso que se trata.
Phil
7
@ m3th0dman São tipos perfeitamente comuns. Não há nada de especial nas listas, exceto algumas sutilezas sináticas. Você pode definir facilmente seu próprio tipo de dados algébrico equivalente ao tipo de lista interno, exceto a sintaxe literal e os nomes dos construtores.
sepp2k

Respostas:

63

("Java", conforme usado aqui, é definido como padrão Java SE 7 ; "Haskell", conforme usado aqui, é definido como padrão Haskell 2010. )

Coisas que o sistema de tipos de Java tem, mas o de Haskell não:

  • polimorfismo do subtipo nominal
  • informações do tipo de tempo de execução parcial

Coisas que o sistema de tipos de Haskell tem, mas o Java não:

  • polimorfismo ad-hoc limitado
    • gera polimorfismo de subtipo "baseado em restrições"
  • polimorfismo paramétrico de tipo superior
  • digitação principal

EDITAR:

Exemplos de cada um dos pontos listados acima:

Exclusivo para Java (em comparação com Haskell)

Polimorfismo do subtipo nominal

/* declare explicit subtypes (limited multiple inheritance is allowed) */
abstract class MyList extends AbstractList<String> implements RandomAccess {

    /* specify a type's additional initialization requirements */
    public MyList(elem1: String) {
        super() /* explicit call to a supertype's implementation */
        this.add(elem1) /* might be overridden in a subtype of this type */
    }

}

/* use a type as one of its supertypes (implicit upcasting) */
List<String> l = new ArrayList<>() /* some inference is available for generics */

Informações do tipo de tempo de execução parcial

/* find the outermost actual type of a value at runtime */
Class<?> c = l.getClass // will be 'java.util.ArrayList'

/* query the relationship between runtime and compile-time types */
Boolean b = l instanceOf MyList // will be 'false'

Exclusivo para Haskell (em comparação com Java)

Polimorfismo ad-hoc limitado

-- declare a parametrized bound
class A t where
  -- provide a function via this bound
  tInt :: t Int
  -- require other bounds within the functions provided by this bound
  mtInt :: Monad m => m (t Int)
  mtInt = return tInt -- define bound-provided functions via other bound-provided functions

-- fullfill a bound
instance A Maybe where
  tInt = Just 5
  mtInt = return Nothing -- override defaults

-- require exactly the bounds you need (ideally)
tString :: (Functor t, A t) => t String
tString = fmap show tInt -- use bounds that are implied by a concrete type (e.g., "Show Int")

Polimorfismo de subtipo "baseado em restrições" (baseado em polimorfismo ad-hoc limitado)

-- declare that a bound implies other bounds (introduce a subbound)
class (A t, Applicative t) => B t where -- bounds don't have to provide functions

-- use multiple bounds (intersection types in the context, union types in the full type)
mtString :: (Monad m, B t) => m (t String)
mtString = return mtInt -- use a bound that is implied by another bound (implicit upcasting)

optString :: Maybe String
optString = join mtString -- full types are contravariant in their contexts

Polimorfismo paramétrico de tipo superior

-- parametrize types over type variables that are themselves parametrized
data OneOrTwoTs t x = OneVariableT (t x) | TwoFixedTs (t Int) (t String)

-- bounds can be higher-kinded, too
class MonadStrip s where
  -- use arbitrarily nested higher-kinded type variables
  strip :: (Monad m, MonadTrans t) => s t m a -> t m a -> m a

Digitação principal

É difícil dar um exemplo direto disso, mas significa que toda expressão tem exatamente um tipo maximamente geral (chamado de tipo principal ), que é considerado o tipo canônico dessa expressão. Em termos de polimorfismo de subtipo "baseado em restrição" (veja acima), o tipo principal de uma expressão é o subtipo exclusivo de todos os tipos possíveis com os quais essa expressão pode ser usada. A presença da digitação principal em Haskell (sem extensão) é o que permite inferência de tipo completa (ou seja, inferência de tipo bem-sucedida para cada expressão, sem a necessidade de nenhuma anotação de tipo). As extensões que quebram a digitação principal (das quais existem muitas) também quebram a integridade da inferência de tipo.

Chama de Ptharien
fonte
7
Não use lcomo uma única variável de letra, é MUITO difícil distinguir 1!
recursion.ninja
5
Pode ser interessante notar que, embora você esteja absolutamente certo de que o Java tem algumas informações sobre o tipo de tempo de execução e o Haskell não, você pode usar a classe de tipo Typeable no Haskell para fornecer algo que se comporta como informações do tipo de tempo de execução para muitos tipos (com o PolyKinded mais recente classes no caminho, serão todos os tipos iirc), embora eu pense que depende da situação se ela realmente passa alguma informação de tipo em tempo de execução ou não.
3
@DarkOtter que eu conheço Typeable, mas o Haskell 2010 não o possui (talvez o Haskell 2014 o faça?).
Chama de Ptharien
5
E os tipos de soma (fechados)? Eles são um dos mecanismos mais importantes para codificar restrições.
Tibbe
3
Anulabilidade? Solidez (sem covariância sillinses)? Tipos de soma fechada / correspondências de padrão? Esta resposta é muito estreita
Peaker
32

O sistema de tipos do Java não possui polimorfismo de tipo superior; O sistema de tipos de Haskell possui.

Em outras palavras: em Java, construtores de tipo podem abstrair sobre tipos, mas não sobre construtores de tipo, enquanto em Haskell, construtores de tipo podem abstrair sobre construtores de tipo, bem como tipos.

Em inglês: em Java, um genérico não pode pegar outro tipo genérico e parametrizá-lo,

public void <Foo> nonsense(Foo<Integer> i, Foo<String> j)

enquanto em Haskell isso é bem fácil

higherKinded :: Functor f => f Int -> f String
higherKinded = fmap show
Jörg W Mittag
fonte
28
Se importa de repetir isso por nós novamente, em inglês desta vez? : P
Mason Wheeler
8
@ Matt: Como exemplo, eu não posso escrever isso em Java, mas eu posso escrever o equivalente em Haskell: <T<_> extends Collection> T<Integer> convertStringsToInts(T<string> strings). A idéia aqui seria que, se alguém o chamasse, convertStringsToInts<ArrayList>pegaria uma lista de cadeias de caracteres e retornaria uma lista de matrizes de números inteiros. E se eles usassem convertStringsToInts<LinkedList>, seria o mesmo com listas vinculadas.
sepp2k
8
Não é esse polimorfismo de tipo superior, em vez de rank 1 vs n?
8111 Adam
8
@ JörgWMittag: Meu entendimento é que o polimorfismo de classificação mais alta se refere a onde você pode colocar o forallseu tipo. Em Haskell, um tipo a -> bé implicitamente forall a. forall b. a -> b. Com uma extensão, você pode tornar esses forallitens explícitos e movê-los.
Tikhon Jelvis 9/10/12
8
@ Adam é rigtht: classificação mais alta e mais alta são totalmente diferentes. O GHC também pode fazer tipos de classificação mais alta (ou seja, todos os tipos) com alguma extensão de idioma. Java não conhece tipos com classificação mais alta nem classificação mais alta.
Ingo
11

Para complementar as outras respostas, o sistema de tipos de Haskell não possui subtipagem , enquanto as linguagens orientadas a objetos digitadas, como o Java.

Na teoria da linguagem de programação , subtipo (também polimorfismo de subtipo ou polimorfismo de inclusão ) é uma forma de polimorfismo de tipo no qual um subtipo é um tipo de dados que está relacionado a outro tipo de dados (o supertipo ) por alguma noção de substituibilidade , o que significa que os elementos do programa, tipicamente sub-rotinas ou funções, escritas para operar em elementos do supertipo, também podem operar em elementos do subtipo. Se S é um subtipo de T, a relação de subtipo é frequentemente escrita S <: T, para significar que qualquer termo do tipo S pode ser usado com segurança em um contexto em queé esperado um termo do tipo T. A semântica precisa da subtipagem depende crucialmente dos detalhes do que "usado com segurança em um contexto em que" significa em uma determinada linguagem de programação. O sistema de tipos de uma linguagem de programação define essencialmente sua própria relação de subtipagem, que pode muito bem ser trivial.

Devido à relação de subtipagem, um termo pode pertencer a mais de um tipo. A subtipagem é, portanto, uma forma de polimorfismo de tipo. Na programação orientada a objetos, o termo 'polimorfismo' é comumente usado para se referir apenas a esse subtipo de polimorfismo , enquanto as técnicas do polimorfismo paramétrico seriam consideradas programação genérica ...

Petr Pudlák
fonte
4
Embora isso não signifique que você não tenha polimorfismo ad-hoc. Você faz, apenas de uma forma diferente (digite classes em vez de subtipo polimorfismo).
3
Subclassificação não é subtipagem!
precisa saber é o seguinte
8

Uma coisa que ninguém mencionou até agora é a inferência de tipos: um compilador Haskell geralmente pode inferir o tipo de expressões, mas você precisa informar ao compilador Java seus tipos em detalhes. Estritamente, esse é um recurso do compilador, mas o design do sistema de idiomas e tipos determina se a inferência de tipos é viável. Em particular, a inferência de tipo interage mal com o polimorfismo de subtipo de Java e a sobrecarga ad hoc. Por outro lado, os designers de Haskell se esforçam para não introduzir recursos que impactam a inferência de tipo.

Outra coisa que as pessoas parecem não ter mencionado até agora são os tipos de dados algébricos. Ou seja, a capacidade de construir tipos a partir de somas ('ou') e produtos ('e') de outros tipos. As classes Java fazem os produtos (campo ae campo b, digamos) bem. Mas eles realmente não fazem somas (campo a OU campo b, digamos). O Scala deve codificar isso como várias classes de casos, o que não é exatamente o mesmo. E, embora funcione para o Scala, é um pouco difícil dizer que o Java o possui.

Haskell também pode construir tipos de funções usando o construtor de funções, ->. Embora os métodos do Java tenham assinaturas de tipo, você não pode combiná-los.

O sistema de tipos do Java permite um tipo de modularidade que Haskell não possui. Vai demorar um pouco até que haja um OSGi para Haskell.

GarethR
fonte
11
@ MattFenwick, modifiquei o terceiro parágrafo com base nos seus comentários. Os dois sistemas de tipos tratam as funções de maneira muito diferente.
GarethR
Eu não chamaria ADTs de um recurso do sistema de tipos. Você pode emular completamente (se não for o caso) com os invólucros OO.
leftaroundabout
@leftaroundabout Acho que isso é discutível. Por exemplo, pode haver coisas que são nativas para um sistema de tipos de um idioma, mas podem ser implementadas com padrões de design em outro. Obviamente, a maneira do padrão de design, em comparação com a nativa, é uma solução alternativa. A solução alternativa devido a um sistema do tipo mais fraco.
Hi-Angel
A resposta escolhida mencionou 'inferência completa de tipo' na seção 'Digitação principal'. O Java pode emular somas com subtipos e informações de tipo de tempo de execução, mas como você diz, não é o mesmo que a soma não é um atributo holístico do sistema de tipos.
Shelby Moore III