Abusando da álgebra de tipos de dados algébricos - por que isso funciona?

A expressão 'algébrica' para tipos de dados algébricos parece muito sugestiva para alguém com experiência em matemática. Deixe-me tentar explicar o que quero dizer.

Tendo definido os tipos básicos

• produtos •
• União +
• Singleton X
• Unidade 1

e usando a abreviação X²de X•Xe 2Xpara X+Xet cetera, podemos definir expressões algébricas para, por exemplo, listas vinculadas

data List a = Nil | Cons a (List a) ↔ L = 1 + X • L

e árvores binárias:

data Tree a = Nil | Branch a (Tree a) (Tree a) ↔ T = 1 + X • T²

Agora, meu primeiro instinto como matemático é enlouquecer com essas expressões e tentar resolver por Le T. Eu poderia fazer isso através de substituições repetidas, mas parece muito mais fácil abusar da notação horrivelmente e fingir que posso reorganizá-la à vontade. Por exemplo, para uma lista vinculada:

L = 1 + X • L

(1 - X) • L = 1

L = 1 / (1 - X) = 1 + X + X² + X³ + ...

onde eu usei a expansão de séries de potência de 1 / (1 - X)uma maneira totalmente injustificada para obter um resultado interessante, ou seja, que um Ltipo é Nilou contém 1 elemento ou contém 2 elementos ou 3 etc.

Fica mais interessante se o fizermos para árvores binárias:

T = 1 + X • T²

X • T² - T + 1 = 0

T = (1 - √(1 - 4 • X)) / (2 • X)

T = 1 + X + 2 • X² + 5 • X³ + 14 • X⁴ + ...

novamente, usando a expansão da série Power (feita com Wolfram Alpha ). Isso expressa o fato não óbvio (para mim) de que existe apenas uma árvore binária com 1 elemento, 2 árvores binárias com dois elementos (o segundo elemento pode estar no ramo esquerdo ou direito), 5 árvores binárias com três elementos etc. .

Então, minha pergunta é - o que estou fazendo aqui? Essas operações parecem injustificadas (qual é exatamente a raiz quadrada de um tipo de dados algébrico?), Mas levam a resultados sensatos. o quociente de dois tipos de dados algébricos tem algum significado na ciência da computação ou é apenas truque notacional?

E, talvez mais interessante, é possível estender essas idéias? Existe uma teoria da álgebra de tipos que permita, por exemplo, funções arbitrárias em tipos, ou os tipos requerem uma representação de séries de poder? Se você pode definir uma classe de funções, a composição de funções tem algum significado?

Isenção de responsabilidade: Muito disso realmente não funciona muito bem quando você responde por so, então eu vou desconsiderar descaradamente isso por uma questão de simplicidade.

Alguns pontos iniciais:

• Observe que "união" provavelmente não é o melhor termo para A + B aqui - isso é especificamente uma união disjunta dos dois tipos, porque os dois lados são distintos mesmo que seus tipos sejam os mesmos. Pelo que vale, o termo mais comum é simplesmente "tipo de soma".

• Tipos Singleton são, efetivamente, todos os tipos de unidades. Eles se comportam de forma idêntica sob manipulações algébricas e, mais importante, a quantidade de informações presentes ainda é preservada.

• Você provavelmente quer um tipo zero também. Haskell fornece isso como Void. Não há valores cujo tipo seja zero, assim como há um valor cujo tipo é um.

Ainda falta uma operação importante aqui, mas voltarei a isso daqui a pouco.

Como você já deve ter notado, Haskell tende a emprestar conceitos da Teoria das categorias, e todas as opções acima têm uma interpretação muito direta como essa:

• Dados os objetos A e B em Hask , seu produto A × B é o tipo único (até o isomorfismo) que permite duas projeções fst : A × B → A e snd : A × B → B, onde é dado qualquer tipo C e funções f : C → A, g : C → B, você pode definir o emparelhamento f &&& g : C → A × B de modo que fst ∘ (f &&& g) = f e da mesma forma para g . A parametridade garante as propriedades universais automaticamente e minha escolha menos que sutil de nomes deve lhe dar a idéia. O (&&&)operador é definido Control.Arrow, a propósito.

• A dupla acima é o coproduto A + B com injeções inl : A → A + B e inr : B → A + B, onde é dado qualquer tipo C e funções f : A → C, g : B → C, você pode definir o copairing f ||| g : A + B → C tal que as equivalências óbvias se mantêm. Novamente, a parametridade garante a maioria das partes complicadas automaticamente. Neste caso, as injecções de padrão são simplesmente Lefte Righte o copairing representa a função either.

