Relajar las restricciones de ordenamiento en el cómputo monádico

Question

aquí hay algo de reflexión.

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

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

sé doSomething se ejecutarán antes doSomethingElse.

Ahora, consideremos el código equivalente en un lenguaje como C:

return (doSomething() + doSomethingElse()); 

La semántica de C en realidad no especifica qué orden serán evaluadas estas dos llamadas a la función, por lo que el compilador es libre de moverse cosas todo lo que le plazca.

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

Estas son algunas de las técnicas posibles que no hacer el trabajo, pero están en el "espíritu" derecha:

• escribir el código en estilo funtorial, es decir, escribir y dejar que plus doSomething doSomethingElseplus programar las llamadas monádicas. Inconvenientes: pierde el intercambio de los resultados de las acciones monádicas, y plus todavía toma una decisión sobre cuándo se evalúan las cosas.
• Use lazy IO, es decir, unsafeInterleaveIO, que difiere la programación de las demandas de evaluación. Pero perezoso es diferente de estricto con un orden indefinido: en particular, quiero que se ejecuten todas mis acciones monádicas.
• Lazy IO, combinado con la selección inmediata de todos los argumentos. En particular, seq no impone restricciones de ordenamiento.

En este sentido, quiero algo más flexible que el ordenamiento monádico pero menos flexible que la holgazanería total.

Answer 1

Este problema de código mónada sobre-sequentializing se conoce como el "commutative monads problem" C.

mónadas conmutativos son mónadas para los que el orden de las acciones no hace ninguna diferencia (que conmutan), que es cuando siguiente 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 conmutan (por ejemplo, Maybe, Random). Si la mónada es conmutativa, entonces las operaciones capturadas dentro de ella se pueden calcular en paralelo, por ejemplo. ¡Son muy útiles!

Sin embargo, no tenemos una buena sintaxis de mónadas que viajan, aunque a lot of people have asked para que tal cosa - todavía es una open research problem.

Como un lado, los funtores aplicativos nos dan tanta libertad para reordenar los cálculos, sin embargo, debe darse por vencido con la noción de bind (como sugerencias para, por ejemplo, mostrar liftM2).

Answer 2

La semántica de C en realidad no especifica en qué orden se evaluarán estas dos llamadas de función, por lo que el compilador puede mover libremente las cosas como lo desee.

Pero lo que si doSomething() provoca un efecto secundario que va a cambiar el comportamiento de doSomethingElse()? ¿Realmente quieres que el compilador juegue con la orden? (Sugerencia: no) El hecho de que estés en una mónada sugiere que tal puede ser el caso. Tu nota de que "pierdes compartir los resultados" también sugiere esto.

Sin embargo, tenga en cuenta que monadic no siempre significa secuenciado. No es exactamente lo que describes, pero puede interesarte el Par monad, que te permite ejecutar tus acciones en paralelo.

Le interesa dejar el orden indefinido para que el compilador pueda optimizarlo mágicamente para usted. Tal vez, en su lugar, debería usar algo como la mónada Par para indicar las dependencias (algunas cosas inevitablemente tienen que suceder antes que otras) y luego dejar que el resto se ejecute en paralelo.

Nota al margen: no confunda de Haskell return a ser algo como de return

Answer 3

Esto es un hack sucio y profundo, pero parece que me debe hacer 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 no determinismo en manos del compilador, debe comportarse "correctamente" (es decir nondeterministically) en lo que respecta a controlar problemas de flujo (es decir, excepciones), así.

Por otro lado, no se puede tirar del mismo truco mayoría de las mónadas estándar como State y Either a ya que estamos realmente dependen de la acción fantasmal a distancia disponible a través de jugar con el token RealWorld. Para obtener el comportamiento correcto, necesitamos alguna anotación disponible para el optimizador que indique que estamos bien con la elección no determinista entre dos alternativas no equivalentes.