haskell - utiliza - ¿Existe una aplicabilidad en el mundo real para la mónada de continuación fuera del uso académico?

programacion funcional historia

Question

(Visitantes posteriores: dos respuestas a esta pregunta dan una idea excelente, si estás interesado, probablemente deberías leer ambas, solo pude exceptuar una como una limitación de SO)

De todas las discusiones que encuentro en línea sobre la mónada de continuación, mencionan cómo podría usarse con algunos ejemplos triviales, o explican que es un componente fundamental, ya que en este artículo sobre la Madre de todas las mónadas es la mónada de continuación .

Me pregunto si hay aplicabilidad fuera de este rango. Quiero decir, ¿tiene sentido ajustar una función recursiva o recurrencia mutua en una mónada de continuación? ¿Ayuda en la legibilidad?

Aquí hay una versión F # del modo de continuación tomado de esta publicación SO :

type ContinuationMonad() =
    member this.Bind (m, f) = fun c -> m (fun a -> f a c)
    member this.Return x = fun k -> k x

let cont = ContinuationMonad()

¿Es meramente de interés académico, por ejemplo para ayudar a entender las mónadas o los constructores de computación? ¿O hay alguna aplicabilidad en el mundo real, mayor seguridad de tipo, o elude los típicos problemas de programación que son difíciles de resolver de otro modo?

Es decir, la mónada de continuación con llamada / CC de Ryan Riley muestra que es complejo manejar excepciones, pero no explica qué problema está tratando de resolver y los ejemplos no muestran por qué necesita específicamente esta mónada. Es cierto, simplemente no entiendo lo que hace, pero puede ser un tesoro!

(Nota: no estoy interesado en entender cómo funciona la mónada de continuación, creo que tengo una buena comprensión de ella, simplemente no veo qué problema de programación resuelve).

Answer 1

La "madre de todas las mónadas" no es puramente académica. Dan Piponi hace referencia a Representing Monads, de Andrzej Filinski, un documento bastante bueno. El resultado es si su lenguaje ha delimitado las continuidades (o puede imitarlas con call/cc y una sola pieza de estado mutable) entonces puede agregar de forma transparente cualquier efecto monádico a cualquier código. En otras palabras, si tiene continuidades delimitadas y no tiene otros efectos secundarios , puede implementar el estado mutable (global) o excepciones o retroceder el no determinismo o la concurrencia cooperativa. Puede hacer cada uno de estos simplemente definiendo algunas funciones simples. Sin transformación global ni nada necesario. Además, solo paga por los efectos secundarios cuando los usa. Resulta que los Schemer tenían toda la razón sobre que call/cc era altamente expresivo.

Si su idioma no tiene continuaciones delimitadas, puede obtenerlas a través de la mónada de continuación (o mejor la mónada de continuación de doble cañón). Por supuesto, si vas a escribir en estilo monádico de todos modos, que es una transformación global, ¿por qué no usar la mónada deseada desde el primer momento? Para Haskellers, esto es típicamente lo que hacemos, sin embargo, todavía hay beneficios de usar la mónada de continuación en muchos casos (aunque ocultos). Un buen ejemplo es la mónada Maybe / Option que es como tener excepciones, excepto que solo hay un tipo de excepción. Básicamente, esta mónada captura el patrón de devolver un "código de error" y verificarlo después de cada llamada de función. Y eso es exactamente lo que hace la definición típica, excepto por "llamada de función". Quise decir cada paso (monádico) del cálculo. Baste decir que esto es bastante ineficiente, especialmente cuando la gran mayoría de las veces no hay ningún error. Sin embargo, si reflejas Maybe en la mónada de continuación, mientras tienes que pagar el costo del código CPS (que GHC Haskell maneja sorprendentemente bien), solo pagas para verificar el "código de error" en los lugares en los que importa, es decir, declaraciones de catch . En Haskell, la mónada Codensity que danidiaz mencionada es una mejor opción porque lo último que quiere Haskellers es hacer que los efectos arbitrarios puedan intercalarse transparentemente en su código.

Como también mencionó Danidiaz, muchas mónadas se implementan más fácil o más eficientemente utilizando esencialmente una mónada de continuación o alguna variante. La búsqueda de retroceso es un ejemplo. Si bien no es lo más nuevo en el retroceso, uno de mis papeles favoritos que lo utilizó fue Typed Logical Variables en Haskell . Las técnicas utilizadas en él también se usaron en el Lenguaje de descripción de hardware con cable. También de Koen Claesson es Monad de concurrencia de un pobre . Los usos más modernos de las ideas en este ejemplo incluyen: la mónada para el paralelismo determinista en Haskell A Monad para Paralelismo determinista y administradores escalables de E / S Combinación de eventos e hilos para servicios de red escalables . Estoy seguro de que puedo encontrar técnicas similares utilizadas en Scala. Si no se proporcionó, podría usar una mónada de continuación para implementar flujos de trabajo asincrónicos en F #. De hecho, Don Syme hace referencia exactamente a los mismos documentos que acabo de mencionar. Si puede serializar funciones pero no tiene continuaciones, puede usar una mónada de continuación para obtenerlas y hacer el tipo de continuación serializada de programación web popularizada por sistemas como Seaside . Incluso sin continuaciones serializables, puede usar el patrón (esencialmente el mismo que el de sincronización) para evitar por lo menos devoluciones de llamadas mientras se almacenan las continuaciones localmente y solo se envía una clave.

