¿Cómo se implementan los genéricos en un compilador moderno?

Lo que quiero decir aquí es cómo pasamos de una plantilla T add(T a, T b) ...al código generado. He pensado en algunas maneras de lograr esto, almacenamos la función genérica en un AST como Function_Nodey luego cada vez que la usamos almacenamos en el nodo de función original una copia de sí mismo con todos los tipos Tsustituidos por los tipos que son siendo utilizado. Por ejemplo add<int>(5, 6), almacenará una copia de la función genérica addy sustituirá todos los tipos T en la copia con int.

Entonces se vería algo así como:

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

Entonces podría generar código para estos y cuando visite un lugar Function_Nodedonde aparece la lista de copias copies.size() > 0, invocará visitFunctiontodas las copias.

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;
    }
}

¿Funcionaría bien? ¿Cómo abordan los compiladores modernos este problema? Creo que quizás otra forma de hacerlo sería inyectar las copias en el AST para que atraviese todas las fases semánticas. También pensé que tal vez podrías generarlos de forma inmediata como Rust's MIR o Swifts SIL, por ejemplo.

Mi código está escrito en Java, los ejemplos aquí son C ++ porque es un poco menos detallado para los ejemplos, pero el principio es básicamente lo mismo. Aunque puede haber algunos errores porque solo está escrito a mano en el cuadro de preguntas.

Tenga en cuenta que me refiero al compilador moderno como cuál es la mejor manera de abordar este problema. Y cuando digo genéricos, no me refiero a los genéricos de Java donde usan borrado de tipo.

¿Cómo se implementan los genéricos en un compilador moderno?

Los invito a leer el código fuente de un compilador moderno si desean saber cómo funciona un compilador moderno. Comenzaría con el proyecto Roslyn, que implementa compiladores de C # y Visual Basic.

En particular, llamo su atención sobre el código en el compilador de C # que implementa símbolos de tipo:

https://github.com/dotnet/roslyn/tree/master/src/Compilers/CSharp/Portable/Symbols

y es posible que también desee ver el código para las reglas de convertibilidad. Hay muchas cosas relacionadas con la manipulación algebraica de tipos genéricos.

https://github.com/dotnet/roslyn/tree/master/src/Compilers/CSharp/Portable/Binder/Semantics/Conversions

Traté de hacer que este último fuera fácil de leer.

He pensado en algunas formas de lograr esto, almacenamos la función genérica en un AST como Function_Node y luego, cada vez que la usamos, almacenamos en el nodo de función original una copia de sí mismo con todos los tipos T sustituidos con los tipos que están siendo utilizados

Estás describiendo plantillas , no genéricos . C # y Visual Basic tienen genéricos reales en sus sistemas de tipos.

Brevemente, funcionan así.

• Comenzamos estableciendo reglas para lo que formalmente constituye un tipo en tiempo de compilación. Por ejemplo: intes un tipo, un parámetro de tipo Tes un tipo, para cualquier tipo X, el tipo de matriz X[]también es un tipo, y así sucesivamente.

• Las reglas para los genéricos implican sustitución. Por ejemplo, class C with one type parameterno es un tipo. Es un patrón para hacer tipos. class C with one type parameter called T, under substitution with int for T es un tipo

• Las reglas que describen las relaciones entre tipos (compatibilidad tras la asignación, cómo determinar el tipo de una expresión, etc.) están diseñadas e implementadas en el compilador.

• Se diseña e implementa un lenguaje de código de bytes que admite tipos genéricos en su sistema de metadatos.

• En tiempo de ejecución, el compilador JIT convierte el bytecode en código de máquina; es responsable de construir el código de máquina apropiado dada una especialización genérica.

Entonces, por ejemplo, en C # cuando dices

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

entonces el compilador verifica que en C<int>, el argumento intes una sustitución válida para T, y genera metadatos y bytecode en consecuencia. En tiempo de ejecución, el jitter detecta que C<int>se está creando a por primera vez y genera el código de máquina apropiado dinámicamente.

La mayoría de las implementaciones de genéricos (o más bien: polimorfismo paramétrico) usan borrado de tipo. Esto simplifica enormemente el problema de compilar código genérico, pero solo funciona para tipos encuadrados: dado que cada argumento es efectivamente un puntero opaco, necesitamos un VTable o un mecanismo de envío similar para realizar operaciones en los argumentos. En Java:

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