Muitas das propriedades dos tipos de produto e soma podem ser derivadas do exposto acima. Observe que qualquer tipo singleton é um objeto terminal do Hask e qualquer tipo vazio é um objeto inicial.

Voltando à operação ausente mencionada acima, em uma categoria fechada cartesiana, você possui objetos exponenciais que correspondem às setas da categoria. Nossas setas são funções, nossos objetos são tipos com tipos *, e o tipo A -> Brealmente se comporta como B ^A no contexto da manipulação algébrica de tipos. Se não for óbvio por que isso deve ocorrer, considere o tipo Bool -> A. Com apenas duas entradas possíveis, uma função desse tipo é isomórfica para dois valores do tipo A, ie (A, A). Pois Maybe Bool -> Atemos três entradas possíveis, e assim por diante. Observe também que, se reformularmos a definição de copairing acima para usar notação algébrica, obtemos a identidade C ^A × C ^B = C^{A + B} .

Quanto ao motivo pelo qual tudo isso faz sentido - e, em particular, por que o uso da expansão da série de potência é justificado - observe que grande parte dos itens acima se refere aos "habitantes" de um tipo (ou seja, valores distintos tendo esse tipo) em ordem para demonstrar o comportamento algébrico. Para tornar essa perspectiva explícita:

• O tipo de produto (A, B)representa um valor para cada um deles Ae Bobtido independentemente. Portanto, para qualquer valor fixo a :: A, há um valor de tipo (A, B)para cada habitante de B. É claro que esse é o produto cartesiano, e o número de habitantes do tipo de produto é o produto do número de habitantes dos fatores.

• O tipo de soma Either A Brepresenta um valor de um Aou B, com os ramos esquerdo e direito distintos. Como mencionado anteriormente, esta é uma união disjunta, e o número de habitantes do tipo soma é a soma do número de habitantes dos somandos.

• O tipo exponencial B -> Arepresenta um mapeamento de valores do tipo Bpara valores do tipo A. Para qualquer argumento fixo b :: B, qualquer valor de Apode ser atribuído a ele; um valor do tipo B -> Aseleciona um desses mapeamentos para cada entrada, o que equivale a um produto com tantas cópias Aquanto Bhabitantes, daí a exponenciação.

Embora, no início, seja tentador tratar tipos como conjuntos, isso não funciona muito bem nesse contexto - temos união desunida em vez da união padrão de conjuntos, não há interpretação óbvia de interseção ou muitas outras operações de conjunto, e nós geralmente não se preocupam com a associação de conjuntos (deixando isso para o verificador de tipos).

Por outro lado, as construções acima passam muito tempo conversando sobre a contagem de habitantes, e enumerar os possíveis valores de um tipo é um conceito útil aqui. Isso rapidamente nos leva a combinações enumerativas e, se você consultar o artigo vinculado da Wikipedia, descobrirá que uma das primeiras coisas a fazer é definir "pares" e "uniões" exatamente no mesmo sentido que os tipos de produto e soma por meio de gerando funções , então faz o mesmo para "sequências" idênticas às listas de Haskell, usando exatamente a mesma técnica que você fez.

Edit: Ah, e aqui está um bônus rápido que eu acho que demonstra o ponto de forma impressionante. Você mencionou em um comentário que, para um tipo de árvore, T = 1 + T^2você pode derivar a identidade T^6 = 1, o que está claramente errado. No entanto, T^7 = T é válido, e uma bijeção entre árvores e sete tuplas de árvores pode ser construída diretamente, cf. "Sete Árvores em Uma", de Andreas Blass .

Editar × 2: Sobre o assunto da construção "derivada de um tipo" mencionada em outras respostas, você também pode apreciar este artigo do mesmo autor, que se baseia mais na idéia, incluindo noções de divisão e outros enfeites interessantes.

Árvores binárias são definidas pela equação T=1+XT^2na semirrada de tipos. Por construção, T=(1-sqrt(1-4X))/(2X)é definido pela mesma equação na semiring de números complexos. Portanto, dado que estamos resolvendo a mesma equação na mesma classe de estrutura algébrica, na verdade não deve surpreender que vejamos algumas semelhanças.

O problema é que, quando raciocinamos sobre polinômios na semirrigação de números complexos, normalmente usamos o fato de que os números complexos formam um anel ou mesmo um campo, então nos encontramos usando operações como subtração que não se aplicam a semirreclamações. Mas muitas vezes podemos eliminar subtrações de nossos argumentos se tivermos uma regra que nos permita cancelar de ambos os lados de uma equação. Esse é o tipo de coisa comprovada por Fiore e Leinster, mostrando que muitos argumentos sobre anéis podem ser transferidos para semirriscos.

