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

14

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_Node y luego, cada vez que la usamos, almacenamos en el nodo de la función original una copia de sí misma con todos los tipos T . Se sustituye con los tipos que se están utilizando. Por ejemplo, add<int>(5, 6) almacenará una copia de la función genérica para add y 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;
};

Luego, podría generar un código para estos y cuando visite un Function_Node donde la lista de copias copies.size() > 0 , invoque visitFunction en todas 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;
    }
}

¿Esto funcionaría bien? ¿Cómo abordan los compiladores modernos este problema? Creo que tal vez otra forma de hacer esto sería inyectar las copias en el AST para que se ejecute a través de todas las fases semánticas. También pensé que quizás podrías generarlos de forma inmediata, como MIR de Rust 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 se escriben a mano en el cuadro de preguntas.

Tenga en cuenta que me refiero al compilador moderno ya que es la mejor manera de abordar este problema. Y cuando digo genéricos no me refiero a los genéricos de Java en los que utilizan el borrado de tipos.

    
pregunta Jon Flow 20.10.2016 - 17:29
fuente

2 respuestas

14
  

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

Te invito a leer el código fuente de un compilador moderno si deseas saber cómo funciona un compilador moderno. Comenzaría con el proyecto Roslyn, que implementa compiladores 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:

enlace

y es posible que también desee consultar el código de las reglas de convertibilidad. Hay mucho allí que pertenece a la manipulación algebraica de tipos genéricos.

enlace

Me esforcé por hacer que este último fuera fácil de leer.

  

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

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

Brevemente, funcionan así.

  • Comenzamos por establecer reglas para lo que formalmente constituye un tipo en tiempo de compilación. Por ejemplo: int es un tipo, un parámetro de tipo T es 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 la sustitución. Por ejemplo, class C with one type parameter no 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 los tipos (compatibilidad en la asignación, cómo determinar el tipo de expresión, etc.) están diseñadas e implementadas en el compilador.

  • Se diseñó e implementó un lenguaje de bytecode que admite tipos genéricos en su sistema de metadatos.

  • En el 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.

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

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

    
respondido por el Eric Lippert 20.10.2016 - 22:48
fuente
9

La mayoría de las implementaciones de genéricos (o más bien: polimorfismo paramétrico) utilizan el borrado de tipo. Esto simplifica en gran medida el problema de compilar el código genérico, pero solo funciona para tipos encajonados: como 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) { … }

puede compilarse, verificarse y escribirse del mismo modo que

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

excepto que los genéricos proporcionan al comprobador 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 deducen 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 datos a medida que se conocen, hasta que se puede reemplazar por un tipo concreto. El algoritmo de verificación de tipo debe escribirse de manera que se adapte a estas variables de tipo, incluso si aún no se han resuelto en un tipo completo. En Java mismo, esto generalmente se puede hacer fácilmente ya que el tipo de los argumentos se conoce a menudo antes de que el tipo de la llamada a la función deba ser conocida. 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 determinado conjunto de argumentos, esto sería efectivamente un tipo de integración.

Una VTable para argumentos de tipo genérico se puede evitar si la función genérica no realiza ninguna operación en el tipo, sino que solo pasa a otra función. P.ej. La función de Haskell call :: (a -> b) -> a -> b; call f x = f x no tendría que marcar el argumento x . Sin embargo, esto requiere una convención de llamada que pueda pasar a través de los valores sin saber 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 (aquí solo discutiré las funciones con plantilla) no se puede llamar en sí misma. En su lugar, las plantillas deben entenderse como una meta-función en tiempo de compilación que devuelve una función real. Ignorando la inferencia de los argumentos de la 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 a template<class T> T add(T a, T b) { … } as add<int>(1, 2) nos daría la función real int __add__T_int(int a, int b) (o cualquier método de identificación de nombres).

  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 una función int __add__T_int(int a, int b) { … } se hubiera escrito en el código fuente. Esto implica reemplazar todas las apariciones del argumento de la plantilla con sus valores. Esta es probablemente una transformación AST → AST. Luego, realice una comprobación de tipo en el AST generado.

  3. Compile la llamada como si el código fuente hubiera sido __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 de plantilla que también sea virtual: un enfoque basado en el borrado de tipo no sufre de 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 tipos en ausencia de inferencia de tipos es el enfoque más simple posible si admite tipos encuadrados. La especialización de la plantilla parece bastante simple, pero por lo general implica la manipulación de nombres y (para múltiples unidades de compilación) una duplicación sustancial en la salida, ya que las plantillas se crean instancias 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 / creadas como "versiones" de la plantilla principal. Esto es engañoso: no son lo mismo 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 su lugar, necesitaría una noción de un conjunto de sobrecarga que contenga todas las funciones y plantillas posibles que comparten un nombre. Excepto por resolver la sobrecarga, puede considerar que las diferentes plantillas instanciadas estén completamente separadas unas de otras.

    
respondido por el amon 20.10.2016 - 19:02
fuente

Lea otras preguntas en las etiquetas