Polimorfismo (ciencias de la computación)

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 25 de marzo de 2021; las comprobaciones requieren 11 ediciones .

El polimorfismo en lenguajes de programación y teoría de tipos  es la capacidad de una función para procesar datos de diferentes tipos [1] [2] [3] .

Hay varios tipos de polimorfismo. Dos fundamentalmente diferentes fueron descritos por Christopher Strachey en 1967 : estos son el polimorfismo paramétrico y el polimorfismo ad-hoc , otras formas son sus subespecies o combinaciones. El polimorfismo paramétrico es verdadero porque implica la ejecución del mismo código para todos los tipos de argumentos válidos, y el polimorfismo ad-hoc es imaginario, porque es asegurar la uniformidad cosmética de código ejecutable potencialmente diferente para cada tipo particular de argumento [1] [4] . Al mismo tiempo, hay situaciones en las que es necesario utilizar polimorfismo exactamente ad-hoc, y no paramétrico [5] . La teoría de los tipos calificados combina todo tipo de polimorfismo en un solo modelo.

Existe una definición generalizada de polimorfismo atribuida a Björn Stroustrup : " una interfaz (como una lista de declaraciones) - muchas implementaciones (definiciones asociadas con estas declaraciones) " [6] , pero solo el polimorfismo ad-hoc (polimorfismo imaginario) cae bajo esta definición.

Información general

La posibilidad fundamental de que el mismo código procese datos de diferentes tipos está determinada por las propiedades del sistema de tipos del lenguaje . Desde este punto de vista, se distingue [7] tipificación no polimórfica estática (descendientes de Algol y BCPL ), tipificación dinámica (descendientes de Lisp , Smalltalk , APL ) y tipificación polimórfica estática (descendientes de ML ). El uso de polimorfismo ad-hoc es más característico de la tipificación no polimórfica. El polimorfismo paramétrico y la tipificación dinámica aumentan la reutilización del código mucho más que el polimorfismo ad-hoc, ya que una función definida una vez implementa el comportamiento especificado sin duplicación para un número infinito de tipos recién definidos que satisfacen las condiciones requeridas en la función. Por otro lado, a veces se hace necesario proporcionar un comportamiento diferente de la función dependiendo del tipo de parámetro, y entonces es necesario un polimorfismo especial.

El polimorfismo paramétrico es sinónimo de abstracción de tipos [8] . Es omnipresente en la programación funcional , donde generalmente se lo denomina simplemente "polimorfismo".

En la comunidad de programación orientada a objetos , el término "polimorfismo" generalmente significa herencia , y el uso de polimorfismo paramétrico se denomina programación genérica [9] , o a veces "polimorfismo estático".

Clasificación

Por primera vez, la clasificación de variedades de polimorfismo fue realizada por Christopher Strachey .

Si exactamente un tipo está asociado con un parámetro de función, dicha función se denomina monomórfica. Muchos lenguajes de programación proporcionan un mecanismo sintáctico para asignar un solo nombre (identificador) a múltiples funciones monomórficas. En este caso, en el código fuente es posible llamar a una función con parámetros reales de diferentes tipos, pero en el código compilado, en realidad se llaman a diferentes funciones (ver procedimiento y sobrecarga de funciones ). Strachey llamó a esta posibilidad "polimorfismo ad-hoc".

Si más de un tipo está asociado con un parámetro de función, dicha función se denomina polimórfica . Por supuesto, solo se puede asociar un tipo con cada valor real, pero una función polimórfica considera parámetros basados ​​en propiedades externas, no en su propia organización y contenido. Strachey llamó a esta posibilidad "polimorfismo paramétrico".

Posteriormente, la clasificación fue refinada por Luca Cardelli [10] , destacando cuatro tipos de polimorfismo:

En algunos trabajos, el polimorfismo paramétrico, ad-hoc y de subtipo se distinguen como tres clases independientes de polimorfismo [11] .

La dualidad del significado del término "ad hoc" (por un lado - "espontáneo, mal concebido, hecho en la ocasión", por el otro - "especial, dispuesto específicamente para un propósito dado o una ocasión dada") se ha merecido durante muchos años [5] . Strachey eligió este término con base en el primer significado, enfatizando que con el polimorfismo ad-hoc no existe una única forma sistemática de inferir el tipo de resultado a partir del tipo de argumentos, y aunque es posible construir un cierto conjunto de reglas para estrechan el espectro de búsqueda, estas reglas son de naturaleza espontánea, tanto en contenido como en contexto de aplicación [1] .

De hecho, el polimorfismo ad-hoc no es un verdadero polimorfismo [12] . La sobrecarga de funciones no produce "valor que tiene múltiples tipos" sino "carácter que tiene múltiples tipos ", pero los valores identificados por ese símbolo son de tipos diferentes (potencialmente incompatibles). Del mismo modo, la conversión no es un verdadero polimorfismo: el operador parece aceptar valores de muchos tipos, pero los valores deben convertirse a alguna representación antes de que pueda usarlos, de modo que el operador realmente opera en un solo tipo (es decir, tiene un tipo). Además, el tipo del valor devuelto aquí no depende del tipo del parámetro de entrada , como en el caso del polimorfismo paramétrico.