Isso significa que muito do seu conhecimento matemático sobre anéis pode ser transferido com segurança para tipos. Como resultado, alguns argumentos que envolvem números complexos ou séries de potências (no círculo das séries formais de potência) podem ser transferidos para tipos de maneira completamente rigorosa.

No entanto, há mais na história do que isso. Uma coisa é provar que dois tipos são iguais (digamos), mostrando duas séries de potência iguais. Mas você também pode deduzir informações sobre tipos inspecionando os termos da série de potências. Não tenho certeza de qual deveria ser a declaração formal aqui. (Eu recomendo o artigo de Brent Yorgey sobre espécies combinatórias para alguns trabalhos que estão intimamente relacionados, mas espécies não são iguais aos tipos.)

O que acho absolutamente surpreendente é que o que você descobriu pode ser estendido ao cálculo. Teoremas sobre cálculo podem ser transferidos para a semirrada de tipos. De fato, mesmo argumentos sobre diferenças finitas podem ser transferidos e você descobre que os teoremas clássicos da análise numérica têm interpretações na teoria dos tipos.

Diverta-se!

Parece que tudo o que você está fazendo é expandir a relação de recorrência.

L = 1 + X • L
L = 1 + X • (1 + X • (1 + X • (1 + X • ...)))
  = 1 + X + X^2 + X^3 + X^4 ...

T = 1 + X • T^2
L = 1 + X • (1 + X • (1 + X • (1 + X • ...^2)^2)^2)^2
  = 1 + X + 2 • X^2 + 5 • X^3 + 14 • X^4 + ...

E como as regras para as operações nos tipos funcionam como as regras para operações aritméticas, você pode usar meios algébricos para ajudá-lo a descobrir como expandir a relação de recorrência (já que isso não é óbvio).

Não tenho uma resposta completa, mas essas manipulações tendem a "apenas funcionar". Um artigo relevante pode ser Objetos de categorias como números complexos de Fiore e Leinster - me deparei com esse enquanto lia o blog de sigfpe sobre um assunto relacionado ; o restante desse blog é uma mina de ouro para idéias semelhantes e vale a pena conferir!

Você também pode diferenciar tipos de dados, a propósito - que fornecerão o Zipper apropriado para o tipo de dados!

A Álgebra de Processos de Comunicação (ACP) lida com tipos semelhantes de expressões para processos. Oferece adição e multiplicação como operadores para escolha e sequência, com elementos neutros associados. Com base nisso, existem operadores para outras construções, como paralelismo e interrupção. Veja http://en.wikipedia.org/wiki/Algebra_of_Communicating_Processes . Há também um artigo on-line chamado "Uma Breve História da Álgebra de Processos".

Estou trabalhando na extensão de linguagens de programação com o ACP. Em abril passado, apresentei um trabalho de pesquisa no Scala Days 2012, disponível em http://code.google.com/p/subscript/

Na conferência, demonstrei um depurador executando uma especificação recursiva paralela de uma bolsa:

Bag = A; (Bag & a)

onde A e um representam ações de entrada e saída; o ponto e vírgula e o e comercial representam sequência e paralelismo. Veja o vídeo em SkillsMatter, acessível a partir do link anterior.

Uma especificação de bolsa mais comparável à

L = 1 + X • L

seria

B = 1 + X&B

ACP define paralelismo em termos de escolha e sequência usando axiomas; veja o artigo da Wikipedia. Gostaria de saber qual seria a analogia da bolsa.

L = 1 / (1-X)

A programação no estilo ACP é útil para analisadores de texto e controladores GUI. Especificações como

searchCommand = clicado (botão de pesquisa) + tecla (Enter)

cancelCommand = clicado (cancelButton) + tecla (Escape)

pode ser anotado de forma mais concisa, tornando implícitos os dois refinamentos "clicados" e "chave" (como o que Scala permite com funções). Por isso, podemos escrever:

searchCommand = searchButton + Enter

cancelCommand = cancelButton + Escape

O lado direito agora contém operandos que são dados, e não processos. Nesse nível, não é necessário saber quais refinamentos implícitos transformarão esses operandos em processos; eles não necessariamente se refinariam em ações de entrada; as ações de saída também se aplicariam, por exemplo, na especificação de um robô de teste.

Os processos obtêm os dados dessa maneira como complementares; assim, cunho o termo "álgebra de itens".

Séries de cálculo e Maclaurin com tipos

