return within dolist did not return

[k-okada]

* (dolist (var (list 1 2 3 4 5)) (if (eq var 3) (return var)))

3

 (dolist (var (list 1 2 3 4)) (if (eq var 3) (return var)))
nil

from @Affonso-Gui

[k-okada]

$ (dolist (var (list 1 2 3 4) var) (if (eq var 3) (return var)))
3

$ (block :dolist (dolist (var (list 1 2 3 4)) (if (eq var 3) (return-from :dolist var))))
3

[Affonso-Gui]

Could be solved by using do instead of while on dolist definition.

	(do ()
	    ((null ,lists) ,(caddr vars))

However, this would lead to inefficiency, and therefore is not recommended.

Before:
bench (dotimes (i 10000) (dolist (a '(1 2 3 4 5))))
;; time -> 0.279851[s]

After:
bench (dotimes (i 10000) (dolist (a '(1 2 3 4 5))))
;; time -> 0.380254[s]

Alternatively, we could check if while returned with non-nil values and return that in this case, which would do the job without major changes on efficiency.

       (or
        (while ... )
	,(caddr vars))

(dolist (var (list 1 2 3 4 5)) (if (eq var 3) (return var)))
;; -> 3

bench (dotimes (i 10000) (dolist (a '(1 2 3 4 5))))
;; time -> 0.293503[s]

However, this wouldn't work for cases like (return nil), and it's not very classy.

[furushchev]

In eus, dolist is expanded as follows:

2.eus$ (pprint (macroexpand '(dolist (i '(1 2 3)) (return t))))
(let
   ((i nil) (#:dolist60 '(1 2 3)))
   nil
   (while #:dolist60 (setq i (pop #:dolist60)) (return t))
   nil)

In sbcl, dolist is expanded as follows:

* (pprint (macroexpand '(dolist (i '(1 2 3)) (if (eq i 2) (return t)))))

(BLOCK NIL
  (LET ((#:N-LIST466 '(1 2 3)))
    (TAGBODY
     #:START467
      (UNLESS (ENDP #:N-LIST466)
	(LET ((I (TRULY-THE (MEMBER 3 2 1) (CAR #:N-LIST466))))
          (SETQ #:N-LIST466 (CDR #:N-LIST466))
          (TAGBODY
            (IF (EQ I 2)
		(RETURN T))))
	(GO #:START467))))

The original problem is that looping block is not returned as the return value of dolist.
Since we have both tagbody and go in euslisp, I think it is good chance to migrate to this implementation if there is no difference in performance.

how about if we implement like below?:

(block nil
  (let
     ((i nil) (#:dolist60 '(1 2 3)))
      nil
     (TAGBODY
     #:START467
      (UNLESS (ENDP #:dolist60)
       (setq i (pop #:dolist60))
            (IF (EQ I 2)
		(RETURN T))))
	(GO #:START467))))

[furushchev]

I wrote a simple script for comparison:

#!/usr/bin/env roseus
;; dolist-test.l                                                                                                   
;; Author: furushchev <[email protected]>                                                         

(defun iota (n)
  (let ((l (make-sequence cons n)))
    (dotimes (i n)
      (setf (elt l i) i))
    l))

(pprint (macroexpand '(dolist (i (iota 10000)))))
(bench (dolist (i (iota 10000))))
(dolist (i (iota 5)) (print i))

(defmacro dolist (vars &rest forms)
  (let ((lists (gensym "DOLIST"))
        (loop-tag (gensym "DOLIST"))
        (maybe-decl (car forms)))
    (if (and (consp maybe-decl) (eq (car maybe-decl) 'declare))
        (setq forms (cdr forms))
        (setq maybe-decl nil))
    `(block nil
       (let ((,(car vars) nil)
             (,lists ,(cadr vars)))
         ,maybe-decl
         (tagbody ,loop-tag
            (unless (endp ,lists)
              (setq ,(car vars) (pop ,lists))
              ,@forms
              (go ,loop-tag)))
         ,(caddr vars)
         ))))


(pprint (macroexpand '(dolist (i (iota 10000)))))
(bench (dolist (i (iota 10000))))
(dolist (i (iota 5)) (print i))

   ((i nil) (#:dolist353 (iota 10000)))
   nil
   (while #:dolist353 (setq i (pop #:dolist353)))
   nil)
;; time -> 0.165225[s]
0
1
2
3
4
(block
   nil
   (let
      ((i nil) (#:dolist10367 (iota 10000)))
      nil
      (tagbody
         #:dolist10368
         (unless
            (endp #:dolist10367)
            (setq i (pop #:dolist10367))
            (go #:dolist10368)))))
;; time -> 0.14457[s]
0
1
2
3
4

It can be even more efficient 🥇

[furushchev]

Summarized on gist.
https://gist.github.com/furushchev/7865e22d23006765a5ca08e33cdeeeb9

• dolist: 0.164395 -> 0.126355 sec
• dotimes: 0.07142 -> 0.13525 sec

Hmm, dotimes...

[Affonso-Gui]

Testing iteration/dolist.lsp and iteration/dotimes.lsp from ansi-test.

With the new tagbody version (with latest comments on the git file)

ALL RESULTS:
  TEST-NUM: 51
  PASSED:   38
  FAILURE:  13

dolist.6 dolist.16 dolist.17 dolist.18 dolist.19 dotimes.17 dotimes.17a dotimes.18 dotimes.18a dotim\
es.23 dotimes.23a dotimes.25 dotimes.26	

Currently:

ALL RESULTS:                                                                                         
  TEST-NUM: 51
  PASSED:   27
  FAILURE:  24                                                                                       
                                                                                                     
dolist.5 dolist.6 dolist.9 dolist.10 dolist.11 dolist.12 dolist.13 dolist.15 dolist.16 dolist.17 dol\
ist.18 dolist.19 dotimes.8 dotimes.9 dotimes.11 dotimes.12 dotimes.17 dotimes.17a dotimes.18 dotimes\
.18a dotimes.23 dotimes.23a dotimes.25 dotimes.26 

Changes involve:

• being able to return from loops
• being able to use tags inside loops
• return nil in (dolist (i '(1 2 3) i)) WARN: different from current eus implementation

Fails in new implementation are caused by problems with declare and macrolet.