如何將Scheme中的這些過程轉換爲CPS形式?轉換爲CPS(延續傳遞樣式)
(lambda (x y) ((x x) y))
(lambda (x) (lambda (f) (f (lambda (y) (((x x) f) y))))
((lambda (x) (x x) (lambda (x) (x x))
*這不是任何的功課!
如何將Scheme中的這些過程轉換爲CPS形式?轉換爲CPS(延續傳遞樣式)
(lambda (x y)
((x x) y))
(lambda (x)
(lambda (f)
(f (lambda (y)
(((x x) f) y))))
((lambda (x) (x x)
(lambda (x) (x x))
*這不是任何的功課!
請參閱Programming Languages, Application and Interpretation,從第15章開始。第18章討論如何自動完成此操作,但如果您不熟悉如何表達一個執行「接下來要做什麼」的函數,您可能需要先嚐試手指練習。
沒有人爲你做:你真的想了解這個過程,並且能夠獨立於Scheme或其他方式手動完成。特別是在異步JavaScript網頁編程中,你真的別無選擇,只能進行轉換。
在CPS變換,所有非基本功能需要消耗現在表示「什麼對DO-未來」的功能。這包括所有的lambda。對稱地,非原始函數的任何應用都需要提供「下一步做什麼」的功能,並在該功能中填充其餘的計算。
所以,如果我們有一個程序來計算一個三角形的hypothenuse:
(define (hypo a b)
(define (square x) (* x x))
(define (add x y) (+ x y))
(sqrt (add (square a)
(square b))))
,如果我們規定只有原始應用這裏有*
,+
,並且sqrt
,那麼所有其他的函數定義和函數調用需要翻譯,像這樣:
(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)))
最後一個表達式表明,你最終不得不計算「由內向外」,並認爲轉型是很普遍的:所有的lambda表達式在原始源代碼程序中最終需要採取額外的參數,並且所有非原始應用程序都需要填充「下一步做什麼」作爲該參數。
仔細看看引用的書的第17.2節:它涵蓋了這個以及17.5,它講述了爲什麼你需要觸摸源程序中的所有lambda表達式,以便更高階的情況也起作用。
作爲另一個例子變換,應用於高階的情況下,讓我們說,我們有:
(define (twice f)
(lambda (x)
(f (f x))))
那麼的像這樣的翻譯是:
(define (twice/k f k1)
(k1 (lambda ...)))
...因爲這個lambda只是一個值,可以傳遞給。但是,當然,翻譯也需要貫穿lambda。
我們必須先對f
與x
進行內部調用(並記住所有非原始函數應用程序都需要傳遞適當的「下一步做什麼!「):
(define (twice/k f k1)
(k1 (lambda (x k2)
(f x (lambda (fx-val)
...)))))
...採取的價值,並再次應用它到f ...
(define (twice/k f k1)
(k1 (lambda (x k2)
(f x (lambda (fx-val)
(f fx-val ...))))))
...最後該值返回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)))))
你需要選擇你需要的水平/想要CPS轉換。
如果你只想(lambda (x y) ((x x) y))
in continuati傳球(CP)的風格,然後(lambda (k x y) (k ((x x) y)))
會做罰款。
如果您希望它的參數也被當作CP樣式,那麼您需要多一點。
首先假設只有第二個參數(y
)是CP的形式,因此真的像(lambda (k) (k y0))
,因此需要一些延續被調用,以提取其價值,那麼你將需要:
(lambda (k x y)
(y (lambda (y0) (k ((x x) y0)))))
最後假設x
和y
都是CP風格。那麼你就需要這樣的:
(lambda (k x y)
(x (lambda (x0)
(x (lambda (x1)
(y (lambda (y0)
(k ((x0 x1) y0))))))
在這裏,你可以自由地重新排序,以x
和y
呼叫。或者,也許你只需要撥打x
一個電話,因爲你知道它的價值並不取決於它被稱爲的延續。例如:
(lambda (k x y)
(y (lambda (y0)
(x (lambda (x0)
(k ((x0 x0) y0))))))
您詢問的其他表達式可以進行類似的轉換。
對不起,這不幫助我。 無論如何謝謝你的嘗試。 – 2012-02-02 16:11:06
你有什麼問題嗎?你知道如何將一個簡單的函數,如(lambda(x)(+ x 1))轉換爲CPS風格?這很難提供幫助,沒有心智模式來解決你陷入困境的問題。你是否閱讀過引用過的書中的那些章節,或者你沒有時間? – dyoo 2012-02-02 17:05:41
是的,我知道如何變換像(lambda(x)(+ x 1))這樣的簡單程序,但是如果'x'是一個程序本身呢? like(lambda(x)(x 1))?我確實需要改變每個用戶定義的過程嗎? – 2012-02-02 17:20:58