Aqui está outra pequena adição - uma visão combinatória sobre por que os coeficientes de uma expansão em série devem 'funcionar', focando especialmente as séries que podem ser derivadas usando a abordagem de Taylor-Maclaurin do cálculo. Nota: o exemplo de expansão de série que você fornece do tipo de lista manipulada é uma série de Maclaurin.

Como outras respostas e comentários lidam com o comportamento das expressões algébricas do tipo (somas, produtos e expoentes), essa resposta elimina esse detalhe e se concentra no tipo 'cálculo'.

Você pode notar vírgulas invertidas fazendo algum trabalho pesado nesta resposta. Existem dois motivos:

• estamos no negócio de interpretar um domínio para entidades de outro e parece apropriado delimitar essas noções estrangeiras dessa maneira.
• algumas noções poderão ser formalizadas com mais rigor, mas a forma e as idéias parecem mais importantes (e requerem menos espaço para escrever) do que os detalhes.

Definição da série Maclaurin

A série Maclaurin de uma função f : ℝ → ℝé definida como

f(0) + f'(0)X + (1/2)f''(0)X² + ... + (1/n!)f⁽ⁿ⁾(0)Xⁿ + ...

onde f⁽ⁿ⁾significa a nth derivada de f.

Para entender a série Maclaurin como interpretada com tipos, precisamos entender como podemos interpretar três coisas em um contexto de tipo:

• um derivado (possivelmente múltiplo)
• aplicar uma função a 0
• termos como (1/n!)

e acontece que esses conceitos da análise têm contrapartes adequadas no mundo dos tipos.

O que quero dizer com "contraparte adequada"? Deveria ter o sabor de um isomorfismo - se podemos preservar a verdade em ambas as direções, fatos deriváveis ​​em um contexto podem ser transferidos para o outro.

Cálculo com tipos

Então, o que a derivada de uma expressão de tipo significa? Acontece que, para uma classe grande e bem-comportada ('diferenciável') de expressões e functores de tipo, há uma operação natural que se comporta de maneira semelhante o suficiente para ser uma interpretação adequada!

Para estragar o argumento, a operação análoga à diferenciação é a de criar "contextos de um buraco". Este é um excelente local para expandir ainda mais esse ponto específico, mas o conceito básico de um contexto de um buraco ( da/dx) é que ele representa o resultado da extração de um único subitem de um tipo específico ( x) de um termo (do tipo a), preservando todas as outras informações, incluindo as necessárias para determinar a localização original do subitem. Por exemplo, uma maneira de representar um contexto de um buraco para uma lista é com duas listas: uma para itens que vieram antes do extraído e outra para itens que vieram depois.

A motivação para identificar esta operação com diferenciação vem das seguintes observações. Escrevemos da/dxpara significar o tipo de contextos de um furo para o tipo acom furo do tipo x.

d1/dx = 0
dx/dx = 1
d(a + b)/dx = da/dx + db/dx
d(a × b)/dx = a × db/dx + b × da/dx
d(g(f(x))/dx = d(g(y))/dy[f(x)/a] × df(x)/dx

Aqui, 1e 0representam tipos com exatamente um e exatamente zero habitantes, respectivamente, +e ×representam os tipos de soma e produto, como de costume. fe gsão usados ​​para representar funções de tipo ou formadores de expressão de tipo e [f(x)/a]significa a operação de substituir f(x)todos aos itens na expressão anterior.

Isso pode ser escrito em um estilo sem ponto, escrevendo f'para significar a função derivada da função type f, assim:

(x ↦ 1)' = x ↦ 0
(x ↦ x)' = x ↦ 1
(f + g)' = f' + g'
(f × g)' = f × g' + g × f'
(g ∘ f)' = (g' ∘ f) × f'

o que pode ser preferível.

Nota: as igualidades podem ser rigorosas e exatas se definirmos derivadas usando classes de isomorfismo de tipos e functores.

Agora, notamos em particular que as regras em cálculo referentes às operações algébricas de adição, multiplicação e composição (geralmente chamadas de regras de soma, produto e cadeia) são refletidas exatamente pela operação de "fazer um buraco". Além disso, os casos básicos de 'fazer um buraco' em uma expressão constante ou o xpróprio termo também se comportam como diferenciação; portanto, por indução, obtemos um comportamento semelhante à diferenciação para todas as expressões do tipo algébrico.

Agora podemos interpretar diferenciação, o que significa a n"derivada" de uma expressão de tipo dⁿe/dxⁿ? É um tipo que representa ncontextos -place: termos que, quando 'preenchidos' com ntermos do tipo, xproduzem um e. Há outra observação importante relacionada a ' (1/n!)' vir mais tarde.

