Know Your Idioms

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 😉