Konwertuj na CPS (kontynuacja stylu przekazywania)

Question

Jak mogę przekonwertować te procedury w schemacie na formularz 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)) 
   

* To nie jest jakaś praca domowa!

Answer 1

Zobacz Programming Languages, Application and Interpretation, zaczynając od rozdziału 15. Rozdział 18 mówi o tym, jak zrobić to automatycznie, ale jeśli nie jesteś zaznajomiony z myśleniem o wyrażaniu funkcji, która robi "co dalej", prawdopodobnie będziesz chciał spróbuj najpierw ćwiczeń palcem.

Nie pozwól, aby ktoś zrobił to za ciebie: naprawdę będziesz chciał zrozumieć proces i być w stanie zrobić to ręcznie, niezależnie od Planu lub w inny sposób. Pojawia się szczególnie w programowaniu w języku Asynchronicznym JavaScript, gdzie naprawdę nie masz innego wyboru, jak zrobić transformację.

---

W CPS przekształcić wszystkie non-prymitywne funkcje muszą teraz konsumować funkcję, która reprezentuje "co-to-do-next". Obejmuje to wszystkie lambdy. Symetrycznie, każda aplikacja funkcji nie-prymitywnej musi zapewniać funkcję "co do zrobienia dalej", a resztę obliczeń w tej funkcji.

Więc jeśli mieliśmy program do obliczania trójkąta hypothenuse:

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

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

i jeżeli stwierdzamy, że tylko prymitywne wnioski oto *, + i sqrt, to wszystkie inne definicje funkcji i wywołania funkcji muszą być tłumaczone, tak:

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

ostatni wyrażenie pokazuje, że kończy się konieczności obliczania „inside-out”, i że transformacja jest wszechobecna: wszystkie lambdy w źródłowym programie źródłowym wymaga dodatkowego argumentu, a wszystkie aplikacje niepochodzące z prymitywów muszą nazywać "co dalej" jako ten argument.

Przyjrzyj się dokładnie sekcji 17.2 cytowanej książki: obejmuje to, a także 17,5, która mówi o tym, dlaczego musisz dotknąć WSZYSTKICH lambd w programie źródłowym, aby przypadek wyższego rzędu działał .

---

Jako inny przykład transformacji, zastosowano dla przypadku wyższego rzędu, powiedzmy, że mamy:

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

Wtedy tłumaczenie coś takiego jest:

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

... ponieważ lambda to tylko wartość, którą można przekazać k1. Ale oczywiście tłumaczenie również musi przebiegać przez lambdę.

Najpierw musimy wykonać wewnętrzne połączenie z numerem f z x (pamiętajmy, że wszystkie niepochodzące z prymitywów aplikacje funkcyjne muszą przekazać odpowiednie "co dalej"!„):

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

... wziąć tę wartość i zastosować go ponownie do f ...

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

... i wreszcie powrócić tę wartość do 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

Musisz wybrać, do jakiego poziomu potrzebujesz/chcesz przekształcić CPS.

Jeśli chcesz tylko (lambda (x y) ((x x) y)) w kontynuacji on-passing (CP), a następnie (lambda (k x y) (k ((x x) y))) będzie dobrze.

Jeśli chcesz, aby jego argumenty były traktowane jako również w stylu CP, potrzebujesz trochę więcej.

Załóżmy najpierw, że dopiero drugi argument (y) jest w postaci CP, a zatem jest naprawdę coś (lambda (k) (k y0)) i tak musi być wywoływana z jakiejś kontynuacji wyodrębnić swoją wartość, wtedy trzeba:

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

Na koniec przyjmijmy, że zarówno x, jak i y są w stylu CP. Wtedy trzeba coś takiego:

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

Tutaj masz swobodę Aby zmienić kolejność połączeń na x i y. A może potrzebujesz tylko jednego połączenia z x, ponieważ wiesz, że jego wartość nie zależy od kontynuacji, z którą jest wywoływana. Na przykład:

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

Pozostałe wyrażenia Pytałeś o można przekształcić w podobny sposób.