Vi várias fontes ecoarem a opinião de que "Haskell está gradualmente se tornando uma linguagem dependente". A implicação parece ser que, com mais e mais extensões de linguagem, Haskell está à deriva nessa direção geral, mas ainda não existe.
Há basicamente duas coisas que eu gostaria de saber. A primeira é, simplesmente, o que "ser uma linguagem de tipo dependente" realmente significa ? (Esperemos que sem ser muito técnico sobre isso.)
A segunda pergunta é ... qual é a desvantagem? Quero dizer, as pessoas sabem que estamos indo nessa direção, então deve haver alguma vantagem nisso. E, no entanto, ainda não estamos lá, então deve haver alguma desvantagem em impedir as pessoas de seguir em frente. Tenho a impressão de que o problema é um aumento acentuado da complexidade. Mas, não entendendo realmente o que é digitação dependente, não sei ao certo.
O que sei é que toda vez que começo a ler sobre uma linguagem de programação de tipo dependente, o texto é totalmente incompreensível ... Presumivelmente, esse é o problema. (?)
fonte
Respostas:
A digitação dependente é realmente apenas a unificação dos níveis de valor e tipo, para que você possa parametrizar valores em tipos (já possível com classes de tipos e polimorfismo paramétrico em Haskell) e você pode parametrizar tipos em valores (ainda não, estritamente falando, possível ainda em Haskell , embora
DataKinds
fique muito próximo).Edit: Aparentemente, a partir deste ponto, eu estava errado (veja o comentário do @ pigworker). Vou preservar o resto disso como um registro dos mitos que fui alimentado. : P
O problema de passar para a digitação dependente total, pelo que ouvi dizer, é que isso quebraria a restrição de fase entre os níveis de tipo e valor que permite que Haskell seja compilado para código de máquina eficiente com tipos apagados. Com o nosso nível atual de tecnologia, uma linguagem de tipo dependente deve passar por um intérprete em algum momento (imediatamente, ou após ser compilada em código de código ou tipo similar).
Isso não é necessariamente uma restrição fundamental, mas não conheço pessoalmente nenhuma pesquisa atual que pareça promissora a esse respeito, mas que ainda não tenha entrado no GHC. Se mais alguém souber mais, ficaria feliz em ser corrigido.
fonte
Haskell de tipo dependente, agora?
Haskell é, em pequena medida, uma linguagem tipicamente dependente. Existe uma noção de dados em nível de tipo, agora digitada de forma mais sensata, graças a
DataKinds
, e existem alguns meios (GADTs
) para fornecer uma representação em tempo de execução aos dados em nível de tipo. Portanto, os valores das coisas em tempo de execução são efetivamente exibidos em tipos , o que significa que um idioma deve ser digitado com dependência.Tipos de dados simples são promovidos para o nível de tipo, para que os valores que eles contêm possam ser usados nos tipos. Daí o exemplo arquetípico
torna-se possível e, com ele, definições como
que é bom. Observe que o comprimento
n
é uma coisa puramente estática nessa função, garantindo que os vetores de entrada e saída tenham o mesmo comprimento, mesmo que esse comprimento não tenha nenhum papel na execução devApply
. Por outro lado, é muito mais complicado (ou seja, impossível) para implementar a função que fazn
cópias de um dadox
(o que seriapure
avApply
's<*>
)porque é vital saber quantas cópias fazer em tempo de execução. Digite singletons.
Para qualquer tipo de promoção, podemos construir a família singleton, indexada sobre o tipo promovido, habitado por duplicatas em tempo de execução de seus valores.
Natty n
é o tipo de cópias em tempo de execução do nível de tipon :: Nat
. Agora podemos escreverPortanto, você tem um valor em nível de tipo associado a um valor em tempo de execução: a inspeção da cópia em tempo de execução refina o conhecimento estático do valor em nível de tipo. Embora os termos e os tipos sejam separados, podemos trabalhar de maneira dependente, usando a construção singleton como um tipo de resina epóxi, criando ligações entre as fases. Isso está longe de permitir expressões arbitrárias em tempo de execução nos tipos, mas não é nada.
O que é desagradável? O que está a faltar?
Vamos colocar um pouco de pressão nessa tecnologia e ver o que começa a tremer. Podemos ter a ideia de que singletons devem ser administrados um pouco mais implicitamente
nos permitindo escrever, digamos,
Isso funciona, mas agora significa que nosso
Nat
tipo original gerou três cópias: uma espécie, uma família singleton e uma classe singleton. Temos um processo bastante complicado para trocarNatty n
valores eNattily n
dicionários explícitos . Além disso,Natty
não éNat
: temos algum tipo de dependência dos valores de tempo de execução, mas não do tipo que pensamos inicialmente. Nenhuma linguagem digitada totalmente dependente torna os tipos dependentes tão complicados!Enquanto isso, embora
Nat
possa ser promovido,Vec
não pode. Você não pode indexar por um tipo indexado. Completo em idiomas de tipo dependente não impõe essa restrição e, em minha carreira como um show de tipo dependente, aprendi a incluir exemplos de indexação em duas camadas em minhas palestras, apenas para ensinar as pessoas que fizeram a indexação em uma camada difícil, mas possível, não esperar que eu dobre como um castelo de cartas. Qual é o problema? Igualdade. Os GADTs funcionam traduzindo as restrições que você obtém implicitamente quando atribui a um construtor um tipo de retorno específico em demandas equacionais explícitas. Como isso.Em cada uma de nossas duas equações, ambos os lados são gentis
Nat
.Agora tente a mesma tradução para algo indexado sobre vetores.
torna-se
e agora formamos restrições equacionais entre
as :: Vec n x
eVCons z zs :: Vec (S m) x
onde os dois lados têm tipos sintaticamente distintos (mas comprovadamente iguais). O núcleo do GHC atualmente não está equipado para esse conceito!O que mais está faltando? Bem, a maioria de Haskell está faltando no nível de tipo. O idioma dos termos que você pode promover tem apenas variáveis e construtores não pertencentes ao GADT, na verdade. Depois de adquiri-los, o
type family
mecanismo permite que você escreva programas em nível de tipo: alguns deles podem ser como funções que você consideraria escrever no nível do termo (por exemplo, equiparNat
com adição, para que você possa dar um bom tipo para acrescentarVec
) , mas isso é apenas uma coincidência!Outra coisa que falta, na prática, é uma biblioteca que utiliza nossas novas habilidades para indexar tipos por valores. Fazer o que
Functor
eMonad
se tornar neste admirável mundo novo? Estou pensando nisso, mas ainda há muito a fazer.Executando programas de nível de tipo
Haskell, como a maioria das linguagens de programação tipicamente dependentes, possui duas semânticas operacionais. Existe a maneira como o sistema de tempo de execução executa programas (somente expressões fechadas, após o apagamento do tipo, altamente otimizado) e depois a maneira como o datilógrafo executa programas (suas famílias de tipos, sua "classe de tipo Prolog", com expressões abertas). Para Haskell, você normalmente não mistura os dois, porque os programas que estão sendo executados estão em idiomas diferentes. As linguagens tipicamente dependentes têm modelos de execução estáticos e de tempo de execução separados para o mesmo idioma dos programas, mas não se preocupe, o modelo de tempo de execução ainda permite que você digite apagamento e, na verdade, apagamento de prova: é isso que Coq's extraimecanismo dá a você; isso é pelo menos o que o compilador de Edwin Brady faz (embora Edwin apague valores duplicados desnecessariamente, bem como tipos e provas). A distinção de fase pode não ser mais uma distinção de categoria sintática por mais tempo, mas está vivo e bem.
As linguagens tipicamente dependentes, sendo totais, permitem ao checador de tipos executar programas livres do medo de algo pior que uma longa espera. À medida que o Haskell se torna mais dependente, enfrentamos a questão de qual deveria ser o seu modelo de execução estática? Uma abordagem pode ser restringir a execução estática ao total de funções, o que nos permitirá a mesma liberdade de execução, mas pode nos forçar a fazer distinções (pelo menos no código de tipo) entre dados e codados, para que possamos dizer se devemos impor rescisão ou produtividade. Mas essa não é a única abordagem. Somos livres para escolher um modelo de execução muito mais fraco, relutante em executar programas, com o custo de fazer com que menos equações apareçam apenas pela computação. E, de fato, é isso que o GHC realmente faz. As regras de digitação para o núcleo do GHC não mencionam execução programas, mas apenas para verificar evidências de equações. Ao traduzir para o núcleo, o solucionador de restrições do GHC tenta executar seus programas em nível de tipo, gerando uma pequena trilha prateada de evidência de que uma determinada expressão é igual à sua forma normal. Esse método de geração de evidências é um pouco imprevisível e inevitavelmente incompleto: ele combate a recursão de aparência assustadora, por exemplo, e provavelmente é sábio. Uma coisa com a qual não precisamos nos preocupar é com a execução de
IO
cálculos no verificador de datilografia: lembre-se de que o datilógrafo não precisa darlaunchMissiles
o mesmo significado que o sistema de tempo de execução!Cultura Hindley-Milner
O sistema do tipo Hindley-Milner alcança a incrível coincidência de quatro distinções distintas, com o infeliz efeito colateral cultural de que muitas pessoas não conseguem ver a distinção entre as distinções e assumem que a coincidência é inevitável! Do que estou falando?
Estamos acostumados a escrever termos e deixar tipos a serem inferidos ... e depois apagados. Estamos acostumados a quantificar sobre variáveis de tipo, com a abstração e aplicação de tipo correspondentes acontecendo silenciosa e estaticamente.
Você não precisa se afastar muito da baunilha Hindley-Milner antes que essas distinções saiam do alinhamento, e isso não é ruim . Para começar, podemos ter tipos mais interessantes se quisermos escrevê-los em alguns lugares. Enquanto isso, não precisamos escrever dicionários de classes de tipo quando usamos funções sobrecarregadas, mas esses dicionários certamente estão presentes (ou embutidos) no tempo de execução. Em linguagens de tipo dependente, esperamos apagar mais do que apenas tipos em tempo de execução, mas (como nas classes de tipos) que alguns valores implicitamente deduzidos não serão apagados. Por exemplo,
vReplicate
o argumento numérico de muitas vezes é inferível a partir do tipo do vetor desejado, mas ainda precisamos conhecê-lo em tempo de execução.Quais opções de design de idioma devemos revisar porque essas coincidências não são mais válidas? Por exemplo, é certo que Haskell não fornece nenhuma maneira de instanciar
forall x. t
explicitamente um quantificador? Se o datilógrafo não consegue adivinharx
unificandot
, não temos outra maneira de dizer o quex
deve ser.De maneira mais ampla, não podemos tratar a "inferência de tipo" como um conceito monolítico do qual temos tudo ou nada. Para começar, precisamos separar o aspecto "generalização" (regra "let" de Milner), que depende muito da restrição de quais tipos existem para garantir que uma máquina estúpida possa adivinhar um, do aspecto "especialização" (var de Milner " "regra), que é tão eficaz quanto seu solucionador de restrições. Podemos esperar que os tipos de nível superior se tornem mais difíceis de inferir, mas essas informações de tipo interno permanecerão razoavelmente fáceis de propagar.
Próximos passos para Haskell
Estamos vendo os níveis de tipo e tipo crescerem muito semelhantes (e eles já compartilham uma representação interna no GHC). Nós também podemos fundi-los. Seria divertido tomar
* :: *
isso se pudéssemos: perdemos a integridade lógica há muito tempo, quando permitimos o fundo, mas a solidez do tipo geralmente é um requisito mais fraco. Nós devemos verificar. Se precisarmos ter níveis distintos de tipo, tipo, etc., podemos pelo menos garantir que tudo no nível de tipo e acima sempre possa ser promovido. Seria ótimo apenas reutilizar o polimorfismo que já temos para os tipos, em vez de reinventar o polimorfismo no nível de tipo.Devemos simplificar e generalizar o sistema atual de restrições, permitindo equações heterogêneas em
a ~ b
que os tipos dea
eb
não são sintaticamente idênticos (mas podem ser provados iguais). É uma técnica antiga (na minha tese, no século passado) que facilita muito a dependência da dependência. Poderíamos expressar restrições sobre expressões nos GADTs e, assim, relaxar as restrições sobre o que pode ser promovido.Devemos eliminar a necessidade da construção singleton introduzindo um tipo de função dependente
pi x :: s -> t
,. Uma função com esse tipo pode ser aplicada explicitamente a qualquer expressão do tipos
que mora na interseção das linguagens de tipos e termos (portanto, variáveis, construtores, com mais coisas para vir mais tarde). O lambda e o aplicativo correspondentes não seriam apagados no tempo de execução, portanto poderíamos escreversem substituir
Nat
porNatty
. O domínio depi
pode ser qualquer tipo de promoção; portanto, se os GADTs podem ser promovidos, podemos escrever sequências quantificadoras dependentes (ou "telescópios", como de Briuijn os chamava)para qualquer comprimento que precisarmos.
O objetivo dessas etapas é eliminar a complexidade , trabalhando diretamente com ferramentas mais gerais, em vez de se contentar com ferramentas fracas e codificações desajeitadas. O atual buy-in parcial torna os benefícios dos tipos dependentes de Haskell mais caros do que precisam.
Demasiado difícil?
Os tipos dependentes deixam muitas pessoas nervosas. Eles me deixam nervoso, mas eu gosto de ficar nervoso, ou pelo menos acho difícil não ficar nervoso de qualquer maneira. Mas não ajuda que exista uma névoa de ignorância em torno do assunto. Parte disso se deve ao fato de todos ainda termos muito a aprender. Sabe-se, porém, que os defensores de abordagens menos radicais estimulam o medo de tipos dependentes sem sempre garantir que os fatos estejam totalmente a seu favor. Não vou citar nomes. Esses "tipos de letra indecidíveis", "Turing incompleto", "nenhuma distinção de fase", "nenhum tipo de apagamento", "provas em todos os lugares" etc., etc., mitos persistem, mesmo que sejam lixo.
Certamente não é o caso de que programas digitados com dependência sempre devem ser comprovadamente corretos. Pode-se melhorar a higiene básica de seus programas, aplicando invariantes adicionais em tipos, sem chegar a uma especificação completa. Pequenos passos nessa direção geralmente resultam em garantias muito mais fortes, com poucas ou nenhuma obrigação adicional de prova. Não é verdade que os programas tipicamente dependentes estejam inevitavelmente cheios de provas; de fato, geralmente tomo a presença de quaisquer provas no meu código como a sugestão para questionar minhas definições .
Pois, como em qualquer aumento da articulação, ficamos livres para dizer coisas novas e equivocadas. Por exemplo, existem muitas maneiras precárias de definir árvores de pesquisa binárias, mas isso não significa que não há uma boa maneira . É importante não presumir que experiências ruins não possam ser melhoradas, mesmo que o ego seja admitido. O design de definições dependentes é uma nova habilidade que requer aprendizado, e ser um programador Haskell não o torna automaticamente um especialista! E mesmo que alguns programas sejam ruins, por que você negaria a outros a liberdade de serem justos?
Por que ainda se incomoda com Haskell?
Eu realmente gosto de tipos dependentes, mas a maioria dos meus projetos de hackers ainda está em Haskell. Por quê? Haskell tem classes de tipo. Haskell tem bibliotecas úteis. Haskell tem um tratamento viável (embora longe do ideal) de programação com efeitos. Haskell possui um compilador de força industrial. As linguagens de tipo dependente estão em um estágio muito anterior do crescimento da comunidade e da infraestrutura, mas chegaremos lá, com uma mudança geracional real no que é possível, por exemplo, por meio de metaprogramação e genéricos de tipo de dados. Mas você só precisa analisar o que as pessoas estão fazendo como resultado dos passos de Haskell em relação aos tipos dependentes, para ver que há muitos benefícios a serem ganhos ao empurrar também a geração atual de idiomas.
fonte
fmap read getLine >>= \n -> vReplicate n 0
. Como você observa,Natty
é muito longe disso. Além disso, o vReplicate deve ser traduzido para uma matriz de memória real, algo comonewtype SVector n x = SVector (Data.Vector.Vector x)
, onden
tem tipoNat
(ou similar). Talvez outro ponto de demonstração para um "show-off de tipo dependente?"John é outro equívoco comum sobre tipos dependentes: que eles não funcionam quando os dados estão disponíveis apenas em tempo de execução. Veja como você pode fazer o exemplo getLine:
Edit: Hm, isso deveria ser um comentário para a resposta do trabalhador de porcos. Eu falho claramente no SO.
fonte
Vec Zy -> IO String
. Você não pode usá-lo comwithZeroes
, porque o tipoZy
não pode ser unificado com forall n. Talvez você possa solucionar isso em um ou dois casos especiais, mas isso rapidamente fica fora de controle.forall n
faz sentido. Restrições mais precisas podem ser implementadas da mesma maneira. Você tem um exemplo melhor do queVec Zy
(o programa ainda precisaria lidar com o usuário digitando 5 em vez de 0)?Vec Zy -> IO String
e outra paraVec n -> IO String
e deseje usar a primeira apenas se o tipo corresponder. Sim, é possível, mas os mecanismos para habilitá-lo são desajeitados. E essa é uma lógica muito simples; se você tem uma lógica mais complexa, é pior. Além disso, pode ser necessário reescrever muito código no CPS. E você ainda não tem uma expressão de nível tipo que é dependente de um prazo ao nível valorzeroes :: IO (Some (Flip Vec Int))
.O pigworker oferece uma excelente discussão sobre por que devemos nos dirigir a tipos dependentes: (a) são impressionantes; (b) eles realmente simplificariam muito do que Haskell já faz.
Quanto ao "por que não?" pergunta, existem alguns pontos que eu acho. O primeiro ponto é que, embora a noção básica por trás dos tipos dependentes seja fácil (permita que os tipos dependam dos valores), as ramificações dessa noção básica são sutis e profundas. Por exemplo, a distinção entre valores e tipos ainda está viva e bem; mas discutir a diferença entre eles se torna longemais sutil do que Hindley - Milner ou Sistema F. Até certo ponto, isso se deve ao fato de que os tipos dependentes são fundamentalmente difíceis (por exemplo, a lógica de primeira ordem é indecidível). Mas acho que o maior problema é que realmente não temos um bom vocabulário para capturar e explicar o que está acontecendo. À medida que mais e mais pessoas aprendem sobre tipos dependentes, desenvolveremos um vocabulário melhor e, assim, as coisas ficarão mais fáceis de entender, mesmo que os problemas subjacentes ainda sejam difíceis.
O segundo ponto tem a ver com o fato de Haskell ser crescendopara tipos dependentes. Como estamos fazendo um progresso incremental em direção a esse objetivo, mas sem chegar lá, estamos presos a uma linguagem que possui patches incrementais em cima de patches incrementais. O mesmo tipo de coisa aconteceu em outros idiomas quando novas idéias se tornaram populares. Java não costumava ter polimorfismo (paramétrico); e quando eles finalmente o adicionaram, foi obviamente uma melhoria incremental com alguns vazamentos de abstração e poder prejudicado. Acontece que misturar subtipo e polimorfismo é inerentemente difícil; mas essa não é a razão pela qual o Java Generics funciona da maneira que funciona. Eles funcionam da maneira que funcionam devido à restrição de ser uma melhoria incremental para versões mais antigas do Java. O mesmo vale para os tempos antigos em que o OOP foi inventado e as pessoas começaram a escrever "objetivos". C (não confunda com Objective-C), etc. Lembre-se, o C ++ começou sob o disfarce de ser um superconjunto estrito de C. A adição de novos paradigmas sempre requer a definição da linguagem novamente, ou o resultado é uma bagunça complicada. O que quero dizer com tudo isso é que, a adição de tipos dependentes verdadeiros ao Haskell exigirá uma certa quantidade de estripação e reestruturação da linguagem - se quisermos fazer o certo. Mas é realmente difícil se comprometer com esse tipo de revisão, enquanto o progresso incremental que estamos fazendo parece mais barato no curto prazo. Realmente, não existem muitas pessoas que invadem o GHC, mas há uma boa quantidade de código legado para manter vivo. Isso é parte da razão pela qual existem tantas linguagens derivadas como DDC, Cayenne, Idris, etc. O C ++ começou sob o pretexto de ser um superconjunto estrito de C. A adição de novos paradigmas sempre requer a definição da linguagem novamente, ou então, com uma bagunça complicada. O que quero dizer com tudo isso é que, a adição de tipos dependentes verdadeiros ao Haskell exigirá uma certa quantidade de estripação e reestruturação da linguagem - se quisermos fazer o certo. Mas é realmente difícil se comprometer com esse tipo de revisão, enquanto o progresso incremental que estamos fazendo parece mais barato no curto prazo. Realmente, não existem muitas pessoas que invadem o GHC, mas há uma boa quantidade de código legado para manter vivo. Isso é parte da razão pela qual existem tantas linguagens derivadas como DDC, Cayenne, Idris, etc. O C ++ começou sob o pretexto de ser um superconjunto estrito de C. A adição de novos paradigmas sempre requer a definição da linguagem novamente, ou então, com uma bagunça complicada. O que quero dizer com tudo isso é que, a adição de tipos dependentes verdadeiros ao Haskell exigirá uma certa quantidade de estripação e reestruturação da linguagem - se quisermos fazer o certo. Mas é realmente difícil se comprometer com esse tipo de revisão, enquanto o progresso incremental que estamos fazendo parece mais barato no curto prazo. Realmente, não existem muitas pessoas que invadem o GHC, mas há uma boa quantidade de código legado para manter vivo. Isso é parte da razão pela qual existem tantas linguagens derivadas como DDC, Cayenne, Idris, etc. ou então terminando com uma bagunça complicada. O que quero dizer com tudo isso é que, a adição de tipos dependentes verdadeiros ao Haskell exigirá uma certa quantidade de estripação e reestruturação da linguagem - se quisermos fazer o certo. Mas é realmente difícil se comprometer com esse tipo de revisão, enquanto o progresso incremental que estamos fazendo parece mais barato no curto prazo. Realmente, não existem muitas pessoas que invadem o GHC, mas há uma boa quantidade de código legado para manter vivo. Isso é parte da razão pela qual existem tantas linguagens derivadas como DDC, Cayenne, Idris, etc. ou então terminando com uma bagunça complicada. O que quero dizer com tudo isso é que, a adição de tipos dependentes verdadeiros ao Haskell exigirá uma certa quantidade de estripação e reestruturação da linguagem - se quisermos fazer o certo. Mas é realmente difícil se comprometer com esse tipo de revisão, enquanto o progresso incremental que estamos fazendo parece mais barato no curto prazo. Realmente, não existem muitas pessoas que invadem o GHC, mas há uma boa quantidade de código legado para manter vivo. Isso é parte da razão pela qual existem tantas linguagens derivadas como DDC, Cayenne, Idris, etc. é realmente difícil nos comprometer com esse tipo de revisão, enquanto o progresso incremental que estamos fazendo parece mais barato no curto prazo. Realmente, não existem muitas pessoas que invadem o GHC, mas há uma boa quantidade de código legado para manter vivo. Isso é parte da razão pela qual existem tantas linguagens derivadas como DDC, Cayenne, Idris, etc. é realmente difícil nos comprometer com esse tipo de revisão, enquanto o progresso incremental que estamos fazendo parece mais barato no curto prazo. Realmente, não existem muitas pessoas que invadem o GHC, mas há uma boa quantidade de código legado para manter vivo. Isso é parte da razão pela qual existem tantas linguagens derivadas como DDC, Cayenne, Idris, etc.
fonte