se puede compilar, verificar y escribir de la misma manera que

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

excepto que los genéricos proporcionan al verificador de tipos mucha más información en el sitio de la llamada. Esta información adicional se puede manejar con variables de tipo , especialmente cuando se infieren tipos genéricos. Durante la verificación de tipos, cada tipo genérico se puede reemplazar con una variable, llamémoslo $T1:

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

La variable de tipo se actualiza con más hechos a medida que se conocen, hasta que se pueda reemplazar por un tipo concreto. El algoritmo de verificación de tipo debe escribirse de manera que acomode estas variables de tipo incluso si aún no se han resuelto en un tipo completo. En Java, esto generalmente se puede hacer fácilmente ya que el tipo de argumentos a menudo se conoce antes de que sea necesario conocer el tipo de llamada a la función. Una excepción notable es una expresión lambda como argumento de función, que requiere el uso de tales variables de tipo.

Mucho más tarde, un optimizador puede generar código especializado para un cierto conjunto de argumentos, esto sería efectivamente una especie de línea.

Se puede evitar una VTable para argumentos de tipo genérico si la función genérica no realiza ninguna operación en el tipo, sino que solo los pasa a otra función. Por ejemplo, la función Haskell call :: (a -> b) -> a -> b; call f x = f xno tendría que encuadrar el xargumento. Sin embargo, esto requiere una convención de llamada que pueda pasar valores sin conocer su tamaño, lo que esencialmente lo restringe a los punteros de todos modos.

C ++ es muy diferente de la mayoría de los lenguajes a este respecto. Una clase o función con plantilla (solo discutiré funciones con plantilla aquí) no es invocable en sí misma. En cambio, las plantillas deben entenderse como una metafunción en tiempo de compilación que devuelve una función real. Ignorando la inferencia de argumentos de plantilla por un momento, el enfoque general se reduce a estos pasos:

1. Aplique la plantilla a los argumentos de plantilla proporcionados. Por ejemplo, llamar template<class T> T add(T a, T b) { … }como add<int>(1, 2)nos daría la función real int __add__T_int(int a, int b)(o cualquier enfoque de cambio de nombre utilizado).

2. Si el código para esa función ya se ha generado en la unidad de compilación actual, continúe. De lo contrario, genere el código como si se int __add__T_int(int a, int b) { … }hubiera escrito una función en el código fuente. Esto implica reemplazar todas las apariciones del argumento de plantilla con sus valores. Esta es probablemente una transformación AST → AST. Luego, realice una verificación de tipo en el AST generado.

3. Compila la llamada como si lo hubiera sido el código fuente __add__T_int(1, 2).

Tenga en cuenta que las plantillas de C ++ tienen una interacción compleja con el mecanismo de resolución de sobrecarga, que no quiero describir aquí. También tenga en cuenta que esta generación de código hace que sea imposible tener un método con plantilla que también sea virtual: un enfoque basado en el borrado de tipo no sufre esta restricción sustancial.

¿Qué significa esto para su compilador y / o idioma? Tienes que pensar cuidadosamente sobre el tipo de genéricos que quieres ofrecer. El borrado de tipo en ausencia de inferencia de tipo es el enfoque más simple posible si admite tipos en caja. La especialización de la plantilla parece bastante simple, pero generalmente implica el cambio de nombre y (para múltiples unidades de compilación) una duplicación sustancial en la salida, ya que las plantillas se instancian en el sitio de la llamada, no en el sitio de definición.

El enfoque que ha mostrado es esencialmente un enfoque de plantilla similar a C ++. Sin embargo, almacena las plantillas especializadas / instanciadas como "versiones" de la plantilla principal. Esto es engañoso: no son los mismos conceptualmente, y las diferentes instancias de una función pueden tener tipos muy diferentes. Esto complicará las cosas a largo plazo si también permite la sobrecarga de funciones. En cambio, necesitaría una noción de un conjunto de sobrecarga que contiene todas las funciones y plantillas posibles que comparten un nombre. Excepto para resolver la sobrecarga, puede considerar que diferentes plantillas instanciadas estén completamente separadas entre sí.