Inferência de tipo com tipos de produto

Estou trabalhando em um compilador para uma linguagem concatenativa e gostaria de adicionar suporte à inferência de tipo. Entendo Hindley-Milner, mas tenho aprendido a teoria dos tipos à medida que passo, por isso não tenho certeza de como adaptá-la. O sistema a seguir é sólido e decididamente inferível?

Um termo é um literal, uma composição de termos, uma cotação de um termo ou um primitivo.

e ::= x | e e | [e] | \dots

$e ::= x \:\big|\: e\:e \:\big|\: [e] \:\big|\: \dots$

Todos os termos denotam funções. Para duas funções e , , isto é, a justaposição indica a composição inversa. Os literais denotam funções niládicas. $e_1$ $e_2$ $e_1\:e_2 = e_2 \circ e_1$

Os termos que não sejam composição têm regras básicas de tipo:

\frac{}{x : ι} [Lit] \frac{Γ ⊢ e : σ}{Γ ⊢ [e] : \forall α . α \to σ \times α} [Quot], α not free in Γ

$\dfrac{}{x : \iota}\text{[Lit]} \\ \dfrac{\Gamma\vdash e : \sigma}{\Gamma\vdash [e] : \forall\alpha.\:\alpha\to\sigma\times\alpha}\text{[Quot]}, \alpha \text{ not free in } \Gamma$

As regras de aplicação são notavelmente ausentes, pois as linguagens concatenativas não possuem.

Um tipo é um literal, uma variável de tipo ou uma função de pilhas para pilhas, em que uma pilha é definida como uma tupla aninhada à direita. Todas as funções são implicitamente polimórficas em relação ao "resto da pilha".

\begin{aligned} τ & ::= ι | α | ρ \to ρ \\ ρ & ::= () | τ \times ρ \\ σ & ::= τ | \forall α . σ \end{aligned}

$\begin{aligned} \tau & ::= \iota \:\big|\: \alpha \:\big|\: \rho\to\rho \\ \rho & ::= () \:\big|\: \tau\times\rho \\ \sigma & ::= \tau \:\big|\: \forall\alpha.\:\sigma \end{aligned}$

Esta é a primeira coisa que parece suspeita, mas não sei exatamente o que há de errado nisso.

Para facilitar a legibilidade e reduzir os parênteses, presumo que nos esquemas de tipos. Também usarei uma letra maiúscula para uma variável que denota uma pilha, em vez de um único valor. $a\:b = b \times (a)$

Existem seis primitivos. Os cinco primeiros são bastante inócuos. duppega o valor mais alto e produz duas cópias. swapaltera a ordem dos dois principais valores. popdescarta o valor superior. quotepega um valor e produz uma cotação (função) que o retorna. applyaplica uma cotação à pilha.

\begin{aligned} d u p & :: \forall A b . A b \to A b b \\ s w a p & :: \forall A b c . A b c \to A c b \\ p o p & :: \forall A b . A b \to A \\ q u o t e & :: \forall A b . A b \to A (\forall C . C \to C b) \\ a p p l y & :: \forall A B . A (A \to B) \to B \end{aligned}

$\begin{aligned} \mathtt{dup} & :: \forall A b.\: A\:b \to A\:b\:b \\ \mathtt{swap} & :: \forall A b c.\: A\:b\:c \to A\:c\:b \\ \mathtt{pop} & :: \forall A b.\: A\:b \to A \\ \mathtt{quote} & :: \forall A b.\: A\:b \to A\:(\forall C. C \to C\:b) \\ \mathtt{apply} & :: \forall A B.\: A\:(A \to B) \to B \\ \end{aligned}$

O último combinador, composedeve pegar duas aspas e retornar o tipo de concatenação, ou seja, . Na linguagem concatenativa estaticamente tipada Cat , o tipo de é muito direto. $[e_1]\:[e_2]\:\mathtt{compose} = [e_1\:e_2]$ compose

c o m p o s e :: \forall A B C D . A (B \to C) (C \to D) \to A (B \to D)

$\mathtt{compose} :: \forall A B C D.\: A\:(B \to C)\:(C \to D) \to A\:(B \to D)$

