Categories

A minor thought for today. Part of becoming an expert in any programming language is learning the idioms. Through experience, research and your peers you discover what makes your programming language hum. How to get the best performance and how to trade that against the best expressiveness. Since spoken language affects the way that what we think it’s reasonable to expect that programming languages affect the way we think about programming problems.

I have on a number of occassions wanted to write an expression in Lisp that will return true if all the elements are T and nil if any are not T. A sort of ‘and’ for a list. It seemed like a classic case of a ‘reduce’ or fold operation to me and so I went about doing that as a starting point.

CL-USER> (reduce #'(lambda (x y) (and x y)) '(t t t t t t t))
T

Hmm, because AND is a macro it can’t be an argument to reduce therefore I have to wrap it in a lambda. Which is ok but it removes the short-circuit feature from the AND.

So, I wasn’t terribly excited by this result but it served the purpose and life continued as normal. That was until today when I discovered the LOOP tutorial which inspired me with this trivial alternative …

CL-USER> (loop for x in '(t t t t t t) always (eq t x))
T

Yes it’s a little bit less functional but it it’s very clear what’s going on here and that was my original problem with the second reduce form. I was interested to see how the LOOP expanded too, so:

CL-USER> (macroexpand-1 '(loop for x in '(t t t t t t) always (eq t x)))
(BLOCK NIL
(LET ((X NIL) (#:LOOP-LIST-1613 '(T T T T T T)))
(DECLARE (TYPE LIST #:LOOP-LIST-1613))
(SB-LOOP::LOOP-BODY NIL
(NIL
(SB-LOOP::LOOP-REALLY-DESETQ X (CAR #:LOOP-LIST-1613))
NIL
(SB-LOOP::LOOP-REALLY-DESETQ #:LOOP-LIST-1613
(CDR #:LOOP-LIST-1613)))
((UNLESS (EQ T X) (RETURN-FROM NIL NIL)))
((WHEN (ENDP #:LOOP-LIST-1613) (GO SB-LOOP::END-LOOP))
(SB-LOOP::LOOP-REALLY-DESETQ X (CAR #:LOOP-LIST-1613))
NIL
(SB-LOOP::LOOP-REALLY-DESETQ #:LOOP-LIST-1613
(CDR #:LOOP-LIST-1613)))
((RETURN-FROM NIL T)))))
T
CL-USER>
... Jeeeeezus.    No way that can be efficient surely?  So I ran both arguments with a temporary list of 1,000,000 elements all equal to true:
CL-USER> (time (reduce #'(lambda (x y) (and x y)) (loop for i below 1e6 collect t)))
Evaluation took:
0.149 seconds of real time
0.100006 seconds of user run time
0.040002 seconds of system run time
[Run times include 0.068 seconds GC run time.]
0 calls to %EVAL
0 page faults and
7,999,488 bytes consed.
T
CL-USER> (time (loop for x in (loop for i below 1e6 collect t) always (eq t x)))
Evaluation took:
0.059 seconds of real time
0.052003 seconds of user run time
0.0 seconds of system run time
0 calls to %EVAL
0 page faults and
7,995,392 bytes consed.
T
Guess again brother.   The more I thought about it the more other solutions I could find to this problem.   For instance I could just count all the nulls and if I find one then the answer is false.
(eq 0 (count-if #'null
(loop for i below 1e6 collect t)))

This was marginally faster than the 'loop' on my implementation, but then I reasoned that on a list of a million items  'AND' should really retain that short-circuit ability to make it stop on the first false.   So perhaps the correct thing to do is return the first non-true argument:
(not (find-if #'null
(loop for i below 1e6 collect t)))
This solution is less imperative in style and less complicated than all the other solutions.  Now that I've thought of it I can't imagine how I didn't think of it sooner.   A winner!
Lisp is such an old language that there seems literally dozens of ways to attack most problems and that really is the point.   Since I don't know what I don't know there's probably dozens more ways I could try to solve this trivial problem that only experience, research and interaction with my peers will get me.
This is where books like the O'Reilly cookbook series should come in right?  They should have all that hard work done for me so I can stop making mistakes and start making systems.    Books, however, are not very easily searchable when they are on the shelf.   Therefore on-line resources are best for searching for optimal solutions.  So I was pleased to find that Common Lisp has an online cookbook.   However you still have to KNOW where to look in a resource like this because I might not have found the 'find-if' solution if I was stuck in a rut banging on the 'reduce' solution.    Not only that, every situation is different, 'reduce' definitely has its uses but perhaps not in this case.
This further suggests to me that it's only your peers and your own research (i.e. trial and error) that can show you the way.  Just make sure you give yourself enough time for the research and pick your peers carefully 😉


 
 ← Floating Point Flotsam → Educate A Business Person Today! 6 replies on “Know Your Idioms” Zaksays: 18/04/08 at 10:47 I tried notany and every on SBCL/linux-x86: (notany #’null ‘(t t t t t t)) (every (lambda (x) x) ‘(t t t t t t)) Both were slightly slower than the loop, but twice as fast as reduce. count-if and find-if were both a little slower than reduce. Personally, I think notany is the clearest way to express this. Note also that not all of these forms are semantically equivalent: some test that all elements are the symbol ‘t, and some test that none of the elements are nil. It is traditional Lisp style (and the behavior of CL’s if) that any value that isn’t nil is considered true, so if you’re testing to see if a list of values are true it’s probably best to use a form that does the latter. foosays: 18/04/08 at 16:02 (eq t x) is the same as x . (loop for item in list always item) (lambda (x) x) exists already. It is called IDENTITY. (every #’identity list) Zaksays: 18/04/08 at 20:03 >(eq t x) is the same as x . No, it isn’t: CL-USER> (eq ‘t 8) NIL You’re right that identity is what I was looking for though. Daniel Lyonssays: 24/06/08 at 18:19 The smartass in me tried this: (time (eval (cons ‘and (loop for i below 1e6 collect t)))) But it blew up. And comparing it for 1e5 did not seem to show it being faster. Bummer. 🙂 Eric Normandsays: 24/06/08 at 23:03 It seems like you changed requirements halfway through. At first you say this: >return true if all the elements are T and nil if any are not T Then you start counting (null x), not (not (eq t x)) Try this: (every #'(lambda (x) (eq t x)) list) Steve Knightsays: 29/06/08 at 11:48 Hi Eric, Yeah, I found the family of functions that ‘every’ belongs to as a result of Zak’s response. Hurrah for the web! But yes, if I understand you correctly, (null x) and (not (eq t x)) are not quite the same. Since the second form does what I said I wanted whereas the first returns true for any non-nil value. Thanks for the LispCast stuff, by-the-way! Steve By Post Author Comments are closed.