¿Qué quieren decir los programadores funcionales cuando dicen que una determinada cosa es composable o no composable?¿Qué significa capacidad de compilación en el contexto de la programación funcional?
Algunas de las declaraciones de este tipo que he leído son:
Marcelo Cantos gave a pretty good explanation, pero creo que se puede hacer un poco más preciso.
Un tipo de cosas se pueden componer cuando se pueden combinar varias instancias de una cierta manera para producir el mismo tipo de cosas.
Capacidad de compilación de la estructura de control. lenguajes como C hacen una distinción entre expresiones, que pueden estar compuestos usando los operadores para producir nuevas expresiones y declaraciones, que puede estar compuesto usando estructuras de control como if, for y la "estructura de control de secuencia" que simplemente realiza declaraciones en orden. Lo que ocurre con esta disposición es que estas dos categorías no están en pie de igualdad: muchas estructuras de control utilizan expresiones (por ejemplo, la expresión evaluada por if para elegir qué rama ejecutar), pero las expresiones no pueden usar estructuras de control (p. no puede devolver un bucle for). Aunque pueda parecer loco o sin sentido querer "devolver un bucle for", de hecho, la idea general de tratar las estructuras de control como objetos de primera clase que pueden almacenarse y transmitirse no solo es posible sino también útil. En lenguajes funcionales perezosos como Haskell, las estructuras de control como if y for se pueden representar como funciones ordinarias, que pueden manipularse en expresiones como cualquier otro término, habilitando funciones como "construir" otras funciones según los parámetros que se transmiten y devolverlos a la persona que llama. Entonces, mientras C (por ejemplo) divide "las cosas que un programador podría querer hacer" en dos categorías y limita las formas en que se pueden combinar los objetos de estas categorías, Haskell (por ejemplo) tiene una sola categoría y no impone tales límites. , por lo que en este sentido proporciona más capacidad de compilación.
Capacidad de subprocesos. Asumiré, como dijo Marcelo Cantos, que realmente está hablando de la capacidad de compilación de los hilos que usan bloqueos/mutexes. Este es un caso un poco más complicado porque, en vista de ello, puede tener hilos que usan bloqueos múltiples; pero el punto importante es que no podemos tener hilos que usen cerrojos múltiples con la garantía de que están destinados a tener.
Podemos definir un bloqueo como un tipo de cosa que tiene ciertas operaciones que se pueden realizar en él, que vienen con ciertas garantías. Una garantía es: suponga que hay un objeto de bloqueo x, luego, siempre que cada proceso que llame a lock(x) eventualmente llame a unlock(x), cualquier llamada a lock(x) eventualmente regresará con éxito con x bloqueado por el proceso/proceso actual. Esta garantía simplifica enormemente el razonamiento sobre el comportamiento del programa.
Desafortunadamente, si hay más de un bloqueo en el mundo, ya no es cierto. Si el hilo A llama a lock(x); lock(y); y el hilo B llama al lock(y); lock(x);, entonces es posible que A agarre el bloqueo x y B tome el bloqueo y y que ambos esperen indefinidamente para que el otro hilo libere el otro bloqueo: punto muerto. Por lo tanto, los bloqueos no son compostables, porque cuando usa más de uno, no puede simplemente afirmar que esa importante garantía aún se mantiene - no sin antes analizar el código en detalle para ver cómo se maneja el bloqueo. En otras palabras, ya no puede darse el lujo de tratar las funciones como "cajas negras".
Las cosas que son componibles son buenas, ya que permiten abstracciones, lo que significa que nos permiten razonar sobre el código sin tener que preocuparse por todos los detalles, y que reduce la carga cognitiva en el programador.
La composición en informática es la capacidad de ensamblar comportamientos complejos al agregar un comportamiento más simple. La descomposición funcional es un ejemplo de esto, mediante el cual una función compleja se divide en funciones más pequeñas fáciles de comprender y se ensambla en el sistema final mediante una función de nivel superior. Se puede decir que la función de nivel superior ha "compuesto" las piezas en el todo.
Ciertos conceptos no se componen fácilmente. Por ejemplo, una estructura de datos segura para subprocesos puede permitir la inserción y eliminación segura de elementos, y lo hace bloqueando la estructura de datos o algún subconjunto para que un subproceso pueda realizar las manipulaciones necesarias sin que sus cambios se inmiscuyan en — y el la estructura de datos corrompió — mientras funciona. Sin embargo, una función comercial puede requerir la eliminación de un elemento de una colección, seguido de su inserción en otra, y para que toda la operación se realice atómicamente. El problema es que el bloqueo solo ocurre por estructura de datos. Puede eliminar de forma segura un elemento de uno, pero luego puede encontrar que no puede insertarlo en el otro debido a una violación de clave. O puede intentar insertarlo en un segundo y luego quitarlo del primero, solo para descubrir que otro hilo lo ha robado por debajo de la nariz. Al darse cuenta de que no puede completar la operación, puede tratar de volver a poner las cosas como estaban, solo para descubrir que la inversión falla por razones similares, ¡y ahora se encuentra en el limbo! Podría, por supuesto, implementar un esquema de bloqueo más completo que cubra múltiples estructuras de datos, pero eso solo funciona si todos aceptan el nuevo esquema de bloqueo, y se lleva la carga de usarlo todo el tiempo, incluso cuando todas sus operaciones están en un único estructura de datos.
El bloqueo de estilo Mutex es, por lo tanto, un concepto que no se cumple. No puede implementar un comportamiento seguro de subprocesos de nivel superior simplemente agregando operaciones de seguridad de subprocesos de nivel inferior. La solución en este caso es usar un concepto que sí lo haga, como STM.
+1, pero su punto acerca de que los bloqueos no se componen aún más.Incluso si 'lock (x)' * always * eventualmente tiene éxito cuando 'x' es el único bloqueo en el mundo, y' lock (y) '* always * eventualmente tiene éxito cuando' y' es el único bloqueo en el mundo, función que llama 'lock (x); lock (y); 'puede interbloqueo si otro hilo/proceso intenta agarrar los bloqueos en el orden opuesto. Es decir, la falla es posible * incluso cuando se garantiza que las operaciones individuales tendrán éxito cuando se realicen en forma aislada *. –
Buen punto, @j_random_hacker. Además, una política canónica de orden de adquisición de candados puede ayudar, pero no siempre es posible observarla. Por ejemplo, es posible que no sepa qué bloqueo adquirir en una tabla hash de destino hasta que realmente absorbe un elemento de la tabla hash de origen, por lo que se ve obligado a adquirir bloqueos en orden de origen-destino, lo que podría ser al revés otro hilo. –
Otro ejemplo: considere la programación asincrónica en .NET. Si usa un lenguaje como C# y necesita realizar una serie de llamadas de E/S asíncronas (no bloqueantes) a través de API de inicio/finalización, para llamar a dos operaciones, Foo y Bar, en secuencia, debe exponer dos métodos (BeginFooAndBar, EndFooAndBar), donde BeginFooAndBar llamadas BeginFoo y pasa una devolución de llamada a Intermediate, y Intermediate llama entonces BeginBar, y hay que enhebrar los valores intermedios y IAsyncResult información de estado a través, y si quieres un try - bloque catch todo el conjunto cosa, entonces buena suerte, necesitas duplicar el código de manejo de excepciones en tres lugares, ¡ay! y es un desastre tremendo.
Pero luego con F #, está el tipo async, construido sobre las continuación funcionales que se pueden componer, y para que pueda escribir, p.
let AsyncFooAndBar() = async {
let! x = Async.FromBeginEnd(BeginFoo, EndFoo)
let! y = Async.FromBeginEnd(BeginBar, EndBar, x)
return y * 2 }
o lo que sea, y es simple, y si usted quiere poner una try-catch alrededor de ella, grande, el código está en un solo método, en lugar de propagación a través de tres, que acaba de poner un try - catch a su alrededor y funciona.
Aquí hay un ejemplo del mundo real. Los nombres de todas las personas que viven en su casa son la lista de nombres de todos los hombres de su casa combinados con la lista de todas las mujeres de su casa.
Esto se puede componer, ya que cada uno de esos dos subproblemas se puede resolver de forma independiente y sin interferir con la resolución del otro.
Por otro lado, muchas recetas no se pueden componer, ya que los pasos se deben realizar en un orden particular y se basan en los resultados de otros pasos. ¡Tienes que romper los huevos antes de batirlos!
Estoy de acuerdo con la respuesta de Marcelo Cantos, pero creo que puede asumir más antecedentes que algunos lectores, lo que también está relacionado con por qué la composición en la programación funcional es especial. La composición funcional funcional de programación es esencialmente idéntica a la composición de funciones en matemáticas. En matemáticas, puede tener una función f(x) = x^2, y una función g(x) = x + 1. Componer las funciones significa crear una nueva función, en la que los argumentos de función se asignan a la función "interna", y la salida de la función "interna" sirve como entrada a la función "externa". Componer f exterior con g interior podría escribirse f(g(x)). Si proporciona un valor de 1 para x, entonces g(1) == 1 + 1 == 2, entonces f(g(1)) == f(2) == 2^2 == 4. Más en general, f(g(x)) == f(x + 1) == (x+1)^2. Describí la composición usando la sintaxis f(g(x)), pero los matemáticos a menudo prefieren una sintaxis diferente, (f . g)(x). Creo que esto se debe a que hace más claro que f composed with g es una función en sí misma, que toma un solo argumento.
Los programas funcionales se crean completamente utilizando primitivas de composición. Un programa en Haskell es, para simplificar en exceso, una función que toma como argumento un entorno de tiempo de ejecución y devuelve el resultado de alguna manipulación de ese entorno. (Grokking esta afirmación requerirá cierta comprensión de las mónadas). Todo lo demás se hace con composition in the mathematical sense.
Un ejemplo simple de capacidad de compilación es la línea de comandos de Linux, donde el carácter de tubería le permite combinar comandos simples (ls, grep, cat, etc.) en un número virtualmente ilimitado de formas, "componiendo" una gran cantidad de comportamientos complejos de un pequeño número de primitivos más simples.
Hay varias ventajas a componibilidad:
more) se obtiene una grado de uniformidad de paginación que no sería posible si cada comando fuera a implementar sus propios mecanismos (y indicadores de línea de comando) para hacer paginación.medida que la línea de comandos de Linux ejemplo muestra, del composability no se limita necesariamente a la programación funcional, pero el concepto es el mismo: Tener piezas más bien pequeñas de código que pueden hacer tareas restringidas, y construir una funcionalidad más compleja mediante el enrutamiento de las salidas y entradas apropiadamente.
El punto es que la programación funcional es adecuada para esto: con variables inmutables y restricciones en los efectos secundarios puede componer más fácilmente ya que no necesita preocuparse por lo que ocurre debajo de la función llamada variable, por lo que el resultado no será válido para ciertas secuencias de operaciones o para acceder a un bloqueo compartido, por lo que ciertas secuencias de llamadas generarán un interbloqueo.
Esa capacidad de compilación de programación funcional: cualquier función depende solo de sus parámetros de entrada, y la salida se puede pasar a cualquier función que pueda manejar el tipo del valor de retorno.
Por extensión, tener menos tipos de datos ofrece más capacidad de compilación. Rich Hickey de Clojure dijo algo en la línea de
cada nuevo tipo de objeto es inherentemente incompatible con todo el código cada vez escrita
que sin duda es un punto bien hecho.
La capacidad de compilación práctica también depende de una estandarización en un pequeño conjunto de tipos de datos, como hacen los comandos de Unix con su estándar de "texto delimitado por tabulaciones".
PostScript
Eric Raymond escribió un libro sobre la filosofía Unix, dos de los principios de diseño que se enumeran fueron
De http://catb.org/~esr/writings/taoup/html/ch01s06.html#id2877537
Compuestabilidad en la programación funcional puede decirse para llevar a los principios hasta el nivel de las funciones individuales.
+1, excelente explicación! – missingfaktor
La capacidad de composición permite que la comunidad de desarrolladores eleve continuamente el nivel de abstracción, niveles múltiples, sin estar encadenado a la capa base.
+1. Bonito * "Las cosas que se pueden componer son buenas porque permiten abstracciones, lo que significa que nos permiten razonar sobre el código sin tener que preocuparnos por todos los detalles, y eso reduce la carga cognitiva del programador." * – Nawaz
expandiéndose un poco directamente en Las viñetas de op: Nunca escuché "los hilos no son compostables", pero un ejemplo de una abstracción delgada y composable que se puede construir fácilmente _atop_ hilos son [async/promises] (https://hackage.haskell.org/package/async). Re. las mónadas solo necesitan observar el tipo de enlace: '>> = :: Monad m => m a -> (a -> m b) -> m b'. – jberryman
Después de 3 años, leí esta respuesta ** de nuevo ** y ahora creo que la entiendo mejor de lo que lo entendí la última vez. En particular, puedo imaginar varias cosas que se relacionan con esto * "Un tipo de cosa es composable cuando se pueden combinar varias instancias de una cierta manera para producir el mismo tipo de cosas." * ... y varias otras que no (significa cosas que no son compostables). Una vez más, ¡gracias por esta increíble respuesta! – Nawaz