Converti in CPS (Continuous Passing Style)

Question

Come si convertono queste procedure in Schema in modulo CPS?

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)) 
   

* Questo non è un qualsiasi lavoro!

Answer 1

Vedere Programming Languages, Application and Interpretation, iniziare intorno al Capitolo 15. Il capitolo 18 parla di come farlo automaticamente, ma se non si ha familiarità con l'idea di esprimere una funzione che fa "cosa fare dopo", probabilmente si vorrà prova prima gli esercizi per le dita.

Non fare in modo che qualcuno lo faccia per voi: vorrete davvero capire il processo ed essere in grado di farlo a mano, indipendentemente dallo Schema o altro. Si tratta in particolare della programmazione web JavaScript asincrona, in cui non hai davvero altra scelta che fare la trasformazione.

---

Nei CPS trasformano, tutte le funzioni non primitive hanno bisogno di consumare ora una funzione che rappresenta "what-to-do-next". Questo include tutti i lambda. Simmetricamente, qualsiasi applicazione di una funzione non primitiva deve fornire una funzione "what-to-do-next" e riempire il resto del calcolo in quella funzione.

Quindi, se abbiamo avuto un programma per calcolare ipotenusa di un triangolo:

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

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

e se affermiamo che le uniche applicazioni primitive qui sono *, +, e sqrt, poi tutti gli altri definizioni di funzioni e chiamate di funzione devono essere tradotte, come questo:

(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))) 

l'ultima espressione mostra che si finisce per dover calcolare "dentro-fuori", e che la trasformazione è diffuso: tutti lambda nel programma sorgente originale si finisce per dover prendere un argomento addizionale, e tutte le applicazioni non primitive devono inserire "what-to-do-next" come argomento.

Dare un'occhiata alla sezione 17.2 del libro citato: copre questo, nonché il 17.5, che parla del motivo per cui è necessario toccare TUTTI i lambda nel programma sorgente, in modo che anche il caso di ordine superiore funzioni .

---

Come altro esempio della trasformazione, applicato per un caso di ordine superiore, diciamo che abbiamo:

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

Poi la traduzione di qualcosa di simile a questo è:

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

... perché quel lambda è solo un valore che può essere passato a k1. Ma naturalmente, la traduzione deve passare anche attraverso il lambda.

Dobbiamo prima effettuare la chiamata interna a f con x (e ricordare che tutte le applicazioni di funzione non primitive devono passare un appropriato "what-to-do-next!"):

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

... prendere quel valore e applicare di nuovo per f ...

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

... e, infine, tornare a quel valore 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))))) 

Answer 2

Devi scegliere a quale livello ti serve/vuoi trasformare CPS

Se vuoi solo (lambda (x y) ((x x) y)) in continuati in transito (CP), quindi (lambda (k x y) (k ((x x) y))) andrà bene.

Se si desidera che i suoi argomenti vengano trattati anche in stile CP, è necessario un po 'di più.

Supponiamo prima che solo il secondo argomento (y) è in forma CP e quindi è davvero qualcosa di simile (lambda (k) (k y0)) e così deve essere chiamato con una certa continuità per estrarre il suo valore, allora si avrebbe bisogno:

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

Supponiamo infine che sia x sia siano in stile CP. Poi si avrebbe bisogno di qualcosa di simile a:

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

Qui si ha la libertà di riordinare le chiamate a x e y. O forse hai solo bisogno di una chiamata a x, perché sai che il suo valore non dipende dalla continuazione con cui è chiamato. Ad esempio:

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

Le altre espressioni che hai chiesto possono essere trasformate in modo simile.