ML (linguagem de programação)

Da Wikipédia, a enciclopédia livre
Ir para navegação Pular para pesquisar
ML
ParadigmaMulti-paradigma : funcional , imperativo
Projetado porRobin Milner e outros da Universidade de Edimburgo
Apareceu pela primeira vez1973 ; 48 anos atrás ( 1973 )
Disciplina de digitaçãoInferido , 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 pelo uso do 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. [1] 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 . [ citação necessária ]

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 , [2] e sua sintaxe é inspirada pelo 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 predicados 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 , [3] ATS e Elm . [4]

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 uma 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:

diversão  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:

 fato  divertido n  =  deixe 
  divertido  fac  0  =  1 
    |  fac  n  =  n  *  fac  ( n  -  1 ) 
  em 
    if  ( n  <  0 )  então  aumente  Domínio  senão  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

 fato  divertido n  =  deixe 
  divertido  fac  0  acc  =  acc 
    |  fac  n  acc  =  fac  ( n  -  1 )  ( n  *  acc ) 
  em 
    if  ( n  <  0 )  então  aumente  Domínio  else  fac  n  1 
  end

Lista inversa

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.

 reverso  divertido []  =  [] 
  |  reverso  ( x  ::  xs )  =  ( reverso  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 :

divertido  'um  reverso  xs  :  ' uma  lista  =  Lista . 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:

assinatura  ARITH  = 
sig 
        tipo  t 
        val  zero  :  t 
        val  succ  :  t  ->  t 
        val  soma  :  t  *  t  ->  t 
fim
estrutura  Racional  :  ARITH  = 
tipo de dados de estrutura 
        t = Rato de int * int val zero = Rato ( 0 , 1 ) succ divertido ( Rato ( a , b )) = Rato ( a + b , b ) soma divertida ( Rato ( a , b) ), Rato ( c , d ))       
             
                  
                =  Rato  ( a  *  d  +  c  *  b  ,  b  *  d ) 
final

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

  1. ^ Robin Milner. Uma teoria do polimorfismo de tipo em programação. Journal of Computer and System Sciences, 17 (3): 348-375, 1978.
  2. ^ Gordon, Michael JC (1996). “Do LCF ao HOL: uma breve história” . Página visitada em 2007-10-11 .
  3. ^ Linguagem de programação para "forças especiais" de desenvolvedores , Russian Software Development Network: Nemerle Project Team , recuperado em 24 de janeiro de 2021
  4. ^ Tate, Bruce A .; Daoud, Fred; Dees, Ian; Moffitt, Jack (2014). "3. Elm". Sete Mais Línguas em Sete Semanas (Versão do livro: P1.0-novembro 2014 ed.). The Pragmatic Programmers, LLC. pp. 97, 101. ISBN 978-1-941222-15-7. Na página 101, o criador do Elm, Evan Czaplicki, diz: 'Tenho a tendência de dizer' Elm é uma língua da família ML 'para obter a herança compartilhada de todas essas línguas.' ["esses idiomas" se refere a Haskell, OCaml, SML e F #.]
  5. ^ "OCaml é uma linguagem de programação de força industrial que suporta estilos funcionais, imperativos e orientados a objetos" . Obtido em 2 de janeiro de 2018.

Outras leituras

Ligações externas