A parte invariável de um tipo functor: aplicando uma função a 0

Já temos uma interpretação para 0o mundo dos tipos: um tipo vazio sem membros. O que significa, do ponto de vista combinatório, aplicar uma função de tipo a ela? Em termos mais concretos, supondo que fseja uma função de tipo, como é f(0)? Bem, certamente não temos acesso a nada do tipo 0, portanto, quaisquer construções f(x)que requeiram um xestão indisponíveis. O que resta são aqueles termos acessíveis na ausência deles, que podemos chamar de parte 'invariável' ou 'constante' do tipo.

Para um exemplo explícito, Maybeuse o functor, que pode ser representado algebricamente como x ↦ 1 + x. Quando aplicamos isso a 0, obtemos 1 + 0- é como 1: o único valor possível é o Nonevalor. Para uma lista, da mesma forma, obtemos apenas o termo correspondente à lista vazia.

Quando o devolvemos e interpretamos o tipo f(0)como um número, ele pode ser considerado a contagem de quantos termos do tipo f(x)(para qualquer x) podem ser obtidos sem acesso a um x: ou seja, o número de termos "vazios" .

Juntando tudo: interpretação completa de uma série Maclaurin

Receio não poder pensar em uma interpretação direta apropriada (1/n!)como um tipo.

Se considerarmos, no entanto, o tipo f⁽ⁿ⁾(0)de luz do exposto, vemos que ele pode ser interpretado como o tipo de ncontextos -Coloque para um mandato do tipo f(x)que já não contêm um x - isto é, quando nós 'integrar' eles nvezes , o termo resultante tem exatamente n x s, nem mais, nem menos. Então, a interpretação do tipo f⁽ⁿ⁾(0)como um número (como nos coeficientes da série Maclaurin de f) é simplesmente uma contagem de quantos ncontextos vazios existem. Estamos quase lá!

Mas onde (1/n!)acaba? Examinar o processo do tipo 'diferenciação' mostra que, quando aplicado várias vezes, preserva a 'ordem' na qual os subtermos são extraídos. Por exemplo, considere o termo (x₀, x₁)do tipo x × xe a operação de "fazer um buraco" nele duas vezes. Temos as duas sequências

(x₀, x₁)  ↝  (_₀, x₁)  ↝  (_₀, _₁)
(x₀, x₁)  ↝  (x₀, _₀)  ↝  (_₁, _₀)
(where _ represents a 'hole')

mesmo que ambos venham do mesmo termo, porque existem 2! = 2maneiras de obter dois elementos de dois, preservando a ordem. Em geral, existemn! maneiras de extrair nelementos n. Portanto, para obter uma contagem do número de configurações de um tipo de functor que possuem nelementos, precisamos contar o tipo f⁽ⁿ⁾(0)e dividir por n!, exatamente como nos coeficientes da série Maclaurin.

Então, dividir por n!acaba sendo interpretável simplesmente como ele mesmo.

Considerações finais: definições "recursivas" e analiticidade

Primeiro, algumas observações:

• se uma função f: ℝ → ℝ tem uma derivada, essa derivada é única
• Da mesma forma, se uma função f: ℝ → ℝ é analítica, ela possui exatamente uma série polinomial correspondente

Como temos a regra da cadeia, podemos usar diferenciação implícita , se formalizarmos derivadas de tipo como classes de isomorfismo. Mas a diferenciação implícita não requer nenhuma manobra alienígena, como subtração ou divisão! Portanto, podemos usá-lo para analisar definições de tipo recursivo. Para dar um exemplo de lista, temos

L(X) ≅ 1 + X × L(X)
L'(X) = X × L'(X) + L(X)

e então podemos avaliar

L'(0) = L(0) = 1

para obter o coeficiente da X¹série Maclaurin.

Mas, como estamos confiantes de que essas expressões são realmente estritamente 'diferenciáveis', mesmo que implícitas, e como temos a correspondência com as funções ℝ → ℝ, onde derivadas são certamente únicas, podemos ter certeza de que, mesmo se obtivermos os valores usando ' ilegais ', o resultado é válido.

Agora, da mesma forma, para usar a segunda observação, devido à correspondência (é um homomorfismo?) Com funções ℝ → ℝ, sabemos que, desde que estejamos satisfeitos que uma função tenha uma série de Maclaurin, se pudermos encontrar alguma série em todos , os princípios descritos acima podem ser aplicados para torná-lo rigoroso.