En última instancia, relativamente pocas personas fuera de Haskellers están usando mónadas en cualquier capacidad, y como he mencionado anteriormente, los Haskeller tienden a querer usar mónadas más contiguas que la mónada de continuación, aunque sí las usan internamente. Sin embargo, las mónadas de continuación o la mónada de continuación como las cosas, particularmente para la programación asincrónica, son cada vez menos comunes. A medida que C #, F #, Scala, Swift e incluso Java comienzan a incorporar una programación de soporte monádica o al menos de estilo monádico, estas ideas se utilizarán de forma más general. Si los desarrolladores de Node estuvieran más familiarizados con esto, tal vez se habrían dado cuenta de que podrían tener su pastel y comerlo también en lo que respecta a la programación basada en eventos.

Answer 2

Para proporcionar una respuesta más específica de F # específica (aunque Derek ya lo haya cubierto), la mónada de continuación captura bastante el núcleo de cómo funcionan los flujos de trabajo asíncronos .

Una mónada de continuación es una función que, cuando se le da una continuación, finalmente llama a la continuación con el resultado (puede que nunca lo llame o que también lo llame repetidamente):

type Cont<''T> = (''T -> unit) -> unit

Los cómputos asíncronos F # son un poco más complejos: dan continuidad (en caso de éxito), contingencias de excepción y cancelación, y también incluyen el token de cancelación. Usando una definición ligeramente simplificada, la biblioteca F # core usa (vea la definición completa aquí ):

type AsyncParams =
    { token : CancellationToken
      econt : exn -> unit
      ccont : exn -> unit } 

type Async<''T> = (''T -> unit) * AsyncParams -> unit

Como puede ver, si ignora AsyncParams , es prácticamente la mónada de continuación. En F #, creo que las mónadas "clásicas" son más útiles como inspiración que como mecanismo de implementación directa. Aquí, la mónada de continuación proporciona un modelo útil de cómo manejar ciertos tipos de cálculos, y con muchos aspectos adicionales asíncronos específicos, la idea central se puede usar para implementar cálculos asincrónicos.

Creo que esto es bastante diferente de cómo se usan las mónadas en obras académicas clásicas o en Haskell, donde tienden a ser utilizadas "tal como están" y tal vez compuestas de varias maneras para construir mónadas más complejas que capturan comportamientos más complejos.

Esta puede ser solo mi opinión personal, pero diría que la mónada de continuación no es prácticamente útil en sí misma, pero es una base para algunas ideas muy prácticas. (Al igual que el cálculo lambda no es realmente útil en sí mismo, ¡pero puede verse como una inspiración para buenos lenguajes prácticos!)

Answer 3

Ciertamente me resulta más fácil leer una función recursiva implementada utilizando la mónada de continuación en comparación con una implementada mediante recursión explícita. Por ejemplo, dado este tipo de árbol:

type ''a Tree = 
| Node of ''a * ''a Tree * ''a Tree
| Empty

aquí hay una forma de escribir un doblez de abajo hacia arriba sobre un árbol:

let rec fold e f t = cont {
    match t with
    | Node(a,t1,t2) ->
        let! r1 = fold e f t1
        let! r2 = fold e f t2
        return f a r1 r2
    | Empty -> return e
}

Esto es claramente análogo a un doblez ingenuo:

let rec fold e f t =
    match t with
    | Node(a,t1,t2) ->
        let r1 = fold e f t1
        let r2 = fold e f t2
        f a r1 r2
    | Empty -> return e

excepto que el pliegue naif volará la pila cuando se llame a un árbol profundo porque no es cola recursiva, mientras que el pliegue escrito usando la mónada de continuación no lo hará. Por supuesto, puede escribir lo mismo utilizando continuaciones explícitas, pero a mi juicio la cantidad de desorden que agregan distrae de la estructura del algoritmo (y ponerlos en su lugar no es completamente infalible):

let rec fold e f t k = 
    match t with
    | Node(a,t1,t2) -> 
        fold e f t1 (fun r1 ->
        fold e f t2 (fun r2 ->
        k (f r1 r2)))
    | Empty -> k e

Tenga en cuenta que para que esto funcione, deberá modificar su definición de ContinuationMonad para incluir

member this.Delay f v = f () v