ML ( Meta Language ) es un lenguaje de programación funcional , de alto nivel y de propósito general . Es conocido por su uso del sistema de tipos polimórfico Hindley-Milner , que asigna automáticamente los tipos de datos de la mayoría de las expresiones sin requerir anotaciones de tipo explícitas ( inferencia de tipos ) y garantiza la seguridad de los tipos; Existe una prueba formal de que un programa ML bien escrito no causa errores de tipo en tiempo de ejecución. [1] ML proporciona coincidencia de patrones para argumentos de funciones, recolección de basura , programación imperativa , llamada por valor y curry . Si bien es un lenguaje de programación de propósito general , ML 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 mediante semántica formal . Sus tipos y coincidencia de patrones lo hacen muy adecuado y comúnmente utilizado para operar en otros lenguajes formales, como en la escritura de compiladores , la demostración automatizada de teoremas y la verificación formal .
Las características de ML incluyen una estrategia de evaluación de llamada por valor , funciones de primera clase , administración automática de memoria mediante recolección de basura, polimorfismo paramétrico , escritura estática , inferencia de tipos , tipos de datos algebraicos , coincidencia de patrones y manejo de excepciones . ML utiliza reglas de alcance estáticas . [2]
Se puede hacer referencia al ML como un lenguaje funcional impuro , porque aunque fomenta la programación funcional, permite efectos secundarios [3] (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 se puede lograr una evaluación diferida mediante el uso de cierres . Por tanto, se pueden crear y utilizar infinitas corrientes como en Haskell, pero su expresión es indirecta.
Las fortalezas de ML se aplican principalmente en el diseño y manipulación de lenguajes (compiladores, analizadores, demostradores de teoremas), pero es un lenguaje de propósito general que también se utiliza 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 , [4] y su sintaxis está inspirada en ISWIM . Históricamente, ML fue concebido para desarrollar tácticas de demostración en el demostrador del teorema 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 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 , [5] ATS y Elm . [6]
Los siguientes ejemplos utilizan la sintaxis de Standard ML. Otros dialectos de ML, como OCaml y F#, difieren en pequeños aspectos.
La función factorial expresada como ML pura:
dato curioso ( 0 : int ) : int = 1 | fac ( n : int ) : int = n * fac ( n - 1 )Esto describe el factorial como una función recursiva, con un único caso base terminal. 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 que la expresión E tiene tipo t . Por ejemplo, al argumento n se le asigna un tipo entero (int), y fac (n : int), el resultado de aplicar fac al número entero n, también tiene un tipo entero. La función fac en su conjunto tiene entonces un tipo de función de entero a entero (int -> int), es decir, fac acepta un número 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 tiene el siguiente aspecto:
dato curioso 0 = 1 | 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 prueba la segunda línea. Esta es la recursividad y ejecuta la función nuevamente hasta alcanzar 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 sólida buscaría un argumento no negativo antes de recurrir, de la siguiente manera:
dato curioso n = let dato curioso 0 = 1 | fac n = n * fac ( n - 1 ) en si ( n < 0 ) entonces aumenta el dominio en caso contrario fac n end El caso problemático (cuando n es negativo) demuestra el uso del sistema de excepciones de ML.
La función se puede mejorar aún más escribiendo su bucle 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
dato curioso n = let fun fac 0 acc = acc | fac n acc = fac ( n - 1 ) ( n * acc ) in if ( n < 0 ) luego aumentar Dominio else fac n 1 finalLa 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.
divertido reverso [] = [] | revertir ( x :: xs ) = ( revertir xs ) @ [ x ]Esta implementación de la inversión, si bien es correcta y clara, es ineficiente y requiere un tiempo cuadrático para su ejecución. La función se puede reescribir para ejecutarse en tiempo lineal :
divertido 'un xs inverso : 'una lista = Lista . foldl ( op :: ) [] xs Esta función es un ejemplo de polimorfismo paramétrico. Es decir, puede consumir listas cuyos elementos sean de cualquier tipo y devolver listas del mismo tipo.
Los módulos son el sistema de ML para estructurar bibliotecas y proyectos grandes. 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 -> t finalestructura Racional : ARITH = estructura tipo de datos t = Rat of int * int val zero = Rat ( 0 , 1 ) fun succ ( Rat ( a , b )) = Rat ( a + b , b ) fun sum ( Rat ( a , b ), Rata ( c , d )) = Rata ( a * d + c * b , b * d ) finEstos se importan al intérprete mediante el comando 'usar'. La interacción con la implementación solo se permite a través de las funciones de firma; por ejemplo, no es posible crear un objeto de datos 'Rat' directamente a través de este código. El bloque 'estructura' oculta todos los detalles de implementación desde el exterior.
Las bibliotecas estándar de ML se implementan como módulos de esta manera.
En la página 101, el creador de Elm, Evan Czaplicki, dice: "Tiendo a decir "Elm es un lenguaje de la familia ML" para llegar a la herencia compartida de todos estos lenguajes". ["estos lenguajes" se refiere a Haskell, OCaml, SML y F#.]