========================[ 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.

====================[ Additional reading ]==========================

"Cheney on the M.T.A." https://www.more-magic.net/posts/internals-gc.html
  (from https://news.ycombinator.com/item?id=12776198)

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. mentions this on their history page, search for "Charlie":
  https://www.mbta.com/history

(note that charging extra for _exit_ is a terrible design idea---but
  it continues to be popular in various forms to this day, cf. various "egress fees".
  Some even say that the price of the software product is determined by the cost of
  switching away from it.)

=================[ 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 fast and often needlessly, compared to the
loop-based iterations.

Tail-call optimization (TCO) is one way to work around that problem. Emacs
is later to the TCO game with named-let (emacs-version >= 29), but SBCL and
some other LISPs do full TCO, even applying it to pairs of functions
calling each other tail-recursively (f calls g, g calls f, so-called mutual
recursion, or indirect recursion). See examples in http://0branch.com/notes/tco-cl.html.

Another mechanism we mentioned today and will continue working through is CALL/CC.
For all its strangeness, CALL/CC is very general and can express any other control
flow pattern, such as break, throw/catch, callbacks, generators,
co-routines, etc. If you are curious, see
http://matt.might.net/articles/programming-with-continuations--exceptions-backtracking-search-threads-generators-coroutines 

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. (see
above).  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 to be confused with 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.

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 an
Intermediate Representation (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.

If this vaguely reminds you of function applications associating to the left
in lambda calculus, this is not incidental :)

Paul Graham in Chapter 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. 

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.

=================[ 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