Sin embargo, definir implementaciones de funciones específicas para diferentes tipos es en algunos casos una necesidad, no un accidente. Ejemplos clásicos son la implementación de operaciones aritméticas (físicamente diferentes para números enteros y de coma flotante ) y la igualdad de tipos, que durante décadas no tuvieron una formalización universal aceptada. La solución fueron las clases de tipo , que son un mecanismo para la enumeración discreta explícita de los valores permitidos de variables de tipo para despacho estático en la capa de tipo. Reúnen las dos variedades de polimorfismo separadas por Strachey, " haciendo que el polimorfismo ad-hoc sea menos ad hoc " [5] ( jugando con la dualidad). La generalización adicional de las clases de tipos condujo a la construcción de una teoría de tipos calificados , que formaliza uniformemente los sistemas de tipos más exóticos, incluidas las notaciones extensibles y los subtipos.

A diferencia de la sobrecarga y la conversión de tipos , el polimorfismo de subtipo es polimorfismo verdadero: los objetos de subtipo se pueden manipular de manera uniforme como si pertenecieran a sus supertipos (pero esto no es cierto para los lenguajes que implementan "polimorfismo por herencia" a través de conversión tipos y sobrecarga de funciones , como en el caso de C++ ). El más puro es el polimorfismo paramétrico : el mismo objeto o función se puede usar de manera uniforme en diferentes contextos de escritura sin modificaciones, conversiones o cualquier otra verificación o conversión en tiempo de ejecución. Sin embargo, esto requiere una representación uniforme de los datos (por ejemplo, a través de punteros ) [4] .

Tipos básicos de polimorfismo

Polimorfismo ad-hoc

El polimorfismo ad-hoc (traducido con mayor frecuencia en la literatura rusa como "polimorfismo especial" o "polimorfismo especializado", aunque ambas opciones no siempre son ciertas ) se admite en muchos idiomas a través de la sobrecarga de funciones y métodos , y en tipos débiles  también a través de tipos de fundición .

En el siguiente ejemplo ( lenguaje Pascal ), las funciones Addparecen implementar la misma funcionalidad en diferentes tipos, pero el compilador las define como dos funciones completamente diferentes.

programa Adhoc ; función Sumar ( x , y : Entero ) : Entero ; empezar Sumar := x + y terminar ; función Añadir ( s , t : Cadena ) : Cadena ; comenzar Añadir := Concat ( s , t ) fin ; comenzar Writeln ( Add ( 1 , 2 )) ; Writeln ( Add ( 'Hola, ' , '¡Mundo!' )) ; fin _

En lenguajes tipificados dinámicamente, la situación puede ser más complicada, ya que la elección de la función requerida para llamar solo se puede realizar en tiempo de ejecución.

La sobrecarga  es un mecanismo sintáctico que permite llamar a diferentes funciones mediante un único identificador [13] . La conversión de tipos  es un mecanismo semántico realizado para convertir el tipo real de un argumento en el tipo esperado de una función, sin el cual se produciría un error de tipo . Es decir, cuando se llama a una función con una conversión de tipo, se ejecuta un código diferente para diferentes tipos (precediendo a la llamada de la función en sí) [13] .

Polimorfismo paramétrico

El polimorfismo paramétrico permite definir una función o tipo de datos de forma genérica, de forma que los valores sean tratados de forma idéntica independientemente de su tipo. Una función paramétricamente polimórfica utiliza argumentos basados ​​en el comportamiento en lugar de los basados ​​en valores, accediendo solo a las propiedades de los argumentos que necesita, haciéndola utilizable en cualquier contexto donde el tipo de objeto satisfaga los requisitos de comportamiento dados.

Los sistemas de tipos avanzados (como el sistema Hindley-Milner ) proporcionan mecanismos para definir tipos polimórficos , lo que hace que el uso de funciones polimórficas sea más conveniente y proporciona seguridad de tipo estático . Dichos sistemas son sistemas de tipos de segundo orden, añadiendo a los sistemas de tipos de primer orden (utilizados en la mayoría de los lenguajes procedimentales ) la parametrización de tipos (mediante una variable de tipo ) y la abstracción de tipos (mediante cuantificación existencial sobre ellos). En los sistemas de tipos de segundo orden, no hay una necesidad inmediata de admitir tipos primitivos , ya que pueden expresarse a través de medios más avanzados. [catorce]

El ejemplo clásico de un tipo polimórfico es una lista de elementos de tipo arbitrario, para los cuales muchos lenguajes tipificados Hindley-Milner (la mayoría de los lenguajes de programación funcional tipificados estáticamente ) proporcionan azúcar sintáctico . El siguiente ejemplo demuestra la definición de un nuevo tipo algebraico " lista paramétricamente polimórfica " y dos funciones en él:

lista de datos a = cero | Contras a ( Lista a ) longitud :: Lista a -> Longitud entera Nil = 0 longitud ( Contras x xs ) = 1 + longitud xs map :: ( a -> b ) -> Lista a -> Lista b map f Nil = Nil map f ( Cons x xs ) = Cons ( f x ) ( map f xs )

