Como os genéricos são implementados em um compilador moderno?

14

O que quero dizer aqui é como vamos de algum template T add(T a, T b) ... para o código gerado? Eu pensei em algumas maneiras de conseguir isso, nós armazenamos a função genérica em um AST como Function_Node e, em seguida, cada vez que usamos, armazenamos no nó da função original uma cópia de si mesmo com todos os tipos T substituído com os tipos que estão sendo usados. Por exemplo, add<int>(5, 6) armazenará uma cópia da função genérica para add e substituirá todos os tipos T na cópia por int .

Então, seria algo parecido com:

struct Function_Node {
    std::string name; // etc.
    Type return_type;
    std::vector<std::pair<Type, std::string>> arguments;
    std::vector<Function_Node> copies;
};

Em seguida, você pode gerar código para eles e, quando visitar um Function_Node , em que a lista de cópias copies.size() > 0 , invocará visitFunction em todas as cópias.

visitFunction(Function_Node& node) {
    if (node.copies.size() > 0) {
        for (auto& node : nodes.copies) {
            visitFunction(node);
        }
        // it's a generic function so we don't want
        // to emit code for this.
        return;
    }
}

Isso funcionaria bem? Como os compiladores modernos abordam esse problema? Eu acho que talvez outra maneira de fazer isso seja você poderia injetar as cópias na AST para que ela seja executada em todas as fases semânticas. Eu também pensei que talvez você pudesse gerá-los de uma forma imediata como o MIR de Rust ou o Swifts SIL, por exemplo.

Meu código está escrito em Java, os exemplos aqui são C ++ porque é um pouco menos detalhado para exemplos - mas o princípio é basicamente a mesma coisa. Embora possa haver alguns erros, porque eles são escritos à mão na caixa de perguntas.

Note que quero dizer compilador moderno como a melhor maneira de abordar esse problema. E quando falo de genéricos não quero dizer como os genéricos de Java onde eles usam o apagamento de tipos.

    
por Jon Flow 20.10.2016 / 17:29
fonte

2 respostas

14

How are generics implemented in a modern compiler?

Convido você a ler o código-fonte de um compilador moderno se quiser saber como um compilador moderno funciona. Eu começaria com o projeto Roslyn, que implementa compiladores C # e Visual Basic.

Em particular, chamo a sua atenção para o código no compilador C # que implementa símbolos de tipo:

link

e você também pode querer ver o código das regras de conversibilidade. Há muito o que diz respeito à manipulação algébrica de tipos genéricos.

link

Eu tentei fazer com que o último fosse fácil de ler.

I've thought of a few ways to achieve this, we store the generic function in an AST as Function_Node and then each time we use it we store in the original function node a copy of itself with all of the types T substituted with the types that are being used.

Você está descrevendo modelos , não genéricos . C # e Visual Basic possuem genéricos reais em seus sistemas de tipos.

Resumidamente, eles funcionam assim.

  • Começamos estabelecendo regras para o que formalmente constitui um tipo em tempo de compilação. Por exemplo: int é um tipo, um parâmetro de tipo T é um tipo, para qualquer tipo X , o tipo de matriz X[] também é um tipo e assim por diante.

  • As regras para genéricos envolvem substituição. Por exemplo, class C with one type parameter não é um tipo. É um padrão para fazer tipos. class C with one type parameter called T, under substitution with int for T é um tipo.

  • As regras que descrevem as relações entre os tipos - compatibilidade na atribuição, como determinar o tipo de uma expressão e assim por diante - são projetadas e implementadas no compilador.

  • Uma linguagem de código de bytes que suporta tipos genéricos em seu sistema de metadados é projetada e implementada.

  • No tempo de execução, o compilador JIT transforma o bytecode em código de máquina; é responsável pela construção do código de máquina apropriado, dada uma especialização genérica.

Então, por exemplo, em C # quando você diz

class C<T> { public void X(T t) { Console.WriteLine(t); } }
...
var c = new C<int>(); 
c.X(123);

o compilador verifica que, em C<int> , o argumento int é uma substituição válida para T e gera metadados e bytecode de acordo. No tempo de execução, o jitter detecta que um C<int> está sendo criado pela primeira vez e gera o código de máquina apropriado dinamicamente.

    
por 20.10.2016 / 22:48
fonte
9

A maioria das implementações de genéricos (ou melhor: polimorfismo paramétrico) usa o tipo de apagamento. Isso simplifica muito o problema de compilar código genérico, mas funciona apenas para tipos de caixa: como cada argumento é efetivamente um ponteiro opaco, precisamos de um mecanismo de despacho VTable ou similar para executar operações nos argumentos. Em Java:

