¿Cuál es el significado de "no compone"?

35

Veo muchos textos, especialmente textos de programación funcional, que afirman que ciertos conceptos de CS "no componen" . Los ejemplos son: las cerraduras no componen, las mónadas no componen.

He tenido dificultades para rastrear exactamente el significado de esta frase. Cuando pienso en la composición, pienso en la composición de funciones o en la agregación de objetos (como en "favorecer la composición sobre la herencia"), pero ese no parece ser el sentido en el que las personas la usan aquí.

¿Alguien puede explicar qué significa esta frase cuando se usa en expresiones como los dos ejemplos anteriores (es decir, cerraduras y mónadas)?

Cuenta
fuente
Tiene un significado más cercano a la composición de funciones que a la agregación de objetos.
Andres F.
Aproximadamente e informalmente, si tiene dos cosas separadas que usan cerraduras, es difícil mantenerlas juntas. (en el caso de las cerraduras, es difícil hacerlo sin introducir puntos muertos; en el caso de las mónadas, los tipos pueden complicarse)
user253751

Respuestas:

35

Cuando la gente dice "X no compone", lo que quieren decir con "componer" en realidad solo significa "juntar", y qué y cómo los juntas pueden ser muy diferentes, dependiendo de qué es exactamente "X".

Además, cuando dicen "no compone", pueden significar algunas cosas ligeramente diferentes:

  1. No puedes poner dos X juntas, punto.
  2. Usted puede poner dos Xs juntos, pero el resultado puede ser que no sea una X (OIA: X no está cerrado bajo la composición ).
  3. Puede juntar dos X, pero la X resultante podría no funcionar de la manera esperada.

Un ejemplo para el n. ° 1 son los analizadores con escáneres / lexers. Es posible que escuche la frase "los escáneres / lexers no componen". Eso no es realmente cierto. Lo que quieren decir es "el analizador que usa una etapa lexing separada no compone".

¿Por qué quieres componer analizadores? Bueno, imagina que eres un proveedor de IDE como JetBrains, Eclipse Foundation, Microsoft o Embarcadero, y quieres construir un IDE para un marco web. En el desarrollo web típico, a menudo mezclamos idiomas. Tiene archivos HTML con <script>elementos que contienen ECMAScript y<style>elementos que contienen CSS. Tiene archivos de plantilla que contienen HTML, algún lenguaje de programación y algunas metasintaxis de lenguaje de plantilla. No desea escribir marcadores de sintaxis diferentes para "Python", "Python incrustado en una plantilla", "CSS", "CSS dentro de HTML", "ECMASCript", "ECMAScript dentro de HTML", "HTML", "HTML dentro de una plantilla ", y así sucesivamente. Desea escribir un resaltador de sintaxis para Python, uno para HTML, uno para el lenguaje de plantilla y luego componer los tres en un resaltador de sintaxis para un archivo de plantilla.

Sin embargo, un lexer analiza el archivo completo en una secuencia de tokens, lo que solo tiene sentido para ese idioma. El analizador para el otro idioma no puede funcionar con los tokens que el lexer lo pasa. Por ejemplo, los analizadores de Python generalmente se escriben de tal manera que el lexer realiza un seguimiento de la sangría e inyecta falsificaciones INDENTy DEDENTtokens en la secuencia de tokens, lo que permite que el analizador esté libre de contexto aunque la sintaxis de Python no lo sea. Sin embargo, un lexer HTML ignorará completamente los espacios en blanco, ya que no tiene significado en HTML.

Sin embargo, un analizador sin escáner, que simplemente lee caracteres, puede pasar el flujo de caracteres a un analizador diferente, que luego puede devolverlo, lo que hace que sean mucho más fáciles de componer.

Un ejemplo de # 2 son las cadenas con consultas SQL en ellas. Puede tener dos cadenas, cada una de las cuales tiene una consulta SQL sintácticamente correcta, pero si concatena las dos cadenas, el resultado puede no ser una consulta SQL sintácticamente correcta. Es por eso que tenemos de consulta como álgebra ARel, que hacen componer.