Al sustituir tipos concretos en una variable de tipo , etc., se construirán tipos concretos, respectivamente, y así sucesivamente. Estos tipos particulares pueden, a su vez, ser sustituidos nuevamente en esa variable de tipo , produciendo tipos , y así sucesivamente. En este caso, para todos los objetos de todos los tipos construidos, se utilizará la misma implementación física de las funciones y . aIntStringList IntList StringList List StringList (Int, List String)lengthmap

Formas limitadas de polimorfismo paramétrico también están disponibles en algunos lenguajes de programación imperativos (particularmente orientados a objetos ), donde el término " programación genérica " ​​se usa comúnmente para referirse a ella. En particular, en C, el polimorfismo paramétrico sin tipo se proporciona tradicionalmente mediante el uso de un puntero void* sin tipo , aunque también es posible una forma con tipo. El uso de plantillas de C++ es superficialmente similar al polimorfismo paramétrico, pero se implementa semánticamente mediante una combinación de mecanismos ad-hoc; en la comunidad de C++ se llama "polimorfismo estático" (a diferencia del "polimorfismo dinámico" ).

Parametricidad

La formalización del polimorfismo paramétrico conduce al concepto de parametricidad , que consiste en la capacidad de predecir el comportamiento de los programas observando únicamente sus tipos. Por ejemplo, si una función es del tipo " forall a. a -> a", entonces sin ningún medio externo que complemente el lenguaje , se puede demostrar que solo puede ser idéntica . Por lo tanto, la parametricidad suele ir acompañada del lema "teoremas gratis" ( ing.  teoremas gratis ). [15] [16] [17]

Una consecuencia importante de  esto es también la independencia de representación , lo que significa que las funciones sobre un tipo abstracto son insensibles a su estructura, y diferentes implementaciones de este tipo pueden reemplazarse libremente (incluso dentro del mismo programa) sin afectar el comportamiento de estas funciones. [18] .

Los sistemas paramétricamente polimórficos más avanzados (punto más alto en el cubo lambda ) llevan la idea de parametricidad hasta el punto de poder probar completamente la corrección de los programas: permiten escribir programas que son correctos por diseño, de modo que al pasar una verificación de consistencia de tipos en sí misma garantiza que el comportamiento del programa es correcto .

Polimorfismo de registro y variante

Un problema aparte es la extensión del polimorfismo paramétrico a tipos agregados: productos discriminados de tipos (tradicionalmente llamados registros ) y sumas discriminadas de tipos (también conocidos como tipos variantes ). Varios " record calculus " ( cálculos de registros en inglés  ) sirven como base formal para la programación modular y orientada a objetos [20] .

val r = { a = 1 , b = verdadero , c = "hola" } val { a = n , ... = r1 } = r val r2 = { d = 3.14 , ... = r1 }

Los puntos suspensivos significan una cierta cantidad de campos escritos, es decir, una abstracción del código de tipos específicos de registros que podrían procesarse aquí (y la "longitud" de esta serie también puede variar). La compilación de accesos polimórficos a campos que se pueden colocar en un orden diferente en diferentes registros es un problema difícil, tanto desde el punto de vista del control de la seguridad de las operaciones a nivel del lenguaje, como desde el punto de vista del rendimiento en el código máquina. nivel. Una solución ingenua podría ser buscar dinámicamente el diccionario en cada llamada (y los lenguajes de secuencias de comandos lo usan), pero obviamente esto es extremadamente ineficiente. Este problema se ha estudiado activamente durante varias décadas; se han construido muchos modelos teóricos y sistemas prácticos basados ​​en ellos, que difieren en poder expresivo y complejidad metateórica. Los logros más importantes en esta área son el polimorfismo en línea propuesto por Mitchell Wand y el cálculo de registros polimórficos construido por Atsushi Ohori .  Un modelo más común, pero rezagado en muchas características, es la subtipificación en los registros .  

La compatibilidad con el polimorfismo de registros de una forma u otra puede abrir posibilidades en un lenguaje polimórfico, como mensajes de orden superior (la forma más poderosa de programación orientada a objetos ), la incrustación perfecta de operaciones en elementos de bases de datos ( SQL ) en código de lenguaje de propósito general, y otros, hasta programación extensible (es decir, programación libre del problema de la expresión ), garantizando la ausencia de excepciones no controladas en los programas, y ciertas formas de metaprogramación .

Polimorfismo de subtipo

El polimorfismo de inclusión esuna formalización generalizada de la subtipificación y la herencia [21] . Estos conceptos no deben confundirse: los subtipos definen relaciones a nivel de interfaz, mientras que la herencia define relaciones a nivel de implementación [22] .

La subtipificación ( subtyping ), o polimorfismo de subtipo (subtype polymorphism ), significa que el comportamiento de una función paramétricamente polimórfica está limitado a un conjunto de tipos acotados en una jerarquía de supertipo-subtipo [23] [10] [24] . Por ejemplo, si hay tipos , y , limitados por relaciones y , entonces una función definida en tipo , también podrá aceptar argumentos de tipos o , y su comportamiento será idéntico. El tipo real de un objeto se puede ocultar como una "caja negra" y solo se proporciona previa solicitud de identificación del objeto. De hecho, si un tipo es abstracto, entonces un objeto concreto de ese tipo ni siquiera puede existir (ver clase abstracta , pero no debe confundirse con tipo de datos abstracto ). Esta jerarquía de tipos se conoce (especialmente en el contexto del lenguaje Scheme ) como la torre de números y normalmente contiene más tipos. NumberRationalIntegerNumber :> RationalNumber :> IntegerNumberIntegerRationalNumber

