Wednesday, October 31, 2012

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.