Las cerraduras son un ejemplo de # 3. Si tiene dos programas con bloqueos, y los combina en un solo programa, todavía tiene un programa con bloqueos, pero incluso si los dos programas originales eran completamente correctos, libres de puntos muertos y carreras, el programa resultante no necesariamente tiene esto propiedad. El uso correcto de los bloqueos es una propiedad global de todo el programa y una propiedad que no se conserva al componer programas. Esto es diferente de, por ejemplo, transacciones, que hacen de redacción. Un programa que usa transacciones correctamente puede componerse con otro de esos programas y producirá un programa combinado que usa transacciones correctamente.

Jörg W Mittag
fuente
1
En otras palabras, "no compone" significa "no forma un semigrupo" (o, un poco más fuerte, un monoide).
Jon Purdy
No estoy seguro de que se requiera una asociación, así que más bien un Magma (del que aprendí literalmente hace 3 segundos :-D)
Jörg W Mittag
Sin embargo, si le preguntas a alguien qué significan cuando dicen "los bloqueos no componen", estoy bastante seguro de que no responderán "Quiero decir que el conjunto de programas concurrentes correctos con bloqueos y la operación de composición forman un Magma" .
Jörg W Mittag
Ja, por supuesto que no. Solo una frase alternativa. Tengo la sensación de que se requiere asociatividad para mantener el sentimiento "plano" de composición, pero no hay un argumento sólido para respaldar eso.
Jon Purdy
20

La capacidad de composición significa que puede combinar de manera fácil y confiable los componentes del programa para producir componentes más grandes y una funcionalidad más compleja.

Algunas cosas que ayudan a que los componentes sean más compostables:

  1. Idempotencia Una función idempotente siempre producirá la misma salida o efectos secundarios, si se llama varias veces con los mismos valores de parámetros. Esto mejora la componibilidad porque el resultado de una llamada de función es predecible.

  2. Transparencia referencial. Una expresión referencialmente transparente siempre evaluará el mismo resultado. Esto mejora la componibilidad al permitir que las expresiones idénticas se sustituyan entre sí y al permitir que las expresiones se calculen independientemente entre sí (es decir, en diferentes hilos) sin usar bloqueos.

  3. Inmutabilidad. El estado de un objeto inmutable no se puede cambiar una vez que se crea. Esto mejora la capacidad de compilación porque puede confiar en un valor estable del objeto, sin preocuparse si alguna función u objeto en algún lugar ha cambiado el estado del objeto después de su creación.

  4. Pureza. Las funciones puras no tienen efectos secundarios. Solo tienen una entrada y una salida, lo que las hace más componibles porque puede poner la salida de una función en la entrada de otra función sin preocuparse de si algo fuera de la función ha cambiado o no.

Los bloqueos no se componen porque son un elemento externo en el que debe confiar al combinar dos operaciones juntas que comparten algún estado, y por todo tipo de razones que tienen que ver con la complejidad inherente al uso de bloqueos.

La frase "las mónadas no componen" no tiene mucho sentido para mí. El objetivo de una mónada es tomar algo con estado como entrada de teclado o salida de pantalla, y convertirlo en una forma matemática más pura que, de hecho, sea más componible.

Robert Harvey
fuente
44
Creo que stackoverflow.com/questions/7040844/… hace un buen trabajo explicando lo que probablemente significa "mónadas no componen", aunque estoy de acuerdo en que las mónadas son mucho más componibles que las cerraduras.
Ixrec
Sus viñetas para "transparencia referencial" y "pureza" son en realidad los dos requisitos para la pureza . El término "transparencia referencial" debe evitarse porque no está bien definido .
BlueRaja - Danny Pflughoeft
1
Una mónada es una estructura algebraica con ciertas operaciones. Lo que describió en su párrafo final es el IOtipo que captura "acciones con estado" como entrada de teclado. Los valores del IOtipo, de hecho, componen, pero es todo el tipo lo IO que es una mónada. Este tipo no se compone de otros tipos que son mónadas como, por ejemplo, el tipo de lista. Es decir, no podemos producir sistemáticamente un tipo IO . Listque se comporte como ambos IO y Listsimultáneamente. ¿Tiene sentido? No estoy seguro de haberlo explicado bien.
Tikhon Jelvis