Relajarse las limitaciones de pedido en el cálculo monádico

Question

He aquí algunos elementos de reflexión.

Cuando escribo código monádico, la mónada impone ordenar en las operaciones realizadas. Por ejemplo, si escribo en la monada IO:

do a <- doSomething
   b <- doSomethingElse
   return (a + b)

lo sé doSomething se ejecutará antes doSomethingElse.

Ahora, considere el código equivalente en un idioma como C:

return (doSomething() + doSomethingElse());

La semántica de C en realidad no especifica qué orden se evaluarán estas dos llamadas de funciones, por lo que el compilador es libre de mover las cosas según lo desee.

Mi pregunta es esta: ¿Cómo escribiría el código monádico en Haskell que también deja esta orden de evaluación indefinida? Idealmente, cosecharía algunos beneficios cuando el optimizador de mi compilador mira el código y comience a mover las cosas.

Aquí hay algunas técnicas posibles que no hacen el trabajo, pero están en el "espíritu" correcto:

• Escribe el código en estilo funcional, es decir, escribir plus doSomething doSomethingElse y deja plus Programe las llamadas monádicas. Inconvenientes: pierdes compartir los resultados de las acciones monádicas, y plus Todavía toma una decisión sobre cuándo terminan evaluando las cosas.
• Usar perezoso io, eso es, unsafeInterleaveIO, que defiende la programación de las demandas perezosas de la evaluación. Pero el flojo es diferente de estricto con orden indefinido: en particular quiero que todas mis acciones monádicas se ejecuten.
• Lazy io, combinado con inmediatamente por ver todos los argumentos. En particular, seq no impone limitaciones de orden.

En este sentido, quiero algo más flexible que el pedido monádico pero menos flexible que la pereza completa.

Answer 1

Este problema de sobre-secuencializar el código de mónada se conoce como el "Problema de monadas conmutativas".

Las mónadas conmutativas son mónadas para las cuales el orden de las acciones no hace ninguna diferencia (viajan), es decir, cuando siguen el código:

do a <- f x
   b <- g y
   m a b

es lo mismo que:

do b <- g y
   a <- f x
   m a b

Hay muchas mónadas que viajan (por ejemplo Maybe, Random). Si la mónada es conmutativa, las operaciones capturadas dentro de ella se pueden calcular en paralelo, por ejemplo. ¡Son muy útiles!

Sin embargo, nos No tenga una buena sintaxis para las mónadas que viajan, aunque mucha gente ha pedido Para tal cosa, sigue siendo un Problema de investigación abierta.

Por otro lado, los functores aplicativos nos dan tanta libertad para reordenar los cálculos, sin embargo, debe renunciar a la noción de bind (Como sugerencias para EG liftM2 mostrar).

Answer 2

Este es un truco sucio profundo, pero parece que debería hacerme el truco.

{-# OPTIONS_GHC -fglasgow-exts #-}
{-# LANGUAGE MagicHash #-}
module Unorder where
import GHC.Types

unorder :: IO a -> IO b -> IO (a, b)
unorder (IO f) (IO g) = IO $ \rw# ->
           let (# _, x #) = f rw#
               (# _, y #) = g rw#
           in (# rw# , (x,y) #)

Dado que esto pone el no determinismo en manos del compilador, debe comportarse "correctamente" (es decir, no determinista) con respecto a controlar los problemas de flujo (es decir, las excepciones) también.

Por otro lado, no podemos sacar el mismo truco, la mayoría de las mónadas estándar, como State y Either a Dado que realmente confiamos en una acción espeluznante a distancia disponible a través del metro con el RealWorld simbólico. Para obtener el comportamiento correcto, necesitaríamos alguna anotación disponible para el optimizador que indicaba que estábamos bien con la elección no determinista entre dos alternativas no equivalentes.

Answer 3

La semántica de C en realidad no especifica qué orden se evaluarán estas dos llamadas de funciones, por lo que el compilador es libre de mover las cosas según lo desee.

Pero que si doSomething() causa un efecto secundario que cambiará el comportamiento de doSomethingElse()? ¿Realmente quieres que el compilador se meta con el pedido? (Sugerencia: No) El hecho de que esté en una mónada sugiere que tal puede ser el caso. Su nota de que "pierde compartir los resultados" también sugiere esto.

Sin embargo, tenga en cuenta que Monadic no siempre significa secuenciar. No es exactamente lo que usted describe, pero puede estar interesado en el Par monad, que le permite ejecutar sus acciones en paralelo.

Está interesado en dejar el pedido indefinido para que el compilador pueda optimizarlo mágicamente por usted. Quizás, en su lugar, debería usar algo como la PAR Monad para indicar las dependencias (algunas cosas inevitablemente tienen que suceder antes que otras) y luego dejar que el resto funcione en paralelo.

Nota al margen: no confunda a Haskell's return ser cualquier cosa como C's return