Idioma del módulo ML

El lenguaje de módulos ML es un sistema de módulos utilizado principalmente en lenguajes de programación de la familia ML , que tiene semántica aplicativa , en otras palabras, es un pequeño lenguaje funcional que opera con módulos [1] .

Es el sistema de módulos más desarrollado entre los que se encuentran en los lenguajes de programación [2] [3] .

Información general

En su forma más simple, un lenguaje de módulos consta de tres tipos de módulos:

La firma puede considerarse como una descripción de la estructura y la estructura, respectivamente, como la implementación de la firma. Muchos lenguajes proporcionan construcciones similares, generalmente con diferentes nombres: las firmas a menudo se denominan interfaces o especificaciones de paquetes, y las estructuras a menudo se denominan implementaciones o paquetes. Independientemente de la terminología, la idea es asignar un tipo a un código completo. A diferencia de muchos lenguajes, en ML, la relación entre firmas y estructuras es de muchos a muchos en lugar de muchos a uno o uno a uno . Una firma puede describir muchas estructuras diferentes y una estructura puede corresponder a muchas firmas diferentes. La mayoría de los otros idiomas están sujetos a restricciones más estrictas, que requieren que una estructura determinada tenga una firma única o que una firma determinada se derive de una estructura única. Este no es el caso de ML [4] .

En los principales lenguajes orientados a objetos como C++ o Java , la abstracción se proporciona a través de clases que combinan una serie de características ( herencia , subtipado y despacho dinámico ) en un concepto a la vez, lo que las hace difíciles de formalizar. y puede tener consecuencias indeseables cuando se usa sin cuidado. A diferencia de las clases, el lenguaje del módulo ML se enfoca completamente en la abstracción , brindando una amplia gama de sus formas y brindando una base formal sólida para su estudio. [5] Proporciona administración de jerarquía de espacio de nombres, personalización de interfaz detallada , abstracción del lado del implementador y abstracción del lado del cliente .

Los funtores son un concepto único que no tiene equivalente en la mayoría de los lenguajes . Son funciones sobre estructuras, es decir, calculan nuevas estructuras a partir de las ya calculadas, naturalmente, de acuerdo con determinadas firmas. Esto le permite resolver una amplia variedad de problemas de estructuración de programas complejos .

En este caso, se cumplen dos requisitos [6] :

En la práctica, la posibilidad de compilación separada no siempre se usa - hay compiladores de optimización completa que abren el marco de módulos para aumentar significativamente el rendimiento de programas .

Idioma

Estructuras y firmas

Entorno ( eng.  environment ) en el ML central ( ing.  Core ML ) es una colección de definiciones ( tipos , incluidos los funcionales , y valores , incluidos los funcionales y exclusivos ). El entorno tiene un alcance léxico .

Una estructura ( structure) es un entorno "materializado", convertido en un valor manipulable [7] . En relación a implementaciones tempranas del lenguaje de módulos, esta definición es algo así como una convención, ya que inicialmente las estructuras podrían definirse o evaluarse solo en el nivel superior del código (en el entorno global). El trabajo posterior desarrolla el lenguaje del módulo a un nivel de primera clase .

La introducción del concepto de estructura requiere una revisión de la definición de entorno en el núcleo del lenguaje. De ahora en adelante, el medio ambiente es una colección de tipos, valores y estructuras. En consecuencia, una estructura es una colección de tipos, valores y otras estructuras. No se permite el anidamiento recursivo de estructuras, aunque algunas implementaciones las admiten [5] .

Los medios principales para definir estructuras son declaraciones encapsuladas , es decir, declaraciones encerradas entre corchetes sintácticos struct...end. Por ejemplo, la siguiente estructura implementa una pila , definiendo la organización interna de objetos del tipo algebraico "pila" y el conjunto mínimo requerido de funciones sobre ella:

tipo de estructura 'a t = 'una lista val vacío = [] val isEmpty = nulo val push = op :: val pop = List . fin de getItem

El "valor" de esta declaración encapsulada es una estructura. Para usar este valor, debe asignarle un identificador:

estructura Pila = tipo de estructura 'a t = 'una lista val vacío = [] val isEmpty = nulo val push = op :: val pop = Lista . fin de getItem

Ahora se puede acceder a los componentes de la estructura a través de nombres compuestos (o calificados), como Stack.push, Stack.empty : Stack.t.

La firma ( signature) es una enumeración de las descripciones de los elementos de la estructura, es decir, la interfaz de la estructura. Cada elemento de esta enumeración se denomina especificación. Si el tipo se especifica para un valor en la firma , entonces en la estructura el identificador debe estar vinculado a un valor de tipo . Puede pensar en una firma como una especie de " tipo " de una estructura, pero una firma no es un tipo en sentido estricto, ya que un tipo es un conjunto de valores y un "valor de firma" puede contener tipos (que en ML no son valores). Cada identificador en la firma debe ser único. No se observa la regla del sombreado léxico de los nombres en las firmas, por lo que no importa el orden de su enumeración, pero los tipos deben declararse antes de su uso, por lo que tradicionalmente se colocan al comienzo de la firma. x tx t

La definición de la firma se escribe entre paréntesis sintácticos sig...end. Por ejemplo, una estructura Stacktiene la siguiente firma (el compilador la deduce automáticamente):

pila de estructura : sig tipo 'a t = 'una lista val vacía : 'a t val isEmpty : 'a t -> bool val push : 'a * 'a t -> 'a t val pop : 'a t -> ( 'a * 'a t ) fin de opción

La propiedad principal de las firmas es que las estructuras se pueden comparar con ellas .  Una estructura es comparable a una firma dada si contiene al menos los tipos, valores y estructuras anidadas enumeradas en la firma [8] . Hay dos formas de combinar estructuras con firmas: transparente ( inglés  transparente ) y oscuro ( inglés  opaco ). En general, la capacidad de elegir la forma de firmar se denomina propiedad de translucidez de las  firmas [ 9] [10] .

La "firma predeterminada" inferida por el compilador suele ser redundante, ya que expone al público la información de implementación de sus componentes, lo que es una violación del principio de abstracción . Por lo tanto, en la mayoría de los casos, el programador describe explícitamente la firma deseada y realiza firma con una firma ( English  signature description ) o sellado ( English  Sealing ) [5] [3] [11] [12] , asegurando así que los componentes de la estructura elegida por él se ocultan del resto del programa [13] . Más precisamente, se realiza el enlace de la estructura emparejada.

Por ejemplo, un desarrollador puede definir una firma que describa varios flujos de datos ( estructuras de datos con acceso secuencial) y asignarle un identificador:

firma STREAM = tipo de firma 'a t val vacío : 'a t val isEmpty : 'a t -> bool val push : 'a * 'a t -> 'a t val pop : 'a t -> ( 'a * ' a t ) fin de opción

La firma propia de una estructura puede enriquecer ( eng.  enrich ) la firma con la que se hace la comparación, es decir, contener más componentes, más tipos, y estos tipos pueden ser más generales. La relación de enriquecimiento se escribe formalmente como (firma enriquece firma ).

En este caso, puedes escribir :

La coincidencia transparente tradicionalmente tiene la S : SSsintaxis " ", mientras que la coincidencia oscura tiene la sintaxis " " S :> SS. Sin embargo, los creadores de OCaml han dejado de admitir la coincidencia transparente por completo, lo que significa que todas las asignaciones en OCaml son oscuras, pero la sintaxis " " se usa por simplicidad. S : SS

En los casos más simples, puede firmar una firma inmediatamente sin asignarle un identificador separado:

pila de estructura :> tipo de firma 'a t val isEmpty : 'a t -> bool val push : 'a * 'a t -> 'a t val pop : 'a t -> ( 'a * 'a t ) opción final = tipo de estructura 'a t = 'una lista val vacío = [] val isEmpty = null val push = op :: val pop = List . fin de getItem

Sin embargo, en la práctica, las firmas sin nombre son bastante raras, ya que el uso de firmas no se limita a ocultar .

Una estructura en diferentes contextos se puede asignar a diferentes firmas, y una firma puede servir como interfaz para diferentes estructuras. La firma define una clase de estructuras (en el sentido matemático del término " clase ") [14] . Una "vista exterior" diferente para una estructura, con diferentes grados de abstracción , puede ser proporcionada por varias firmas con un conjunto diferente de especificaciones [15] . El orden de las declaraciones no importa y no afecta la comparabilidad de estructuras con firmas.

Esto puede verse como el análogo más simple de las clases abstractas (en términos de programación orientada a objetos ), en el sentido de que una firma describe una interfaz común y estructuras comparables implementan esa interfaz de diferentes maneras. Sin embargo, en ML, la relación padre-hijo no se declara explícitamente, porque el sistema de tipo ML tiene estructural , es decir, hacer coincidir una estructura con una firma se lleva a cabo mediante el mismo mecanismo que hacer coincidir un valor con un tipo . 5int

Por ejemplo, se puede definir una estructura que implemente una cola , pero que también sea comparable a una firma STREAM:

estructura Cola = struct tipo de datos 'a t = T de 'una lista * 'una lista val vacío = T ([], []) val isEmpty = fn T ([], _) => verdadero | _ => false val normalize = fn ([], ys ) => ( rev ys , []) | q => q fun push ( y , T ( xs , ys )) = T ( normalizar ( xs , y::ys )) val pop = fn ( T ( x::xs , ys )) => ALGUNOS ( x , T ( normalizar ( xs , ys ))) | _ => NINGUNO fin

Dado que la estructura Stackno se firmó explícitamente con una firma más pobre, el programa externo "sabe" que el tipo tes idéntico al tipo listy puede usar este conocimiento para procesar objetos de este tipo usando métodos de módulo estándar List. Si más tarde es necesario cambiar la implementación de la estructura (por ejemplo, al representar la pila con una matrizStack preasignada ), será necesario volver a escribir todo el código que usó este conocimiento. Lo mismo es cierto para la estructura . Además, si un módulo ha sido parametrizado con su propia firma de estructura , entonces no será posible pasarle una estructura como parámetro . QueueStackQueue

