\documentclass{article}
\usepackage[utf8]{inputenc}
\usepackage{amsmath,amssymb,amsthm,pxfonts,listings,color}
\usepackage[colorlinks]{hyperref}
\definecolor{gray}{rgb}{0.6,0.6,0.6}

\usepackage{caption}
\DeclareCaptionFormat{listing}{\llap{\color{gray}#1\hspace{10pt}}\tt{}#3}
\captionsetup[lstlisting]{format=listing, singlelinecheck=false, margin=0pt, font={bf}}

\lstset{columns=fixed,basicstyle={\tt},numbers=left,firstnumber=auto,basewidth=0.5em,showstringspaces=false,numberstyle={\color{gray}\scriptsize}}

\newcommand{\Ref}[2]{\hyperref[#2]{#1 \ref*{#2}}}

\lstnewenvironment{asmcode}       {}{}
\lstnewenvironment{cppcode}       {\lstset{language=c++}}{}
\lstnewenvironment{javacode}      {\lstset{language=java}}{}
\lstnewenvironment{javascriptcode}{}{}
\lstnewenvironment{htmlcode}      {\lstset{language=html}}{}
\lstnewenvironment{perlcode}      {\lstset{language=perl}}{}
\lstnewenvironment{rubycode}      {\lstset{language=ruby}}{}

\lstnewenvironment{resourcecode}{}{}

\title{{\tt call/cc} in Ten Minutes}
\author{Spencer Tipping}

\begin{document}
\maketitle{}
\tableofcontents{}

\section{Introduction}
  I'm going to go off on an inexplicable tangent for a minute here, but I promise it has something to do with continuations.

  I was writing an ext4 filesystem driver recently and came across something I didn't expect. You know how you can say {\tt cd ..} to go up one directory? I always assumed this worked by
  removing a directory from your current location, sort of like returning from a function. But it doesn't work this way at all. Instead, every directory in ext4 actually has a {\em
  subdirectory} called {\tt ..} that you can {\tt cd} {\em into}. This special subdirectory points back to the parent of whichever directory you're in.\footnote{Each directory also has a
  subdirectory called {\tt .}, which points back to the current directory.}

  At first this made no sense to me because it meant that your path would just keep growing forever. But then I realized that programs don't store their path, they store only their current
  directory by its inode. This meant that it didn't matter how you got to a directory, it only mattered where you were and where you could go from there.\footnote{The path can be constructed
  after the fact by continuously {\tt cd}ing into {\tt ..} until the root is reached. Wild, huh?}

  So instead of a call stack working like this:

\begin{verbatim}
/           cd usr (add usr/)
/usr/       cd bin (add bin/)
/usr/bin/   cd ..  (remove bin/)
/usr/
\end{verbatim}

  \noindent it in fact works like this:

\begin{verbatim}
/             cd usr (follow usr/ pointer)
/usr/         cd bin (follow bin/ pointer)
/usr/bin/     cd ..  (follow ../ pointer)
/usr/bin/../
\end{verbatim}

  Now imagine that your path is like a function call stack. You {\tt cd} into a subdirectory, you do stuff, and you {\tt cd} back out of it. Logically this resembles a single function call,
  and if {\tt cd ..} were implemented as an ``undo'' of the last {\tt cd} it would indeed be a real stack. However, each {\tt cd} is doing the same thing: It's calling into a subdirectory of
  wherever you are. And this is exactly how continuations work.

\section{{\tt return}}
  If you've written code in any normal programming language like C, Java, Javascript,\footnote{Ok, Javascript isn't normal, but you get the idea.} etc, you've probably written the word {\tt
  return}. And further, you've probably used it to escape from a function earlier than you normally would. For instance:

\begin{verbatim}
var factorial = function (n) {
  if (n === 0) return 1;
  var result = factorial(n - 1);
  return n * result;
};
\end{verbatim}

  \noindent If the first {\tt return} is hit, the second one will never happen. So {\tt return} is really doing two things; it's setting up the value that the function will have, and it's
  jumping back to the parent function. The jump works because when we called into {\tt factorial}, we left the return address on the stack. {\tt return} doesn't really know where to go, it
  just goes to whichever address the caller specifies.

  Let's step back for a moment and think about a different interpretation of the word {\tt return}. What if it were a function? The call into {\tt factorial} is a jump, and the return from
  {\tt factorial} is also a jump (just like {\tt cd {\em directory}} and {\tt cd ..} are both jumps). Are they really the same thing?

  As it turns out, they are indeed.\footnote{With the exception of how state is saved, which I'll get to in a bit.} Here's the normal way you'd call {\tt factorial}:

\begin{verbatim}
alert('About to call factorial');
var x = factorial(5);
alert('The factorial of 5 is ' + x);
exit();     // Exits immediately and never returns.
\end{verbatim}

  \noindent And here's what it looks like when we model {\tt return} as a function:\footnote{My original {\tt factorial} definition was incorrect; thanks to Brian Ollenberger for submitting
  the correct version shown here.}

\begin{verbatim}
var factorial = function (n, ret) {
  if (n === 0) ret(1);
  factorial(n - 1, function (result) {
    ret(n * result);
  });
};

alert('About to call factorial');
factorial(5, function (value) {
  var x = value;
  alert('The factorial of 5 is ' + x);
  exit();   // Exits immediately and never returns.
});
\end{verbatim}

  {\em Todo:} explain the {\tt exit()} function.

\end{document}
