=====================[ Readings ]===================== Read Chapter 20 of OnLisp. Focus on the Scheme DFT example in 20.1 and step through it by adding debug prints throughout the code, until you understand how it works. You will need a working Scheme set-up for this (see below). Ch. 20.2 explains how continuations can be approximated in LISP. This approximation is neither complete nor first-class, but stepping though it is quite useful as well. Remember, there are several levels of understanding continuations: 1. What will this code even do? (see examples from today) 2. How to use this in a program? 3. How to implement it in an interpreter, so that it works as specified, regardless of efficiency? 4. How to implement it efficiently in a compiler? (4) has been the subject of much research in PL. So to understand why it was given such attention, here's a somewhat hand-wavy explanation: =====================[ Why Continuations? ]===================== Continuations and the continuation-passing style of writing programs belong to the key concepts of functional programming. Just as closures provide a neat way to deal with variable scoping and data dependencies of functions, continuations help deal with the control flow in a rigorous, functional way. Your programming intuition would probably support the idea that mixing together code that serves different purposes makes programs harder to read. For example, peppering your C code with checking the return values of every systems function or system call is necessary---e.g., trying to write to a file your program failed to open makes no sense---but it's tedious to both read and write. Similarly, when you need to walk a data structure such as a tree, and do something with its elements, you want to keep the code that walks the data to get you the next element separate from the code that works on these elements. Although there are design patterns that help you to separate the walk from the processing---such as the Visitor pattern---most of the time you just want to call a "get me the next element" method repeatedly. Handling the code that mixes the walk and the per-element logic is tedious and error-prone, and much of Object-oriented programming is all about making it less so (at the cost of additional complexity---just look at the C++ Standard Library). These tedium and propensity for error come from having to continually switch between code meant to do different things, such as interact with the OS and handle errors, or deal with the internals of a collection and with its elements, and so on. Programming languages offer various solutions to keeping the code that addresses different concerns conveniently apart. Among these are: exception handling, generators, (co-operative) threading, co-routines, etc. Yet each of these introduces new mechanisms that make reasoning about functions and state more difficult---which is exactly the kind of complexity functional programming tries to avoid, by _reducing_ state and various control flow mechanisms to function calls and closures. So this is where continuations come in, and why they are so important in the grand scheme of things. They give a rigorous, functional method of passing control non-locally, between functions, to relevant pieces of code otherwise kept conveniently apart---while not going far beyond first-class functions (think lambdas and closures). For an overview of what continuations can do, read Matt Might's http://matt.might.net/articles/programming-with-continuations--exceptions-backtracking-search-threads-generators-coroutines/ [UPDATE:] The AMB example from this post is solved below. Don't worry if you cannot see how to implement all these things---this is our topic for Thursday :) You can see code that uses continuations to implement a loop in scheme/cont-loop.scm and something like a break or an exception in scheme/cont-break.scm (you need Guile to run it, though---WHILE is absent from MIT's Scheme). More examples from class: scheme/cont-frozen.scm scheme/cont-might-examples.scm scheme/cont-dft.scm scheme/cont-loop.scm scheme/cont-break.scm and another one: scheme/cont-list-iter.scm =====================[ How to read code with CALL/CC ]===================== Note that defining continuations in Scheme is much easier than, say, for C or even Ruby. In Scheme (and LISP) both whole programs and any of their parts _are_ s-expressions. So taking any s-expression inside a program and inserting a CALL/CC there makes it perfectly clear just where execution will resume when the continuation made by that call/cc returns there---if it's ever called, of course. If it does get called, this sexp will be replaced with whatever argument that call is given, while the rest about the containing sexp will be exactly as it was at the moment of evaluating CALL/CC: the local variables and the stack. Namely, that argument will simply replace the (call/cc ...) node of the s-expression, and the execution will continue when the closure _and the same stack_ as of the moment CALL/CC was called. It may sound like time-travel, and it is in the same sense as cryogenic sleep is, except it's every relevant aspect of the environment that is frozen and brought forward---whereas the value placed in this restored program is itself new, replacing what (call/cc ..) originally returned without the unfrozen world knowing. On the other hand, you will be discarding whatever stack and whatever environment that you called the continuation _from_. This is also like time-travel: once you unfreeze a previously saved world and go there, your pending future will not happen. The beauty of this is, you can freeze and save many copies of the world, including inside each other, and in "global" variables that are not a part of the game. Compare the behavior of (+ 1 (frozen 'safely)) from the OnLisp example, and the behavior of the (dft-node ) (restart) ... example for the pair of trees later in OnLisp's 20.1. You will find these examples in scheme/cont-frozen.scm and scheme/cont-dft.scm The continuation in _frozen_ was created before (+ 1 ..), from under (append (list ...)), and will return there, discarding (+ 1 ..) and landing back inside (append (list ..)), as LIST's argument. The timeline of (+ 1 ..)---with its pending type error from trying to add a number and a list---gets discarded, the error never happens. This is not unlike getting away from code that caused an exception (and would likely cause errors if continued) to a "safe" piece of code in 'catch'. On the other hand, in the example of (let ((node1 (dft-node t1))) (if (eq? node1 'done) 'done (list node1 (dft-node t2)))) the calls to CALL/CC happen *inside* dft-node, and thus capture everything outside them: the call to LIST that makes the pairs, the EQ? check, and even---for the internal call to dft-node---the state of the other dft-node call. That's why these continuations, when popped from *saved*, print the _pairs of values_ from the respective trees T1 and T2, creating an iterator over the pair of trees. Thus we created an iterator with no more work than describing how we build just one pair of node values! The rest happens automagically. [UPDATE:] ===========[ Logical Programming/Search with Call/CC ]====== Matt Might's AMB search example, solved, is in scheme/amb.scm It turns out that the list iterator is exactly what's needed! See comments in the code and observe the sequence in which continuations are stacked and executed. For the third variable, c, continuations nest three deep, and the "frozen world" includes two other continuations! It's very important to understand this example. The search there iterates over the direct product of the three lists (i.e., the set of all ordered triples). The looping---till a solution is found---is implicit in the use of the *saved* queue for continuations. Suggestion: implement the SAT solver example from Matt Mights' blogpost. Suggestion: implement a similar search in Ruby. Suggestion: implement other patterns discussed in the post. =====================[ Running Scheme ]===================== I tried several combinations of various Scheme implementations with my Emacs. This is what I found workable: 1. MIT Scheme + Emacs's built-in scheme-mode. This is pretty basic and lacks tab-completion, doc string hints, and other things I am used to with LISP, but it's workable: Open an .scm file, and you'll get the scheme-mode (or do M-x scheme-mode). Then do M-x run-scheme . If you have a scheme executable in your path, it will get launched. Then you can edit your program in one buffer and then feed its sexps to the scheme process in the other buffer with C-x C-e. MIT scheme is mit-scheme in MacPorts ("port install mit-scheme"). More on running Scheme: http://www-users.cs.umn.edu/~gini/1901-07s/emacs_scheme/ https://courses.cs.washington.edu/courses/cse341/common/help/mit-scheme.html (also, see "Finally, ..." below.) 2. Another option gives you tab completion (with ESC-TAB), auto doc hints for functions, and other nice features. For this, get the Guile dialect of Scheme ("port install guile") and the Geiser mode for Emacs, http://www.nongnu.org/geiser/ . Geiser's page on installing it is long, but I just got the tarball from http://download-mirror.savannah.gnu.org/releases/geiser/0.8.1/geiser-0.8.1.tar.gz, untarred it in my scheme directory, and did "emacs -l ./geiser-0.8.1/geiser.el" to start Emacs in geiser-mode, then did "M-x run-guile" to start my Guile scheme process. More on Geiser: http://www.nongnu.org/geiser/geiser_3.html#The-REPL It's a rich environment, in which I mostly use just tab-completion, command history, and doc hints. Finally, MIT Scheme's insistence on me typing "(restart 1)" every time to get out of the debugger annoyed me. So I bound my "C-x C-a" key sequence to "jump to the other buffer, insert that command there and press return, then get back", like this: ;;; Put this into your .emacs for mit scheme hack ;; macro to switch buffers and paste a key to the other buffer (defun foo () (interactive) (execute-kbd-macro (kbd "C-x o")) ; switch to the other buffer (insert "(restart 1)") ; spit out this (execute-kbd-macro (kbd "RET")) ; and make like RET is pushed (execute-kbd-macro (kbd "C-x o")) ; and switch again ) ;; bind it to key (global-set-key (kbd "C-x C-a") 'foo) ;;; end mit-scheme hack Also useful: To adjust split windows: "C-x ^" or "M-x enlarge-window"/"M-x shrink-window" http://ergoemacs.org/emacs/emacs_winner_mode.html =====================[ Continuations in Ruby ]===================== Ruby has continuations (just like it also has closures), although you need to add require "continuations" to use them. In recent versions, ruby's been deprecating them in favor of "Fibers", but they are still usable till v. 2.3 (at least). [UPDATE:] See examples cont1.rb--cont4.rb in the ruby/ directory. A good one with a few basic examples: http://liufengyun.chaos-lab.com/prog/2013/10/23/continuation-in-ruby.html Suggestion: Write the loop example and the DFT example in Ruby. More blogposts: http://deadprogrammersociety.blogspot.com/2007/02/ruby-blocks-closures-and-continuations.html http://blog.ontoillogical.com/blog/2014/07/12/delimited-continuations-in-ruby/ http://blog.ontoillogical.com/blog/2014/07/21/delimited-continuations-in-ruby-part-2/ http://gnuu.org/2009/03/21/demystifying-continuations-in-ruby/ -- Too informal for my taste, but might help you anyway.