Por lo tanto, exportar información innecesaria de las estructuras empeora significativamente la modificabilidad de los programas. Para aumentar el nivel de abstracción , las estructuras deben firmarse con firmas más pobres, por ejemplo:

pila de estructura :> STREAM = tipo de estructura 'a t = 'una lista val vacío = [] val isEmpty = nulo val push = op :: val pop = List . fin de getItem

La estructura está Stackasignada a la firma STREAMde forma oscura, por lo que un programa externo podrá operar completamente sobre los valores de tipo Stack.t, pero no tendrá acceso a su implementación, y de todos los valores posibles de este tipo, podrá usar solo el valor Stack.empty(de nuevo, "sin saber » que es igual a nil). Cualquier tratamiento de datos de este tipo se realizará de forma abstracta , sin tener en cuenta su implementación, y sólo podrá realizarse a través de las funciones Stack.pushy Stack.pop.

Pero en ninguna parte las firmas son más importantes y útiles que cuando se usan funtores [16] .

Herencia

Las estructuras se pueden anidar unas dentro de otras:

estructura E = estructura estructura A estructura B ... fin

Naturalmente, las firmas le permiten describir estructuras anidadas. En este caso, como en otros casos, el anidamiento de estructuras se controla en base a firmas, y no a coincidencias idénticas:

firma D = sig estructura A : C estructura B : C final

Las firmas se pueden incluir (sintaxis include S) entre sí, enriqueciendo secuencialmente la interfaz:

firma POBRE = sig type 'a t val isEmpty : 'a t -> bool val push : 'a * 'a t -> 'a t val pop : 'a t -> ( 'a * 'a t ) option end firma RICO = sig incluir POBRE val vacío : 'a t fin

Cabe señalar que, de acuerdo con la semántica descrita, la firma de la firma no tiene que realizarse de inmediato. Si necesita desarrollar un determinado conjunto de módulos estrechamente interconectados que son más "amigables" entre sí que con el resto del programa, luego de que se complete su desarrollo, puede firmar las estructuras con firmas más pobres:

estructura SomeModule :> RICH = struct ... end ... estructura SomeModule :> POOR = SomeModule

La última línea no debe considerarse una asignación destructiva . Este idioma se basa en la visibilidad léxica , que es una parte integral de la semántica de cualquier lenguaje aplicativo . Tanto en el núcleo de ML como a nivel de módulo, la construcción x = asiempre significa vincular un valor a un identificador. La vinculación no es una asignación , "crea" un nuevo identificador que no tiene nada que ver con el (posiblemente) definido previamente [17] . La estructura original SomeModuletodavía existe en el programa, pero el código posterior no tiene acceso a aquellos de sus componentes que no forman parte de la firma más pobre (en este caso, es una constante empty).

La estructura se puede abrir (sintaxis open S). En el caso más simple, esto se puede considerar como azúcar sintáctico , sirviendo para la conveniencia de usar las definiciones encapsuladas en el módulo (análogas a la construcción withen el lenguaje Pascal ):

fun foo x = abrir SMLofNJ .Cont en fun f x = callcc ( fn k => ... throw k ... ) fun g x = aislar ... fin

Si se hace lo mismo en el nivel superior del programa (en el entorno global), esto puede considerarse como un análogo de la construcción using namespaceen el lenguaje C++ . Por ejemplo, las estructuras que implementan tipos estándar y operaciones sobre ellas ( Int, Realy Stringotras) están abiertas de forma predeterminada (para obtener más información sobre esto, consulte control numérico ). Sin embargo, la posibilidad de abrir estructuras también existe dentro de otras estructuras y, en este caso, la apertura sirve como una herramienta para incluir estructuras entre sí para expandir la funcionalidad de manera consistente (análogo a la herencia de clases más simple ). Por ejemplo:

estructura B = estructura abierta A ... fin

La estructura Bincluye todas las definiciones de la estructura Ay las complementa con nuevas definiciones. Esto es lo mismo que enumerar explícitamente todas las definiciones Adentro de B. Esta posibilidad tiene dos desventajas [18] :

  • si hay identificadores en la estructura que se abre que coinciden con los identificadores que ya existen en el contexto dado, estos últimos se volverán inaccesibles para el acceso directo. Por el contrario, las definiciones después de abrir sombrearán los componentes importados. No hay conflicto de nombres, solo se ve la última definición, pero esto puede ser un inconveniente para el desarrollador. La excepción es si los nombres de tipos coinciden con los nombres de valores existentes, ya que el compilador de ML siempre puede determinar el significado de un identificador a partir del contexto de su uso [19] (ver inferencia de tipos ). El problema de sombrear nombres es especialmente relevante cuando se incluyen dos o más estructuras.
  • a veces se vuelve difícil determinar qué se incluye exactamente de la estructura abierta, especialmente cuando se abren estructuras grandes que definen una gran cantidad de identificadores.

Por lo tanto, a menudo se recomienda utilizar la introducción de un identificador local corto [18] en lugar de abrir , por ejemplo:

estructura SomeModule :> sig fun f x : ... fun g x : ... ... end = struct estructura local C = SMLofNJ . Continúa en ... diversión f x = C . callcc ( fn k => ... C . throw k ...) divertido gramo x = C . aislar ... _ _

Sin embargo, a veces se puede utilizar la precedencia de la última definición para "redefinir" deliberadamente un identificador (que, sin embargo, no es una sobrecarga ).

Antecedentes históricos

Anteriormente, en la Definición SML'90 [20] , era posible abrir en firmas. Esta función fue criticada debido al deterioro de la autodocumentación (aprender la interfaz de un módulo mientras se usa te obliga a referirte a otro) [21] , y fue abolida en la revisión del lenguaje SML'97. Es importante señalar aquí que la apertura ( open) es fundamentalmente diferente de la inclusión ( include), ya que cada identificador debe ser único dentro de la firma y no se sigue la regla de sombreado del nombre, de modo que un identificador de la firma incluida que coincida con el de la firma uno nuevo conduce a un error de compilación.

En SML'90 [20] había una subespecie especial de firma - abstraction, y para las firmas ordinarias sólo había una forma de coincidencia - transparente ( S : SS). Cuando se revisó el lenguaje en 1997, esta parte del lenguaje del módulo se simplificó: en lugar de firmas abstractas ,  se introdujo la correspondencia oscura ( opaca ) con la firma ( S :> SS) ( la solución se basa en el cálculo de Harper-Lilybridge translúcido sumas ).

Funtores

Un functor ( functor) es una función sobre estructuras , es decir, una función que toma una estructura como entrada y construye una nueva estructura [22] . A veces, un funtor se ve visualmente como una "estructura parametrizada", es decir, una estructura cuya definición la construye el compilador sobre la base de alguna otra estructura de acuerdo con las reglas especificadas por el programador. Sin embargo, las ortodoxias argumentan que los funtores deberían ser considerados como funciones peculiares [23] .

La firma juega el papel del tipo de parámetro del funtor. Todo tipo de estructuras que se pueden emparejar con esta firma juegan el papel de valores pertenecientes a este tipo y se pasan al funtor para evaluar nuevas estructuras [22] . La estructura que se obtiene como resultado de aplicar el funtor tiene su propia firma (aunque, en general, no puede diferir de la firma del parámetro).

La forma general de la definición de un funtor se ve así:

funtor F ( X : S1 ) : S2 = cuerpo

Ejemplos de uso:

estructura B1 = F ( A1 ) estructura B2 = F ( A2 ) estructura B3 = F ( A3 ) ...

Los funtores le permiten describir de forma segura las formas más diversas de relaciones entre los componentes del programa, resolviendo una amplia gama de problemas de estructuración de código [24] :

  • Implementación de algoritmos genéricos y gestión de dependencias. Los funtores le permiten combinar grandes componentes de comportamiento similar pero diferente implementación en un programa y reemplazarlos según sea necesario. Esto es especialmente útil durante la etapa de prototipado rápido , cuando hay que probar el sistema por partes o simular el comportamiento de forma simplificada (ver, por ejemplo, control numérico y pruebas de estructura ).
  • Expansión automática de funcionalidad. Los funtores lo salvan del trabajo de rutina cuando necesita implementar la misma funcionalidad para diferentes tipos. Por ejemplo, si desea definir conjuntos a partir de elementos de diferentes tipos de datos, en ML basta con definir un funtor que genere una estructura que defina un conjunto, en función de una estructura que defina el tipo de un elemento. En otros lenguajes, este tipo de problema se resuelve mediante programación generativa .
  • Creación de instancias de módulos con estado mutable encapsulado . Si una estructura encapsula un estado mutable y el programa necesita tener varias instancias con estados independientes, entonces los funtores le permiten automatizar la construcción de tales estructuras.

Estas posibilidades se ilustran mejor con ejemplos ilustrativos .

Sin embargo, algunos programadores usan funtores en lugar de estructuras (es decir, describen un funtor y definen una estructura como su única aplicación a un parámetro conocido y, a veces, un funtor con un parámetro vacío). Este enfoque parece exagerado a primera vista, pero en la práctica proporciona dos ventajas que aumentan la productividad de los desarrolladores en proyectos grandes [25] [26] :

  • por un lado, la correcta organización de las interfaces se asegura inmediatamente en la etapa de compilación de un módulo apenas escrito, y no a medida que se desarrolla el proyecto (porque las dependencias de las estructuras entre sí en este caso están controladas por el mecanismo de coincidencia de tipos , y no se detectan durante el montaje)
  • por otro lado, las estructuras se vuelven "más independientes" entre sí, de modo que pueden desarrollarse en cualquier orden, y los programadores de un equipo son libres de trabajar en direcciones exactamente opuestas ( de arriba hacia abajo o de abajo hacia arriba ).

especificación de uso conjunto .

Tipo de equivalencia

Cuando se programa a gran escala , cuando se vinculan módulos para crear otros nuevos y más complejos, surge la pregunta sobre la consistencia de los tipos abstractos exportados desde estos módulos. Para resolver este problema, el lenguaje del módulo ML proporciona un mecanismo especial que le permite indicar explícitamente la identidad de dos o más tipos o estructuras:

firma D = sig estructura A : C estructura B : C compartir tipo A .t = B . t final

Tal especificación impone una restricción sobre el conjunto permitido de estructuras sustituibles, declarando el requisito de que estas deben ser estructuras que comparten ( eng  . share ) el uso de la misma especificación (tipo, firma o estructura). Así, sólo aquellas estructuras son comparables con la firma , en las que el identificador significa el mismo tipo [27] . Por lo tanto, esta especificación se denomina " restricción de compartición ".  Dt

Nota : en la literatura en idioma ruso, la traducción de este término no se ha resuelto. Son posibles variantes como " especificación de uso conjunto " [28] , " restricción de uso compartido ", así como " requisito de separabilidad " o " requisito de uso compartido " de la traducción semántica . Existe [29] la traducción “ restricciones paracompartir ” , que es un error semántico.

Semánticamente, existen dos formas de tal especificación, una para firmas y tipos, otra para estructuras, pero su sintaxis es idéntica. La segunda forma es más restrictiva: dos estructuras pueden ser iguales si y sólo si resultan de evaluar la misma declaración de estructura o aplicar el mismo funtor a argumentos iguales [28] .

La especificación de uso conjunto también se usa para forzar una reducción del rango de tipos permitidos en algún contexto de uso particular de una firma que es "demasiado abstracta", por ejemplo:

funtor Try ( Gr : sig type g sharing type g = int val e : g val bullet : g * g -> g val inv : g -> g end ) = struct val x = Gr . inv ( Gr . viñeta ( 7 , 9 ) ) fin

Aquí, la firma del parámetro del funtor impone un requisito especial sobre la composición de la estructura que realmente se le puede pasar: el tipo abstracto g utilizado debe ser un tipo int. Los casos en los que esto es necesario son bastante comunes, por lo que en SML'97 [30] para simplificar su descripción y la posibilidad de usar firmas nombradas, se agregó una construcción alternativa para la especificación de uso conjunto: where type(en OCaml sintaxis ) : with type

GRUPO de firma = tipo de firma g val e : g val bullet : g * g -> g val inv : g - > g end functor Try ( Gr : GRUPO donde tipo g = int ) = struct val x = Gr . inv ( Gr . viñeta ( 7 , 9 ) ) fin

Ambos diseños tienen sus limitaciones.

sharingle permite expresar la igualdad de tipos sin especificar específicamente su estructura. La construcción puede tener aridad arbitraria :

firma S = sig estructura A : S estructura B : S estructura C : S estructura D : S compartir tipo A .t = B . t = C. _ t = re . t final

pero le permite referirse a tipos abstractos solo directamente, es decir expresión de la forma

compartiendo tipo B .t = A . t * A . t

where typees unario y pretende, por el contrario, instanciar un tipo abstracto por un tipo conocido (pero no permite cambiar la estructura de un tipo que ya ha sido instanciado).

La construcción no es compatible con OCaml , por lo que siempre debe usar el . En el sucesor ML , se supone que implementa una única construcción más universal. sharingwith type

Otro aspecto importante a la hora de establecer la equivalencia de tipos abstractos es la generabilidad de los funtores .

El aprendizaje automático estándar utiliza la semántica generativa de los funtores, lo que significa que cada aplicación de un funtor a la misma estructura genera nuevas definiciones de tipos, es decir, dos tipos del mismo nombre y de estructura idéntica, pertenecientes a estructuras diferentes, no son iguales.

OCaml usa funtores aplicativos, lo que significa que aplicar un funtor a argumentos demostrablemente iguales genera automáticamente el mismo resultado. Esto reduce la necesidad de una especificación de uso conjunto y es especialmente útil cuando se trata de funtores de orden superior. A partir de la versión 4, OCaml agrega la capacidad de hacer que los funtores sean parentales.

Extensiones y dialectos

Functores de orden superior

El funtor recibe una estructura especificada por la firma como entrada. Para pasar varias estructuras, es necesario construir una estructura contenedora adicional que incluya estas estructuras y describa la firma correspondiente. La definición del lenguaje ML estándar por conveniencia proporciona azúcar sintáctico : se pueden pasar varios parámetros como una tupla y el compilador construye automáticamente la estructura envolvente y su firma. Sin embargo, Core ML proporciona funciones de orden superior , y seguir la analogía a nivel de módulo significa introducir una forma curry de functors. De hecho, lo único que debe implementarse en el lenguaje para proporcionar esta capacidad es soporte para describir funtores en firmas [31] [32] . Esta no es una innovación fundamental (a diferencia de los módulos de primera clase ) - no hay nada que los funtores curry permitan, pero los clásicos de primer orden no lo harían - sin embargo, su disponibilidad simplifica significativamente la implementación (y por lo tanto la legibilidad ) de complejos jerarquías de componentes multinivel [32] .

Un ejemplo sorprendente que muestra la conveniencia de usar functores de orden superior es la implementación de combinadores monádicos completos .

El potencial para implementar functores de orden superior ya se señaló en los Comentarios [31] a la Definición de SML'90 [20] . Muchos compiladores de Standard ML proporcionan alguna implementación de funtores de orden superior como una extensión experimental [32] . Ocaml implementa todo tipo de módulos de una manera sintácticamente uniforme, por lo que usar funtores de orden superior es lo más natural.

Nota : en la literatura en idioma ruso hay [33] confusión entre " módulos de orden superior " y " módulos de primera clase " , lo cual es un error semántico.

Funciones orientadas a objetos

El soporte completo para la programación orientada a objetos según Abadi y Cardelli (ver Programación orientada a objetos#Clasificación de subtipos de OOP ) significa soporte al mismo tiempo:

  • relaciones de subtipado
  • objetos
  • tipos de objetos
  • clases (generadores de objetos)

Todo esto ha sido proporcionado por Ocaml durante muchos años . Además, el polimorfismo paramétrico también se extiende a estas características , lo que hace que el lenguaje sea aún más expresivo. Por supuesto, el lenguaje del módulo en OCaml se ha mejorado para permitir que se incluyan objetos y clases en los módulos.

Estas facilidades (posiblemente ampliadas a tipos de orden superior ; ver subtipificación de orden superior ) se convertirán en parte del sucesor ML .

Módulos de primera clase

Problema

Una debilidad del lenguaje del módulo original es que no está cerrado al lenguaje central: los tipos y valores base pueden ser componentes de módulos, pero los módulos no pueden ser componentes de tipos y valores base. En SML, esta separación del lenguaje en dos capas se hizo intencionalmente, ya que simplificó enormemente el mecanismo de verificación de consistencia de tipos [31] . Sin embargo, esto hace que sea imposible vincular dinámicamente los módulos, lo que significa que la siguiente expresión no es válida:

estructura Map = si maxElems < 100 entonces BinTreeMap else HashTableMap (* ¡no permitido en ML clásico! *)

Tal prohibición es una vergüenza para un sistema de módulos tan expresivo, ya que sería completamente normal para cualquier lenguaje orientado a objetos [34] .

De hecho, el lenguaje del módulo ML no necesita ser estático [35] (ver la sección sobre representación de bajo nivel ). El problema radica principalmente en la verificación de tipo estático que es la naturaleza de ML . El soporte en ML para módulos de primera clase per se no es un problema para un lenguaje de módulos de primer orden (que no contiene funtores), pero es la combinación de módulos de primera clase con módulos de orden superior lo que toma el lenguaje "a otra realidad" [36] , es decir, abre enormes posibilidades, pero complica significativamente tanto los mecanismos para derivar y verificar la consistencia de los tipos del lenguaje [37] , como su optimización completa del programa . La idea de módulos de primera clase fue enterrada durante muchos años por Harper y Lilybridge , al construir una versión idealizada del lenguaje de módulos de primera clase utilizando la teoría de tipos dependientes y demostrando que la verificación de consistencia de tipo para este modelo es indecidible [9] [38] . Sin embargo, con el tiempo, comenzaron a aparecer modelos alternativos con otras justificaciones.

Paquetes

A finales del siglo XX, Claudio Russo propuso [39] [40] la forma más sencilla de hacer módulos de primera clase : complementar la lista de tipos primitivos del núcleo del lenguaje con el tipo “ paquete ” ( paquete en inglés  ) , que es un par , y la lista de expresiones del kernel con operaciones de empaquetado y desempaquetado. En otras palabras, solo cambia el núcleo del idioma y el idioma de los módulos permanece sin cambios [41] . структура : сигнатура

El empaquetado de estructuras en paquetes y el posterior desempaquetado le permite vincular dinámicamente diferentes estructuras a identificadores (incluidos los calculados mediante funtores). El ejemplo más simple [42] :

estructura Mapa = desempaquetar ( si maxElems < 100 entonces empaquetar BinTreeMap : MAP de lo contrario empaque HashTableMap : MAP ) : MAP

Al desempaquetar un paquete, la estructura se puede firmar con una firma diferente, incluida la firma más pobre .

La presencia explícita de la firma en el paquete elimina el problema de la inferencia y coincidencia de tipos durante el desempaquetado dinámico de la estructura. Esto refuta la tesis temprana de Harper-Mitchell sobre la imposibilidad de elevar las estructuras en ML a niveles de primera clase sin sacrificar la separación de las fases de compilación y ejecución y la decidibilidad del sistema de verificación de consistencia de tipo [41] , ya que en lugar de primero- tipos dependientes de orden , una extensión de la teoría de los tipos existenciales se utiliza como justificación de segundo orden Mitchell-Plotkin [43] .

De esta forma, se implementan módulos de primera clase en Alice y en Ocaml , a partir de la 4ª versión.

1ML

Inspirado en la conversión F , Rossberg incrusta el módulo boxing-unboxing más profundamente en la semántica del lenguaje, lo que da como resultado un lenguaje monolítico en el que los funtores, las funciones e incluso los constructores de tipos son realmente la misma construcción primitiva, y no se hace ninguna distinción. hecho entre registros , tuplas y estructuras - la representación interna del lenguaje es un Sistema F ω plano . Esto dio una gran cantidad de resultados positivos [44] :

  • probar la confiabilidad del lenguaje se vuelve mucho más simple que tradicionalmente para el lenguaje de módulos (no se requiere el uso de la teoría de tipos dependientes );
  • se proporciona soporte para tipos "materializados" ( ing.  cosificados ) en el núcleo del lenguaje, proporcionando al lenguaje poder expresivo al nivel de sistemas con tipos dependientes (y nuevamente sin requerir su presencia en la metateoría);
  • el lenguaje en su conjunto resulta ser más expresivo (le permite describir sistemas complejos con mayor capacidad y precisión) y más simple (más minimalista y más uniforme en su composición).

El lenguaje se denominó " 1ML ", lo que refleja tanto el soporte de módulos verdaderamente de primera clase como la unificación de primitivas y módulos en un solo lenguaje (no dividido en dos capas) [44] .

La decisión se basó en la idea de Harper-Mitchell de subdividir los tipos en "pequeños" y "grandes". Rossberg aplicó esta distinción a la regla de inclusión de consistencia de tipo (coincidencia de estructura a firma subyacente), lo que la hace resoluble .

Presumiblemente, un mayor desarrollo de 1ML también puede proporcionar suficiente expresividad para admitir muchos modelos interesantes, cuya implementación se consideraba difícil anteriormente: clases de tipos , funtores aplicativos , módulos recursivos, etc. En particular, la introducción del polimorfismo en línea en 1ML probablemente permitirá de inmediato expresar la subtipificación en amplitud , lo que mantendrá la metateoría simple mientras expande significativamente sus capacidades. [45]

MixML

MixML [10] es un lenguaje de módulos creado mediante la combinación del lenguaje de módulos ML clásico de McQueen y la formalización del modelo de complementos de Bracha & Cook .  Los autores de MixML son Rossberg y Dreyer.

La idea básica de MixML es simple: las estructuras y las firmas se combinan en un solo concepto de módulo, combinando definiciones y especificaciones, tanto transparentes como abstractas.

Esto hace posible definir gráficos de dependencia arbitrarios en los programas, incluidos los cíclicos. En particular, esto le permite incorporar funtores no solo para la parametrización directa (dependencia de la salida de la entrada), sino también recursiva (dependencia de la entrada de la salida), mientras mantiene el soporte para la compilación separada (a diferencia de muchos modelos privados que amplían el lenguaje del módulo ML con soporte para recursividad).

MixML implementa una sola notación unificada para modelos semánticos tradicionalmente emparejados (para estructuras y firmas por separado) y una gran cantidad de mecanismos separados del lenguaje clásico de los módulos ML, tales como:

  • herencia (inclusión) de firmas
  • especificaciones de uso conjunto
  • dos formas de firma (transparente y oscura)
  • aplicaciones de funtores

Varios

Las siguientes extensiones también están disponibles en varios modelos:

  • módulos locales
  • muchas opciones para el sistema recursivo de módulos que le permiten formar gráficos de dependencia cíclica, el más expresivo de los cuales es el sistema MixML (la mayoría de los otros no brindan la posibilidad de compilación separada)
  • soporte de anidamiento de módulo extendido
  • notación generalizada para estructuras de apertura
  • varias opciones para limitar el uso
  • firmas anidadas, incluidas las abstractas
  • declaraciones de operadores infijos que especifican la asociatividad y la precedencia dentro de las firmas y requieren una coincidencia exacta

Ecosistema lingüístico

Implementaciones y dialectos

Alicia

El lenguaje Alice es una extensión de Standard ML , que incluye muchas de las ideas del proyecto sucesor de ML , así como herramientas de programación competitivas avanzadas para desarrollar aplicaciones distribuidas , soporte para escritura dinámica fuerte y un solucionador de restricciones . Diseñado por Andreas Rossberg.

El lenguaje de los módulos en Alice se extiende a la notación de componentes ( eng.  components ), que implementan módulos de primera clase en forma de paquetes Russo y además admiten escritura dinámica (pero de acuerdo con las mismas reglas de semántica estática) y carga diferida (es decir, se admiten estructuras futuras y firmas futuras; consulte la llamada futura ) [46] [47] . La derivación de tipos se respeta en Alice , y la especificación de uso conjunto debe usarse cuando sea necesario . Un ejemplo ilustrativo de la utilidad práctica de los paquetes viene con Alice : una biblioteca de serialización de datos que permite que los subprocesos intercambien tipos y datos dinámicos.

Además, Alice proporciona azúcar sintáctico : la capacidad de usar paréntesis libremente en las expresiones del lenguaje del módulo, incluso en lugar de los tradicionales "corchetes" struct...endy sig...end:

val p = paquete ( val x = longitud ) : ( val x : 'una lista -> int ) (* val p : paquete = paquete{|...|} *) OCaml

En Ocaml , la sintaxis del lenguaje del módulo es uniforme:

módulo tipo S = (* firma *) sig ... módulo M : T (* estructura anidada *) fin módulo X : S = (* estructura *) estructura ... fin módulo F ( X : S ) = (* estructura parametrizada (functor) *) struct ... fin módulo G ( X : S ) ( Y : T ) = (* estructura parametrizada curry (funtor de orden superior) *) estructura ... fin

Sin embargo, hay una serie de diferencias en la semántica [48] .

Comenzando con la versión 4, Ocaml soporta módulos de primera clase en una notación similar a los paquetes de Alice . La sintaxis sigue siendo homogénea, es decir, parece indistinguible de las estructuras anidadas en las firmas.

Desde sus inicios, Ocaml ha ido ampliando el lenguaje de módulos con clases y objetos .

Las diferencias más importantes entre Standard ML y Ocaml aparecen en la semántica de equivalencia de tipo (ver la sección sobre equivalencia de tipo ).

Gestión de módulos

Para enlazar programas gigantes ML, en principio se pueden usar enlazadores tradicionales para la mayoría de los lenguajes , como make . Sin embargo, el lenguaje de módulos SML es mucho más poderoso que las herramientas de modularización de otros lenguajes [2] , y make no soporta sus ventajas, y más aún no es adecuado para el análisis global del flujo de control de programas [49] . Por lo tanto, diferentes compiladores ofrecen sus propios sistemas de gestión de módulos: Compilation Manager (CM) en SML/NJ y MLBasis System (MLB) en MLton . SML.NET [50] tiene un sistema de seguimiento de dependencia incorporado. MLton también incluye un convertidor de archivos .cm a .mlb .

La mayoría de las implementaciones usan compilación separada, lo que resulta en tiempos de compilación rápidos. Para soportar la compilación separada en modo REPL , se usa una función useque compila el archivo especificado e importa las definiciones. Algunos compiladores (como MLton ) no son compatibles con REPL y, por lo tanto, no implementan la compatibilidad con use. Otros (por ejemplo, Alice ), por el contrario, implementan características adicionales de compilación dinámica y carga de módulos durante la ejecución del programa. Poly/ML [51] proporciona una función PolyML.ifunctorque le permite depurar la implementación de un funtor de forma interactiva pieza por pieza.

Ejemplos de programas

A pesar de su simplicidad, el lenguaje del módulo es notablemente flexible y proporciona un alto nivel de reutilización de código , como se ilustra en los siguientes ejemplos.

Gestión del número de dígitos

Los tipos de datos tradicionales , como enteros ( inty word), reales ( real), caracteres ( chary widechar), cadenas ( stringy widestring), matrices ( vectory array) y otros, se implementan en dialectos de ML, no en forma de tipos primitivos y operadores integrados sobre ellos, como en la mayoría de los lenguajes, pero en forma de tipos de datos abstractos y funciones correspondientes incluidas en las firmas, respectivamente, INTEGER, WORD, REAL, CHAR, STRINGetc., proporcionadas en forma de bibliotecas estándar. Las implementaciones de lenguajes concretos pueden proporcionar representaciones muy eficientes de estos tipos abstractos (por ejemplo, MLton representa matrices y cadenas de la misma manera que lo hace el lenguaje C ).

Por ejemplo:

firma INTEGER = sig eqtype int val toLarge : int -> LargeInt . int val fromLarge : LargeInt . int -> int val toInt : int -> Int . int val fromInt : Int . int -> int val precision : Int . int opción val minInt : int opción val maxInt : int opción val ˜ : int -> int val * : ( int * int ) -> int val div : ( int * int ) -> int val mod : ( int * int ) - > int val quot : ( int * int ) -> int val rem : ( int * int ) -> int val + : ( int * int ) -> int val - : ( int * int ) -> int val compare : ( int * int ) -> order val > : ( int * int ) -> bool val > = : ( int * int ) -> bool val < : ( int * int ) -> bool val < = : ( int * int ) -> bool val abs : int -> int val min : ( int * int ) -> int val max : ( int * int ) -> int val sign : int -> Int . int val sameSign : ( int * int ) -> bool val fmt : StringCvt . radix -> int -> string val toString : int -> string val fromString : string -> int option val scan : StringCvt . raíz -> ( char , 'a ) StringCvt . lector -> 'a -> ( int * 'a ) opción final

Las estructuras , , , y muchas otras INTEGERse pueden comparar con la firma . Del mismo modo, las estructuras / y / (y posiblemente otras) se pueden combinar con firmas / y para cada variante los funtores generarán una pila de E/S adecuada ( , ). Int8Int16Int32Int64IntInfCHARSTRINGCharStringWideCharWideStringStreamIOTextIO

Al mismo tiempo, algunas estructuras ocultan la representación tradicional de la máquina bajo la definición abstracta (por ejemplo, Int32, Int64), otras, campos de bits (por ejemplo, Int1), y la estructura IntInfimplementa aritmética larga . Al mismo tiempo, las bibliotecas pueden atravesar intensamente relaciones de muchos a muchos : la especificación SML Basis define un conjunto de módulos obligatorios y opcionales construidos sobre la implementación de tipos "primitivos": arreglos monomórficos, sus segmentos que no se copian, etc. . Incluso los tipos "cadena" ( ) y "subcadena" ( ) se definen en la especificación SML Basis como y (o y para ). Así, para usar los mismos algoritmos con números de distinta capacidad, basta con pasar explícitamente la estructura correspondiente al functor (abrir no cambiará las estructuras ya calculadas). stringsubstringChar.char vectorChar.char VectorSlice.sliceWideChar.char vectorWideChar.char VectorSlice.sliceWideString

Diferentes compiladores proporcionan diferentes conjuntos de estructuras implementadas. MLton ofrece la variedad más completa : de Int1a Int32inclusive y Int64, el mismo conjunto para Word(enteros sin signo), así como IntInf(implementado por GNU Multi-Precision Library ) y muchos más , como Int32Array, y más. PackWord32BigPackWord32Little

En la mayoría de las implementaciones, por defecto, en el nivel superior (en el entorno global), una estructura Int32(o Int64) está abierta, es decir, usar un tipo inty una operación +por defecto significa usar un tipo Int32.inty una operación Int32.+(o, respectivamente, Int64.inty Int64.+). Además, se proporcionan identificadores Inty LargeInt, que por defecto están vinculados a determinadas estructuras (por ejemplo, LargeIntnormalmente igual a IntInf). Diferentes compiladores, dependiendo de su orientación, pueden usar diferentes enlaces en el entorno global por defecto, y tal sutileza puede afectar la portabilidad de los programas entre compiladores. Por ejemplo, una constante Int.maxIntcontiene el valor del entero más grande posible, envuelto en un tipo opcional , y debe recuperarse mediante coincidencia de patrones o mediante una llamada de función valOf. Para los tipos de dimensión finita, el valor es y ambos métodos de extracción son equivalentes. Pero es igual , por lo que acceder al contenido directamente a través de lanzará una excepción . Por defecto , está abierto en el compilador Poly/ML [51] , ya que se centra en problemas de trituración de números . IntN.maxIntSOME(m)IntInf.maxIntNONEvalOf OptionIntInf

Conjuntos abstractos

Las bibliotecas OCaml incluyen un módulo que proporciona un functor . Con él, puede crear fácilmente un conjunto basado en un tipo de elemento dado: SetMake

módulo Int_set = Conjunto . Make ( tipo de estructura t = int let compare = compare end )

El módulo de conjunto de enteros generado tiene el siguiente compilador - firma inferida :

módulo Int_set : sig tipo elt = int tipo t val vacío : t val is_empty : t -> bool val mem : elt -> t -> bool val add : elt -> t -> t val singleton : elt -> t val remove : elt -> t -> t val union : t -> t -> t val inter : t -> t -> t val diff : t -> t -> t val compare : t -> t -> int val equal : t -> t -> valor bool subconjunto : t -> t -> valor bool iter : ( elt -> unidad ) -> t -> valor unidad fold : ( elt -> ' a -> ' a ) -> t -> ' a -> ' a val for_all : ( elt -> bool ) -> t -> bool val existe : ( elt -> bool ) -> t -> bool val filter : ( elt -> bool ) -> t -> t val partición : ( elt -> bool ) -> t -> t * t val cardinal : t -> int val elementos : t -> elt list val min_elt : t -> elt val max_elt : t -> elt val elegir : t -> elt val dividir : elt -> t -> t * bool * t val encontrar : elt -> t -> elt end

Se incluye una funcionalidad similar en las bibliotecas del compilador SML/NJ ( ListSetFn). SML Basis proporciona solo herramientas elementales.

El propósito principal de usar un módulo dependiente en lugar de una estructura simple aquí es que la función de comparación se especifica una vez , y todas las funciones en un conjunto con tipo particular usan la misma función de comparación en el tipo de los elementos de este conjunto, de modo que el programador está así protegido de sus propios errores. Los conjuntos abstractos podrían implementarse pasando cada función sobre el conjunto una función de comparación cada vez (como se hace, por ejemplo, en una función estándar del lenguaje C qsort - ver polimorfismo paramétrico en C y C ++ ), sin embargo, esto no sería solo aumentaría la complejidad de trabajar con conjuntos, pero también conllevaría el riesgo de confundir la función de comparación requerida al introducir un error difícil de detectar en el programa (ver duplicación de código ).

Desafortunadamente [24] , históricamente, OCaml ha adoptado una firma para la función de comparación que indica el valor de retorno de un tipo de dos vías ( booleano ) (y se deben observar las convenciones de este tipo para poder usar ampliamente los módulos de biblioteca) . Más poderosa es la solución SML Basis (así como Haskell Prelude ) basada en un tipo de tres vías:

orden de tipo de datos = MENOS | IGUAL | MAYOR QUE comparación de valores : int * int -> orden

Pruebas estructurales

Con el prototipado rápido , a menudo es necesario probar el sistema por partes o simular el comportamiento de forma simplificada (implementar los llamados "stubs"). Los funtores manejan esta tarea con gracia.

Por ejemplo, digamos que hay tres implementaciones diferentes de alguna estructura de datos , digamos una cola [52] :

firma COLA = tipo de firma 'a t excepción E val vacío : 'a t val enq : 'a t * 'a -> 'a t val null : 'a t -> bool val hd : 'a t -> 'a val deq : 'a t -> 'a t fin estructura Cola1 :> COLA = estructura ... fin estructura Cola2 :> COLA = estructura ... fin estructura Cola3 :> COLA = estructura ... fin

En muchos idiomas, por falta de abstracción , sería necesario crear programas separados de copiar y pegar para compararlos . Los funtores, por otro lado, le permiten abstraer la prueba de la implementación e iterar sobre ellos en un solo programa:

functor TestQueue ( Q : QUEUE ) = struct fun fromList I = foldl ( fn ( x , q ) => Q . enq ( q , x )) Q . vacío I fun toList q = if Q . null q luego [] else Q . hd q :: toList ( Q . deq q ) end val ns = hasta ( 1 , 10000 ) (* val ns = [1, 2, 3, 4, ...] : lista int *) estructura TQ1 = TestQueue ( Cola1 ) val q1 = TQ1 . fromList ns val l1 = TQ1 . toList q1 l1 = ns (* verdadero: bool *) ... estructura TQ2 = TestQueue ( Cola2 ) estructura TQ3 = TestQueue ( Cola3 ) ...

Luego puede elegir entre búsqueda primero en amplitud y búsqueda primero en profundidad para cada implementación, todo en un solo programa:

funtor BreadthFirst ( Q : QUEUE ) = struct ... fin functor DepthFirst ( Q : QUEUE ) = struct ... end estructura BF_Q1 = BreadthFirst ( Cola1 ) estructura BF_Q2 = BreadthFirst ( Cola2 ) estructura BF_Q3 = BreadthFirst ( Cola3 ) estructura DF_Q1 = DeepFirst ( Queue1 ) estructura DF_Q2 = DeepthFirst ( Queue2 ) estructura DF_Q3 = DeepthFirst ( Queue3 ) ...

En el futuro, no es necesario eliminar las implementaciones "adicionales". Además, los compiladores de optimización total como MLton los eliminarán por sí solos; consulte la eliminación de código inactivo .

Este método también se puede usar para medir la eficiencia, pero en la práctica es mucho más conveniente (y más confiable) medirla usando un generador de perfiles integrado en el compilador.

La seguridad de tipo global de dependencias entre componentes que proporciona el lenguaje del módulo es visible en el ejemplo de un intento erróneo de usar un functor:

estructura Incorrecta = AnchoPrimero ( Lista ); (* > Error: especificación de tipo no coincidente: t > Error: especificación de excepción no coincidente: E > Error: especificación de valor no coincidente: vacío > Error: especificación de valor no coincidente: enq > Error: especificación de valor no coincidente: deq *)

Mónadas y clases de tipos

Haskell , que es descendiente de ML , no es compatible con el lenguaje del módulo ML . En cambio, brinda soporte para la programación a gran escala (además del sistema trivial de módulos similares a los que se usan en la mayoría de los lenguajes) a través de mónadas y clases de tipos . Los primeros expresan un comportamiento abstracto, incluido el modelado de estados mutables en términos de transparencia referencial ; estos últimos sirven como un medio para controlar la cuantificación de variables de tipo mediante la implementación de polimorfismo ad-hoc . El lenguaje del módulo ML permite implementar ambos lenguajes [53] [11] .

Una clase de tipo no es más que una interfaz que describe un conjunto de operaciones cuyo tipo viene dado por una variable de tipo abstracto independiente llamada parámetro de clase. Por lo tanto, una representación natural de una clase en términos del lenguaje del módulo será una firma que, además del conjunto requerido de operaciones, también incluye una especificación de tipo (que representa un parámetro de clase) [11] :

firma EQ = sig tipo t val eq : t * t -> bool end

La mónada se implementa mediante la firma:

firma MONAD = sig type 'a monad val ret : 'a -> 'a monad val bnd : 'a monad -> ( 'a -> 'b monad ) -> 'b monad end

Ejemplos de su uso:

Opción de estructura : MONAD = struct type 'a monad = 'a option fun ret x = ALGUNOS x fun bnd ( ALGUNOS x ) k = k x | bnd NINGUNO k = NINGUNO fin firma REF = sig tipo 'a ref val ref : 'a -> 'a ref IO . mónada val ! : 'a referencia -> 'a IO . monad val : = : 'a ref -> 'a -> unidad IO . final de la mónada

Los combinadores monádicos completos son especialmente convenientes para implementar utilizando funtores de orden superior [32] [53] :

(*Primer orden*) firma MONOID = tipo de firma t val e : t val plus : t * t -> t end functor Prod ( M : MONOID ) ( N : MONOID ) = tipo de estructura t = M . t * norte . t val e = ( M . e , N . e ) fun plus (( x1 , y1 ), ( x2 , y2 )) = ( M . plus ( x1 , x2 ), N . plus ( y1 , y2 )) end funtor Cuadrado ( M : MONOID ) : MONOID = Prod M M estructura Plano = Cuadrado ( tipo t = real val e = 0.0 val plus = Real . + ) val x = Plano . más ( Plano . e , ( 7.4 , 5.4 )) (*orden superior*) firma PROD = MONOIDE -> MONOIDE -> MONOIDE functor Cuadrado ( M : MONOID ) ( Prod : PROD ) : MONOID = Prod M M estructura T = Cuadrado Plano Prod val x = T . más ( T.e , T.e ) _ _ _ _ (*Transparentemente*) firma PROD' = fct M : MONOID -> fct N : MONOID -> MONOID donde escriba t = M . t * norte . t funtor Square' ( M : MONOID ) ( Prod : PROD' ) : MONOID = Prod M M estructura T' = Cuadrado' Plano Prod val x = T' . más ( T' . e , (( 7.4 , 5.4 ), ( 3.0 , 1.7 )))

Valores indexados por tipos

Valores indexados por tipos es un modismo común a todos los primeros lenguajes de la familia ML , diseñado para implementar polimorfismo ad-hoc ( sobrecarga de funciones ) a través de polimorfismo paramétrico [54] . Las clases de tipo , introducidas por primera vez en Haskell , son compatibles con los valores indexados por tipo a nivel de idioma (y como tales, se implementan fácilmente en el módulo de idioma ).

En su forma más simple, este modismo se demuestra en el siguiente ejemplo de OCaml [55] :

tipo de módulo Arith = tipo de signo t val (+) : t -> t -> t val neg : t -> t val cero : t end módulo Build_type ( M : Arith ) = struct let typ x = { Tipo . más = METRO . (+); neg = M._ _ (-); cero = METRO . cero ; } fin let int = let módulo Z = Build_type ( Int ) en Z. _ typ let int64 = let módulo Z = Build_type ( Int64 ) en Z. _ typ let int32 = let módulo Z = Build_type ( Int32 ) en Z. _ typ let native = let module Z = Build_type ( Native_int ) en Z . typ let float = let module Z = Build_type ( Float ) en Z . typ let complejo = let módulo Z = Build_type ( Complex ) en Z . escribe

Modelo de objetos

Usando el lenguaje del módulo, puede construir un modelo de objeto simple con despacho dinámico. Este ejemplo es interesante dado que SML no proporciona ninguna función de programación orientada a objetos y no admite subtipos .

El modelo de objeto dinámicamente despachable más simple se puede construir fácilmente en SML a través de . Un tipo de entrada que incluye valores de función desempeña el papel de una clase abstracta que define la firma del método. El ámbito léxico de ML proporciona ocultar el estado interno y los métodos privados de estos objetos ; por lo tanto, los cierres (funciones ML) pueden desempeñar el papel de constructores de objetos de esta clase. Tal implementación no permite construir jerarquías de herencia multinivel complejas (esto requiere implementar subtipos, lo que se hace a través de una implementación compleja de valores indexados por tipos y para los cuales existen varios métodos diferentes), pero en la práctica es suficiente para la mayoría de las tareas con un buen diseño [12] . La derivación de dicho modelo de objeto al nivel de módulo se considera a continuación.

Los flujos de datos más simples se utilizan como base:

firma ABSTRACT_STREAM = sig type 'a t val isEmpty : 'a t -> bool val push : 'a * 'a t -> 'a t val pop : 'a t -> ( 'a * 'a t ) option end firma STREAM = sig include ABSTRACT_STREAM val vacío : ' al final pila de estructura :> STREAM = tipo de estructura 'a t = 'una lista val vacío = [] val isEmpty = nulo val push = op :: val pop = List . fin de getItem cola de estructura :> FLUJO = tipo de datos de estructura 'a t = T de 'una lista * 'una lista val vacío = T ([], []) val isEmpty = fn T ([], _) => verdadero | _ => false val normalize = fn ([], ys ) => ( rev ys , []) | q => q fun push ( y , T ( xs , ys )) = T ( normalizar ( xs , y::ys )) val pop = fn ( T ( x::xs , ys )) => ALGUNOS ( x , T ( normalizar ( xs , ys ))) | _ => NINGUNO fin

Usando functors, puede implementar algoritmos generalizados que manipulan flujos de datos de un dispositivo interno desconocido y propósito:

funtor StreamAlgs ( ST : ABSTRACT_STREAM ) = estructura abierta ST fun pushAll ( xs , d ) = doblar empujar d xs fun popAll d = let fun lp ( xs , NONE ) = rev xs | lp ( xs , ALGUNOS ( x , d )) = lp ( x::xs , pop d ) in lp ([], pop d ) fin fun cp ( desde , hasta ) = pushAll ( popAll desde , hasta ) end

Instanciar este funtor con estructuras comparables a la firma ABSTRACT_STREAMproduce funciones que manipulan los flujos de datos correspondientes:

estructura S = StreamAlgs ( pila ) estructura Q = StreamAlgs ( cola ) S._ _ popAll ( S . pushAll ([ 1 , 2 , 3 , 4 ], Stack . vacío )) (* resultado: [4,3,2,1] *) P._ _ popAll ( Q . pushAll ([ 1 , 2 , 3 , 4 ], Queue . vacío )) (* resultado: [1,2,3,4] *)

Cabe señalar que el funtor StreamAlgstoma un parámetro de firma ABSTRACT_STREAM, y ​​las estructuras Stacky Queuese firmaron con la firma STREAMenriqueciendo la firma . Esto implica una sutileza: al desarrollar, es deseable seguir las convenciones adoptadas en la biblioteca estándar de un dialecto en particular para hacer un uso más amplio de los desarrollos existentes, especialmente los funtores estándar (no hay tantos en SML Basis' 2004, pero en las extensiones de algunos compiladores y en OCaml hay ejemplos muy interesantes). ABSTRACT_STREAM

Las estructuras derivadas contienen la definición ST.tde tipo del parámetro funtor, pero son tipos diferentes : cada definición de tipo en ML genera un nuevo tipo. Por lo tanto, un intento de mezclarlos da como resultado un error de coherencia de tipo . Por ejemplo, el compilador rechazará la siguiente línea:

valor q = Q . empujar ( 1 , Pila . vacía )

La interfaz de clase de hilo se define convenientemente como . Por motivos de seguridad de tipo , es preferible no utilizar un alias de tipo, sino una función de constructor que asigne dicha entrada a un objeto de clase:

estructura Corriente = struct tipo de datos 'a t = I of { isEmpty : unit -> bool , push : 'a -> 'a t , pop : unit -> ( 'a * 'a t ) option } fun O m ( I t ) = m t fun isEmpty t = O #isEmpty t () fun push ( v , t ) = O #push t v fun pop t = O #pop t () fin

El módulo Streamrealmente implementa la firma ABSTRACT_STREAM( ), pero la firma explícita se pospone hasta más adelante.

Para convertir un módulo de subproceso en una clase de subproceso, debe agregarle dos constructores con nombre , lo que se puede hacer con un functor y la construcción de apertura :

functor StreamClass ( D : STREAM ) : STREAM = struct open Stream divertido hacer d = I { isEmpty = fn () => D . isEmpty d , push = fn x => make ( D . push ( x , d )), pop = fn () => case D . pop d de NINGUNO => NINGUNO | ALGUNOS ( x , d ) => ALGUNOS ( x , hacer d ) } val vacío = I { isEmpty = fn () => verdadero , empujar = fn x => hacer ( D . empujar ( x , D . vacío )), pop = fn () => NINGUNO } fin

La estructura generada por el funtor StreamClassincluye todos los componentes de la estructura Stream(incluido el constructor I ), pero no son visibles desde el exterior, ya que el resultado del funtor está firmado por la firma STREAM.

Finalmente, puede sellar el módulo Stream:

estructura Flujo : ABSTRACT_STREAM = Flujo

Esto no es necesario desde el punto de vista de la seguridad del tipo , ya que el módulo Streamno permite romper el encapsulado como estaba. Sin embargo, la ocultación del constructor I proporciona una garantía de que solo el funtor StreamClassse puede usar para crear subclases ABSTRACT_STREAM.

Casos de uso obvios:

estructura StackClass = StreamClass ( pila ) estructura QueueClass = StreamClass ( cola )

Pero eso no es todo. Dado que el funtor definido anteriormente StreamAlgstoma una estructura de tipo como entrada ABSTRACT_STREAM, puede ser instanciado por una estructura Streamque implementa la clase de flujo abstracto:

estructura D = StreamAlgs ( Flujo )

Un módulo derivado D, como un módulo Stream, funciona con cualquier clase que herede de ABSTRACT_STREAM, lo que se puede considerar como un despacho dinámico:

D._ _ popAll ( D . pushAll ([ 1 , 2 , 3 , 4 ], StackClass . vacío )) (* resultado: [4,3,2,1] *) D._ _ popAll ( D . pushAll ([ 1 , 2 , 3 , 4 ], QueueClass . vacío )) (* resultado: [1,2,3,4] *)

Es interesante notar que ni Stream, ni Dcontiene no solo estado mutable , sino también constantes, solo tipos y funciones; sin embargo, al pasar a través del mecanismo de parámetros, la clase abstracta se usa aquí como un valor de primera clase , y no solo una entidad virtual, como en muchos lenguajes orientados a objetos.

Sobre el idioma

Representación y eficiencia de bajo nivel

Tradicionalmente, las estructuras se representan en el compilador por medio de registros , y los funtores se representan mediante funciones sobre dichos registros [35] . Sin embargo, existen representaciones internas alternativas, como la semántica de Harper-Stone y 1ML .

Usar funtores como medio para descomponer un proyecto grande significa ralentizar el acceso a los componentes finales de los programas calculados a través de ellos, y para cada nivel de anidamiento, las pérdidas se multiplican, al igual que cuando se usan funciones ordinarias en lugar de valores inmediatos. Los compiladores de optimización total ( MLton , MLKit [56] , SML.NET [50] ) amplían el marco del módulo y crean las definiciones finales de los componentes del funtor teniendo en cuenta las características de las estructuras realmente pasadas, lo que elimina la penalización del rendimiento. MLKit también usa la expansión de módulos para inferir regiones, lo que permite usar el lenguaje para desarrollar aplicaciones en tiempo real . En este caso, la divulgación del marco de los módulos se puede llevar a cabo mediante varias estrategias: por ejemplo, MLton realiza la " desfunción del programa " y MLKit realiza la " interpretación estática del lenguaje del módulo ". Hay una implementación de un defuntorizador opcional para OCaml [57] .

Justificación de la semántica

Durante muchos años, el lenguaje del módulo ML se consideró en el nivel de teoría de tipos como una aplicación de la teoría de tipos dependientes , y esto permitió finalizar el lenguaje y examinar cuidadosamente sus propiedades. En realidad, los módulos (incluso en un rol de primera clase ) no son " verdaderamente dependientes ": la firma de un módulo puede depender de los tipos contenidos en otro módulo, pero no de los valores contenidos en él [3 ] .

Detalles Correspondencia Mitchell-Plotkin Fuertes sumas de McQueen

[58]

Sumas translúcidas de Harper-Lilybridge

Robert Harper y Mark Lillibridge construyeron [9] [59] el cálculo translúcido de sumas para justificar formalmente el lenguaje de los módulos de primera clase de orden superior .  Este cálculo se usa en la semántica de Harper-Stone . Además, sus elementos se han convertido en parte de la Definición SML revisada (SML'97).

Semántica de Harper-Stone

La semántica de Harper-Stone ( semántica HS para abreviar ) es una interpretación de SML en un marco tipado .  Este último incluye un sistema de módulos basado en sumas translúcidas de Harper-Lilybridge (ver arriba). La interpretación es teóricamente elegante, pero mantiene la falsa impresión de que los módulos ML son difíciles de implementar: utiliza tipos singleton , tipos dependientes y un sistema complejo de efectos [3] .

Transformada F de Rossberg-Rousseau-Dreyer

Andreas Rossberg, Claudio Russo y Derek Dreyer han demostrado conjuntamente que la creencia popular sobre un umbral de entrada irrazonablemente alto para un módulo de lenguaje es falsa. Construyeron una transformación del lenguaje de los módulos en un Sistema F ω plano ( cálculo lambda de segundo orden), mostrando así que el lenguaje de los módulos en sí mismo es realmente solo un caso especial ( azúcar sintáctico ) del uso del Sistema F ω . En este sentido, la principal ventaja de utilizar módulos frente a trabajar directamente en el Sistema F ω es un grado significativo de automatización de muchas acciones complejas (coincidencia de firmas teniendo en cuenta el enriquecimiento, empaquetado/desempaquetado implícito de existenciales , etc.).

" F-ing semantics " ( Semántica F-ing ), o F-transformación, admite la inclusión de functores de orden superior y módulos de primera clase en forma de paquetes de Rousseau. La prueba de la fiabilidad de la transformada F ha sido mecanizada mediante el método "localmente sin nombre" ( Locally Nameless ) en Coq . Los autores resumieron el trabajo realizado como extremadamente doloroso y no recomiendan utilizar este método en el futuro [3] . Los resultados logrados inspiraron aún más a Rossberg para crear 1ML .

Crítica y comparación con alternativas

El lenguaje de módulos ML es el sistema de módulos más desarrollado en lenguajes de programación [2] y sigue evolucionando. Proporciona control sobre jerarquías de espacios de nombres (a través de ) , interfaces detalladas (a través de firmas ), abstracción del lado del cliente (a través de functors ) y del lado del implementador (a través de tipeo ) [ 3 ] .

La mayoría de los lenguajes no tienen nada comparable a los funtores [52] . El análogo más cercano a los funtores son las plantillas de clase de C++ posteriores , pero los funtores son mucho más fáciles de usar [60] porque las plantillas de C++ no solo no tienen seguridad de tipos , sino que también tienen otras desventajas [61] . Algunos lenguajes proporcionan subsistemas de macros que permiten la generación automática de código y la gestión flexible de las dependencias en tiempo de compilación ( Lisp , C ), pero a menudo estos subsistemas de macros son un complemento no verificable del lenguaje principal, lo que permite la reescritura arbitraria de una línea de programa. by-line, lo que puede generar muchos problemas [62] . Recién en el siglo XXI se desarrollaron macro-subsistemas con seguridad de tipos ( Template Haskell , Nemerle ), algunos de los cuales están disponibles simultáneamente con funtores (MetaML [63] , MetaOCaml ).

Lo mejor de los funtores es que se pueden compilar y verificar el tipo incluso si no hay una estructura en el programa que se les pueda pasar como un parámetro real [64] . Al hacerlo, los funtores describen la interacción a nivel de interfaces en lugar de implementaciones , lo que permite romper las dependencias en tiempo de compilación. Esto generalmente se produce a expensas de cierta degradación del rendimiento, pero los métodos de optimización de programa completo resuelven con éxito este problema .

El lenguaje de los módulos a menudo se percibe como difícil de entender, la razón por la cual radica en las matemáticas complejas requeridas para justificarlo. Simon Peyton-Jones comparó los funtores con un automóvil Porsche por su " gran potencia pero mala relación calidad-precio " [65] . Los defensores de ML no están de acuerdo con este punto de vista, argumentando que el lenguaje del módulo no es más difícil de usar/implementar/comprender que las clases de tipos de Haskell o el sistema de clases de Java con genéricos y comodines [ , y es realmente una cuestión de preferencia subjetiva [3] .

Si el compilador detecta errores en las definiciones de los módulos, los mensajes de error de salida pueden ser muy largos, lo que en el caso de los funtores, especialmente de orden superior, puede causar inconvenientes particulares. Por lo tanto, un bloque de definiciones de tipos y funciones por encima de ellos debe formatearse como un módulo solo después de que se haya desarrollado en partes (para lo cual se proporciona el modo REPL en la mayoría de las implementaciones ). Algunas implementaciones (por ejemplo , Poly/ML [51] ) proporcionan sus propias extensiones para resolver este problema. Otros (por ejemplo, SML2c), por el contrario, solo permiten compilar programas a nivel de módulo.

Historia, filosofía, terminología

La idea del lenguaje del módulo es que la semántica a gran escala de los programas debe repetir la semántica del núcleo ML ( ing.  Core ML ), es decir, las dependencias entre los componentes grandes del programa se formulan como dependencias de un pequeño nivel. En consecuencia, las estructuras son "valores" del nivel del módulo ( valores de nivel de módulo en inglés  ); Las firmas (también denominadas " tipos de módulo " o " tipos de módulo ") caracterizan los "tipos" de valores de nivel de módulo , mientras que los funtores caracterizan las "funciones" del nivel de módulo. La analogía, sin embargo, no es idéntica: tanto el contenido de los módulos como las relaciones entre módulos pueden ser más complejas que en el núcleo del lenguaje. Las complicaciones más significativas en este sentido son la inclusión de subestructuras en firmas y la restricción sobre el uso conjunto de [4] . En los comentarios [31] sobre la definición de SML'90, se señaló la implementación potencial de functores de orden superior (analogías con funciones de orden superior ), pero sus implementaciones aparecieron más tarde .

El lenguaje del módulo fue propuesto originalmente por David MacQueen [66 ] .  En el futuro, muchos científicos hicieron la contribución más significativa a la justificación de la teoría de tipos y la expansión del lenguaje de los módulos. El trabajo incluye la formalización de módulos recursivos , y de primera clase , así como la revisión repetida de su justificación para simplificar tanto el modelo en sí como su metateoría de apoyo y probar su fiabilidad. El desarrollo del lenguaje del módulo se cruza estrechamente con el desarrollo del ML central y está marcado por docenas de trabajos de muchos científicos, pero se pueden distinguir los siguientes hitos clave:

  • 1984 - McQueen - idea inicial [66] .
  • 1990 - Milner, Harper, McQueen, Tofty - un modelo separado del núcleo del lenguaje como parte de la Definición, prueba de su confiabilidad a través del llamado sellado de tipo generativo [20] .
  • 1994 - Appel, McQueen - compilación separada [6] .
  • 1995 - Leroy - simplificación de la metateoría a tipos transparentes (no generadores), funtores aplicativos [67] .
  • 1994 - Harper, Lilybridge - Fundamento teórico de tipos con tipos dependientes [9] .
  • 1999-2000 - Rousseau - simplificación de la metateoría al segundo orden, módulos de primera clase en forma de paquetes [39] [40] .
  • 2000 - Semántica de Harper-Stone .
  • 2010 - Rossberg, Rousseau, Dreyer - simplificación de la metateoría a un Sistema F plano , mecanización de la prueba de su confiabilidad en Coq [3] .
  • 2015 - Rossberg - 1ML , un único modelo con el núcleo del lenguaje [34] .

Otro dialecto de ML, el lenguaje Caml , originalmente admitía el lenguaje del módulo con una serie de diferencias . Posteriormente, se convirtió en el lenguaje Objective Caml , que complementó el lenguaje del módulo con un subsistema de programación orientado a objetos que desarrolló orgánicamente las ideas del lenguaje del módulo . OCaml continuó evolucionando continuamente y, a mediados de la década de 2010, su lenguaje de módulos se complementó con una serie de características experimentales. Las implementaciones individuales de SML admiten algunas de estas características como extensiones. de primera clase , que también son compatibles con el lenguaje Alice .

Aplicación

En varios idiomas

La semántica del lenguaje del módulo es completamente independiente del hecho de que ML es un lenguaje estricto : también se puede usar en lenguajes perezosos [68] . Además, se han propuesto implementaciones privadas del lenguaje del módulo sobre los núcleos de lenguajes semánticamente diferentes (por ejemplo, Prolog y Signal ).

Crecimiento paramétrico de lenguajes

En 2000, Xavier Leroy (desarrollador de OCaml ) propuso una implementación de un modelo generativo generalizado que le permite construir el lenguaje del módulo ML sobre el núcleo de un lenguaje arbitrario (en un rango bastante amplio) con su propio sistema de tipos ( por ejemplo, C ) [1] . Este modelo se implementa a través del propio lenguaje del módulo, en forma de un funtor , parametrizado por datos sobre el núcleo del lenguaje y una descripción de su mecanismo de verificación de consistencia de tipos .

Módulos como base para el núcleo del lenguaje

Después de tres décadas de evolución del lenguaje de módulos como complemento al núcleo del lenguaje, en 2015 Andreas Rossberg (el desarrollador de Alice ) propuso en lugar de la construcción tradicional del lenguaje de módulos sobre el lenguaje central, para usar el lenguaje del módulo como un lenguaje intermedio para representar las construcciones del lenguaje central. Esto hace que los módulos sean realmente valores de primera clase (que no requieren empaquetado en paquetes); consulte 1ML .

Notas

  1. ↑ 12 Leroy, "Sistema de módulos modulares", 2000 .
  2. ↑ 1 2 3 Cardelli, "Programación tipificada", 1991 , 2. Lenguajes tipificados, p. 5.
  3. ↑ 1 2 3 4 5 6 7 8 Rossberg, Russo, Dreyer, "Módulos F-ing", 2010 .
  4. ↑ 1 2 Harper, "Programación en SML", 2011 .
  5. ↑ 1 2 3 Dreyer, "Evolución del sistema de módulos ML", 2005 .
  6. ↑ 1 2 Appel, MacQueen, "Compilación separada para ML estándar", 1994 .
  7. ↑ Harper, "Introducción a SML", 1986 , p. cincuenta.
  8. ↑ Paulson, "ML for the Working Programmer", 1996 , 7.4 La firma prevista para las colas, p. 264.
  9. ↑ 1 2 3 4 Harper, Lillibridge, "Enfoque teórico de tipos para módulos de orden superior con uso compartido", 1994 .
  10. ↑ 1 2 Dreyer, Rossberg, "MixML", 2008 .
  11. ↑ 1 2 3 Dreyer, Harper, "Clases de tipo modular", 2007 .
  12. ↑ 1 2 Programación orientada a objetos en ML estándar
  13. ↑ Paulson, "ML for the Working Programmer", 1996 , 2.22 Signatures, p. 62.
  14. ↑ Paulson, "ML for the Working Programmer", 1996 , 2.19 Introducción a los módulos, p. 59.
  15. ↑ Paulson, "ML for the Working Programmer", 1996 , 7.5 Restricciones de firma, p. 264.
  16. ↑ Pucella, "Notas sobre programación SML/NJ", 2001 , p. 58.
  17. ↑ Harper, "Introducción a SML", 1986 , p. 13
  18. ↑ 1 2 Paulson, "ML para el programador que trabaja", 1996 , 7.14 La opendeclaración, p. 299-305.
  19. ↑ Harper, "Introducción a SML", 1986 , p. 36.
  20. ↑ 1 2 3 4 La definición de SML, 1990 .
  21. ↑ Appel, "A Critique of Standard ML", 1992 , abierto en firmas, p. 17
  22. ↑ 1 2 Paulson, "ML for the Working Programmer", 1996 , Guía de referencia de módulos, p. 309.
  23. ↑ Combinación de objetos: funtores y tiempo de ejecución frente a tiempo de compilación
  24. ↑ 1 2 Minsky traducido por DMK, 2014 , Capítulo 9. Funtores.
  25. ↑ Harper, "Introducción a SML", 1986 , p. 75-76.
  26. ↑ Paulson, "ML for the Working Programmer", 1996 , 7.13 Programación completamente funcional, p. 294.
  27. ↑ Harper, "Introducción a SML", 1986 , p. 77.
  28. ↑ 1 2 Harper, "Introducción a SML", 1986 , p. 77-78.
  29. ↑ Minsky traducido por DMK, 2014 .
  30. ↑ La definición de SML: revisada, 1997 .
  31. ↑ 1 2 3 4 Comentario sobre SML, 1991 .
  32. ↑ 1 2 3 4 HOF en SML/NJ .
  33. ↑ Minsky traducido por DMK, 2014 , p. 235.
  34. ↑ 1 2 Rossberg, "1ML - Núcleo y módulos unidos", 2015 .
  35. ↑ 1 2 Frisch, Garrigue, "Módulos de primera clase en OCaml", 2010 .
  36. ↑ Rossberg - Funtores y tiempo de ejecución vs tiempo de compilación .
  37. ↑ Neis, Dreyer, Rossberg, "Parametricidad no paramétrica", 2009 , p. 1-2.
  38. ↑ Rossberg, "1ML - Core and Modules United", 2015 , p. 2.
  39. ↑ 1 2 Russo, "Tipos no dependientes para módulos", 1999 .
  40. ↑ 1 2 Russo, "Estructuras de primera clase", 2000 .
  41. ↑ 1 2 Russo, "Estructuras de primera clase", 2000 , p. 17
  42. ↑ Alice-Paquetes .
  43. ↑ Russo, "Estructuras de primera clase", 2000 , p. catorce.
  44. ↑ 1 2 Rossberg, "1ML - Core and Modules United", 2015 , p. 3.
  45. ↑ Rossberg, "1ML - Core and Modules United", 2015 , p. 13
  46. ↑ Rossberg, "Componentes dinámicos", 2006 .
  47. ↑ Alice-ExtModules .
  48. ↑ SML vs. OCaml .
  49. ↑ MLBase
  50. ↑ 1 2 compilador SML.NET
  51. ↑ 1 2 3 Página del compilador Poly/ML
  52. ↑ 1 2 Paulson, "ML for the Working Programmer", 1996 , 7.8 Probando las estructuras de la cola, p. 274.
  53. ↑ 1 2 Harper, "¡Por supuesto que ML tiene mónadas!" .
  54. ↑ Valores indexados por tipo
  55. ↑ Yaron Minsky - Una guía para programadores activos sobre valores indexados por tipo
  56. ↑ Comiler de MLKit (enlace descendente) . Consultado el 21 de enero de 2015. Archivado desde el original el 7 de enero de 2016. 
  57. ↑ Desfunctorizador para OCaml .
  58. ↑ MacQueen, "Tipos dependientes para expresar módulos", 1986 .
  59. ↑ Reynolds, "Teorías de los lenguajes de programación", 1998 , 18. Especificación del módulo, p. 398-410.
  60. ↑ Vanden Berghe .
  61. ↑ K. Czarnecki, J. O'Donnell, J. Striegnitz, W. Taha. Implementación de DSL en metaocaml, plantilla haskell y C++ . — Universidad de Waterloo, Universidad de Glasgow, Centro de Investigación Julich, Universidad de Rice, 2004. Archivado desde el original el 5 de marzo de 2016.
  62. ↑ Appel, "A Critique of Standard ML", 1992 , Falta de macros, p. 9.
  63. ↑ Steven E. Ganz, Amr Sabry, Walid Taha . Macros como cálculos de varias etapas: macros de tipo seguro, generativas y vinculantes en MacroML . - Conferencia internacional sobre programación funcional, ACM Press, 2001. Archivado desde el original el 23 de septiembre de 2015.
  64. ↑ Tofte, "Fundamentos de los módulos SML", 1996 .
  65. ↑ Simón Peyton Jones . Vistiendo el cilicio: una retrospectiva de Haskell. — POPL, 2003.
  66. ↑ 1 2 MacQueen, "Módulos para ML estándar", 1984 .
  67. ↑ Xavier Leroy, "Funtores aplicativos", 1995 .
  68. ↑ Tofte, "Fundamentos de los módulos SML", 1996 , p. una.

Literatura

Tutoriales, guías, libros de referencia, uso

Lenguaje de aprendizaje automático estándar
  • Robert Harper . Introducción al ML Estándar (indefinido). - Universidad Carnegie Mellon, 1986. - ISBN PA 15213-3891.
    • Traducción al ruso:
      Robert Harper. Introducción al ML estándar  (neopr.) . - Universidad Carnegie Mellon, 1986. - 97 p. — ISBN PA 15213-3891.
  • Lawrence C. Paulson. ML para el Programador de Trabajo  (neopr.) . — 2do. - Cambridge, Gran Bretaña: Cambridge University Press, 1996. - 492 p. - ISBN 0-521-57050-6 (tapa dura), 0-521-56543-X (tapa blanda).
lenguaje OCaml
  • Minsky, Madhavapeddy, Hickey. Real World OCaml: Programación funcional para las masas  (indefinido) . - O'Reilly Media, 2013. - 510 p. — ISBN 9781449324766 .
    • Traducción al ruso:
      Minsky, Madhavapeddy, Hickey. Programación en el lenguaje OCaml  (neopr.) . - DMK, 2014. - 536 p. — (Programación funcional). - ISBN 978-5-97060-102-0 .
Idioma del módulo
  • El lenguaje del módulo . (Capítulo de la versión en línea de Développement d'applications avec Objective Caml de Emmanuel Chailloux, Pascal Manoury y Bruno Pagano)

Historia, análisis, crítica

  • David McQueen. Módulos para Standard ML  (neopr.) . - LFP'84 Actas del Simposio ACM de 1984 sobre LISP y programación funcional, 1984. - P. 198-207. - ISBN 0-89791-142-3 . -doi : 10.1145/ 800055.802036 .
  • Robin Milner , Mads Tofte, Robert Harper. La definición de ML estándar  (neopr.) . - The MIT Press, 1990. - ISBN 0-262-63181-4 .
  • Luca Cardelli . Programación tipificada( (inglés)) // Informes de Estado del Arte IFIP. - Nueva York: Springer-Verlag, 1991. -vol. Descripción formal de los conceptos de programación. —S. 431–507.
  • Claudio Ruso. Tipos no dependientes para módulos (  ( inglés) ) // Principios y práctica de la programación declarativa. — Principios y práctica de la programación declarativa, 1999.
  • Javier Leroy. A Modular Module System (  (inglés) ) // vol.10, número 3. - Journal of Functional Programming, 2000. - S. 269-303 .
  • Andreas Rossberg, Claudio Russo, Derek Dreyer. Módulos F-ing (  (Inglés) ). —TLDI, 2010.

Enlaces