Qual é o significado de "não compõe"?

35

Eu vejo muitos textos, especialmente textos de programação funcional, alegando que certos conceitos de CS "não compõem" . Exemplos são: fechaduras não compõem, mônadas não compõem.

Tenho tido dificuldade em rastrear exatamente o significado dessa frase. Quando penso em composição, penso em composição de funções ou agregação de objetos (como em "favorecer composição sobre herança"), mas esse não parece ser o sentido em que as pessoas a estão usando aqui.

Alguém pode explicar o que essa frase significa quando usada em expressões como os dois exemplos acima (ou seja, bloqueios e mônadas)?

Conta
fonte
É mais próximo do significado da composição das funções do que da agregação de objetos.
Andres F.
Grosso e informalmente, se você tem duas coisas separadas que usam bloqueios, é difícil juntá-las. (no caso de bloqueios, é difícil de fazer sem a introdução de impasses; no caso de mônadas, os tipos podem ficar complicadas)
user253751

Respostas:

35

Quando as pessoas dizem "X não compõe", o que elas querem dizer com "compor" realmente significa apenas "montar", e o que e como você as coloca podem ser muito diferentes, dependendo do que exatamente é "X".

Além disso, quando eles dizem "não compõe", eles podem significar algumas coisas um pouco diferentes:

  1. Você não pode colocar dois Xs juntos, ponto final.
  2. Você pode colocar dois Xs juntos, mas o resultado pode não ser um X (IOW: X não está fechado na composição ).
  3. Você pode colocar dois Xs juntos, mas o X resultante pode não funcionar da maneira que você espera.

Um exemplo para o nº 1 é analisadores com scanners / lexers. Você pode ouvir a frase "scanners / lexers não compõem". Isso não é verdade. O que eles querem dizer é "analisador que usa um estágio lexing separado não compõe".

Por que você gostaria de compor analisadores? Bem, imagine que você é um fornecedor de IDE como JetBrains, Eclipse Foundation, Microsoft ou Embarcadero e deseja criar um IDE para uma estrutura da web. No desenvolvimento típico da Web, geralmente misturamos idiomas. Você possui arquivos HTML com <script>elementos que contêm ECMAScript e<style>elementos que contêm CSS. Você tem arquivos de modelo que contêm HTML, alguma linguagem de programação e algumas metassintaxe da linguagem de modelo. Você não deseja gravar marcadores de sintaxe diferentes para "Python", "Python incorporado em um modelo", "CSS", "CSS dentro de HTML", "ECMASCript", "ECMAScript dentro de HTML", "HTML", "HTML dentro de" um modelo "e assim por diante. Você deseja escrever um marcador de sintaxe para Python, um para HTML, um para a linguagem de modelo e, em seguida, compor os três em um marcador de sintaxe para um arquivo de modelo.

No entanto, um lexer analisa o arquivo inteiro em um fluxo de tokens, o que só faz sentido para esse idioma. O analisador para o outro idioma não pode trabalhar com os tokens que o lexer passa. Por exemplo, os analisadores Python são tipicamente escritos de tal maneira que o lexer controla o recuo e injeta falsos INDENTe DEDENTtokens no fluxo de token, permitindo que o analisador fique livre de contexto, mesmo que a sintaxe do Python não seja. Um lexer HTML, no entanto, ignorará completamente os espaços em branco, pois não tem significado em HTML.

Um analisador sem scanner, no entanto, que simplesmente lê caracteres, pode transmitir o fluxo de caracteres para um analisador diferente, que pode devolvê-lo, facilitando sua composição.

Um exemplo para o número 2 são cadeias de caracteres com consultas SQL. Você pode ter duas cadeias de caracteres, cada uma com uma consulta SQL sintaticamente correta, mas se você concatenar as duas cadeias, o resultado poderá não ser uma consulta SQL sintaticamente correta. É por isso que temos de consulta álgebras como ARel, o que fazer composição.

