Em algumas áreas da programação, é normal escrever uma estrutura ou algoritmo de dados que possa funcionar com elementos de diferentes tipos. Por exemplo, uma lista de genéricos ou um algoritmo de classificação que precisa apenas de uma função de comparação. Em várias linguagens, são oferecidas várias maneiras de solucionar esse problema: desde apontar as funções comuns apropriadas (C, Go) até os programadores e sistemas genéricos tão poderosos que eles se tornam completos em Turing (
Rust ,
C ++ ). Neste artigo, falarei sobre sistemas genéricos de diferentes idiomas e sua implementação. Começarei resolvendo o problema em idiomas sem um sistema semelhante (como C) e depois mostrarei como a adição gradual de extensões leva a sistemas de outros idiomas.
Considero os genéricos uma opção interessante, porque são um caso especial simples da tarefa geral de metaprogramação: escrever programas que podem gerar classes de outros programas. Como prova, mostrarei como três métodos de metaprogramação diferentes e completamente gerais podem ser considerados extensões multidirecionais no espaço de sistemas genéricos: linguagens dinâmicas como Python, macro sistemas procedurais como
Template Haskel e compilação em fases como
Zig e
Terra .
Revisão
Desenhei um diagrama de blocos de todos os sistemas descritos no artigo para que você possa apresentar seu conteúdo e como esses sistemas estão interconectados:
Idéias principais
Suponha que estamos escrevendo em uma linguagem sem sistemas genéricos e queremos criar uma estrutura de dados de estrutura de dados de pilha genérica que funcione com dados de qualquer tipo. O problema é que cada definição de função e tipo funcionará apenas com dados do mesmo tamanho e copiados de uma maneira e geralmente funcionará da mesma forma.
Há duas maneiras de contornar isso: verifique se todos os tipos de dados agem da mesma maneira em nossa estrutura ou faça muitas cópias da estrutura de dados com pequenas alterações para funcionar corretamente com cada tipo de dado. Essas idéias formaram a base de dois grandes grupos de soluções com genéricos: boxe e monomorfização.
Empacotar significa colocar tudo em uma linha em "caixas" unificadas que funcionam da mesma maneira. Isso geralmente é feito assim: os dados são colocados em um heap e os ponteiros para eles são colocados na estrutura de dados. Você pode fazer ponteiros para todos os tipos que funcionarão da mesma maneira, para que o mesmo código funcione com dados de qualquer tipo! No entanto, isso leva ao aumento do consumo de memória, pesquisa dinâmica e falhas de cache. Em C, isso significa que sua estrutura de dados armazena ponteiros
void* e simplesmente armazena em cache os dados de e para
void* (se os dados não estiverem no heap, eles serão colocados lá).
Monomorfização significa copiar repetidamente o código para os diferentes tipos de dados que queremos armazenar. Cada instância de código pode usar diretamente os métodos de tamanho e dados com os quais trabalha, sem pesquisa dinâmica. Com essa abordagem, o código executa o mais rápido, mas seu tamanho e tempo de compilação aumentam, porque compilamos repetidamente o mesmo código com pequenas alterações. Em C, isso corresponde à
definição de toda a estrutura de dados como uma macro , seguida por sua chamada para cada tipo de dado.
Em geral, durante a compilação, o código é compilado mais rapidamente, mas seu desempenho pode se deteriorar durante a execução, enquanto durante a monomorfização geramos código rápido, mas leva mais tempo para compilar e otimizar todas as instâncias do código. Outra diferença é que, quando as extensões de empacotamento permitem um comportamento mais dinâmico do código executável, a monomorfização permite separar com mais flexibilidade diferentes instâncias diferentes do código genérico. Também é importante notar que, em alguns programas grandes, os benefícios da monomorfização podem ser compensados por falhas no cache de instruções adicionais do código gerado.
Cada um dos esquemas descritos para trabalhar com genéricos pode ser expandido em direções diferentes, se você precisar de mais recursos ou segurança, e os autores de vários idiomas apresentaram soluções muito interessantes. Por exemplo, ambas as abordagens podem ser usadas em Rust e C #!
Embalagem
Vamos começar com um exemplo de embalagem básica no Go:
type Stack struct { values []interface{} } func (this *Stack) Push(value interface{}) { this.values = append(this.values, value) } func (this *Stack) Pop() interface{} { x := this.values[len(this.values)-1] this.values = this.values[:len(this.values)-1] return x }
Além disso, o empacotamento é usado em C (
void* ), Go (
interface{} ), Java pré-genérico (
Object ) e Objective-C pré-genérico (
id ).
Genéricos compactados com tipos de purificação
O principal método de embalagem tem desvantagens:
- Dependendo do idioma, geralmente precisamos converter valores para ou do tipo correto sempre que lemos ou gravamos na estrutura de dados.
- Nada nos impede de inserir elementos de tipos diferentes na estrutura, o que pode provocar bugs que parecem travamentos durante a execução do código.
Ambos os problemas podem ser resolvidos adicionando genéricos ao sistema de tipos de funcionalidade, enquanto o método de empacotamento principal é usado da mesma maneira que antes durante a execução do código. Essa abordagem costuma ser chamada de apagamento de tipo, porque os tipos no sistema genérico são substituídos e se tornam um tipo sob o capô (como
Object ).
Java e Objective-C começaram com o empacotamento usual e, posteriormente, adquiriram ferramentas de linguagem para genéricos com tipo de mash, por motivos de compatibilidade, usando os mesmos tipos de coleção de antes, mas com os parâmetros opcionais de tipos genéricos. Considere um exemplo de um artigo da Wikipedia sobre
genéricos em Java :
List v = new ArrayList(); v.add("test");
Genéricos em pacote derivados com desempenho unificado
O OCaml desenvolve ainda mais a ideia de uma visão unificada. Não há tipos primitivos que precisam de posicionamento adicional de empacotamento (como um
int deve se transformar em
Integer para entrar em um
ArrayList em Java), porque tudo já está compactado ou representado por um valor inteiro do tamanho de um ponteiro, ou seja, tudo se encaixa em uma palavra de máquina. Mas quando o coletor de lixo olha os dados armazenados em estruturas genéricas, ele precisa distinguir ponteiros de números, para que os números sejam marcados com um bit, colocados onde os ponteiros alinhados corretamente não têm um bit, deixando intervalos de apenas 31 ou 63 bits.
O OCaml também possui um sistema de inferência de tipos, para que você possa escrever uma função e o compilador produzirá o tipo genérico mais adequado se você não anotá-la e, portanto, as funções parecerão uma linguagem de tipo dinâmico:
let first (head :: tail) = head (* inferred type: 'a list -> 'a *)
O tipo especificado pode ser chamado de "uma função da lista de elementos do tipo
'a em algo com o tipo
'a ". Isso significa que o tipo de retorno será o mesmo que o tipo de lista e pode ser de qualquer tipo.
Interfaces
Outra limitação da embalagem convencional é que os tipos embalados são
completamente opacos. Isso não é um problema para estruturas de dados como uma pilha, mas ferramentas como classificar funções genéricas precisam de recursos adicionais, como funções de comparação específicas de tipo. Existem várias maneiras de implementar isso em tempo de execução e refletir no idioma. Tecnicamente, essas são direções diferentes, e você pode
implementar o mesmo idioma com várias abordagens semelhantes . No entanto, os recursos de diferentes idiomas afetam sua implementação, e somente então as extensões aumentam os pontos fortes das implementações selecionadas. Isso significa que existem duas famílias de idiomas baseadas em abordagens diferentes para o tempo de execução: tabelas de métodos virtuais (vtables) e transferência de dicionário.
Tabelas de método de interface
Se queremos fornecer funções específicas de tipo, aderindo à estratégia de empacotamento em prol do trabalho unificado com tudo, é suficiente ter uma maneira unificada de encontrar funções semelhantes que precisamos obter do objeto. Essa abordagem é chamada de "tabelas de métodos virtuais" (vtables, tabelas de métodos virtuais), embora ninguém use o nome completo. Ele é implementado da seguinte maneira: em um deslocamento zero em cada objeto de estrutura genérica, há um ponteiro para uma tabela de ponteiros de função com um circuito consistente. Nessas tabelas, o código genérico procura ponteiros para funções específicas de tipo, indexando ponteiros específicos em deslocamentos fixos.
É assim que os tipos de
interface são implementados nos objetos Go e
dyn trait no Rust. Quando você converte um tipo para um tipo de interface do que implementa, um wrapper é criado para a interface que contém um ponteiro para o objeto de origem e um ponteiro para a tabela de funções específicas de tipo. Mas isso requer um nível adicional de endereçamento indireto de ponteiros e outro esquema. Portanto, a classificação em Go usa a
interface do contêiner com o método Swap e não pega a fatia da interface Comparable, porque isso exigiria colocar na memória uma fatia completamente nova dos tipos de interface que seriam classificados em vez da fatia original!
Programação orientada a objetos
OOP é uma propriedade de linguagem que faz bom uso dos recursos das tabelas de tipos virtuais. Em vez de objetos de interface separados com vtables, linguagens OOP como Java simplesmente inserem um ponteiro em uma tabela de tipos virtuais no início de cada objeto. Linguagens do tipo Java possuem um sistema de herança e interfaces que podem ser totalmente implementadas usando essas tabelas de objetos do tipo virtual.
Além de fornecer recursos adicionais, a incorporação de vtable em cada objeto resolve o problema da necessidade de construir novos tipos de interface com endereçamento indireto. Ao contrário de Go, em Java
, a função de classificação pode aplicar a interface
Comparable aos tipos que implementa.
Reflexão
Se você possui tabelas de tipos virtuais, não será difícil forçar o compilador a gerar tabelas de outros tipos de informações, por exemplo, nomes de campos, tipos e locais. Isso permitirá o acesso a todos os dados desse tipo usando um código que pode exibir todos os dados de qualquer outro tipo. Esse comportamento pode ser usado para adicionar "reflexão" ao idioma, o que permite serialização e exibição bonita de tipos arbitrários. A reflexão, como uma extensão do paradigma de empacotamento, tem uma desvantagem: para isso, apenas uma cópia do código é suficiente, mas você precisa executar muitas pesquisas dinâmicas, o que reduz a velocidade da serialização.
Linguagens que usam reflexão para serialização e outras funções: Java, C # e Go.
Idiomas de tipo dinâmico
O Reflection é uma ferramenta muito poderosa que permite resolver várias tarefas de metaprogramação. Mas isso não permite que você crie novos tipos ou edite informações sobre os tipos de valores existentes. Se adicionarmos esse recurso e fizermos com que as sintaxes de acesso e modificação de dados usem reflexão por padrão, obteremos linguagens dinamicamente digitadas! A incrível flexibilidade da metaprogramação em linguagens como Python e Ruby surgiu graças aos sistemas de reflexão eficazes e poderosos que são usados para resolver qualquer problema.
Você pode dizer: “Mas linguagens dinâmicas não funcionam assim, elas apenas implementam tudo usando tabelas de hash!” As tabelas de hash são apenas uma boa estrutura de dados para criar tabelas editáveis com informações de tipo. Além disso, alguns intérpretes, como o CPython, funcionam dessa maneira. Em um JIT de alto desempenho, por exemplo, V8,
existem muitas tabelas de tipos virtuais e informações de reflexão. Na V8, as classes ocultas (vtables e informações de reflexão) e a estrutura dos objetos são semelhantes às que você pode ver na Java VM, com a capacidade de substituir objetos por novas tabelas de tipos virtuais em tempo de execução. Isso não é uma coincidência, porque não há coincidências: o
criador da V8 costumava
trabalhar na Java VM de alto desempenho .
Transferência de dicionário
Outra maneira de implementar interfaces dinâmicas é transferir uma tabela com os ponteiros de função necessários para a função genérica que precisa deles. Isso é algo semelhante à construção de objetos de interface em forma de Go no local da chamada, apenas no nosso caso a tabela é passada como um argumento oculto e não empacotada em um pacote configurável como um dos argumentos existentes.
Essa abordagem é usada nas
classes de tipo em Haskell , embora o GHC permita executar algum tipo de monomorfização usando inlining e especialização. O OCaml usa a transferência de dicionário com um argumento explícito na forma
de módulos de primeira classe , mas já foi proposto
adicionar a capacidade de tornar o parâmetro implícito .
Tabelas de testemunhas em Swift
Os autores do Swift usaram uma solução interessante: transferir o dicionário, além de colocar dados sobre os tamanhos dos tipos e como movê-los, copiá-los e liberá-los na tabela, permite fornecer todas as informações necessárias para o trabalho unificado com qualquer tipo sem embalá-los. Assim, o Swift pode implementar genéricos
sem monomorfização e colocação na memória em uma representação unificada de todas as entidades! Sim, você precisa pagar por pesquisas dinâmicas, como é característico de toda a família que usa embalagens, mas economiza recursos para posicionamento na memória, consumo e inconsistência no cache. Usando as funções
anotadas como @inlinable , o compilador Swift também pode se especializar (monomorfizar) e genéricos em linha dentro de um módulo ou entre módulos para evitar as despesas mencionadas. Provavelmente, é usada uma avaliação heurística do efeito no tamanho do código.
Isso também explica como o Swift pode
implementar a estabilidade da ABI , enquanto ainda permite adicionar e redistribuir campos na estrutura, embora os autores forneçam o atributo
@frozen para recusar pesquisas dinâmicas para obter melhor desempenho.
Análise Intensiva de Tipo
Há outra maneira de implementar interfaces para tipos de pacotes. Adicionamos o identificador de tipo a uma determinada parte do objeto, seguindo o exemplo do ponteiro vtable, e depois geramos funções para cada método de interface que possui uma expressão de
switch grande para todos os tipos que implementam esse método e o transmitimos ao método específico específico do tipo.
Não me importo com o uso de linguagens que usam essa abordagem, mas os compiladores C ++ e as máquinas virtuais Java agem de maneira semelhante. Ao usar a otimização baseada em perfis, eles descobrem que um determinado local de chamada de genéricos geralmente funciona com objetos de certos tipos. Compiladores e VMs substituem os pontos de chamada pelas verificações de cada tipo comum e depois despacham estaticamente esses tipos, como um fallback usando o despacho dinâmico convencional. Portanto, o algoritmo de previsão de ramificação pode prever em qual ramificação o código continuará e continuará a despachar instruções usando chamadas estáticas.
Monomorfização
Esta é uma alternativa à embalagem. Com a monomorfização, precisamos encontrar uma maneira de gerar várias versões do código para cada tipo que queremos usar. Os compiladores têm várias fases de apresentação pelas quais o código passa e, teoricamente, podem ser copiados para qualquer um desses estágios.
Geração de código fonte
A maneira mais fácil de monomorfizar é copiar no primeiro estágio da apresentação: copie o código fonte! Em seguida, o compilador nem precisa oferecer suporte a genéricos, e isso às vezes é feito por usuários das linguagens C e Go, cujos compiladores não têm esse suporte.
Em C, você pode usar um pré-processador e definir a estrutura de dados em uma macro ou cabeçalho, inserindo-o repetidamente com
#define diferente. O Go possui scripts como o
genny que facilitam a geração de código.
A desvantagem de duplicar o código-fonte é que, dependendo do idioma, pode ser necessário lidar com vários problemas e casos extremos, além disso, o compilador analisa muitas vezes e verifica os tipos para praticamente o mesmo código. Novamente, dependendo do idioma e das ferramentas, esses genéricos de métodos podem ser difíceis de escrever e usar, como se dentro de uma macro C cada linha terminasse com uma barra invertida e todos os tipos e nomes de funções fossem colados manualmente em seus identificadores para evitar colisões.
Mixins de strings em D
No entanto, a geração de código tem suas vantagens, como o fato de que você pode gerar código usando uma linguagem de programação completa, além de usar uma exibição familiar para os usuários.
Alguns idiomas nos quais os genéricos são implementados de maneira diferente também permitem gerar código para casos de metaprogramação mais gerais que não são considerados em seus sistemas genéricos, por exemplo, para serialização. O exemplo mais compreensível são
mixins de strings em D , que permitem compilar o código D na forma de valores de strings no meio da compilação, usando todos os recursos do idioma.
Macros processuais de ferrugem
Um exemplo semelhante, apenas com uma representação no compilador em apenas um estágio.
As macros de procedimento da Rust usam fluxos de token como entrada e saída, fornecendo utilitários para converter esses fluxos em string e vice-versa. A vantagem dessa abordagem é que os fluxos de token podem armazenar informações de localização do código-fonte. O código escrito pelo usuário, a macro pode ser inserida como tokens diretamente da entrada para o fim de semana. E se esse código levar a um erro de compilação na saída dos macos, o compilador exibirá uma mensagem e apontará com precisão para o arquivo, linha e coluna da parte quebrada do código. Mas se a macro gerar um código quebrado, uma mensagem de erro indicará uma chamada de macro. Por exemplo, se você usar uma
macro que agrupa uma função no registro de chamadas e comete um erro na implementação de uma função agrupada, a mensagem de erro apontará diretamente para o erro no arquivo e não para o código gerado pela macro.
Macros de árvore de sintaxe
Alguns idiomas vão ainda mais longe e oferecem ferramentas para usar e criar diferentes tipos de árvores de sintaxe abstrata em macros (Abstract Syntax Tree, AST). Exemplos incluem
Template Haskell ,
macros Nim ,
OCaml PPX e quase todo
Lisp .
A desvantagem das macros AST é que você não deseja forçar os usuários a aprender várias funções para criar tipos AST, bem como idiomas básicos. Na família de linguagens Lisp, isso é resolvido com a ajuda de uma forte simplificação e a máxima correspondência entre a sintaxe e a estrutura do AST; no entanto, nem sempre é fácil criar estruturas.
Assim, em todas as linguagens que mencionei, de uma forma ou de outra, existe uma primitiva de "citação" na qual você fornece um pedaço de código na linguagem, e que retorna uma árvore de sintaxe. Essas primitivas podem mesclar os valores da árvore de sintaxe usando a semelhança da interpolação de cadeias. Aqui está um exemplo no Template Haskell:
, , , . . , PPX OCaml
/ , . Rust ,
parsing quotation , , . Rust
, , !
Padrões
— . ++ D , « ». , , , , .
template <class T> T myMax(T a, T b) { return (a>b?a:b); } template <class T> struct Pair { T values[2]; }; int main() { myMax(5, 6); Pair<int> p { {5,6} };
, , . , , .
D , , : , , . D;
if (
! ):
C++20 «» , , .
D , (compile time function evaluation)
static if , , , , - runtime-. , , , ++ , .
, « ». , Zig:
fn Stack(comptime T: type) type { return struct { items: []T, len: usize, const Self = @This(); pub fn push(self: Self, item: T) { // ... } }; }
Zig , ,
comptime .
Terra , . Terra — Lua, - , Lua API , quoting splicing:
function MakeStack(T) local struct Stack { items : &T;
Terra
- (domain specific) ,
Java Go . Terra runtime , .
Rust
, . , , ++, . , , , , . , . Rust, — Swift Haskell.
Rust « » (trait bounds).
Trait — , , . Rust , - , , , . - Rust
. , -.
fn my_max<T: PartialOrd>(a: T, b: T) -> T { if a > b { a } else { b } } struct Pair<T> { values: [T; 2], } fn main() { my_max(5,6); let p: Pair<i32> = Pair { values: [5,6] };
, . Rust . Rust 2018 ,
v: &impl SomeTrait ,
v: &dyn SomeTrait . GHC Swift Haskell , .
— , . , (placeholders) -, , .
memcpy , ! , . . JIT, , .
, , , , , , ! , , , . , , .