En algunas áreas de programación, es normal querer escribir una estructura de datos o algoritmo que pueda funcionar con elementos de diferentes tipos. Por ejemplo, una lista de genéricos o un algoritmo de clasificación que solo necesita una función de comparación. En varios lenguajes, se ofrecen varias formas de resolver este problema: desde simplemente señalar las funciones comunes apropiadas (C, Go) a los programadores hasta sistemas genéricos tan poderosos que se vuelven completos de Turing (
Rust ,
C ++ ). En este artículo hablaré sobre sistemas genéricos de diferentes idiomas y su implementación. Comenzaré resolviendo el problema en lenguajes sin dicho sistema (como C), y luego mostraré cómo la adición gradual de extensiones conduce a sistemas de otros lenguajes.
Considero que los genéricos son una opción interesante porque son un caso especial simple de la tarea general de metaprogramación: escribir programas que pueden generar clases de otros programas. Como prueba, mostraré cómo tres métodos de metaprogramación diferentes y completamente generales pueden considerarse extensiones multidireccionales en el espacio de sistemas genéricos: lenguajes dinámicos como Python, macro sistemas de procedimientos como
Template Haskel y compilación por fases como
Zig y
Terra .
Revisar
Dibujé un diagrama de bloques de todos los sistemas descritos en el artículo para que pueda presentar su contenido y cómo estos sistemas están interconectados:
Ideas principales
Supongamos que estamos escribiendo en un lenguaje sin sistemas genéricos, y queremos hacer una estructura de datos de estructura de datos de pila genérica que funcione con datos de cualquier tipo. El problema es que cada definición de función y tipo solo funcionará con datos del mismo tamaño y copiados de una manera, y generalmente funciona de manera similar.
Hay dos formas de evitar esto: asegúrese de que todos los tipos de datos actúen de la misma manera en nuestra estructura, o haga muchas copias de la estructura de datos con cambios menores para que funcionen correctamente con cada tipo de datos. Estas ideas formaron la base de dos grandes grupos de soluciones con genéricos: boxeo y monomorfización.
Empaquetar significa poner todo en una fila en "cajas" unificadas que funcionan de la misma manera. Esto generalmente se hace así: los datos se colocan en un montón, y los punteros se colocan en la estructura de datos. ¡Puede hacer punteros a todos los tipos que funcionarán de la misma manera, por lo que el mismo código funcionará con datos de cualquier tipo! Sin embargo, esto conduce a un mayor consumo de memoria, búsqueda dinámica y errores de caché. En C, esto significa que su estructura de datos almacena punteros
void* y simplemente almacena en caché los datos hacia y desde
void* (si los datos no están en el montón, los coloca allí).
Monomorfización significa copiar repetidamente código para los diferentes tipos de datos que queremos almacenar. Luego, cada instancia de código puede usar directamente el tamaño y los métodos de datos con los que trabaja sin búsqueda dinámica. Con este enfoque, el código se ejecuta más rápido, pero su tamaño y el tiempo de compilación aumentan, porque compilamos repetidamente el mismo código con cambios menores. En C, esto corresponde a la
definición de toda la estructura de datos como una macro , seguida de su invocación para cada tipo de datos.
En general, durante la compilación, el código se compila más rápido, pero su rendimiento puede deteriorarse durante la ejecución, mientras que durante la monomorfización generamos código rápido, pero lleva más tiempo compilar y optimizar todas las instancias del código. Otra diferencia es que cuando las extensiones de empaquetado le permiten realizar un comportamiento más dinámico del código ejecutable, y la monomorfización le permite separar de manera más flexible diferentes instancias del código genérico. También vale la pena señalar que en algunos programas grandes, los beneficios de la monomorfización se pueden compensar con errores en el caché de instrucciones adicionales del código generado.
Cada uno de los esquemas descritos para trabajar con genéricos se puede ampliar en diferentes direcciones, si necesita más funciones o seguridad, y los autores de varios idiomas han encontrado soluciones muy interesantes. Por ejemplo, ambos enfoques se pueden usar en Rust y C #!
Embalaje
Comencemos con un ejemplo de empaque básico en 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 }
Además, el empaquetado se usa en C (
void* ), Go (
interface{} ), Java pre-genérico (
Object ) y Objective-C pre-genérico (
id ).
Genéricos empaquetados con tipos de trituración
El método de embalaje principal tiene desventajas:
- Dependiendo del idioma, a menudo tenemos que emitir valores hacia o desde el tipo correcto cada vez que leemos o escribimos en la estructura de datos.
- Nada nos impide poner elementos de diferentes tipos en la estructura, lo que puede provocar errores que parecen fallas durante la ejecución del código.
Ambos problemas se pueden resolver agregando genéricos al sistema de tipos de funcionalidad, mientras se usa el método de empaquetado principal de la misma manera que antes durante la ejecución del código. Este enfoque a menudo se llama borrado de tipo, porque los tipos en el sistema genérico se "sobrescriben" y se convierten en un tipo bajo el capó (como
Object ).
Java y Objective-C comenzaron con el empaquetado habitual, y luego adquirieron herramientas de lenguaje para genéricos con maceración de tipos, en aras de la compatibilidad, utilizando los mismos tipos de colección que antes, pero con los parámetros opcionales de los tipos genéricos. Considere un ejemplo de un artículo de Wikipedia sobre
genéricos en Java :
List v = new ArrayList(); v.add("test");
Genéricos empaquetados derivados con rendimiento unificado
OCaml desarrolla aún más la idea de una vista unificada. No hay tipos primitivos que necesiten una ubicación de empaque adicional (ya que un
int debe convertirse en
Integer para ingresar a una
ArrayList en Java), porque todo ya está empaquetado o representado por un valor entero del tamaño de un puntero, es decir, todo cabe en una sola palabra de máquina. Pero cuando el recolector de basura analiza los datos almacenados en estructuras genéricas, necesita distinguir los punteros de los números, por lo que los números se marcan con un solo bit, colocado donde los punteros correctamente alineados no tienen un bit, dejando rangos de solo 31 o 63 bits.
OCaml también tiene un sistema de inferencia de tipos, por lo que puede escribir una función y el compilador generará el tipo genérico más adecuado si no lo anota, por lo que las funciones se verán como si fuera un lenguaje de tipo dinámico:
let first (head :: tail) = head (* inferred type: 'a list -> 'a *)
El tipo dado se puede llamar "una función de la lista de elementos del tipo
'a en algo con el tipo
'a ". Esto significa que el tipo de retorno será el mismo que el tipo de lista, y puede ser de cualquier tipo.
Interfaces
Otra limitación de los envases convencionales es que los tipos de envases son
completamente opacos. Esto no es un problema para las estructuras de datos como una pila, pero las herramientas como la clasificación de funciones genéricas necesitan características adicionales, como funciones de comparación específicas del tipo. Hay muchas formas de implementar esto en tiempo de ejecución y reflexionar en el lenguaje, técnicamente estas son direcciones diferentes, y puede
implementar el mismo lenguaje con varios enfoques similares . Sin embargo, las características de diferentes idiomas afectan su implementación, y solo entonces las extensiones mejoran las fortalezas de las implementaciones seleccionadas. Esto significa que hay dos familias de idiomas basadas en diferentes enfoques del tiempo de ejecución: tablas de métodos virtuales (vtables) y transferencia de diccionario.
Tablas de métodos de interfaz
Si queremos proporcionar funciones específicas de tipo, adheridas a la estrategia de empaquetado en aras del trabajo unificado con todo, entonces es suficiente tener una forma unificada de encontrar funciones similares que necesitamos obtener del objeto. Este enfoque se denomina "tablas de métodos virtuales" (vtables, tablas de métodos virtuales), aunque nadie usa el nombre completo. Se implementa de la siguiente manera: en un desplazamiento cero en cada objeto de estructura genérico, hay un puntero a una tabla de punteros de función con un circuito consistente. En estas tablas, el código genérico busca punteros para escribir funciones específicas indexando punteros específicos en desplazamientos fijos.
Así es como se implementan los tipos de
interface en los objetos de
dyn trait Go y
dyn trait en Rust. Cuando convierte un tipo a un tipo de interfaz de lo que implementa, se crea un contenedor para la interfaz que contiene un puntero al objeto de origen y un puntero a la tabla de funciones específicas del tipo. Pero esto requiere un nivel adicional de direccionamiento indirecto de punteros y otro esquema. Por lo tanto, la ordenación en Go usa la
interfaz para el contenedor con el método Swap , y no toma el segmento de la interfaz Comparable, ya que esto requeriría colocar en la memoria un segmento de tipo de interfaz completamente nuevo que se ordenaría en lugar del segmento original.
Programación orientada a objetos.
OOP es una propiedad de lenguaje que hace un buen uso de las capacidades de las tablas de tipos virtuales. En lugar de objetos de interfaz separados con vtables, los lenguajes OOP como Java simplemente insertan un puntero a una tabla de tipos virtuales al comienzo de cada objeto. Los lenguajes tipo Java tienen un sistema de herencia e interfaces que pueden implementarse completamente usando estas tablas de objetos de tipo virtual.
Además de proporcionar características adicionales, incrustar vtable en cada objeto resuelve el problema de la necesidad de construir nuevos tipos de interfaz con direccionamiento indirecto (indirección). A diferencia de Go, en Java
, la función de clasificación puede aplicar la interfaz
Comparable a los tipos que implementa.
Reflexion
Si tiene tablas de tipos virtuales, no le resultará difícil forzar al compilador a generar tablas de otros tipos de información, por ejemplo, nombres de campos, tipos y ubicaciones. Esto permitirá el acceso a todos los datos de este tipo utilizando un código que puede ver todos los datos de cualquier otro tipo. Este comportamiento se puede usar para agregar "reflexión" al lenguaje, lo que permite la serialización y una hermosa visualización de tipos arbitrarios. La reflexión, como una extensión del paradigma de empaquetado, tiene un inconveniente: para ello, solo una copia del código es suficiente, pero debe realizar muchas búsquedas dinámicas, lo que reduce la velocidad de serialización.
Lenguajes que usan la reflexión para la serialización y otras funciones: Java, C # y Go.
Idiomas tipificados dinámicamente
Reflection es una herramienta muy poderosa que te permite resolver un montón de diferentes tareas de metaprogramación. Pero no le permite crear nuevos tipos o editar información sobre los tipos de valores existentes. Si agregamos esta función y hacemos que el acceso a los datos y las sintaxis de modificación usen la reflexión de forma predeterminada, ¡obtendremos idiomas escritos dinámicamente! La increíble flexibilidad de la metaprogramación en lenguajes como Python y Ruby ha surgido gracias a los eficaces y potentes sistemas de reflexión que se utilizan para resolver cualquier problema.
Puede decir: "¡Pero los lenguajes dinámicos no funcionan así, simplemente implementan todo usando tablas hash!" Las tablas hash son solo una buena estructura de datos para crear tablas editables con información de tipo. Además, algunos intérpretes, como CPython, funcionan de esta manera. En un JIT de alto rendimiento, digamos V8,
hay muchas tablas de tipos virtuales e información de reflexión. En V8, las clases ocultas (vtables e información de reflexión) y la estructura de los objetos son similares a lo que puede ver en Java VM, con la capacidad de reemplazar objetos con nuevas tablas de tipos virtuales en tiempo de ejecución. Esto no es una coincidencia, porque no hay coincidencias: el
creador de V8 solía
trabajar en Java VM de alto rendimiento .
Transferencia de diccionario
Otra forma de implementar interfaces dinámicas es transferir una tabla con los punteros de función requeridos a la función genérica que los necesita. Esto es algo similar a la construcción de objetos de interfaz en forma de Go en el lugar de la llamada, solo en nuestro caso la tabla se pasa como un argumento oculto y no se empaqueta en un paquete como uno de los argumentos existentes.
Este enfoque se usa en las
clases de tipos en Haskell , aunque GHC le permite realizar algún tipo de monomorfización mediante la incorporación y la especialización. OCaml utiliza la transferencia de diccionario con un argumento explícito en forma
de módulos de primera clase , pero ya se ha propuesto
agregar la capacidad de hacer que el parámetro sea implícito .
Tablas de testigos en Swift
Los autores de Swift usaron una solución interesante: transferir el diccionario, así como poner datos sobre los tamaños de letra y cómo moverlos, copiarlos y soltarlos en la tabla, le permite proporcionar toda la información necesaria para el trabajo unificado con cualquier tipo sin empaquetarlos. Por lo tanto, Swift puede implementar genéricos
sin monomorfización y colocación en la memoria en una representación unificada de todas las entidades. Sí, tiene que pagar por las búsquedas dinámicas, como es característico de toda la familia que utiliza el empaquetado, pero ahorra recursos para su ubicación en la memoria, su consumo y la inconsistencia de la memoria caché. Utilizando las funciones
anotadas como @inlinable , el compilador Swift también puede especializarse (monomorfizar) y genéricos en línea dentro del módulo o entre módulos para evitar los gastos mencionados. Probablemente se utiliza una evaluación heurística del efecto sobre el tamaño del código.
Esto también explica cómo Swift puede
implementar la estabilidad ABI , mientras le permite agregar y redistribuir campos en la estructura, aunque los autores proporcionan el atributo
@frozen para rechazar búsquedas dinámicas para un mejor rendimiento.
Análisis de tipo Intensional
Hay otra forma de implementar interfaces para tipos empaquetados. Agregamos el identificador de tipo a una determinada parte del objeto, siguiendo el ejemplo del puntero vtable, y luego generamos funciones para cada método de interfaz que tiene una expresión de
switch grande para todos los tipos que implementan este método y lo pasan al método específico de tipo correcto.
No advierto contra el uso de lenguajes que usan este enfoque, pero los compiladores de C ++ y las máquinas virtuales Java actúan de manera similar, cuando usan la optimización basada en perfiles descubren que un determinado lugar de llamadas genéricas funciona principalmente con objetos de ciertos tipos. Los compiladores y las máquinas virtuales reemplazan los puntos de llamada con verificaciones para cada tipo ordinario, y luego envían estáticamente estos tipos, como una alternativa usando el despacho dinámico convencional. Por lo tanto, el algoritmo de predicción de bifurcación puede predecir en qué bifurcación continuará el código y continuará enviando instrucciones mediante llamadas estáticas.
Monomorfización
Esta es una alternativa al embalaje. Con la monomorfización, necesitamos encontrar una manera de generar múltiples versiones del código para cada tipo que queremos usar. Los compiladores tienen varias fases de presentación por las que pasa el código y, en teoría, pueden copiarse en cualquiera de estas etapas.
Generación de código fuente
La forma más fácil de monomorfizar es copiar en la primera etapa de presentación: ¡copie el código fuente! Entonces, el compilador ni siquiera tiene que admitir genéricos, y esto a veces lo hacen los usuarios de los lenguajes C y Go, cuyos compiladores no tienen dicho soporte.
En C, puede usar un preprocesador y definir la estructura de datos en una macro o encabezado insertándolo repetidamente con
#define diferente. Go tiene scripts como
genny que facilitan la generación de código.
La desventaja de duplicar el código fuente es que, dependiendo del idioma, puede ser necesario lidiar con numerosos problemas y casos extremos, además, el compilador analiza muchas veces y comprueba los tipos para prácticamente el mismo código. Nuevamente, dependiendo del lenguaje y las herramientas, estos métodos genéricos pueden ser difíciles de escribir y usar, como si dentro de una macro C cada línea terminara con una barra invertida y todos los tipos y nombres de funciones se deben pegar manualmente en sus identificadores para evitar colisiones.
Cadena mixins en D
Sin embargo, la generación de código tiene sus ventajas, como el hecho de que puede generar código utilizando un lenguaje de programación completo, así como utilizar una vista familiar para los usuarios.
Algunos lenguajes en los que los genéricos se implementan de manera diferente también le permiten generar código para casos de metaprogramación más generales que no se consideran en sus sistemas genéricos, por ejemplo, para la serialización. El ejemplo más comprensible son
los mixins de cadenas en D , que permiten compilar código D en forma de valores de cadena en el medio de la compilación, utilizando todas las características del lenguaje.
Macros procesales de óxido
Un ejemplo similar, solo con una representación en el compilador en una sola etapa.
Las macros de procedimiento de Rust usan flujos de tokens como entrada y salida, proporcionando utilidades para convertir estos flujos en cadenas y viceversa. La ventaja de este enfoque es que las secuencias de tokens pueden almacenar información de ubicación del código fuente. El código escrito por el usuario, la macro se puede insertar como tokens directamente desde la entrada al fin de semana. Y si este código conduce a un error de compilación en la salida de los macos, el compilador mostrará un mensaje y señalará con precisión el archivo, la línea y la columna de la parte rota del código. Pero si la macro genera un código roto, entonces un mensaje de error indicará una llamada de macro. Por ejemplo, si usa una
macro que envuelve una función al registrar llamadas y comete un error al implementar una función ajustada, el mensaje de error apuntará directamente al error en el archivo y no al código generado por la macro.
Macros de árbol de sintaxis
Algunos lenguajes van más allá y ofrecen herramientas para usar y crear diferentes tipos de árboles de sintaxis abstracta en macros (Árbol de sintaxis abstracta, AST). Los ejemplos incluyen
Template Haskell ,
macros Nim ,
OCaml PPX y casi todos los
Lisp .
El inconveniente de las macros AST es que no desea obligar a los usuarios a aprender un montón de funciones para construir tipos AST, así como lenguajes básicos. En la familia de idiomas Lisp, esto se resuelve con la ayuda de una fuerte simplificación y la máxima correspondencia entre la sintaxis y la estructura de AST, sin embargo, crear estructuras no siempre es fácil.
Por lo tanto, en todos los idiomas que mencioné, de una forma u otra hay una primitiva de "cita" a la que le da un código en el idioma, y que devuelve un árbol de sintaxis. Estas primitivas pueden fusionar los valores del árbol de sintaxis utilizando la similitud de la interpolación de cadenas. Aquí hay un ejemplo de Template Haskell:
, , , . . , PPX OCaml
/ , . Rust ,
parsing quotation , , . Rust
, , !
Patrones
— . ++ 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, , .
, , , , , , ! , , , . , , .