Ruby Style Continuations In Lisp

A few days ago I found out Ruby supported continuations. I started playing with them in an experiment to be detailed later. One of the things Ruby has over Lisp is an understandable syntax for them. In Lisp all I had was Paul Graham's continuation code from his Lisp book:

(setq *cont* #'identity)

(defmacro =lambda (params &body body)
  `#'(lambda (*cont* ,@params) ,@body))

(defmacro =defun (name params &body body)
  (let ((f (intern (concatenate 'string
				"=" (symbol-name name)))))
    `(progn
      (defmacro ,name ,params
	`(,',f *cont* ,,@params))
      (defun ,f (*cont* ,@params) ,@body))))

(defmacro =bind (params expr &body body)
  `(let ((*cont* #'(lambda ,params ,@body))) ,expr))

(defmacro =values (&rest retvals)
  `(funcall *cont* ,@retvals))

(defmacro =funcall (fn &rest args)
  `(funcall ,fn *cont* ,@args))

(defmacro =apply (fn &rest args)
  `(apply ,fn *cont* ,@args))

PG also provided some examples using that. One of them was a depth first traversal. It creates the continuation when it pushes a lambda. The syntax basically offers no help in understanding how to use it as you can see:

(setq *saved* nil)

(=defun dft-node (tree)
  (cond ((null tree) (dft-restart))
	((atom tree) (=values tree))
	(t (push #'(lambda () (dft-node (cdr tree)))
		 *saved*)
	   (dft-node (car tree)))))

(=defun dft-restart ()
  (if *saved*
      (funcall (pop *saved*))
      (=values 'done)))

(=defun dft2 (tree)
  (setq *saved* nil)
  (=bind (node) (dft-node tree)
    (cond ((eq node 'done) (=values nil))
	  (t (princ node)
	     (dft-restart)))))

Even with that example, I still couldn't wrap my head around it until I started playing with Ruby's. Ruby has a callcc keyword that creates a continuation. It's syntax is basically:

callcc do |cc|
   # Do some stuff
end
# Do some other stuff when we call 'cc' above

That syntax makes it pretty easy to understand how to use them which is all that matters. PG's example code offered nothing in that direction, so I recreated PG's DFT example in Ruby and got the following:

$conts = Array.new

def dft_restart()
  if $conts.length > 0
    $conts.pop.call
    return nil
  end
end

def dft_node(tree)
  if tree == nil
    dft_restart
  elsif tree.class != Array
    return tree
  else
    callcc do |cc|
      $conts.push cc
      return dft_node(tree[0])
    end
    return dft_node(tree[1, tree.length])
  end
end    

def dft2 tree
  $conts = Array.new
  node = dft_node tree
  if node != nil
    puts node
    dft_restart
  end
end

Ruby's callcc helped me understand exactly what was going on. So I started messing around and created a macro that creates Ruby's callcc in Lisp. This is the macro:

;; Ruby style syntax
(defun search-replace (list key value)
  "Replace all instances of KEY found in LIST with VALUE."
  (cond ((null list) nil)
	((symbolp list) (if (eq list key) value list))
	((atom list) list)
	(t (cons (search-replace (car list) key value)
		 (search-replace (cdr list) key value)))))

(defmacro callcc (inner &body body)
  (let ((var-name (first inner))
	(var-exp `#'(lambda () ,@body)))
    `(progn ,@(search-replace (cdr inner) var-name var-exp))))

The syntax for that is essentially like Ruby's:

(callcc (cc do some stuff)
   Do some more stuff when we call 'cc')

The cc variable name can be changed to whatever, and it represents the continuation that you can save to call later. So back in Lisp PG's DFT-NODE then becomes:

(=defun dft-node (tree)
  (cond ((null tree) (dft-restart))
	((atom tree) (=values tree))
	(t (callcc (cc
		    (push cc *saved*)
		    (dft-node (car tree)))
 	      (dft-node (cdr tree))))))

To me anyway that makes more sense because the voodoo isn't up front. It's tucked into the callcc. To you innocent bystanders, it probably still makes no sense, but now you have some code to play with.