Quanto à sua pergunta sobre composição de funções, suponho que a regra da cadeia forneça uma resposta parcial.

Não sei ao certo quantos ADTs ao estilo Haskell se aplicam, mas suspeito que sejam muitos, se não todos. Descobri uma prova realmente maravilhosa desse fato, mas essa margem é muito pequena para contê-lo ...

Agora, certamente, essa é apenas uma maneira de descobrir o que está acontecendo aqui e provavelmente existem muitas outras maneiras.

Resumo: TL; DR

• o tipo 'diferenciação' corresponde a ' fazer um buraco '.
• a aplicação de um functor 0nos fornece os termos "vazios" para esse functor.
• Portanto, as séries de potências Maclaurin (de certa forma) correspondem rigorosamente à enumeração do número de membros de um tipo de functor com um certo número de elementos.
• diferenciação implícita torna isso mais estanque.
• a singularidade de derivadas e a singularidade de séries de potências significam que podemos falsificar os detalhes e ele funciona.

Teoria do tipo dependente e funções do tipo 'arbitrárias'

Minha primeira resposta a essa pergunta foi alta em conceitos e baixa em detalhes e refletida na subquestão "o que está acontecendo?"; esta resposta será a mesma, mas focada na subquestão, 'podemos obter funções de tipo arbitrárias?'.

Uma extensão das operações algébricas de soma e produto são os chamados "grandes operadores", que representam a soma e o produto de uma sequência (ou, mais geralmente, a soma e o produto de uma função sobre um domínio) geralmente escritos Σe Πrespectivamente. Veja Notação Sigma .

Então a soma

a₀ + a₁X + a₂X² + ...

pode ser escrito

Σ[i ∈ ℕ]aᵢXⁱ

onde aestá uma sequência de números reais, por exemplo. O produto seria representado da mesma forma com em Πvez de Σ.

Quando você olha à distância, esse tipo de expressão se parece muito com uma função 'arbitrária' X; é claro que estamos limitados a séries expressáveis ​​e suas funções analíticas associadas. Este é um candidato a uma representação em uma teoria de tipos? Definitivamente!

A classe das teorias de tipos que têm representações imediatas dessas expressões é a classe das teorias de tipos 'dependentes': teorias com tipos dependentes. Naturalmente, temos termos dependentes de termos e em idiomas como Haskell com funções de tipo e quantificação de tipos, termos e tipos dependendo de tipos. Em uma configuração dependente, também temos tipos, dependendo dos termos. Haskell não é uma linguagem de tipo dependente, embora muitos recursos de tipos dependentes possam ser simulados torturando um pouco a linguagem .

Curry-Howard e tipos dependentes

O 'isomorfismo de Curry-Howard' começou a vida como uma observação de que os termos e regras de julgamento de tipo do cálculo lambda de tipagem simples correspondem exatamente à dedução natural (conforme formulada por Gentzen) aplicada à lógica proposicional intuicionista, com os tipos substituindo as proposições , e termos substituindo as provas, apesar de as duas serem inventadas / descobertas independentemente. Desde então, tem sido uma enorme fonte de inspiração para os teóricos do tipo. Uma das coisas mais óbvias a considerar é se, e como, essa correspondência para a lógica proposicional pode ser estendida para predicar ou lógicas de ordem superior. As teorias de tipos dependentes surgiram inicialmente dessa avenida de exploração.

Para uma introdução ao isomorfismo de Curry-Howard para o cálculo lambda de tipo simples, veja aqui . Como exemplo, se queremos provar A ∧ B, devemos provar Ae provar B; uma prova combinada é simplesmente um par de provas: uma para cada conjunto.

Em dedução natural:

Γ ⊢ A    Γ ⊢ B
Γ ⊢ A ∧ B

e no cálculo lambda de tipo simples:

Γ ⊢ a : A    Γ ⊢ b : B
Γ ⊢ (a, b) : A × B

Existem correspondências semelhantes para ∨e tipos de soma, →e tipos de função, e as várias regras de eliminação.

Uma proposição improvável (intuitionisticamente falsa) corresponde a um tipo desabitado.

Com a analogia dos tipos como proposições lógicas em mente, podemos começar a considerar como modelar predicados no mundo dos tipos. Há muitas maneiras pelas quais isso foi formalizado (consulte esta introdução à Teoria dos Tipos Intuicionistas de Martin-Löf para obter um padrão amplamente utilizado), mas a abordagem abstrata geralmente observa que um predicado é como uma proposição com variáveis ​​de termo livre ou, alternativamente, uma função que leva termos a proposições. Se permitirmos que expressões de tipo contenham termos, um tratamento no estilo de cálculo lambda se apresentará imediatamente como uma possibilidade!

