scheme - ¿Por qué la continuación pasa estilo?

continuations continuation-passing

Question

En la sección 3.4 de The Scheme Programming Language de Kent Dybvig (4ª edición), describe muy claramente qué es el estilo de paso de continuación. Por el porqué da dos razones:

1. pasar más de un resultado a su continuación, porque el procedimiento que implementa la continuación puede tomar cualquier número de argumentos.
2. CPS también permite un procedimiento para tomar continuaciones separadas ..., que pueden aceptar diferentes números de argumentos.

Ya que la primera razón también se puede hacer usando el procedimiento de values y la segunda usando case-lambda , no estoy claro las ventajas de usar el estilo de paso de continuación. ¿Podría alguien mostrarme algunos ejemplos de dónde es apropiado el estilo de paso de continuación, donde hace que el código sea mejor, más claro, etc.?

Answer 1

Dado que la primera razón también se puede hacer usando el procedimiento de valores y la segunda usando case-lambda, no estoy claro las ventajas de usar el estilo de paso de continuación.

... excepto que la definición de values especifica que llama a su continuación con múltiples argumentos.

Mi ejemplo favorito de un problema en el que el estilo de paso de continuación es útil es escribir coincidencias de patrones. Este es un tipo de macro que es como un case de esteroides; toma un valor e intenta hacer coincidir su estructura con una secuencia de patrones creados a partir de pares, símbolos (representando variables) y átomos que no son símbolos (representando valores). Si una coincidencia tiene éxito, entonces vincula los identificadores en el patrón a las subpartes correspondientes del valor, y ejecuta un consecuente para ese patrón. Si falla, entonces intenta el siguiente patrón.

Es bastante sencillo escribir este tipo de macro en una forma de estilo de paso de continuación, usando dos continuaciones diferentes para representar "qué hacer si una coincidencia tiene éxito" (la continuación del éxito) y "qué hacer si falla una coincidencia" (el fallo continuaciones).

Tome este fragmento (simplificado) de una macro de coincidencia de patrones que escribí una vez (pido disculpas si no conoce el caso de sintaxis o las reglas de sintaxis; y como lo adapté sobre la marcha, espero que también funcione) Me centraré en la regla que coincide con un patrón de pares. Este es un patrón que consiste en un par de dos patrones, un patrón de cabeza y un patrón de cola; coincide con los pares cuya cabeza coincide con el patrón de la cabeza y cuya cola coincide con el patrón de la cola.

;;;
;;; Outer "driver" macro; the meat is in pmatch-expand-pattern.
;;;
(define-syntax pmatch
  (syntax-rules ()
    ((pmatch value-expr (pattern . exprs) . clauses)
     (let* ((value value-expr)
            (try-next-clause
             (lambda () (pmatch value . clauses))))
       (pmatch-expand-pattern pattern
                              value
                              ;; success-k
                              (begin . exprs)
                              ;; failure-k
                              (try-next-clause))))))

(define-syntax pmatch-expand-pattern
  (lambda (stx)
    (syntax-case stx ()

      ;; Cases for constants and quoted symbols omitted, but they''re trivial.

      ;; Match a pair pattern.  Note that failure-k is expanded three times; 
      ;; that''s why pmatch encapsulates its expansion inside a thunk!
      ((pmatch-expand-pattern (head-pat . tail-pat) value success-k failure-k)
       (syntax
        (if (pair? value)
            (pmatch-expand-pattern head-pat 
                                   (car value)
                                   ;; If we successfully match the head, then
                                   ;; the success continuation is a recursive
                                   ;; attempt to match the tail...
                                   (pmatch-expand-pattern tail-pat
                                                          (cdr value)
                                                          success-k 
                                                          failure-k)
                                   failure-k))
            failure-k))

      ;; Match an identifier pattern.  Always succeeds, binds identifier
      ;; to value
      ((pmatch-expand-pattern identifier value success-k failure-k)
       (identifier? (syntax identifier))
       (syntax (let ((identifier value)) success-k)))
      )))

Tenga en cuenta los pmatch-expand-pattern success-k y failure-k en las expresiones de macro pmatch-expand-pattern . Estos representan expresiones que se están utilizando como la "continuación", en un término ligeramente suelto, para el patrón de coincidencia. La continuación del éxito se utiliza cuando el patrón en consideración coincide con el valor en consideración; la continuación del fallo se utiliza cuando no lo hace. La continuación del éxito es, dependiendo de si hemos igualado todo el patrón de nivel superior actual hasta el momento, ya sea una expresión que coincidirá con el resto del patrón, o el consecuente que ejecutamos cuando un patrón termina de coincidir. Las continuaciones de falla se utilizan cuando un patrón no coincide, para retroceder al siguiente punto de elección.

Como mencioné, el término "continuación" se está usando un poco en general en el código anterior, ya que estamos usando expresiones como continuaciones. Pero esto es solo un detalle sobre cómo implementar esto como una macro: el algoritmo podría implementarse únicamente en tiempo de ejecución con procedimientos reales como las continuaciones. (Además, los procedimientos try-next-clause son continuaciones en el sentido literal).

Answer 2

Dybvig usa las continuaciones explícitas en esta sección para motivar tener call/cc como parte del lenguaje. El punto principal se hace cerca del final de la sección cuando menciona que escribir código sin él requiere una transformación global de todo el código que se utiliza, incluidas las funciones a las que llama. Por lo tanto, en Scheme usualmente construyes tu propia construcción usando macros, y las continuaciones son una de estas construcciones útiles, pero no puedes implementarlas a través de macros ya que solo implementan transformaciones locales.

Pero usar un estilo CPS directamente puede ser útil: por ejemplo, como él menciona, puede escribir una función que tenga más de una continuación, posiblemente con diferentes arrities, como una función de análisis que recibe una función de entrada única para enviar un analiza el valor y una función de fallo nulo a la que llamar cuando falla el análisis (y esta función podría abortar con un error o retroceder e intentar usar otras reglas de análisis). Otro uso posible es cuando desea controlar exactamente qué incluye la continuación en lugar de dejar que call/cc capture el contexto completo.

También existe el caso obvio de escribir código en un idioma que no tiene una continuación de primera clase, lo que hace que el código CPSed sea su única opción. Un ejemplo de eso sería un montón de programas node.js que usan IO y que te obligan a escribir código en CPS explícito.