2012-02-02 6 views
7

¿Cómo convierto estos procedimientos en el esquema a formulario de CPS?Convertir a CPS (Continuing Passing Style)

  1. (lambda (x y) 
        ((x x) y)) 
    
  2. (lambda (x) 
        (lambda (f) 
        (f (lambda (y) 
         (((x x) f) y)))) 
    
  3. ((lambda (x) (x x) 
    (lambda (x) (x x)) 
    

* Esto no es ninguna tarea!

Respuesta

22

Consulte Programming Languages, Application and Interpretation, comenzando por el Capítulo 15. El Capítulo 18 explica cómo hacerlo automáticamente, pero si no está familiarizado con la idea de expresar una función que haga "qué hacer a continuación", es probable que desee prueba los ejercicios con los dedos primero.

No haga que alguien lo haga por usted: realmente querrá comprender el proceso y podrá hacerlo a mano, independientemente de Scheme o de otro modo. Aparece especialmente en la programación web Asynchronous JavaScript, donde realmente no tienes más remedio que hacer la transformación.


En la CPS transformada, todas las funciones no primitivos necesidad de consumir ahora una función que representa "lo-a-do-lado". Eso incluye todas las lambdas. Simétricamente, cualquier aplicación de una función no primitiva debe proporcionar una función "qué hacer para el próximo" y completar el resto del cálculo en esa función.

Así que si teníamos un programa para calcular la hipotenusa de un triángulo:

(define (hypo a b) 
    (define (square x) (* x x)) 
    (define (add x y) (+ x y)) 

    (sqrt (add (square a) 
      (square b)))) 

y si afirmamos que las únicas aplicaciones primitivas aquí están *, + y sqrt, entonces todas las otras definiciones de funciones y llamadas a funciones necesitan ser traducidas, como esto:

(define (hypo/k a b k) 
    (define (square/k x k) 
    (k (* x x))) 

    (define (add/k x y k) 
    (k (+ x y))) 

    (square/k a 
      (lambda (a^2) 
       (square/k b 
         (lambda (b^2) 
         (add/k a^2 b^2 
           (lambda (a^2+b^2) 
            (k (sqrt a^2+b^2))))))))) 

;; a small test of the function. 
(hypo/k 2 3 (lambda (result) (display result) (newline))) 

la última expresión muestra que acaban de tener que calcular "dentro-fuera", y que la transformación es un fenómeno generalizado: todos los lambdas en el programa de origen original terminan necesitando tomar un argumento adicional, y todas las aplicaciones no primitivas necesitan rellenar "qué hacer para después" como ese argumento.

Observe detenidamente la sección 17.2 del libro citado: cubre esto, al igual que 17.5, que explica por qué necesita tocar TODAS las lambdas en el programa de origen, para que el caso de orden superior funcione también .


Como otro ejemplo de la transformación, se aplica para un caso de orden superior, digamos que tenemos:

(define (twice f) 
    (lambda (x) 
    (f (f x)))) 

A continuación, la traducción de algo como esto es:

(define (twice/k f k1) 
    (k1 (lambda ...))) 

... porque ese lambda es solo un valor que se puede pasar a k1. Pero, por supuesto, la traducción también debe ejecutarse a través de la lambda.

Primero debemos hacer la llamada interna a f con x (y recuerde que todas las aplicaciones de funciones no primitivas deben pasar un "Qué hacer para después" apropiado!"):

(define (twice/k f k1) 
    (k1 (lambda (x k2) 
     (f x (lambda (fx-val) 
       ...))))) 

... tomar ese valor y aplicarlo nuevamente a f ...

(define (twice/k f k1) 
    (k1 (lambda (x k2) 
     (f x (lambda (fx-val) 
       (f fx-val ...)))))) 

... y finalmente el valor a k2:

(define (twice/k f k1) 
    (k1 (lambda (x k2) 
     (f x (lambda (fx-val) 
       (f fx-val k2)))))) 

;; test. Essentially, ((twice square) 7) 
(define (square/k x k) (k (* x x))) 
(twice/k square/k 
     (lambda (squaresquare) 
      (squaresquare 7 
         (lambda (seven^4) 
          (display seven^4) 
          (newline))))) 
+0

Lo siento, esto no me está ayudando. Gracias de todos modos por intentarlo. –

+1

¿Qué parte tienes problemas? ¿Sabes cómo transformar una función simple, como (lambda (x) (+ x 1)) al estilo de CPS? Es muy difícil de ayudar, sin un modelo mental de dónde te estás atascado. ¿Has revisado esos capítulos en el libro citado, o no tienes tiempo? – dyoo

+1

Sí, lo tengo, y sé cómo transformar procedimientos "simples" como (lambda (x) (+ x 1)), pero ¿y si la 'x' es un procedimiento en sí mismo? me gusta (lambda (x) (x 1))? Necesito transformar cada procedimiento definido por el usuario ¿no? –

0

Debe elegir a qué nivel necesita/desea transformar CPS.

Si solo desea (lambda (x y) ((x x) y)) en continuidad estilo al pasar (CP), entonces (lambda (k x y) (k ((x x) y))) funcionará bien.

Si desea que sus argumentos se consideren también en estilo CP, necesita un poco más.

Supongamos primero que el segundo argumento (y) está en forma CP y por lo tanto es realmente algo así como (lambda (k) (k y0)) y así tiene que ser llamado con cierta continuidad para extraer su valor, entonces usted tendría que:

(lambda (k x y) 
    (y (lambda (y0) (k ((x x) y0))))) 

Finalmente suponga que ambos x y y están en estilo CP. A continuación, se necesitaría algo así como:

(lambda (k x y) 
    (x (lambda (x0) 
     (x (lambda (x1) 
      (y (lambda (y0) 
       (k ((x0 x1) y0)))))) 

Aquí tiene la libertad de cambiar el orden de las llamadas a x y y. O tal vez solo necesite una llamada al x, porque sabe que su valor no depende de la continuación con la que se llama. Por ejemplo:

(lambda (k x y) 
    (y (lambda (y0) 
     (x (lambda (x0) 
      (k ((x0 x0) y0)))))) 

Las otras expresiones sobre las que ha preguntado se pueden transformar de manera similar.