<T extends Addable> T add(T a, T b) { … }

pode ser compilado, com verificação de tipo e chamado da mesma maneira que

Addable add(Addable a, Addable b) { … }

exceto que os genéricos fornecem ao verificador de tipos muito mais informações no site de chamadas. Essas informações extras podem ser manipuladas com variáveis de tipo , especialmente quando tipos genéricos são inferidos. Durante a verificação de tipo, cada tipo genérico pode ser substituído por uma variável, vamos chamá-lo de $T1 :

$T1 add($T1 a, $T1 b)

A variável de tipo é então atualizada com mais fatos à medida que eles se tornam conhecidos, até que ele possa ser substituído por um tipo concreto. O algoritmo de verificação de tipo deve ser escrito de uma maneira que acomode essas variáveis de tipo, mesmo que elas ainda não tenham sido resolvidas para um tipo completo. Em Java, isso geralmente pode ser feito facilmente, já que o tipo dos argumentos é geralmente conhecido antes que o tipo de chamada de função precise ser conhecido. Uma exceção notável é uma expressão lambda como argumento de função, que requer o uso de tais variáveis de tipo.

Mais tarde, um otimizador pode gerar código especializado para um determinado conjunto de argumentos, o que seria efetivamente uma espécie de inlining.

Um VTable para argumentos de tipo genérico pode ser evitado se a função genérica não executar nenhuma operação no tipo, mas apenas passá-los para outra função. Por exemplo. a função Haskell call :: (a -> b) -> a -> b; call f x = f x não precisaria delimitar o argumento x . No entanto, isso requer uma convenção de chamada que possa passar por valores sem conhecer seu tamanho, o que essencialmente a restringe a ponteiros de qualquer maneira.

O C ++ é muito diferente da maioria das linguagens nesse aspecto. Uma classe ou função modelada (discutirei apenas funções modeladas aqui) não é chamada em si mesma. Em vez disso, os modelos devem ser entendidos como uma meta função de compilação que retorna uma função real. Ignorando inferência de argumento de modelo por um momento, a abordagem geral resume-se a estas etapas:

  1. Aplique o modelo aos argumentos de modelo fornecidos. Por exemplo, chamar template<class T> T add(T a, T b) { … } as add<int>(1, 2) nos daria a função real int __add__T_int(int a, int b) (ou qualquer abordagem de manuseio de nomes usada).

  2. Se o código para essa função já tiver sido gerado na unidade de compilação atual, continue. Caso contrário, gere o código como se uma função int __add__T_int(int a, int b) { … } tivesse sido escrita no código-fonte. Isso envolve a substituição de todas as ocorrências do argumento de modelo por seus valores. Esta é provavelmente uma transformação AST → AST. Em seguida, execute a verificação de tipo na AST gerada.

  3. Compile a chamada como se o código-fonte tivesse sido __add__T_int(1, 2) .

Observe que os modelos C ++ têm uma interação complexa com o mecanismo de resolução de sobrecarga, que não desejo descrever aqui. Observe também que essa geração de código torna impossível ter um método modelado que também seja virtual - uma abordagem baseada em eliminação de tipos não sofre dessa restrição substancial.

O que isso significa para seu compilador e / ou idioma? Você precisa pensar cuidadosamente sobre o tipo de genérico que deseja oferecer. O apagamento de tipo na ausência de inferência de tipos é a abordagem mais simples possível se você suportar tipos de caixas. A especialização em modelos é aparentemente bastante simples, mas geralmente envolve o mangling de nomes e (para várias unidades de compilação) duplicação substancial na saída, já que os modelos são instanciados no site de chamada, não no site de definição.

A abordagem que você mostrou é essencialmente uma abordagem de modelo semelhante ao C ++. No entanto, você armazena os modelos especializados / instanciados como “versões” do modelo principal. Isso é enganoso: eles não são os mesmos conceitualmente, e instanciações diferentes de uma função podem ter tipos muito diferentes. Isso complicará as coisas a longo prazo se você também permitir a sobrecarga de funções. Em vez disso, você precisaria de uma noção de um conjunto de sobrecargas que contenha todas as funções e modelos possíveis que compartilham um nome. Exceto para resolver a sobrecarga, você pode considerar diferentes modelos instanciados para serem completamente separados um do outro.

    
por 20.10.2016 / 19:02
fonte