Existe uma hierarquia de expressividade para sistemas de tipos?

Inspirado pelas extensas hierarquias presentes na teoria da complexidade, perguntei-me se essas hierarquias também estavam presentes nos sistemas de tipos. No entanto, os dois exemplos que encontrei até agora são mais como listas de verificação (com recursos ortogonais) do que hierarquias (com sistemas de tipos sucessivamente cada vez mais expressivos).

Os dois exemplos que encontrei são o cubo Lambda e o conceito de polimorfismo com classificação k . O primeiro é uma lista de verificação com três opções, o segundo é uma hierarquia real (apesar de que k-classificado para valores específicos de k é incomum, acredito). Todos os outros recursos do sistema de tipos que conheço são principalmente ortogonais.

Estou interessado nesses conceitos porque estou projetando minha própria linguagem e estou muito curioso em saber como ela se classifica entre os sistemas de tipos existentes no momento (meu sistema de tipos é um pouco não convencional, tanto quanto eu sei).

Percebo que o conceito de 'expressividade' pode ser um pouco vago, o que pode explicar por que os sistemas de tipos me parecem listas de verificação.

Existem vários sentidos de "expressividade" que você pode querer para um sistema de tipos.

1. Que funções matemáticas você pode expressar em um sistema de tipos específico. Por exemplo, no cálculo lambda simplesmente digitado, nem todas as funções computáveis ​​podem ser expressas. O mesmo vale para o Sistema , mas estritamente mais funções podem ser expressas. Isso não é muito interessante quando você digita sistemas para idiomas completos de Turing.$F$

2. Can sistema typecheck cada programa escrito em sistema B . É basicamente sobre isso que se trata a primeira noção de força de Cody para os PTSs. Mais uma vez, Sistema F é mais forte do que a STLC neste ordenação, uma vez a cada tipos de programa STLC em Sistema F . Da mesma forma, um sistema com subtipagem será mais forte que um sistema sem.$A$$B$$F$$F$

3. Existem transformações locais (no sentido do artigo de Felleisen Sobre o poder expressivo das linguagens de programação ) que permitem que um programa que digita no sistema digite no sistema B , mas não vice-versa. $A$$B$

4. Um sistema de tipo garante propriedades mais fortes que outro. Por exemplo, sistemas do tipo linear apenas rejeitam mais programas, mas isso lhes permite fazer afirmações mais fortes sobre os programas que eles aceitam.

Infelizmente, não acredito que tenha havido trabalho para categorizar ou formalizar essas noções, com exceção do cubo lambda de Barendregt, como o @cody discute.

Não tenho certeza se tenho uma resposta satisfatória para sua pergunta, mas se você considerar o Pure Type Systems, que é uma generalização dos sistemas encontrados no cubo lambda (uma visão geral completa, embora um pouco datada, pode ser encontrada no texto clássico de Barendregt) ), existem algumas noções naturais de hierarquias:

1. Morphisms de PTSses: intuitivamente há um morfismo entre o PTS A eo PTS B se cada termo bem digitado pode ser digitado em B: y- ⊢ B t : $\Gamma\vdash_A\ t\colon T$$\Gamma\vdash_B\ t\colon T$$\Gamma, t$$T$$*\colon *$$(*,*,*)$PTS no sentido de que existe um morfismo de todos os outros PTS para ele. Isso pode ser visto como uma medida da expressividade de um sistema de tipos, onde o PTS final é o sistema mais expressivo.

2. $A$$B$$A$$F_\omega$$ECC$$\leftrightarrow$