ML (lenguaje de programación)

ML (Metalenguaje) es un lenguaje de programación funcional de propósito general. Es conocido por su uso del sistema de tipos polimórficos Hindley-Milner, que asigna automáticamente los tipos de la mayoría de las expresiones sin requerir anotaciones de tipos explícitas y garantiza la seguridad de tipos: existe una prueba formal de que un programa ML bien tipificado no causa tiempo de ejecución. errores de tipo. ML proporciona coincidencia de patrones para argumentos de función, recolección de basura, programación imperativa, llamada por valor y curry. Se usa mucho en la investigación de lenguajes de programación y es uno de los pocos lenguajes que se especifica y verifica completamente usando semántica formal. Sus tipos y la coincidencia de patrones lo hacen adecuado y se usa comúnmente para operar en otros lenguajes formales, como en la escritura de compiladores, la demostración automatizada de teoremas y la verificación formal.

Resumen

Las características de ML incluyen una estrategia de evaluación llamada por valor, funciones de primera clase, administración automática de memoria a través de la recolección de elementos no utilizados, polimorfismo paramétrico, escritura estática, inferencia de tipos, tipos de datos algebraicos, coincidencia de patrones y manejo de excepciones. ML usa reglas de alcance estáticas.

ML puede denominarse un lenguaje funcional impuro, porque aunque fomenta la programación funcional, permite efectos secundarios (como lenguajes como Lisp, pero a diferencia de un lenguaje puramente funcional como Haskell). Como la mayoría de los lenguajes de programación, ML utiliza una evaluación entusiasta, lo que significa que todas las subexpresiones siempre se evalúan, aunque la evaluación perezosa se puede lograr mediante el uso de cierres. Así uno puede crear y usar flujos infinitos como en Haskell, pero su expresión es indirecta.

Las fortalezas de ML se aplican principalmente en el diseño y la manipulación del lenguaje (compiladores, analizadores, probadores de teoremas), pero es un lenguaje de propósito general que también se usa en bioinformática y sistemas financieros.

ML fue desarrollado por Robin Milner y otros a principios de la década de 1970 en la Universidad de Edimburgo, y su sintaxis está inspirada en ISWIM. Históricamente, ML se concibió para desarrollar tácticas de prueba en el probador de teoremas LCF (cuyo lenguaje, pplambda, una combinación del cálculo de predicados de primer orden y el cálculo lambda polimórfico de tipo simple, tenía ML como su metalenguaje).

Hoy en día hay varios idiomas en la familia ML; los tres más destacados son Standard ML (SML), OCaml y F#. Las ideas de ML han influido en muchos otros lenguajes, como Haskell, Cyclone, Nemerle, ATS y Elm.

Ejemplos

Los siguientes ejemplos usan la sintaxis de Standard ML. Otros dialectos de ML como OCaml y F# difieren en aspectos menores.

Factoriales

La función factorial expresada como ML pura:

diversión fac ()0 : int) : int = 1 Silencio fac ()n : int) : int = n * fac ()n - 1)

Esto describe el factorial como una función recursiva, con un único caso base de terminación. Es similar a las descripciones de factoriales que se encuentran en los libros de texto de matemáticas. Gran parte del código ML es similar a las matemáticas en cuanto a facilidad y sintaxis.

Parte de la definición que se muestra es opcional y describe los tipos de esta función. La notación E: t se puede leer como la expresión E tiene tipo t. Por ejemplo, al argumento n se le asigna el tipo entero (int), y fac (n: int), el resultado de aplicar fac al entero n, también tiene el tipo entero. La función fac como un todo tiene entonces el tipo función de entero a entero (int -> int), es decir, fac acepta un entero como argumento y devuelve un resultado entero. Gracias a la inferencia de tipos, las anotaciones de tipo se pueden omitir y el compilador las derivará. Reescrito sin las anotaciones de tipo, el ejemplo se ve así:

diversión fac 0 = 1 Silencio fac n = n * fac ()n - 1)

La función también se basa en la coincidencia de patrones, una parte importante de la programación ML. Tenga en cuenta que los parámetros de una función no están necesariamente entre paréntesis sino separados por espacios. Cuando el argumento de la función es 0 (cero), devolverá el número entero 1 (uno). Para todos los demás casos, se intenta la segunda línea. Esta es la recursión, y ejecuta la función nuevamente hasta que se alcanza el caso base.

No se garantiza que esta implementación de la función factorial termine, ya que un argumento negativo provoca una cadena descendente infinita de llamadas recursivas. Una implementación más robusta verificaría si hay un argumento no negativo antes de recurrir, de la siguiente manera:

diversión hecho n = Deja diversión fac 0 = 1 Silencio fac n = n * fac ()n - 1) dentro si ()n . 0) entonces aumento Dominio más fac n final

El caso problemático (cuando n es negativo) demuestra un uso del sistema de excepciones de ML.

La función se puede mejorar aún más escribiendo su ciclo interno como una llamada final, de modo que la pila de llamadas no necesite crecer en proporción al número de llamadas a la función. Esto se logra agregando un parámetro adicional, acumulador, a la función interna. Por fin llegamos a

diversión hecho n = Deja diversión fac 0 acc = acc Silencio fac n acc = fac ()n - 1) ()n * acc) dentro si ()n . 0) entonces aumento Dominio más fac n 1 final

Lista inversa

La siguiente función invierte los elementos de una lista. Más precisamente, devuelve una nueva lista cuyos elementos están en orden inverso en comparación con la lista dada.

diversión inversión [] = [] Silencio inversión ()x :: xs) = ()inversión xs) @ [x]

Esta implementación de reverse, aunque correcta y clara, es ineficiente y requiere un tiempo cuadrático para su ejecución. La función se puede reescribir para que se ejecute en tiempo lineal:

diversión 'a inversión xs : 'a lista = Lista.plegable ()operaciones ::) [] xs

Esta función es un ejemplo de polimorfismo paramétrico. Es decir, puede consumir listas cuyos elementos tengan cualquier tipo y devolver listas del mismo tipo.

Módulos

Los módulos son el sistema de ML para estructurar grandes proyectos y bibliotecas. Un módulo consta de un archivo de firma y uno o más archivos de estructura. El archivo de firma especifica la API que se implementará (como un archivo de encabezado C o un archivo de interfaz Java). La estructura implementa la firma (como un archivo fuente C o un archivo de clase Java). Por ejemplo, lo siguiente define una firma aritmética y una implementación de la misma utilizando números racionales:

firma ARITH =Sig Tipo t val cero : t val succ : t - t val suma : t * t - tfinal

estructura Racional : ARITH =struct datatype t = Rat de int * int val cero = Rat ()0, 1) diversión succ ()Rat ()a, b) = Rat ()a + b, b) diversión suma ()Rat ()a, b), Rat ()c, d) = Rat ()a * d + c * b , b * d)final

Estos son importados al intérprete por el 'uso' dominio. La interacción con la implementación solo se permite a través de las funciones de firma, por ejemplo, no es posible crear una 'Rata' objeto de datos directamente a través de este código. La 'estructura' El bloque oculta todos los detalles de implementación desde el exterior.

Las bibliotecas estándar de ML se implementan como módulos de esta manera.