Nombre de la técnica para inferir argumentos de tipo de un parámetro de tipo?

9

Configuración: supongamos que tenemos un tipo llamado Iteratorque tiene un parámetro de tipo Element:

interface Iterator<Element> {}

Luego tenemos una interfaz Iterableque tiene un método que devolverá un Iterator.

// T has an upper bound of Iterator
interface Iterable<T: Iterator> {
    getIterator(): T
}

El problema con Iteratorser genérico es que tenemos que proporcionarle argumentos de tipo.

Una idea para resolver esto es "inferir" el tipo de iterador. El siguiente pseudocódigo expresa la idea de que existe una variable de tipo Elementque se infiere que es el argumento de tipo para Iterator:

interface <Element> Iterable<T: Iterator<Element>> {
    getIterator(): T
}

Y luego lo usamos en algún lugar como este:

class Vec<Element> implements Iterable<VecIterator<Element>> {/*...*/}

Esta definición de Iterableno se usa en Elementningún otro lugar en su definición, pero mi caso de uso real sí. Ciertas funciones que utilizan Iterabletambién deben ser capaces de restringir sus parámetros para aceptar Iterablemensajes que solo devuelvan ciertos tipos de iteradores, como un iterador bidireccional, por lo que el iterador devuelto se parametriza en lugar de solo el tipo de elemento.


Preguntas:

  • ¿Existe un nombre establecido para estas variables de tipo inferido? ¿Qué pasa con la técnica en su conjunto? No conocer una nomenclatura específica ha dificultado la búsqueda de ejemplos de esto en la naturaleza o aprender sobre las características específicas del idioma.
  • No todos los idiomas con genéricos tienen esta técnica; ¿Hay nombres para técnicas similares en estos idiomas?
Levi Morrison
fuente
1
¿Puedes mostrar algún código que no compila que quieres compilar? Creo que eso aclarará la pregunta.
Sweeper
1
También puede elegir un idioma (o decir qué idioma está utilizando y qué significa la sintaxis). Obviamente no es, por ejemplo, C #. Hay mucha información sobre "inferencia de tipos" disponible en Internet, pero no estoy seguro de que se aplique aquí.
55
Estoy implementando genéricos en un idioma, no estoy tratando de obtener código en ningún idioma para compilar. También es una cuestión de nomenclatura y diseño. Por eso es algo agnóstico. Sin conocer los términos, es difícil encontrar ejemplos y documentación en los idiomas existentes. ¿Seguramente este no es un problema único?
Levi Morrison

Respuestas:

2

No sé si hay un término particular para este problema, pero hay tres clases generales de soluciones:

  • evitar tipos concretos a favor del despacho dinámico
  • permitir parámetros de tipo de marcador de posición en restricciones de tipo
  • evite los parámetros de tipo mediante el uso de tipos / familias de tipos asociados

Y, por supuesto, la solución predeterminada: seguir deletreando todos esos parámetros.

Evitar tipos concretos.

Ha definido una Iterableinterfaz como:

interface <Element> Iterable<T: Iterator<Element>> {
    getIterator(): T
}

Esto proporciona a los usuarios de la interfaz la máxima potencia porque obtienen el tipo concreto exacto Tdel iterador. Esto también permite que un compilador aplique más optimizaciones, como la alineación.

Sin embargo, si Iterator<E>es una interfaz distribuida dinámicamente, no es necesario conocer el tipo concreto. Esta es, por ejemplo, la solución que utiliza Java. La interfaz se escribiría como:

interface Iterable<Element> {
    getIterator(): Iterator<Element>
}

Una variación interesante de esto es la impl Traitsintaxis de Rust, que le permite declarar la función con un tipo de retorno abstracto, pero sabiendo que el tipo concreto se conocerá en el sitio de la llamada (lo que permite optimizaciones). Esto se comporta de manera similar a un parámetro de tipo implícito.

Permitir parámetros de tipo de marcador de posición.

La Iterableinterfaz no necesita saber sobre el tipo de elemento, por lo que podría ser posible escribir esto como:

interface Iterable<T: Iterator<_>> {
    getIterator(): T
}

