========================[ Readings ]================================

In Chapter 8 of the Mitchell textbook, read 8.1 about the history of
control flow in programming languages, and 8.3 about continuations.

The following readings will help you understand the contributions of
the "Cheney on the M.T.A." paper I mentioned in class,
http://home.pipeline.com/~hbaker1/CheneyMTA.html), and will be good
to read if you have not thought about garbage collection before:
  - 3.4.8 in Mitchell, and then the discussion in 3.5--3.7
  - Mitchell's Chapter 7 does not talk much about garbage collection,
     but 7.2, 7.3, and 7.4 talks about (and draw!) the different
     structures that are closed over and must be garbage-collected.
    These structures should be familiar to you from the Ruby internals
    book ("Ruby under the microscope"), but, depending on your learning
    style, the more abstract style of examples may help.

A nice recording of the "Charley on the M.T.A." song is at
  https://www.youtube.com/watch?v=xsqBtZNBL60 
The M.B.T.A. has a web page about it, 
http://www.mbta.com/about_the_mbta/history/?id=19582
(note that charging extra for _exit_ is a terrible design idea---but
  it continues to be popular in various forms to this day)

=================[ Attacking the idea of stacks ]===================

Recursion is a much nicer way to traverse naturally recursive (or
"self-similar") objects than iteration with explicit loops.  An
explicit loop is easy to get wrong, e.g., by an off-by-one, and not
notice. With recursion, all you need is the right base case and a
proper deconstruction of the object (e.g., getting the CAR and the CDR
of a cons cell)---and if you get it wrong, infinite recursion is hard
to miss :)

The problem with recursion is that function calls normally mean
stack frames, and stack frames pile up without need. Tail-call
optimization (TCO) is one way to work around that problem, and
CALL/CC is another (and also allows you to do any other control
flow pattern, such as break, throw/catch, callbacks, generators,
co-routines, etc.---see http://matt.might.net/articles/programming-with-continuations--exceptions-backtracking-search-threads-generators-coroutines and our class notes on continuations
in LISP and Ruby. TCO can be applied to not just one recursive 
function, but to a pair of functions calling each other 
tail-recursively (f calls g, g calls f, so-called mutual recursion,
or indirect recursion). SBCL and some other LISPs do such full TCO;
GCL does not seem to (see examples in http://0branch.com/notes/tco-cl.html).

Yet there is a much more drastic way of getting rid of the stack
frames: the Continuation-Passing Style (CPS). 

=================[ Continuation-Passing Style ]=====================

Under CPS, _no_ function ever returns, just like Charlie on the M.T.A.
All calls are either inlined (such as simple functions like
+ or *, which get compiled to just an opcode or bytecode), or, as the
last thing they do, call the function passed to them as an extra
argument, the "continuation" (not the result of CALL/CC, just a
function).

Since no function never returns, the call does not need to save its
stack frame nor keep track of the return address. The compiler can
then either reuse the stack frame or deallocate it; the call itself
(passing control) can be compiled as a jump, not caring from where
it happened, but just where it goes.

You might ask, what good are functions that can never return? Can we
write any kind of programs we normally write with only such functions?
The answer is yes, and it can be done (and is done by optimizing
compilers behind the scenes) by an automatic transformation. 



The CPS is another important application of the continuations
idea---except in CPS you write all continuations explicitly, and pass
them explicitly. Under this style of programming, no function ever
"returns" its result. Instead, as the last thing it does, the function
feeds this result to a one-argument function that it gets from the
caller as an extra argument. This function argument represents the
continuation, "all the work from here on"---and often is a lambda,
especially if any additional work needs to be done; it wraps that
work. That function also never returns, etc.

A sequence of actions becomes a series of lambdas passed to each
other as continuations. This looks weird, but can be optimized 
really well after the transformation---in fact, a CPS rewrite
of normal code served as IR to many optimizing compilers.

Think of the program as being turned "inside-out". Normally, you write
the program from the first expressions you want executed to the last;
in LISP and Scheme, the s-expressions evaluated later contain---as
lists---those executed earlier. In CPS, it is as though you need to
start from the very last things you want done, and pass them as a
single-argument function to the things you want done just before, and
so on, to the very first things, which get the much-grown continuation
as an argument.

Paul Graham in 20.2 of OnLisp shows how such transformation can be
done in LISP, and says they should be left to automation. Matt Might,
however, points out that modern Javascript essentially uses CPS for
asynchronous web app event handling---see link below.

In class, we wrote several functions in CPS, from a simple example
of summing up a list and printing a function of the sum (that's three
functions and one identity (lambda (x) x)) to a recursive traversal
of an arbitrary tree. 

See scheme/cps-examples.scm for examples from class.

[Suggestion:] Write in CPS in Ruby. Write a shallow copy of a list
              and a deep copy of a tree in CPS.

=================[ CPS in LISP, CPS rewriting ]===============

Read OnLisp's section 20.2 to see how LISP functions can be rewritten
to use continuations *and* CPS with some clever macros.

These macros add the continuation argument to every function's
definition, and annotate every function's returned values with the
extra call to this argument (this needs to be done on each path
through which a function may return!).

With reasonable restrictions on how the functions are written,
the transformation to CPS is accomplished by these macros.

============[ CPS in Javascript, web programming ]============ 

See another of Matt Might's blog posts (skip the factorial example):

 http://matt.might.net/articles/by-example-continuation-passing-style/
 
about the use of CPS for non-blocking programming---in Javascript.

See also useful discussion here:
http://stackoverflow.com/questions/1888702/are-there-problems-that-cannot-be-written-using-tail-recursion