No entanto, esse tipo é muito restritivo: requer que a produção da primeira função corresponda exatamente ao consumo da segunda. Na realidade, você precisa assumir tipos distintos e depois unificá-los. Mas como você escreveria esse tipo?

c o m p o s e :: \forall A B C D E . A (B \to C) (D \to E) \to A \dots

$\mathtt{compose} :: \forall A B C D E. A\:(B \to C)\:(D \to E) \to A \dots$

Se você deixar denotar uma diferença de dois tipos, acho que você pode escrever o tipo corretamente. $\setminus$ compose

c o m p o s e :: \forall A B C D E . A (B \to C) (D \to E) \to A ((D ∖ C) B \to ((C ∖ D) E))

$\mathtt{compose} :: \forall A B C D E.\: A\:(B \to C)\:(D \to E) \to A\:((D \setminus C)\:B \to ((C \setminus D)\:E))$

Isto ainda é relativamente simples: composeassume uma função e uma . Seu resultado consome acima do consumo de não produzido por e produz acima da produção de não consumido por . Isso dá a regra para a composição comum. $f_1 : B \to C$ $f_2 : D \to E$ $B$ $f_2$ $f_1$ $D$ $f_1$ $f_2$

\frac{Γ ⊢ e_{1} : \forall A B . A \to B Γ ⊢ e_{2} : \forall C D . C \to D}{Γ ⊢ e_{1} e_{2} : ((C ∖ B) A \to ((B ∖ C) D))} [Comp]

$\dfrac{\Gamma\vdash e_1 : \forall A B.\: A \to B \quad \Gamma\vdash e_2 : \forall C D. C \to D}{\Gamma\vdash e_1 e_2 : ((C \setminus B)\:A \to ((B \setminus C)\:D))}\text{[Comp]}$

No entanto, não sei se esse hipotético realmente corresponde a alguma coisa, e eu o persigo em círculos há tempo suficiente para achar que tomei uma decisão errada. Poderia ser uma simples diferença de tuplas? $\setminus$

\begin{aligned} \forall A . () ∖ A & = () \\ \forall A . A ∖ () & = A \\ \forall A B C D . A B ∖ C D & = B ∖ D iff A = C \\ otherwise & = undefined \end{aligned}

$\begin{align} \forall A. () \setminus A & = () \\ \forall A. A \setminus () & = A \\ \forall A B C D. A B \setminus C D & = B \setminus D \textit{ iff } A = C \\ \text{otherwise} & = \textit{undefined} \end{align}$

Existe algo terrivelmente quebrado sobre isso que não estou vendo ou estou no caminho certo? (Provavelmente quantifiquei algumas dessas coisas incorretamente e também apreciaria correções nessa área.)

programming-languages logic compilers type-theory type-checking Jon Purdy
fonte

Como você usa variáveis em sua gramática? Esta pergunta deve ajudá-lo a lidar com o "subtipo" que você parece precisar.

Jmad

@ jmad: Não sei se entendi a pergunta. Variáveis de tipo existem apenas para definir formalmente esquemas de tipos, e a própria linguagem não possui variáveis, apenas definições, que podem ser [mutuamente] recursivas.

precisa

Justo. Você pode dizer por que (talvez com um exemplo) a regra para composeé muito restritiva? Tenho a impressão de que isso está bem assim. (por exemplo, a restrição pode ser tratado por unificação como para aplicação em como no λ-cálculo)

C = D

$C=D$

Jmad

@jmad: Claro. Considere twicedefinido como dup compose apply, que recebe uma cotação e a aplica duas vezes. [1 +] twiceestá bom: você está compondo duas funções do tipo . Mas não é: se , o problema é , portanto a expressão é desaprovada, mesmo que deva ser válida e ter digite . É claro que a solução é colocar o qualificador no lugar certo, mas estou me perguntando principalmente como realmente escrever o tipo sem alguma definição circular.

ι \to ι

$\iota\to\iota$ [pop] twice

\forall A b . f_{1}, f_{2} : A b \to A

$\forall A b.\:f_1, f_2 : A\:b\to A$

A \neq A b

$A \neq A\:b$

\forall A b . A b b \to A

$\forall A b.\:A\:b\:b\to A$ compose

21412 Jon Purdy

