April 22, 2008
Escaping from higher-order functions
Among the different ways to tackle iterative processes I consider to be the higher-order function route the one I use most often. Especially in conjunction with function composition and list predicates it makes great filtering-style code.
A problem that came up several times is interrupting the list processing at an arbitrary point. For example, how do I stop MAPCAR at the third item if I see it fit? Something like that:
(let ((i 0)) (mapcar (lambda (x) (when (eql (incf i) 3) (STOP-HERE))) '(a b c d)))
Sometimes, one can take alternative routes using FIND or other functions. And there’s always LOOP, DOLIST, recursion and other solutions; after all we’re working in a language that really implements the “there’s more than one way to do it” paradigm.
Using TAGBODY and GO:
(tagbody (mapcar (lambda (x) (go X)) '(a b c)) X)
Using BLOCK/RETURN-FROM:
(block X (mapcar (lambda (x) (return-from X)) ‘(a b c)))
I originally posted another version using CATCH/THROW, but as pointed out in the comments this wasn’t all well for several reasons.
Delimited continuations with CL-CONT unfortunately won’t work.
A good alternative solution would be writing your own version of MAPCAR; this has the advantage of being able to return the partially processed list. But there’s the disadvantage of having to rewrite the whole family of mapping functions, though, so for quick prototyping or occasional usage I prefer the above solution.
If you have other neat solutions or see problems with this approach, please leave a comment.
Comments(16)
Tagbody matches go. return-from is matched with block
(block X (mapcar (lambda (x) (return-from X)) ‘(a b c))) works for me. (tagbody (mapcar (lambda (x) (go x)) ‘(a b c)) x) as well.
You’re right. I tried TAGBODY/GO which didn’t work out and must have confused RETURN-FROM with TAGBODY afterwards.
Is it a parody?
‘Lisp programmers know the value of everything and the cost of nothing?
You are uselessly introducing a heap consed function for every escape?
Common Lisp provides BLOCK/RETURN/RETURN-FROM as an efficient mechanism already for non-local exists. It is not just an ‘alternative’. It is the built-in mechanism for non-local-exits. Your ‘solution’ is costly, makes debugging harder and not needed. The other variant for non-local exits is CATCH/THROW. Your use of CATCH/THROW is especially bad, since it combines lexical functions with dynamic CATCH tags.
With CATCH/THROW it is just:
(catch ‘escape (mapcar (lambda (x) (throw ‘escape t)) ‘(a b c)))
(tagbody (mapc (lambda (x) (go OUT)) ‘(a b c)) OUT) works just fine. Also, you forgot to remove the old “return-from” error message.
The errors in this article would be less glaring if not written as though it should be enlightening to people.
In fact, it would be better in my mind to delete the entire article and write a correct one than to leave it up in this state.
Oh, and delimited continuation would do, just not cl-cont, while you’re fixing things…
All fixed, thanks. Let me know if you spot another one.
You might want to try out your examples before you post. Your TAGBODY example is an endless loop.
See in the comments for the right example.
TAGBODY is not the right form to use, because TAGBODY provides more functionality than needed (multiple tags) and also does support returning another value than NIL. BLOCK/RETURN-FROM does allow that.
In the BLOCK example the character before the list (a b c) is not a single quote character.
Sorry, the quote thing is a limitation of my blog software.
I have just started to check out series.
Here is an example on how it could be solved with series
(until-if #’minusp (#Mprinc (scan-range :from 10 :downto -10 :by -1)))
Wow, that looks great, thanks.
This isn’t the right place for mapping. You want a combination of DOLIST and DOTIMES:
(defmacro dolist-times ((x list n &optional rtrn-expr) &body body) (let ((cell (gensym)) ( i (gensym))) `(do ((,cell ,list (cdr ,cell)) ( ,i 0 (1+ ,i) )) ((or (endp ,cell) (= ,i ,n)) ,rtrn-expr) (let ((,x (car ,cell))) ,@body)))) (let ((sum3 0)) (dolist-times (x '(1 2 3 4 5) 3 sum3) (incf sum3 x))) => 6 (let ((sum5 0)) (dolist-times (x '(1 2 3) 5 sum5) (incf sum5 x))) =>6–Dan
In this special case I had to use the mapping interface provided by Elephant.
Anyway the DOLIST/DOTIMES solution isn’t really my style (although it is an interesting tool).
In fact I’d probably do it with LOOP.
I see. I didn’t know about Elephant. Anyway, you don’t prefer repeatedly hard-coding LOOP forms over writing a macro, do you? Here’s a LOOP implementation:
(defmacro dolist-times ((x i list n &optional rtrn-expr) &body body) `(loop for ,x in ,list and ,i below ,n do (progn ,@body) finally (return ,rtrn-expr)))—Dan
Actually sometimes I do prefer an explicit LOOP over a macro if it doesn’t get out of hand. :)
But mainly I think that I just don’t like the name and signature of your macro very much.
I’d probably call it DOLIST* and add a kwarg :LIMIT.