Standard ML é a definição padrão (standard, duh) de ML, uma família de linguagens de programação funcional impura. O representante mais expressivo dessa família é a linguagem francesa OCaml, e uma linguagem prima é Haskell, um parente funcional puro.

A implementação de Standard ML que recomendo é a da Princeton University, SML/NJ.

Gostaria de, antes de tudo, pedir desculpas pelos códigos que passarei aqui,pois Standard ML é uma linguagem que não domino, então alguns conceitos podem estar errados. Se quiser me enviar erratas, comente abaixo.

Linguagem funcional pura vs impura

Para uma linguagem ser considerada funcional pura, ela precisa respeitar algumas constraints:

• O algoritmo deve ser baseado em chamadas de função, que recebem parâmetros e retornam valores. O estado do programa não muda, apenas os dados são reconstruídos através do encadeamento de funções.
• As funções devem ser “avaliadas” (não achei palavra melhor) sob demanda, de modo não-estrito.
• As funções devem ser idempotentes, seja, dado determinado(s) parâmetro(s), ela deve invariavelmente retornar sempre o mesmo resultado.
• Não pode haver mudança de estado: uma vez um valor vinculado a um slot, não pode ser mudado. Neste sentido, a palavra “variável” não representa bem o slot. Pessoalmente prefiro incógnita.
• Assim, loops são resolvidos com recursão. Para que a recursão não estoure a pilha de instâncias de função, como ocorre em algumas linguagens imperativas, a máquina virtual ou interpretador precisa implementar Tail-call optimisation.

Se a linguagem funcional não atende a todas as constraints – ou atendeparcialmente – ela é considerada impura.

A família ML é impura porque usa um recurso de linguagens imperativas: amudança de estado. Assim uma variável do tipo referência (a' ref) pode ter seu valor alterado. Havendo mudança de estado, uma função pode não ser idempotente.

Por exemplo:

- val x = ref 0;
val x = ref 0 : int ref
- x := !x + 1;
val it = () : unit
- !x;
val it = 1 : int

A variável x foi criada como uma referência a uma posição de memória que guarda um inteiro, onde foi colocado o valor zero (0).

Na avaliação seguinte, o conteúdo da posição de memória referenciada por x foi incrementado. É possível ver na última avaliação que aquela posição de memória agora guarda o valor 1.

As linguagens da família ML também suportam que uma variável sejaassociada a outro valor.

Gerador de inteiros

Vamos então ao código!!! 😃

Vamos criar um gerador de números inteiros e uma função que use este geradorpara gerar uma lista de números inteiros.

As assinaturas de nossas funções serão:

val xrange : (int * int) -> unit -> int option
val range : (int * int) -> int list

Tomei os nomes emprestados de Python 2.7. xrange recebe como parâmetro uma tupla de dois inteiros ((int * int)) e retorna uma função que recebe uma unidade, retornando uma “opção” de inteiro.

A tupla recebidas por xrange representa o começo e o fim dareiteração.

Então o parâmetro (a, b) representa matematicamente reiteração sobre oconjunto [a, b).

range recebe o mesmo tipo de parâmetro que xrange, retornandoa lista já composta.

— Mas o que diabos é uma opção de inteiro?

É um valor que pode ser “algum” (SOME) inteiro ou “nenhum” (NONE).

- SOME 42;
val it = SOME 42 : int option
- NONE;
val it = NONE : 'a option

Usaremos NONE para marcar o fim da reiteração. Precisamos também deum closure para armazenar o próximo retorno do gerador (já que geradores não são idempotentes). Usaremos um int ref para o closure.

Atualizei o código removendo a necessidade de usar fn.

local
  fun xrange' i finish () =
    if !i >= finish then
      NONE
    else
      let
        val r = !i
      in
        i := !i + 1;
        SOME r
      end
in
  fun xrange (start, finish) = xrange' (ref start) finish
end

Vamos testar nosso xrange:

- val x = range (0, 10);
val x = fn : unit -> int option
- x ();
val it = SOME 0 : int option
- x ();
val it = SOME 1 : int option
- x ();
val it = SOME 2 : int option
- x ();
val it = SOME 3 : int option
- x ();
val it = SOME 4 : int option
- x ();
val it = SOME 5 : int option
- x ();
val it = SOME 6 : int option
- x ();
val it = SOME 7 : int option
- x ();
val it = SOME 8 : int option
- x ();
val it = SOME 9 : int option
- x ();
val it = NONE : int option

OK! Nossa função se comporta como esperado! Agora precisamos criar a função range.

Gerador para lista

Para criar a função range, criaremos uma função que receba um gerador e retorne uma lista de todos os valores gerados.

Esta função precisa de um acumulador: uma lista que começa vazia (nil) e vai sendo preenchida conforme o gerador é reiterado. Então ela precisa validar o gerador (passando a unidade como parâmetro) e tratar o resultado:

fun genToList' (acc : int list) (gen : unit -> int option) : int list =
  case gen () of NONE       => rev acc
    | SOME value => genToList' (value::acc) gen

Perceba que, passando value::acc, a lista é gerada de trás para frente. Portanto, ao recebermos o valor de parada (NONE), precisamos retornar a inversão do acumulador (rev acc).

Nossa genToList' tem assinatura int list -> (unit -> t option) -> t list, o que significa que, se chamada com um único parâmetro (o acumulador), retorna uma função com a assinatura (unit -> t option) -> t list. Vamos criar o variante com acumulador embutido:

val genToList = genToList' nil

Podemos usar essa segunda função para construir a função range. Colocando tudo junto:

local
  fun genToList' (acc : int list) (gen : unit -> int option) : int list =
    case gen () of NONE       => rev acc
                 | SOME value => genToList' (value::acc) gen
  val genToList = genToList' nil
in
  val range = genToList o xrange
end

A construção o funciona como o de matemática, por exemplo, fog(x) é o mesmo que f(g(x)).

Vamos testar:

- range (0, 10);
val it = [0,1,2,3,4,5,6,7,8,9] : int list

It works!!! 😋

Próximo artigo

No próximo artigo vamos tornar o gerador mais robusto e genérico com structures e functors.