O seguinte rank-2 tipo parece ser suficientemente geral. É muito mais polimórfico do que o tipo proposto na pergunta. Aqui, a variável quantifica sobre pedaços contíguos da pilha, que capturam funções com vários argumentos.

compose : \forall A B C δ . δ (\forall α . α A \to α B) (\forall β . β B \to β C) \to δ (\forall γ . γ A \to γ C)

$\text{compose}:\forall ABC\delta. \delta\ (\forall \alpha.\alpha\ A\to \alpha B)\ (\forall \beta.\beta\ B\to \beta C) \to \delta\ (\forall \gamma.\gamma\ A\to \gamma C)$

Letras gregas são usadas para as variáveis restantes da pilha apenas para maior clareza.

Ele expressa as restrições de que a pilha de saída do primeiro elemento na pilha precisa ser a mesma que a pilha de entrada do segundo elemento. Instanciar adequadamente a variável para os dois argumentos realmente é a maneira de fazer com que as restrições funcionem corretamente, em vez de definir uma nova operação, como você propõe na pergunta. $B$

A verificação de tipos do tipo 2 é indecidível em geral, acredito, embora tenha sido realizado algum trabalho que produz bons resultados na prática (para Haskell):

Simon L. Peyton Jones, Dimitrios Vytiniotis, Stephanie Weirich, Mark Shields: Inferência prática de tipo para tipos de classificação arbitrária. J. Funct. Programa. 17 (1): 1-82 (2007)

A regra de tipo para composição é simplesmente:

\frac{Γ ⊢ e_{1} : \forall α . α A \to α B Γ ⊢ e_{1} : \forall α . α B \to α C}{Γ ⊢ e_{1} e_{2} : \forall α . α A \to α C}

$\dfrac{\Gamma\vdash e_1:\forall \alpha. \alpha\ A\to \alpha\ B\qquad \Gamma\vdash e_1:\forall \alpha. \alpha\ B\to \alpha\ C} {\Gamma\vdash e_1\ e_2:\forall \alpha.\alpha\ A\to\alpha\ C}$

Para que o sistema de tipos funcione em geral, você precisa da seguinte regra de especialização:

\frac{Γ ⊢ e : \forall α . α A \to α B}{Γ ⊢ e : \forall α . C A \to α C B}

$\dfrac{\Gamma\vdash e:\forall \alpha. \alpha\ A \to \alpha\ B} {\Gamma\vdash e:\forall \alpha.C\ A\to \alpha\ C\ B}$

Dave Clarke
fonte

Obrigado, isso foi muito útil. Esse tipo está correto para funções de um único argumento, mas não suporta vários argumentos. Por exemplo, dup +deve ter o tipo porque tem o tipo . Mas a inferência de tipo na ausência de anotações é um requisito absoluto, portanto, claramente, preciso voltar à prancheta. Tenho uma idéia para outra abordagem a seguir, e vou postar um blog sobre isso se der certo.

ι \to ι

$\iota\to\iota$ +

ι ι \to ι

$\iota\:\iota\to\iota$

9114 Jon Purdy

Os tipos de pilha quantificam sobre fragmentos de pilha, portanto não há problema em lidar com duas funções de argumento. Não tenho certeza de como isso se aplica dup +, pois isso não usa composição, como você definiu acima.

18712 Dave

Er, certo, eu quis dizer [dup] [+] compose. Mas eu li como ; diga ; então você tem e não . O aninhamento não está correto, a menos que você gire a pilha para que o topo seja o último elemento (aninhado mais profundo).

α B

$\alpha\:B$

B \times α

$B\times\alpha$

B = ι \times ι

$B=\iota\times\iota$

(ι \times ι) \times α

$(\iota\times\iota)\times\alpha$

ι \times (ι \times α)

$\iota\times(\iota\times\alpha)$

21412 Jon Purdy

Eu posso estar construindo minha pilha na direção errada. Não acho que o aninhamento seja importante, desde que os pares que formam a pilha não apareçam na linguagem de programação. (Eu estou planejando para atualizar a minha resposta, mas necessidade de fazer uma pequena pesquisa em primeiro lugar.)

Dave Clarke

Sim, o aninhamento é praticamente um detalhe de implementação.

21812 Jon Purdy

Inferência de tipo com tipos de produto

Respostas: