ML (linguagem de programação) - ML (programming language)

ML
Paradigma Multi-paradigma : funcional , imperativo
Projetado por Robin Milner e outros da Universidade de Edimburgo
Apareceu pela primeira vez 1973 ; 48 anos atrás ( 1973 )
Disciplina de digitação Inferido , estático , forte
Dialetos
OCaml , ML padrão , F #
Influenciado por
EU NADO
Influenciado
Clojure , Coq , Cyclone , C ++ , Elm , F # , F * , Haskell , Idris , Kotlin , Miranda , Nemerle , OCaml , Opa , Erlang , Rust , Scala , Standard ML

ML ( Meta Language ) é uma linguagem de programação funcional de propósito geral . É conhecido por usar o sistema de tipo polimórfico Hindley-Milner , que atribui automaticamente os tipos da maioria das expressões sem exigir anotações de tipo explícitas e garante a segurança do tipo - há uma prova formal de que um programa de ML bem tipado não causa tempo de execução erros de tipo. O ML fornece correspondência de padrões para argumentos de função, coleta de lixo , programação imperativa , chamada por valor e currying . É muito usado na pesquisa de linguagens de programação e é uma das poucas linguagens a ser completamente especificada e verificada usando semântica formal . Seus tipos e correspondência de padrões o tornam adequado e comumente usado para operar em outras linguagens formais, como na escrita do compilador , prova automatizada de teoremas e verificação formal .

Visão geral

Os recursos do ML incluem uma estratégia de avaliação de chamada por valor , funções de primeira classe , gerenciamento automático de memória por meio de coleta de lixo, polimorfismo paramétrico , tipagem estática , inferência de tipo , tipos de dados algébricos , correspondência de padrões e tratamento de exceções . ML usa regras de escopo estáticas .

ML pode ser referido como uma linguagem funcional impura , porque embora encoraje a programação funcional, ela permite efeitos colaterais (como linguagens como Lisp , mas ao contrário de uma linguagem puramente funcional como Haskell ). Como a maioria das linguagens de programação, o ML usa avaliação rápida , o que significa que todas as subexpressões são sempre avaliadas, embora a avaliação preguiçosa possa ser alcançada com o uso de fechamentos . Assim, pode-se criar e usar fluxos infinitos como em Haskell, mas sua expressão é indireta.

Os pontos fortes do ML são principalmente aplicados no design e manipulação de linguagem (compiladores, analisadores, provadores de teoremas), mas é uma linguagem de propósito geral também usada em bioinformática e sistemas financeiros.

ML foi desenvolvido por Robin Milner e outros no início dos anos 1970 na Universidade de Edimburgo , e sua sintaxe é inspirada em ISWIM . Historicamente, ML foi concebido para desenvolver táticas de prova no provador de teoremas LCF (cuja linguagem, pplambda , uma combinação do cálculo de predicado de primeira ordem e o cálculo lambda polimórfico de tipo simples , tinha ML como sua metalinguagem).

Hoje, existem vários idiomas na família ML; os três mais proeminentes são Standard ML (SML), OCaml e F # . As ideias do ML influenciaram várias outras linguagens, como Haskell, Cyclone , Nemerle , ATS e Elm .

Exemplos

Os exemplos a seguir usam a sintaxe do ML padrão. Outros dialetos ML, como OCaml e F #, diferem em pequenas maneiras.

Fatorial

A função fatorial expressa como ML puro:

fun fac (0 : int) : int = 1
  | fac (n : int) : int = n * fac (n - 1)

Isso descreve o fatorial como uma função recursiva, com um único caso base de terminação. É semelhante às descrições de fatoriais encontradas em livros didáticos de matemática. Muito do código de ML é semelhante à matemática em termos de facilidade e sintaxe.

Parte da definição mostrada é opcional e descreve os tipos desta função. A notação E: t pode ser lida como a expressão E tem tipo t . Por exemplo, ao argumento n é atribuído o tipo inteiro (int), e fac (n: int), o resultado da aplicação de fac ao inteiro n, também tem o tipo inteiro. A função fac como um todo tem então função de tipo de inteiro para inteiro (int -> int), ou seja, fac aceita um inteiro como argumento e retorna um resultado inteiro. Graças à inferência de tipo, as anotações de tipo podem ser omitidas e serão derivadas pelo compilador. Reescrito sem as anotações de tipo, o exemplo se parece com:

fun fac 0 = 1
  | fac n = n * fac (n - 1)

A função também depende do casamento de padrões, uma parte importante da programação de ML. Observe que os parâmetros de uma função não estão necessariamente entre parênteses, mas separados por espaços. Quando o argumento da função for 0 (zero) ela retornará o inteiro 1 (um). Para todos os outros casos, a segunda linha é tentada. Esta é a recursão e executa a função novamente até que o caso base seja alcançado.

Esta implementação da função fatorial não tem garantia de término, uma vez que um argumento negativo causa uma cadeia descendente infinita de chamadas recursivas. Uma implementação mais robusta verificaria se há um argumento não negativo antes de recorrer, da seguinte maneira:

fun fact n = let
  fun fac 0 = 1
    | fac n = n * fac (n - 1)
  in
    if (n < 0) then raise Domain else fac n
  end

O caso problemático (quando n é negativo) demonstra o uso do sistema de exceção do ML.

A função pode ser melhorada ainda mais escrevendo seu loop interno como uma chamada final , de forma que a pilha de chamadas não precise crescer em proporção ao número de chamadas de função. Isso é obtido adicionando um parâmetro extra, acumulador , à função interna. Por fim, chegamos a

fun fact n = let
  fun fac 0 acc = acc
    | fac n acc = fac (n - 1) (n * acc)
  in
    if (n < 0) then raise Domain else fac n 1
  end

Lista reversa

A função a seguir inverte os elementos em uma lista. Mais precisamente, ele retorna uma nova lista cujos elementos estão na ordem inversa em relação à lista fornecida.

fun reverse [] = []
  | reverse (x :: xs) = (reverse xs) @ [x]

Essa implementação de reverso, embora correta e clara, é ineficiente, exigindo tempo quadrático para execução. A função pode ser reescrita para executar em tempo linear :

fun 'a reverse xs : 'a list = List.foldl (op ::) [] xs

Notavelmente, esta função é um exemplo de polimorfismo paramétrico. Ou seja, pode consumir listas cujos elementos são de qualquer tipo e retornar listas do mesmo tipo.

Módulos

Módulos são o sistema do ML para estruturação de grandes projetos e bibliotecas. Um módulo consiste em um arquivo de assinatura e um ou mais arquivos de estrutura. O arquivo de assinatura especifica a API a ser implementada (como um arquivo de cabeçalho C ou arquivo de interface Java ). A estrutura implementa a assinatura (como um arquivo de origem C ou arquivo de classe Java). Por exemplo, o seguinte define uma assinatura aritmética e uma implementação dela usando números racionais:

signature ARITH =
sig
        type t
        val zero : t
        val succ : t -> t
        val sum : t * t -> t
end
structure Rational : ARITH =
struct
        datatype t = Rat of int * int
        val zero = Rat (0, 1)
        fun succ (Rat (a, b)) = Rat (a + b, b)
        fun sum (Rat (a, b), Rat (c, d)) = Rat (a * d + c * b , b * d)
end

Eles são importados para o interpretador pelo comando 'use'. A interação com a implementação só é permitida por meio das funções de assinatura, por exemplo, não é possível criar um objeto de dados 'Rato' diretamente por meio deste código. O bloco 'estrutura' esconde todos os detalhes de implementação de fora.

As bibliotecas padrão do ML são implementadas como módulos desta forma.

Veja também

Referências

Leitura adicional

links externos