for/continue in scheme/lisp

Question

I'm writing a small interpreter for a C-like language in Scheme (R5RS) and trying to convert something like:

for (i = 0; i < 100; i++)
{
    if (isprime(i)) continue;
    else /* do something with i */
}

to valid Scheme (the isprime function is just an example and not important).

However, after trying for some time, I have not been able to find an efficient/simple way to add the equivalent of a continue statement to a do loop in Scheme. What would be even better would be a "for" macro which allows "continue" and "break" to be used.

I'm considering switching to Common Lisp. Would this sort of thing be any easier in CL?

Rabelaisian

Answer 1

We can write FOR as a macro. The Common Lisp version:

(defmacro for ((var start end) &body body)
  (let ((block-name (gensym "BLOCK")))
    `(loop for ,var from ,start below ,end
           do (block ,block-name
                (flet ((continue ()
                         (return-from ,block-name)))
                  ,@body)))))


CL-USER 2 > (for (i 10 20)
              (if (evenp i) (continue))
              (print i))

11 
13 
15 
17 
19 

Plank

Answer 2

CL's tagbody is a convenient target:

(let (i)
  (tagbody
     (setf i 0)
   body
     (if (isprime i)
         (go increment))
     (do-something-with i)
   increment
     (setf i (1+ i))
     (if (< i 100)
         (go body))))

Hertel

Ah, Lisp looks like it has some potential! – Rabelaisian

Answer 3

I'd go for continuations like in this pseudo-scheme example.

Just store the current point of execution in a continuation and call it when appropriate.

(call/cc (lambda break ; jump outside the for
  (for 0 100 (lambda i 
    (call/cc (lambda continue ; jump to the next iteration
      (if (isprime i)
        (continue)
        (break))))))))

Daredeviltry

I assumed that it would be a call/cc (which works fine for break), but why does this perform the increment when you do a continue? Also, I assume this is quite inefficient, as it must surely set a continuation every iteration of the loop. – Rabelaisian

Continue basically just skips the rest of the loop's body, which is exactly what my construct does. The jump does not interfere with the loop itself at all, thus incrementing will happen afterwards. I don't have data concerning efficiency, though your guess might be right. Just try out. – Daredeviltry

what is for? No for here... what is it? – Mercer

Answer 4

I know this is 8 years late, but I thought it might help someone.

Using the iterate construct in Common Lisp, you could use the next-iteration clause:

(iter (for i from 0 to 100) 
  (if (isprime i)
      (next-iteration)
      (do-something-else)))

Salk

Unfortunately iterate is not part of the Common Lisp standard, but available as an external library only, e.g. via quicklisp. – Antimonic

Answer 5

The straightforward Scheme way to achieve this is just to restructure your code:

for (i = 0; i < 100; i++)
{
    if (isprime(i)) continue;
    if (is_bad(i)) break;
    else /* do something with i */
}

is

(let loop ((i 0))
  (cond
     ((isprime i)       ;; continue the loop
         (loop (+ i 1))) 
     ((is_bad i)
         #f)            ;; break from the loop
     (else              ;; do something with i
         .......        ;; and then continue the loop
         (loop (+ i 1)))))

If your loop body is tangled and you want to (continue) or (break) from deep inside its nested structure, either have your compiler restructure it in the above way, or you could set up exit points with call/cc as e.g.

(call/cc (lambda (break)
  (let loop ((i 0))
    (call/cc (lambda (continue)
        ;; your loop logic here, 
        ;; potentially using
        ;;    (continue A)     ;; A is ignored
        ;; or
        ;;    (break B)        ;; B is immediately returned as
        ;;                     ;;   the overall loop's result
        ))
    ;; (continue _) continues here:
    (loop (+ i 1)))))

Racket has delimited continuations which should be more efficient.

Mercer

Answer 6

To implement this particular code sample in Scheme, you don't need continue, break or call/cc:

(let loop ((i 0))
  (when (< i 100)
      (if (prime? i)
          (loop (add1 i)))
      (do-something-else)))

Seaboard

Unfortunately I can't find the "when" form in the R5RS standard. Assuming it does what I think, does this code work. Let's suppose it does the continue by calling the loop. What happens when it finishes the call to loop? Does it then continue on and finish off the body, i.e. execute one more (do-something-else)? Surely this solution only works if the (loop (add1 i)) is a tail call? Or am I misunderstanding how named let works? – Rabelaisian

Yes of course you can find a workaround in most particular cases (which I even consider preferable in functional style). The OP though asks for a general solution, where break/continue are already in use. – Daredeviltry

Actually, this does lead to a solution, I think. See example below. – Rabelaisian

@Rabelaisian you can replace when with if. – Seaboard

Is not when a looping structure, whereas if is execute-once? Would not when be closer to while or loop - if? – Coaster

Answer 7

I think Vijay's answer can be extended in a way that works (sorry for answering my own question, but can't figure out how to format code in a comment):

(let loop ((i 0))
    (define (next)
      (loop (+ i 1)))
    (call/cc 
      (lambda (break)
        (if (< i 100)
         (begin
           (if (isprime i)
             (next)
             (begin
               (if (isbad i)
                 (break break))
               (do-something)
               (next))))))))

It's not a macro, but doubtlessly leads to one that's general enough. I'd be interested to see any improvements. I'm pretty new to Scheme.

Rabelaisian

Answer 8

You can use throw and catch as well (elisp):

(let ((j 0))
  (while (< j 10)
    (catch 'continue
      (setq j (1+ j))
      (if (= j 3) (throw 'continue t))
      (prin1 j))))

1245678910nil

Dyeline