Considerando apenas provas construtivas, do que constitui uma prova ∀x ∈ X.P(x)? Podemos pensar nisso como uma função de prova, levando termos ( x) a provas de suas proposições correspondentes ( P(x)). Assim, os membros (provas) do tipo (proposição) ∀x : X.P(x)são funções dependentes '', o que para cada xem Xdar um termo do tipo P(x).

Que tal ∃x ∈ X.P(x)? Precisamos de qualquer membro X, xjuntamente com uma prova de P(x). Portanto, membros (provas) do tipo (proposição) ∃x : X.P(x)são 'pares dependentes': um termo distinto xem X, juntamente com um termo do tipo P(x).

Notação: vou usar

∀x ∈ X...

para declarações reais sobre os membros da classe Xe

∀x : X...

para expressões de tipo correspondentes à quantificação universal sobre o tipo X. Da mesma forma para ∃.

Considerações combinatórias: produtos e somas

Assim como a correspondência de Curry-Howard de tipos com proposições, temos a correspondência combinatória de tipos algébricos com números e funções, que é o ponto principal desta questão. Felizmente, isso pode ser estendido aos tipos dependentes descritos acima!

Vou usar a notação de módulo

|A|

representar o 'tamanho' de um tipo A, tornar explícita a correspondência descrita na pergunta, entre tipos e números. Note que este é um conceito fora da teoria; Não afirmo que exista um operador desse tipo no idioma.

Vamos contar os possíveis membros (totalmente reduzidos, canônicos) do tipo

∀x : X.P(x)

que é o tipo de funções dependentes que levam termos xde tipo Xa termos de tipo P(x). Cada uma dessas funções deve ter uma saída para cada termo de X, e essa saída deve ser de um tipo específico. Para cada xno X, então, isso dá |P(x)|'escolhas' de saída.

O punchline é

|∀x : X.P(x)| = Π[x : X]|P(x)|

o que, obviamente, não faz muito sentido se Xfor IO (), mas é aplicável a tipos algébricos.

Da mesma forma, um termo do tipo

∃x : X.P(x)

é o tipo de pares (x, p)com p : P(x), portanto, dado que qualquer um xem Xpodemos construir um par apropriado com qualquer membro de P(x), dando |P(x)|'escolhas'.

Conseqüentemente,

|∃x : X.P(x)| = Σ[x : X]|P(x)|

com as mesmas ressalvas.

Isso justifica a notação comum para tipos dependentes em teorias usando os símbolos Πe Σ, de fato, muitas teorias obscurecem a distinção entre 'para todos' e 'produto' e entre 'existe' e 'soma', devido às correspondências mencionadas acima.

Estamos chegando perto!

Vetores: representando tuplas dependentes

Podemos agora codificar expressões numéricas como

Σ[n ∈ ℕ]Xⁿ

como expressões de tipo?

Nem tanto. Embora possamos considerar informalmente o significado de expressões como Xⁿem Haskell, onde Xé um tipo e num número natural, é um abuso de notação; esta é uma expressão de tipo que contém um número: distintamente não é uma expressão válida.

Por outro lado, com tipos dependentes na imagem, tipos contendo números é precisamente o ponto; de fato, tuplas dependentes ou 'vetores' são um exemplo muito citado de como os tipos dependentes podem fornecer segurança pragmática no nível de tipo para operações como o acesso à lista . Um vetor é apenas uma lista, juntamente com informações em nível de tipo sobre seu tamanho: exatamente o que buscamos para expressões de tipo Xⁿ.

Durante a duração desta resposta, deixe

Vec X n

seja o tipo de comprimento de nvetores de Xvalores de tipo.

Tecnicamente, naqui está, em vez de um número natural real , uma representação no sistema de um número natural. Podemos representar números naturais ( Nat) no estilo Peano como zero ( 0) ou o sucessor ( S) de outro número natural, e para n ∈ ℕeu escrever, ˻n˼quero dizer o termo em Natque representa n. Por exemplo, ˻3˼é S (S (S 0)).

Então nós temos

|Vec X ˻n˼| = |X|ⁿ

para qualquer n ∈ ℕ.

Tipos Nat: promovendo ℕ termos para tipos

Agora podemos codificar expressões como

Σ[n ∈ ℕ]Xⁿ

como tipos. Esta expressão em particular daria origem a um tipo que é obviamente isomórfico ao tipo de lista de X, conforme identificado na pergunta. (Não apenas isso, mas do ponto de vista teórico da categoria, a função de tipo - que é um functor - levar Xpara o tipo acima é naturalmente isomórfica para o functor List.)