Bloqueios são um exemplo de # 3. Se você possui dois programas com bloqueios e os combina em um único programa, ainda possui um programa com bloqueios, mas mesmo que os dois programas originais estivessem completamente corretos, livres de impasses e corridas, o programa resultante não tem necessariamente isso propriedade. O uso correto de bloqueios é uma propriedade global de todo o programa e uma propriedade que não é preservada quando você compõe programas. Isso é diferente de, por exemplo, transações que são compostas. Um programa que usa transações corretamente pode ser composto por outro programa e produzirá um programa combinado que usa transações corretamente.

Jörg W Mittag
fonte
11
Em outras palavras, "não compõe" significa "não forma um semigrupo" (ou, um pouco mais fortemente, um monóide).
Jon Purdy
Eu não tenho certeza de associtaivity é necessária, por isso mais como um magma (o que eu aprendi sobre literalmente 3 segundos atrás :-D)
Jörg W Mittag
No entanto, se você perguntar a alguém o que eles querem dizer quando dizem que "bloqueios não compõem", tenho certeza que eles não responderão "Quero dizer que o conjunto de programas simultâneos corretos com bloqueios e a operação de composição formam um Magma" .
Jörg W Mittag
Hah, claro que não. Apenas um fraseado alternativo. Tenho a sensação de que é necessária associatividade para manter o sentimento "plano" de composição, mas não há argumentos fortes para sustentar isso.
21415 Jon Purdy
20

Composibilidade significa que você pode combinar de maneira fácil e confiável os componentes do programa para produzir componentes maiores e funcionalidades mais complexas.

Algumas coisas que ajudam a tornar os componentes mais compostáveis:

  1. Idempotência. Uma função idempotente sempre produzirá a mesma saída ou efeitos colaterais, se chamados várias vezes com os mesmos valores de parâmetro. Isso melhora a composibilidade porque o resultado de uma chamada de função é previsível.

  2. Transparência referencial. Uma expressão referencialmente transparente sempre será avaliada para o mesmo resultado. Isso melhora a composibilidade, permitindo que expressões idênticas sejam substituídas uma pela outra e permitindo que expressões sejam calculadas independentemente uma da outra (ou seja, em threads diferentes) sem usar bloqueios.

  3. Imutabilidade. O estado de um objeto imutável não pode ser alterado depois de criado. Isso melhora a composibilidade porque você pode confiar em um valor estável do objeto, sem se preocupar se alguma função ou objeto em algum lugar mudou o estado do objeto depois que ele foi criado.

  4. Pureza. As funções puras não têm efeitos colaterais. Eles possuem apenas uma entrada e uma saída, o que os torna mais composíveis porque você pode colocar a saída de uma função na entrada de outra função sem se preocupar se alguma coisa fora da função foi alterada.

Os bloqueios não se compõem porque são um elemento externo no qual você deve confiar ao combinar duas operações que compartilham algum estado e por todos os tipos de razões relacionadas à complexidade inerente ao uso de bloqueios.

A frase "mônadas não compõem" não faz muito sentido para mim. O objetivo principal de uma mônada é pegar algo importante, como entrada de teclado ou saída de tela, e transformá-la em uma forma matemática mais pura que é, de fato, mais compostável.

Robert Harvey
fonte
4
Eu acho que stackoverflow.com/questions/7040844/… faz um bom trabalho explicando o que "mônadas não compõem" provavelmente significa, embora eu concorde que as mônadas são muito mais compostas que bloqueios.
Ixrec 17/07/2015
Seus pontos principais para "transparência referencial" e "pureza" são, na verdade, os dois requisitos de pureza . O termo "transparência referencial" deve ser evitado porque não está bem definido .
BlueRaja - Danny Pflughoeft
11
Uma mônada é uma estrutura algébrica com certas operações. O que você descreveu em seu parágrafo final é o IOtipo que captura "ações com estado", como entrada do teclado. Os valores do IOtipo, de fato, compõem, mas é todo o tipo IO que é uma mônada. Esse tipo não compõe com outros tipos de mônadas, como, por exemplo, o tipo de lista. Ou seja, não podemos produzir sistematicamente um tipo IO . Listque se comporte como ambos IO e Listsimultaneamente. Isso faz sentido? Não tenho certeza se expliquei bem.
Tikhon Jelvis 20/08/2015