La idea de la creación de subtipos está motivada por aumentar el conjunto de tipos que pueden manejar las funciones ya escritas y, por lo tanto, aumentar la tasa de reutilización de código bajo tipificación fuerte (es decir, aumentar el conjunto de programas tipificados ). Esto lo proporciona la regla de subsunción : " si una expresión epertenece a un tipo t'en un contexto de escritura Гy es verdadera t'<:t, entonces etambién pertenece al tipot " [25] [26] .

Las relaciones de subtipificación son posibles una amplia variedad de categorías de tipos: tipos primitivos ( as ) , Integer <: Numbertipos de suma , tipos de productos , tipos funcionales , etc. subtipificación [ 27 ] : nombró al género de todos sus subtipos como la potencia -clase del tipo [ 28 ] .

Un lugar especial en informática lo ocupa la subtipificación de registros .

Subtipado en registros

La subtipificación de registros , también conocida como subsunción (  consulte el principio de sustitución de Barbara Liskov ) , es la justificación teórica más común para la programación orientada a objetos (POO) [29] [30] [24] [31] (pero no la única; consulte # registro y polimorfismo variante ).

Martín Abadi y Luca Cardelli formalizaron la subtipificación de los registros a través de la cuantificación restringida sobre tipos paramétricamente polimórficos [29] [30] ; mientras que el parámetro de tipo se establece implícitamente [32] .

En la subtipificación sobre registros se distinguen dos variedades: en ancho y en profundidad.

El subtipo de ancho implica agregar nuevos campos a un registro . Por ejemplo:

tipo Objeto = { edad: Int } tipo Vehiculo = { edad: Int; velocidad: Int} tipo Bicicleta = { edad: Int; velocidad: Internacional; engranaje: Int; } tipoMáquina = { edad: Int; combustible: Cuerda

Por un lado, se pueden escribir las relaciones de subtipificación Vehicle <: Object, Bike <: Vehicle(y dado que la subtipificación es transitiva , entonces y Bike <: Object) y Machine <: Object. Por otro lado, podemos decir que tipos e Vehicleincluyen ( heredan) todas las propiedades de tipo . (Aquí, la semántica estructural del sistema de tipos está implícita ) BikeMachine Object

Debido a que un tipo a menudo se ve intuitivamente como un conjunto de valores, aumentar la cantidad de campos en un subtipo puede ser contrario a la intuición desde el punto de vista de la teoría de conjuntos . En realidad, los tipos no son conjuntos [33] , están destinados a verificar el comportamiento de los programas, y la idea de subtipado es que un subtipo tiene al menos las propiedades de su supertipo, y por lo tanto es capaz de emularlo al menos. donde se espera un objeto supertipo [25] . O en otras palabras: un supertipo define un conjunto mínimo de propiedades para un conjunto de objetos, y luego un tipo que tiene estas propiedades y, posiblemente, algunas otras, forma un subconjunto de este conjunto, y por lo tanto es su subtipo [30] .

Las relaciones de subtipo en términos de conjuntos son más intuitivas en el caso de tipos variantes [34] :

tipo Día = lun | mar | boda | jue | viernes | sentado | sol escriba Día laborable = lun | mar | boda | jue | vie escriba WeekEnd = sáb | sol

Aquí Workday <: Dayy WeekEnd <: Day.

Nombrar campos le permite abstraerse del orden de su aparición en los registros (a diferencia de las tuplas ), lo que hace posible construir gráficos de herencia acíclica dirigidos arbitrarios, formalizando la herencia múltiple [34] :

tipo Coche = { edad: Int; velocidad: Internacional; combustible: Cuerda

Ahora Car <: Vehicley al mismo tiempo Car <: Machine. También es obvio que Car <: Object(ver herencia en forma de diamante ).

La subtipificación profunda significa que los tipos de campos de registros particulares pueden sustituirse por sus subtipos :

type Voyage = {veh: Vehículo; dia de cita tipo Deportes = {veh: Bicicleta; dia de cita tipo Vacaciones = {veh: Coche; fecha: fin de semana }

De las definiciones anteriores, podemos deducir que Sports <: Voyagey Vacation <: Voyage.

Métodos en subtipos de registros

El soporte completo para la programación orientada a objetos implica la inclusión en el número de campos de registro también de funciones que procesan los valores de los tipos de registro a los que pertenecen [29] [35] . Estas funciones se denominan tradicionalmente " métodos ". Un modelo generalizado para vincular registros a métodos es la matriz de despacho ; en la práctica, la mayoría de los lenguajes lo descomponen en vectores en filas o columnas, respectivamente, implementando una organización basada en clases o una organización basada en métodos [36 ] . Al mismo tiempo, se debe distinguir entre métodos de anulación en subtipos ( anulación de métodos ) y funciones de subtipificación ( subtipificación funcional ). La anulación de métodos no los vincula con relaciones de subtipo en funciones, pero les permite cambiar sus firmas de tipo. En este caso, son posibles tres opciones: redefinición invariante, covariante y contravariante , y las dos últimas utilizan la subtipificación de sus parámetros [37] (para más detalles, consulte covarianza y contravarianza ). El cálculo de Abadi-Cardelli [29] considera solo métodos invariantes , lo cual es necesario para probar la seguridad .

Muchos lenguajes orientados a objetos proporcionan un mecanismo incorporado para enlazar funciones en métodos , implementando así una organización de programas basada en clases. Los lenguajes que tratan las funciones como objetos de primera clase y los escriben (consulte funciones de primera clase , tipo funcional , que  no debe confundirse con el tipo de retorno de una función ) permiten una organización arbitraria basada en métodos, lo que permite el diseño orientado a objetos sin apoyo directo desde los lados de la lengua [38] . Algunos lenguajes (como OCaml ) admiten ambos.

Los lenguajes con sistemas de tipos basados ​​en la teoría de subtipificación formal ( OCaml , el proyecto sucesor de ML ) tratan los sistemas de objetos y los sistemas de clases de forma independiente [39] [40] . Esto significa que el tipo de objeto se asocia principalmente con un objeto , y solo cuando se especifica explícitamente, el tipo de objeto se asocia con una determinada clase. En este caso, el envío dinámico se realiza a nivel de objeto, lo que significa que en dichos lenguajes, dos objetos pertenecientes a la misma clase, en términos generales, pueden tener un conjunto diferente de métodos. Junto con la semántica formalmente definida de herencia múltiple , esto brinda un soporte completo e inmediato para los mixins .

CLOS implementa toda la matriz de despacho a través de multimétodos , es decir, métodos despachados dinámicamente que son polimórficos en varios argumentos a la vez [41] .

Algunos lenguajes utilizan peculiares soluciones ad-hoc. Por ejemplo, el sistema de tipos del lenguaje C++ permite la conversión automática de tipos (es decir, es débil ), no polimórfico , emula la creación de subtipos de la herencia manifiesta con firmas de métodos invariantes y no admite la abstracción de tipos (que no debe confundirse con ocultación de campo ). La herencia en C++ se implementa mediante un conjunto de mecanismos ad-hoc; sin embargo, su uso se denomina "polimorfismo" en la comunidad lingüística (y la ocultación de campos se denomina "abstracción" [42] ). Es posible controlar el gráfico de herencia: la herencia en forma de diamante en C++ se llama " herencia virtual " y se especifica mediante un atributo explícito ; de forma predeterminada, los campos heredados se duplican y se accede a ellos mediante un nombre calificado. El uso de dicho lenguaje puede ser inseguro  : no se puede garantizar la estabilidad de los programas [43] [37] (un lenguaje se dice seguro si los programas que contiene, que el compilador puede aceptar como bien formados, nunca van más allá de el comportamiento permitido en dinámica [44] ). virtual

Subtipificación de orden superior

El sistema es una extensión del Sistema F (no representado en el cubo lambda ), que formaliza la cuantificación restringida sobre los operadores de tipos , extendiendo las relaciones de subtipado de género a tipos de género superior . Hay varias versiones del sistema , que difieren en poder expresivo y complejidad metateórica, pero la mayoría de las ideas principales fueron establecidas por Luca Cardelli [45] . *

Una combinación de variedades de polimorfismo

Clases de tipo

Una clase de tipo implementa una sola tabla independiente de métodos virtuales para muchostipos ( cuantificados universalmente ). De esta manera, las clases de tipos difieren de las clases en la programación orientada a objetos , donde cada objeto de cualquier tipo ( restringido cuantificado ) va acompañado de un puntero a una tabla de método virtual [46] . Las clases de tipos no son tipos, sino categorías de tipos; sus instancias no son valores, sino tipos.

Por ejemplo [46] :

class Num a donde ( + ), ( * ) :: a -> a -> a negate :: a -> a

Esta declaración se lee así: " Un tipo apertenece a una clase Numsi las funciones (+), (*)y negate, con las firmas dadas están definidas en él ".

instancia Num Int donde ( + ) = addInt ( * ) = mulInt negate = negInt instancia Num Float donde ( + ) = addFloat ( * ) = mulFloat negate = negFloat

La primera declaración dice: " Hay funciones (+)y firmas correspondientes (*)que negatese definen sobre el tipoInt ". La segunda declaración dice de manera similar.

Ahora puede escribir correctamente las siguientes funciones (y la inferencia de tipo es decidible ):

cuadrado :: Num a => a -> un cuadrado x = x * x cuadrados3 :: Num a , Num b , Num c => ( a , b , c ) -> ( a , b , c ) cuadrados3 ( x , y , z ) = ( cuadrado x , cuadrado y , cuadrado z )

Dado que la operación de multiplicación se implementa físicamente de manera diferente para números enteros y de punto flotante , en ausencia de clases de tipos, aquí ya se requerirían dos funciones sobrecargadassquare y ocho funciones sobrecargadassquares3 , y en programas reales con estructuras de datos complejas, hay mucho más código duplicado . En la programación orientada a objetos, los problemas de este tipo se resuelven mediante el envío dinámico , con la sobrecarga asociada. La clase de tipo se despacha estáticamente, trayendo polimorfismos paramétricos y ad-hoc en un solo modelo [5] . En términos de polimorfismo paramétrico, una clase de tipo tiene un parámetro ( una variable de tipo ) que abarca un conjunto de tipos. Desde el punto de vista del polimorfismo ad-hoc, este conjunto no solo es discreto, sino que también se especifica explícitamente hasta el nivel de implementación. En pocas palabras, la firma significa que la función es paramétricamente polimórfica , pero el rango de tipos de su parámetro está limitado solo a aquellos tipos que pertenecen a la clase de tipos . Debido a esto, la función se escribe de forma única, a pesar de la llamada a la función sobrecargada desde su cuerpo. square :: Num a => a -> aNum

El soporte nativo para las clases de tipos se implementó por primera vez en Haskell , pero también se pueden introducir en cualquier lenguaje polimórfico paramétrico mediante un preprocesamiento simple [5] y también se pueden implementar idiomáticamente (ver, por ejemplo, el lenguaje del módulo ML#Implementación de modelos alternativos ). Sin embargo, el apoyo directo puede facilitar el razonamiento automático sobre el significado de los programas.

Los tipos de igualdad en Haskell se implementan como instancias de una clase de tipoEq(generalizando las variables de tipo de igualdad de Standard ML ) :

( == ) :: Eq a => a -> a -> Bool

Para reducir la molestia de codificar algunas de las propiedades obviamente necesarias de los tipos definidos por el usuario, Haskell también proporciona azúcar sintáctico  , una construcción derivingque es válida para un conjunto limitado de clases de tipos estándar (como Eq). (En la comunidad de habla rusa, su uso suele confundirse con el concepto de " herencia " debido a las peculiaridades de la traducción de la palabra " derivar ".)

Tipos de datos algebraicos genéricos

Politipismo

A veces se utiliza el término "politipismo" o "generalización de tipos de datos". Esencialmente, el politipado se refiere al soporte integrado del lenguaje para el polimorfismo del constructor de tipos , diseñado para unificar las interfaces de programación y aumentar la reutilización del código . Un ejemplo de politipismo es el algoritmo de coincidencia de patrones generalizados [47] .

Por definición, en una función de politipo, " aunque puede haber un número finito de ramas ad-hoc para algunos tipos, no hay un combinador ad-hoc " [48] .

La politipificación se puede implementar mediante el uso de un tipo de datos genérico o un polimorfismo de rango superior . La extensión PolyP [49] de Haskell es una construcción de sintaxis que simplifica la definición de funciones de politipo en Haskell .

Una función de politipado es, en cierto sentido, más general que una función polimórfica, pero, por otro lado, una función puede ser politipada y no polimórfica, como se puede ver en las siguientes firmas de tipo de función :

head :: [ a ] ​​​​-> a ( + ) :: Num a => a -> a -> a length :: Regular d => d a -> Int sum :: Regular d => d Int -> En t

La primera función ( head) es polimórfica (paramétricamente polimórfica ), la segunda (el operador infijo “ ”) está sobrecargada (ad-hoc-polimórfica), la tercera y la cuarta son politipadas: la variable tipo en su definición varía según el tipo constructores _ Al mismo tiempo, la tercera función ( ) es politipada y polimórfica (presumiblemente, calcula la "longitud" de algún conjunto de tipos agregados polimórficos, por ejemplo, el número de elementos en listas y árboles ), y la cuarta ( ) es politipado, pero no polimórfico (monomórfico sobre tipos agregados pertenecientes a la clase de tipos , para los cuales probablemente calcula la suma de los números enteros que forman un objeto de un tipo agregado particular). + dlengthsum Regular

Varios

Los lenguajes tipificados dinámicamente representan uniformemente variedades de polimorfismo, lo que forma una ideología distintiva en ellos y afecta las metodologías de descomposición de tareas aplicadas. Por ejemplo, en Smalltalk , cualquier clase puede recibir mensajes de cualquier tipo y procesarlos por sí mismos (incluso a través de la introspección ), o retransmitirlos a otra clase; por lo tanto, cualquier método es formalmente polimórfico paramétricamente, mientras que su estructura interna puede bifurcarse según la condición del tipo de argumento dinámico, implementando un polimorfismo especial. En CLOS , los multimétodos son simultáneamente funciones de primera clase , lo que nos permite considerarlos tanto como cuantificados limitadamente como generalizados ( polimórficos verdaderos ).

Los lenguajes tipificados con polimorfismo estático , por el contrario, pueden implementar variedades de polimorfismo ortogonalmente (independientemente entre sí), lo que les permite construirse intrincadamente de una manera segura . Por ejemplo, OCaml admite clases paramétricas (similares en capacidades a las plantillas de clase de C++ , pero verificables sin necesidad de creación de instancias), su herencia de amplitud y profundidad (incluidos múltiples ), implementación idiomática de clases de tipos (a través de firmas: ver el correspondiente ejemplo de uso del lenguaje del módulo ML ), polimorfismo en línea , polimorfismo paramétrico de rangos superiores a 1 (por medio de los llamados tipos localmente abstractos que implementan tipos existenciales ) y tipos de datos algebraicos generalizados .

Historia

El término "polimorfismo" proviene del griego. πολύς ("mucho") y μορφή ("forma, forma, dispositivo").

Los términos "polimorfismo especializado" y "polimorfismo paramétrico" se mencionan por primera vez en 1967 en las notas de clase de Christopher Strachey tituladas " Fundamentos de los lenguajes de programación [ " [1] . En 1985, Peter Wegner y Luca Cardelli formalizaron el polimorfismo de contención para modelar subtipos y herencia [10] [27] , aunque las implementaciones de subtipos y herencia aparecieron mucho antes, en el lenguaje Simula en 1967 . El polimorfismo de inclusión se basa en la cuantificación restringida .

La notación del polimorfismo paramétrico como un desarrollo del cálculo λ (llamado sistema F ) fue formalmente descrita por el lógico Jean-Yves Girard [50] [51] ( 1971 ), independientemente de él se describió un sistema similar por el informático John S. Reynolds [52 ] ( 1974 ).

El primer lenguaje completamente basado en el cálculo polimórfico λ fue ML ( 1973 ); independientemente de él, los tipos paramétricos fueron implementados en Clu ( 1974 ) [27] . Muchos lenguajes modernos ( C++ , Java , C# , D y otros) proporcionan tipos paramétricos en una forma más o menos cercana a su implementación en Clu.

En 1987, Mitchel Wand formalizó el polimorfismo en línea y tipificó la inferencia para él [53] ; este trabajo tuvo un gran impacto en el desarrollo posterior de los sistemas tipográficos . En el mismo año, Philip Wadler y Stephen Blott propusieron clases de tipos para formalizar el polimorfismo ad-hoc . 

Véase también

Notas

  1. ↑ 1 2 3 4 Strachey, 1967 .
  2. ↑ Cardelli, 1991 , pág. 3.
  3. ↑ Pierce, 2012 , 22.7. Polimorfismo a través de let, pág. 354.
  4. ↑ 1 2 Cardelli, 1985 , p. 6.
  5. ↑ 1 2 3 4 5 Wadler, 1988 , pág. 1-2.
  6. ↑ Bjarne Stroustrup . Glosario de C++ (19 de febrero de 2007). Archivado desde el original el 29 de junio de 2018.
  7. ↑ Andrew W. Appel. Una crítica del ML estándar . — Universidad de Princeton, 1992.
  8. ↑ Harper, 2012 , 20.1 Sistema F, pág. 172.
  9. ↑ Pierce, 2012 , 23.2 Variedades de polimorfismo, p. 365.
  10. ↑ 1 2 3 Cardelli, 1985 .
  11. ↑ Mitchell, 2002 , 6.4. Polimorfismo y sobrecarga, pág. 145-151.
  12. ↑ Cardelli, 1985 , 1.3. Tipos de polimorfismo, pág. 6.
  13. ↑ 1 2 Cardelli, 1985 , p. 5-6.
  14. ↑ Cardelli, 1996 , 5 Sistemas tipo de segundo orden, p. 25
  15. ↑ Harper, 2012 , 20.3 Resumen de parametricidad, p. 177.
  16. ↑ Harper, 2012 , 49 Parametricidad, p. 495-508.
  17. ↑ Pierce, 2012 , 23.9 Parametricidad, p. 384-385.
  18. ↑ Harper, 2012 , 21.4 Representación Independencia, p. 188.
  19. ↑ Pierce, 2012 , 30.5 Yendo más lejos: Tipos dependientes, p. 489-493.
  20. ↑ Reynolds, 1998 , 16. Subtipos y tipos de intersección. Notas bibliográficas, pág. 376.
  21. ↑ Cardelli, 1985 .
  22. ↑ Mitchell, 2002 , 10.2.6 La herencia no es subtipificación, p. 287.
  23. ↑ Cardelli, 1991 .
  24. ↑ 1 2 Pierce, 2012 , 15 Subtipos, p. 193.
  25. ↑ 1 2 Pierce, 2012 , 15. Subtipos, p. 193.
  26. ↑ Harper, 2012 , 23.1. Subsunción, pág. 208.
  27. ↑ 1 2 3 Pierce, 2012 , 1.4 Breve historia, p. 11-13.
  28. ↑ Cardelli, 1991 , 6. Tipos de poder, p. 32.
  29. ↑ 1 2 3 4 Abadi, Cardelli, 1994 .
  30. ↑ 1 2 3 Cardelli, 1985 , 6. Cuantificación acotada, p. 28
  31. ↑ Minsky traducido por DMK, 2014 , Subtyping, p. 259.
  32. ↑ Cardelli, 1985 , pág. 9.
  33. ↑ Harper, 2012 , Capítulo 16. Tipos recursivos, p. 132.
  34. ↑ 1 2 Cardelli, 1991 , p. 35-37.
  35. ↑ Cardelli, 1985 , 2.3. Tipos básicos, tipos estructurados y recursividad, pág. 12-14.
  36. ↑ Harper, 2012 , Capítulo 25. Despacho dinámico, p. 229.
  37. ↑ 1 2 Joyner, 1996 , 3.38 Signature Variance, p. 35.
  38. ↑ Programación orientada a objetos en ML estándar . Consultado el 11 de marzo de 2016. Archivado desde el original el 14 de enero de 2016.
  39. ↑ Minsky traducido por DMK, 2014 , Capítulo 11. Objetos, p. 253.
  40. ↑ El grupo de trabajo ML2000. Principios y un Diseño Preliminar para ML2000 . — 1999.
  41. ↑ Castaña, Ghelli, Longo. Un cálculo para funciones sobrecargadas con subtipado  // Información y Cómputo. - Prensa académica, 1995. - T. 117 , núm. 1 . - S. 115-135 . -doi : 10.1006/ inco.1995.1033 .
  42. ↑ Joyner, 1996 , 2.8 Encapsulación, p. ocho.
  43. ↑ Mitchell, 2002 , 6.2.1 Tipo de seguridad, p. 132-133.
  44. ↑ Harper, 2012 , Capítulo 4. Estática, p. 35.
  45. ↑ Pierce, 2012 , 31. Subtipos de orden superior, p. 495.
  46. ↑ 12 Wadler , 1988 , pág. 3.
  47. ↑ Johan Jeuring. Coincidencia de patrones politípicos  // FPCA. - 1995. - doi : 10.1.1.36.5645 .
  48. ↑ Ralf Lammel y Joost Visser, "Combinadores tipificados para cruce genérico", en Aspectos prácticos de los lenguajes declarativos: 4º Simposio internacional (2002), p. 153.
  49. ↑ Patrik Jansson, Johan Jeuring. PolyP: una extensión del lenguaje de programación Polytypic . — Sigplan SPPL, 1997.
  50. ↑ Girard - Extensión de la teoría de tipos, 1971 .
  51. ↑ Girard - Cálculo de orden superior, 1972 .
  52. ↑ Reynolds, 1974 .
  53. ↑ Varita, 1987 .

Literatura

  • Christopher Strachey. Conceptos Fundamentales en  Lenguajes de Programación . - 1967. Archivado el 12 de agosto de 2017.
    • Reeditado: Christopher Strachey. Conceptos fundamentales en lenguajes de programación  // Computación de orden superior y simbólica  . - 2000. - vol. 13 _ - P. 11-49 . -doi : 10.1023/A : 1010000313106 .
  • Jean-Yves Girard. Une Extension de l'Interpretation de Gödel à l'Analyse, et son Application à l'Elimination des Coupures dans l'Analyse et la Théorie des Types  (francés)  // Actas del Segundo Simposio de Lógica Escandinava. - Ámsterdam, 1971. - Págs. 63-92 . - doi : 10.1016/S0049-237X(08)70843-7 .
  • Jean-Yves Girard. Interprétation fonctionnelle et eliminación des coupures de l'arithmétique d'ordre supérieur  (francés) . — Universidad París 7, 1972.
  • John C. Reynolds. Hacia una teoría de la estructura de tipos // Apuntes de clase en informática . - París: Colloque sur la programmation, 1974. - Vol. 19 . - S. 408-425 . -doi : 10.1007/ 3-540-06859-7_148 .
  • Luca Cardelli , Peter Wegner. Sobre la comprensión de los tipos, la abstracción de datos y el polimorfismo //Encuestas informáticas de ACM. - Nueva York, EE. UU.:ACM, 1985. -17,no. 4. -S. 471-523. —ISSN 0360-0300. -doi:10.1145/6041.6042.
  • Robert Harper . Introducción al aprendizaje automático estándar. - Universidad Carnegie Mellon, 1986. - ISBN PA 15213-3891.
  • Traducción al ruso: Robert Harper . Introducción al aprendizaje automático estándar. - Universidad Carnegie Mellon, 1986. - 97 p. — ISBN PA 15213-3891.
  • Mitchell Wand . Inferencia completa de tipos para objetos simples // En Proc. 2do Simposio IEEE sobre Lógica en Ciencias de la Computación. - 1987. -P. 37-44.
  • Philip Wadler, Stephen Blott. Cómo hacer que el polimorfismo ad-hoc sea menos ad hoc  . — 1988.
  • Luca Cardelli . Programación tipificada // Informes de Estado del Arte IFIP. - Nueva York: Springer-Verlag, 1991. -Edición. Descripción formal de los conceptos de programación. -431-507.
  • Martín Abadi, Luca Cardelli . Una semántica de los tipos de objetos  . — LICS , 1994.
  • Luca Cardelli . Tipo de sistemas (inglés) // Manual de informática e ingeniería. — Prensa CRC, 1996.
  • Benjamín Pierce. Tipos y Lenguajes de Programación  . - MIT Press , 2002. - ISBN 0-262-16209-1 .
    • Traducción al ruso: Benjamin Pierce. Tipos en lenguajes de programación . - Dobrosvet , 2012. - 680 p. — ISBN 978-5-7913-0082-9 .
  • Juan C Mitchell Conceptos en lenguajes de programación  . - Prensa de la Universidad de Cambridge, 2002. - 540 p. - ISBN 978-0-521-78098-8 .
  • Minsky, Madhavapeddy, Hickey. Real World OCaml: Programación funcional para las  masas . - O'Reilly Media, 2013. - 510 p. — ISBN 9781449324766 .
    • Traducción al ruso: Minsky, Madhavapeddy, Hickey. Programación en el lenguaje OCaml . - DMK, 2014. - 536 p. — (Programación funcional). - ISBN 978-5-97060-102-0 .