O que são combinadores e como eles são aplicados aos projetos de programação? (explicação prática)

O que são combinadores?

Estou procurando por:

• uma explicação prática
• exemplos de como eles são usados
• exemplos de como os combinadores melhoram a qualidade / generalidade do código

Não estou procurando:

• explicações de combinadores que não me ajudam a realizar o trabalho (como o combinador Y)

De um ponto de vista prático, combinadores são tipos de construções de programação que permitem reunir peças de lógica de maneiras interessantes e geralmente avançadas. Normalmente, usá-los depende da possibilidade de poder empacotar código executável em objetos, geralmente chamados (por razões históricas) de funções lambda ou expressões lambda, mas sua milhagem pode variar.

Um exemplo simples de um combinador (útil) é aquele que recebe duas funções lambda sem parâmetros e cria um novo que as executa em sequência. O combinador real parece no pseudocódigo genérico assim:

func in_sequence(first, second):
  lambda ():
    first()
    second()

O crucial que torna isso um combinador é a função anônima (função lambda) na segunda linha; quando Você ligar

a = in_sequence(f, g)

o objeto resultante a não é o resultado da execução de primeiro f () e depois g (), mas é um objeto que você pode chamar posteriormente para executar f () e g () em sequência:

a() // a is a callable object, i.e. a function without parameters

Da mesma forma, você pode ter um combinador que executa dois blocos de código em paralelo:

func in_parallel(first, second):
  lambda ():
    t1 = start_thread(first)
    t2 = start_thread(second)
    wait(t1)
    wait(t2)

E então novamente,

a = in_parallel(f, g)
a()

O legal é que 'in_parallel' e 'in_sequence' são ambos combinadores com o mesmo tipo / assinatura, ou seja, ambos pegam dois objetos de função sem parâmetros e retornam um novo. Você pode escrever coisas como

a = in_sequence(in_parallel(f, g), in_parallel(h, i))

e funciona como esperado.

Basicamente, os combinadores permitem construir o fluxo de controle do seu programa (entre outras coisas) de maneira processual e flexível. Por exemplo, se você usar o combinador in_parallel (..) para executar o paralelismo no seu programa, poderá adicionar depuração relacionada a isso à implementação do combinador in_parallel. Posteriormente, se você suspeitar que seu programa possui um bug relacionado ao paralelismo, na verdade você pode apenas reimplementar o in_parallel:

in_parallel(first, second):
  in_sequence(first, second)

e com um toque, todas as seções paralelas foram convertidas em seqüenciais!

Os combinadores são muito úteis quando usados ​​corretamente.

O combinador Y, no entanto, não é necessário na vida real. É um combinador que permite criar funções auto-recursivas e você pode criá-las facilmente em qualquer idioma moderno sem o combinador Y.

É errado rotular o Y-combinator como algo que não "ajudará a realizar o trabalho". Eu achei isso muito útil em várias ocasiões. O caso mais óbvio é quando você precisa inicializar rapidamente alguma linguagem interpretada incorporada. Se você fornecer um conjunto mínimo de primitivas, ou seja sequence, select, call, conste closure allocation, já é suficiente para edificação, uma linguagem complexa arbitrária completa. Nenhum suporte especial para recursão é necessário - ele pode ser adicionado através de um combinador de ponto fixo. Caso contrário, você precisará de primitivas muito mais complicadas.

Outro caso óbvio para os combinadores é a ofuscação. Um código traduzido no cálculo do SKI é praticamente ilegível. Se você realmente precisa ofuscar uma implementação de um algoritmo, considere usar combinadores, aqui está um exemplo .

E, é claro, os combinadores são uma ferramenta importante para implementar linguagens funcionais. A abordagem mais fácil (como no exemplo acima) é via SKI ou cálculo equivalente. Supercombinadores são usados ​​em algumas outras implementações. Este livro fala sobre isso em profundidade.

Isso é uma piada , mas uma piada vale uma leitura muito cuidadosa, pois muitas técnicas e teorias de programação arcanas são abordadas lá.

Pesquisando um pouco, encontrei uma pergunta do StackOverflow, boa explicação de "Combinators" (para não matemáticos), que é um primo próximo dessa pergunta. Uma das respostas apontou para o blog de Reginald Braithwaite, Homoiconic , que vincula vários exemplos úteis de combinadores em código (por exemplo, o combinador K , implementado pelo Object#tapmétodo Ruby - leia a página para exemplos de por que é útil).

A página da Wikipedia em Combinatory Logic descreve combinadores mais globalmente.