Uma peça final do quebra-cabeça para funções 'arbitrárias' é como codificar, por

f : ℕ → ℕ

expressões como

Σ[n ∈ ℕ]f(n)Xⁿ

para que possamos aplicar coeficientes arbitrários a uma série de potências.

Já entendemos a correspondência de tipos algébricos com números, permitindo mapear de tipos para números e funções de tipo para funções numéricas. Nós também podemos ir para o outro lado! - tomando um número natural, existe obviamente um tipo algébrico definível com tantos membros do termo, independentemente de termos ou não tipos dependentes. Podemos facilmente provar isso fora da teoria dos tipos por indução. O que precisamos é de uma maneira de mapear de números naturais para tipos, dentro do sistema.

Uma percepção agradável é que, uma vez que temos tipos dependentes, a prova por indução e a construção por recursão tornam-se intimamente semelhantes - na verdade, são a mesma coisa em muitas teorias. Como podemos provar por indução que existem tipos que atendem às nossas necessidades, não deveríamos ser capazes de construí-los?

Existem várias maneiras de representar tipos no nível do termo. Usarei aqui uma notação Haskellish imaginária *para o universo de tipos, geralmente considerado um tipo em um ambiente dependente. ¹

Da mesma forma, também existem pelo menos tantas maneiras de ℕanotar 'eliminação' quanto as teorias de tipos dependentes. Usarei uma notação de correspondência de padrões haskellish.

Precisamos de um mapeamento, αde Natpara *, com a propriedade

∀n ∈ ℕ.|α ˻n˼| = n.

A seguinte pseudo-definição é suficiente.

data Zero -- empty type
data Successor a = Z | Suc a -- Successor ≅ Maybe

α : Nat -> *
α 0 = Zero
α (S n) = Successor (α n)

Então, vemos que a ação de αespelha o comportamento do sucessor S, tornando-o um tipo de homomorfismo. Successoré uma função de tipo que 'adiciona um' ao número de membros de um tipo; isto é, |Successor a| = 1 + |a|para qualquer aum com um tamanho definido.

Por exemplo α ˻4˼(que é α (S (S (S (S 0))))), é

Successor (Successor (Successor (Successor Zero)))

e os termos deste tipo são

Z
Suc Z
Suc (Suc Z)
Suc (Suc (Suc Z))

dando-nos exatamente quatro elementos: |α ˻4˼| = 4.

Da mesma forma, para qualquer um n ∈ ℕ, temos

|α ˻n˼| = n

como requerido.

1. Muitas teorias exigem que os membros de *sejam meros representantes de tipos, e uma operação é fornecida como um mapeamento explícito dos termos do tipo *para os tipos associados. Outras teorias permitem que os tipos literais sejam entidades de nível de termo.

Funções 'arbitrárias'?

Agora temos o aparato para expressar uma série de potências totalmente geral como um tipo!

As séries

Σ[n ∈ ℕ]f(n)Xⁿ

torna-se o tipo

∃n : Nat.α (˻f˼ n) × (Vec X n)

onde ˻f˼ : Nat → Nathá alguma representação adequada no idioma da função f. Podemos ver isso da seguinte maneira.

|∃n : Nat.α (˻f˼ n) × (Vec X n)|
    = Σ[n : Nat]|α (˻f˼ n) × (Vec X n)|          (property of ∃ types)
    = Σ[n ∈ ℕ]|α (˻f˼ ˻n˼) × (Vec X ˻n˼)|        (switching Nat for ℕ)
    = Σ[n ∈ ℕ]|α ˻f(n)˼ × (Vec X ˻n˼)|           (applying ˻f˼ to ˻n˼)
    = Σ[n ∈ ℕ]|α ˻f(n)˼||Vec X ˻n˼|              (splitting product)
    = Σ[n ∈ ℕ]f(n)|X|ⁿ                           (properties of α and Vec)

Quão arbitrário é isso? Estamos limitados não apenas a coeficientes inteiros por esse método, mas a números naturais. Além disso, fpode ser qualquer coisa, dada a linguagem Turing Complete com tipos dependentes, podemos representar qualquer função analítica com coeficientes de números naturais.

Não investiguei a interação disso com, por exemplo, o caso fornecido na questão List X ≅ 1/(1 - X)ou que sentido esses 'tipos' negativos e não inteiros podem ter nesse contexto.

Esperamos que esta resposta explique até onde podemos ir com funções de tipo arbitrário.