Continuation Passing Style(CPS) using Scheme

針對近期學習的Scheme中的Continuation Passing Style(CPS)查詢相關資料，做了筆記。

Resource:
http://en.wikibooks.org/wiki/Haskell/Continuation_passing_style
http://mainline.brynmawr.edu/cs245/cps.pdf
http://en.wikipedia.org/wiki/Continuation-passing_style

Definition:
Continuation Passing Style is a formed for expressions such that no function ever returns, instead they pass control onto a continuation.
or,
"A data structure represents what is left to do."

Features:

• return early
• exceptions and failure can be signalled
• pass in a continuation for success
• pass in another continuation for fail
• suspend

Why:

• CPS quickly fills the stack or has to be given hand-coded infrastructure in languages that don't support the automatic merging of unneeded stack frames.

To Complement:

• every function takes an extra argument, its continuation
• every argument in a function call must be either a variable or a lambda expression (not a more complex expression)

Note:

• There's no implicit continuation - every call  is a tail call.
• There's no magic there, every continuation is simply explicitly passed.
• For using CPS without tail call optimisation will cause not only the constructed continuation potentially grow during recursion, but also the call stack.

Another Topic, Call-with-current-continuation:

• Scheme allows the continuation of a computation to be captured by call/cc.
• (call/cc proc), where proc is a one-parameter function.
• (define get-back 'any), usage: (get-back k)
• (exit 0), escaping from deep recursion.

My Review:

Quite hard to read Scheme code especially with lots for function calls and recursion. This might because I am more familiar with basic imperative programming languages.