How to implement redo statement (as in Perl and Ruby) in Lisp

Question

Code that requires break statements or continue statements in other languages can be done with block & return-from or catch & throw in Common Lisp and Emacs Lisp. Then there is code that requires redo statements, or at least best written with redo. And redo statements don't have to be about loops. How can I do redo in Lisp?

If there was a redo equivalent in Lisp, I think it would work like this: special form with-redo which takes a symbol and forms, and redo which takes a symbol. The form (with-redo 'foo BODY-FORMS...) may contain (redo 'foo) in its BODY-FORMS, and (redo 'foo) transfers control back to the beginning of BODY-FORMS.

Answer 1

In Common Lisp:

(tagbody
   start
   (do-something)
   (go start))


(dotimes (i some-list)
  redo
  (when (some-condition-p)
    (go redo))
  (some-more))

Answer 2

Rainer's answer illustrates the use of tagbody which is probably the easiest way to implement this kind of construct (a particular kind of goto, or unconditional jump). I thought it'd be nice to point out that if you don't want to use an explicit tagbody, or an implicit tagbody provided by one of the standard constructs, you can also create a with-redo just as you suggested. The only difference in this implementation is that we won't quote the tag, since they're not evaluted in tagbody, and being consistent with the other constructs is nice too.

(defmacro with-redo (name &body body)
  `(macrolet ((redo (name)
                `(go ,name)))
     (tagbody
        ,name
        ,@body)))

CL-USER> (let ((x 0))
           (with-redo beginning
             (print (incf x))
             (when (< x 3)
               (redo beginning))))
1 
2 
3 
; => NIL

Now this is actually a leaky abstraction, since the body could define other labels for the implicit tagbody, and could use go instead of redo, and so on. This might be desirable; lots of the built in iteration constructs (e.g., do, do*) use an implicit tagbody, so it might be OK. But, since you're also adding your own control flow operator, redo, you might want to make sure that it can only be used with tags defined by with-redo. In fact, while Perl's redo can be used with or without a label, Ruby's redo doesn't appear to allow a label. The label-less cases allow behavior of jumping back to the innermost enclosing loop (or, in our case, the innermost with-redo). We can address the leaky abstraction, as well as the ability to nest redos at the same time.

(defmacro with-redo (&body body)
  `(macrolet ((redo () `(go #1=#:hidden-label)))
     (tagbody
        #1#
        ((lambda () ,@body)))))

Here we've defined a tag for use with with-redo that other things shouldn't know about (and can't find out unless they macroexpand some with-redo forms, and we've wrapped the body in a lambda function, which means that, e.g., a symbol in the body is a form to be evaluated, not a tag for tagbody. Here's an example showing that redo jumps back to the nearest lexically enclosing with-redo:

CL-USER> (let ((i 0) (j 0))
           (with-redo
             (with-redo 
               (print (list i j))
               (when (< j 2)
                 (incf j)
                 (redo)))
             (when (< i 2)
               (incf i)
               (redo))))

(0 0) 
(0 1) 
(0 2) 
(1 2) 
(2 2) 
; => NIL

Of course, since you can define with-redo on your own, you can make the decisions about which design you want to adopt. Perhaps you like the idea of redo taking no arguments (and disguising a go with a secret label, but with-redo still being an implicit tagbody so that you can define other tags and jump to them with go; you can adapt the code here to do just that, too.

Some notes on implementation

This this answer has generated a few comments, I wanted to make a couple more notes about the implementation. Implementing with-redo with labels is pretty straightfoward, and I think that all the answers posted address it; the label-less case is a bit tricker.

First, the use of a local macrolet is a convenience that will get us warnings with redo is used outside of some lexically enclosing with-redo. E.g., in SBCL:

CL-USER> (defun redo-without-with-redo ()
           (redo))
; in: DEFUN REDO-WITHOUT-WITH-REDO
;     (REDO)
; 
; caught STYLE-WARNING:
;   undefined function: REDO

Second, the use of #1=#:hidden-label and #1# means that the go tag for redoing is an uninterned symbol (which lessens the likelihood that the abstraction leaks), but also is the same symbol across expansions of with-redo. In the following snippet tag1 and tag2 are the go-tags from two different expansions of with-redo.

(let* ((exp1 (macroexpand-1 '(with-redo 1 2 3)))
       (exp2 (macroexpand-1 '(with-redo a b c))))
  (destructuring-bind (ml bndgs (tb tag1 &rest rest)) exp1   ; tag1 is the go-tag
    (destructuring-bind (ml bndgs (tb tag2 &rest rest)) exp2
      (eq tag1 tag2))))
; => T

An alternative implementation of with-redo that uses a fresh gensym for each macroexpansion does not have this guarantee. For instance, consider with-redo-gensym:

(defmacro with-redo-gensym (&body body)
  (let ((tag (gensym "REDO-TAG-")))
    `(macrolet ((redo () `(go ,tag)))
       (tagbody 
          ,tag
          ((lambda () ,@body))))))

(let* ((exp1 (macroexpand-1 '(with-redo-gensym 1 2 3)))
       (exp2 (macroexpand-1 '(with-redo-gensym a b c))))
  (destructuring-bind (ml bndgs (tb tag1 &rest rest)) exp1
    (destructuring-bind (ml bndgs (tb tag2 &rest rest)) exp2
      (eq tag1 tag2))))
; => NIL

Now, it's worth asking whether this makes a practical difference, and if so, in which cases, and is it a difference for the better or the worse? Quite frankly, I'm not entirely sure.

If you were performing some complicated code manipulation after the inner macroexpansion of an (with-redo ...) form, form₁, so that (redo) has already been turned into (go #1#), it means that moving the (go #1#) into the body of another (with-redo ...) form, form₂, it will still have the effect of restarting an iteration in form₂. In my mind, this makes it more like a return that could be transported from a block b₁ into a different block b₂, with the only difference it now returns from b₂ instead of b₁. I think that this is desirable, since we're trying to treat label-less with-redo and redo as primitive control structures.