Donde T: Iterator<_>expresa la restricción "T es cualquier iterador, independientemente del tipo de elemento". Más rigurosamente, podemos expresar esto como: "existe algún tipo, Elementpor lo que Tes un Iterator<Element>", sin tener que conocer ningún tipo concreto Element. Esto significa que la expresión de tipo Iterator<_>no describe un tipo real y solo puede usarse como una restricción de tipo.

Utilice familias de tipos / tipos asociados.

Por ejemplo, en C ++, un tipo puede tener miembros de tipo. Esto se usa comúnmente en toda la biblioteca estándar, por ejemplo std::vector::value_type. Esto realmente no resuelve el problema del parámetro de tipo en todos los escenarios, pero dado que un tipo puede referirse a otros tipos, un solo parámetro de tipo puede describir una familia completa de tipos relacionados.

Vamos a definir:

interface Iterator {
  type ElementType
  fn next(): ElementType
}

interface Iterable {
  type IteratorType: Iterator
  fn getIterator(): IteratorType
}

Entonces:

class Vec<Element> implement Iterable {
  type IteratorType = VecIterator<Element>
  fn getIterator(): IteratorType { ... }
}

class VecIterator<T> implements Iterator {
  type ElementType = T
  fn next(): ElementType { ... }
}

Esto parece muy flexible, pero tenga en cuenta que esto puede dificultar la expresión de restricciones de tipo. Por ejemplo, como está escrito Iterableno impone ningún tipo de elemento iterador, y podríamos querer declarar en su interface Iterator<T>lugar. Y ahora se trata de un cálculo de tipo bastante complejo. Es muy fácil hacer accidentalmente que dicho sistema de tipo sea indecidible (¿o tal vez ya lo es?).

Tenga en cuenta que los tipos asociados pueden ser muy convenientes como valores predeterminados para los parámetros de tipo. Por ejemplo, suponiendo que la Iterableinterfaz necesita un parámetro de tipo separado para el tipo de elemento que generalmente es, pero no siempre, el mismo que el tipo de elemento iterador, y que tenemos parámetros de tipo de marcador de posición, podría ser posible decir:

interface Iterable<T: Iterator<_>, Element = T::Element> {
  ...
}

Sin embargo, esa es solo una función de ergonomía del lenguaje y no hace que el lenguaje sea más poderoso.


Los sistemas de tipos son difíciles, por lo que es bueno echar un vistazo a lo que funciona y no funciona en otros idiomas.

Por ejemplo, considere leer el capítulo Rasgos avanzados en el Libro de óxido, que analiza los tipos asociados. Pero tenga en cuenta que algunos puntos a favor de los tipos asociados en lugar de los genéricos solo se aplican allí porque el lenguaje no presenta subtipos y cada rasgo solo se puede implementar como máximo una vez por tipo. Es decir, los rasgos de óxido no son interfaces similares a Java.

Otros sistemas de tipos interesantes incluyen Haskell con varias extensiones de lenguaje. Los módulos / functores OCaml son una versión comparativamente simple de familias de tipos, sin mezclarlos directamente con objetos o tipos parametrizados. Java es notable por las limitaciones en su sistema de tipos, por ejemplo, genéricos con borrado de tipo y sin genéricos sobre los tipos de valor. C # es muy similar a Java, pero logra evitar la mayoría de estas limitaciones, a costa de una mayor complejidad de implementación. Scala intenta integrar genéricos de estilo C # con clases de tipos de estilo Haskell en la parte superior de la plataforma Java. Las plantillas engañosamente simples de C ++ están bien estudiadas pero son diferentes a la mayoría de las implementaciones genéricas.

También vale la pena mirar las bibliotecas estándar de estos idiomas (especialmente las colecciones de bibliotecas estándar como listas o tablas hash) para ver qué patrones se usan comúnmente. Por ejemplo, C ++ tiene un sistema complejo de diferentes capacidades de iterador, y Scala codifica las capacidades de recolección de grano fino como rasgos. Las interfaces de la biblioteca estándar de Java a veces no son sólidas, por ejemplo Iterator#remove(), pero pueden usar clases anidadas como un tipo de tipo asociado (por ejemplo Map.Entry).

amon
fuente