Recursion and Accumulators

Working through Paradigms in Artificial Intelligence Programming, I have worked to wrap my head around accumulators and I have implemented one that worked surprisingly quickly. My example is a factorial design experiment. I have 4 reference implementations of a factorial design on an experiment with 7 factors, with each factor having 10 treatments in it. This is a bit of a ridiculous size, but it gave me clear separation of performances. I have split the code up into sections so you can focus on the parts of the program that matter you.

Supporting Code

(defmacro make-enumerator (head tail) `(cons ,head #'(lambda () ,tail))) (defun get-current (enumerator) (if (consp enumerator) (first enumerator) nil)) (defun get-next (enumerator) (when (functionp (rest enumerator)) (funcall (rest enumerator)))) (defvar empty-indices '(nil)) ;; this is a non-destructive implmentation (defun multiple-radix-counter (radices &key indices terminate) (when (null indices) (setf indices (make-array (length radices) :initial-element 0))) (if (and terminate (equal indices empty-indices)) nil (make-enumerator indices (multiple-radix-counter radices :indices (loop with dest = (make-array (length indices) :initial-contents indices) for i from (1- (length indices)) downto 0 if (< (1+ (aref dest i)) (aref radices i)) do (incf (aref dest i)) (return dest) else do (setf (aref dest i) 0) finally (return (if (and terminate (< i 0)) empty-indices dest))) :terminate terminate)))) (defun extract-by-multiple-radix (source indices) (loop with res = (make-array (length indices)) for i from 0 to (1- (length indices)) do (setf (aref res i) (aref (aref source i) (aref indices i))) finally (return res))) (defmacro discard (&body body) `(let () ,@body nil))

Main Functions

(defun factorialize (factors &optional (accumulator '(nil))) "Given a list of lists, where each list is of treatments, give a complete factorial." (cond ((null factors) accumulator) ((atom factors) (mapcar #'(lambda (u) (cons factors u)) accumulator)) ((atom (first factors)) (loop with res = '(nil) with ending = res for f in factors do (loop for acc in accumulator do (setf (cdr ending) (cons (cons f acc) nil)) (setf ending (cdr ending))) finally (pop res) (return res))) (t (factorialize (first factors) (factorialize (rest factors) accumulator)))) (defun factorialize-2 (factors) "This is the slow version using append. sample usage: (factorialize-2 '((1 2 3) (4 5 6) (a b c))) produces: ((1 4 A) (1 4 B) (1 4 C) (1 5 A) (1 5 B) (1 5 C) (1 6 A) (1 6 B) (1 6 C) (2 4 A) (2 4 B) (2 4 C) (2 5 A) (2 5 B) (2 5 C) (2 6 A) (2 6 B) (2 6 C) (3 4 A) (3 4 B) (3 4 C) (3 5 A) (3 5 B) (3 5 C) (3 6 A) (3 6 B) (3 6 C))" (cond ((null factors) nil) ((null (rest factors)) (mapcar #'(lambda (u) (list u)) (first factors))) (t (loop with remaining = (factorialize-2 (rest factors)) for f in (first factors) append (loop for r in remaining collect (cons f r)))))) (defun factorialize-3 () (loop with res = '(nil) with ending = res for i from 0 to 9 do (loop for j from 0 to 9 do (loop for k from 0 to 9 do (loop for l from 0 to 9 do (loop for m from 0 to 9 do (loop for n from 0 to 9 do (loop for p from 0 to 9 do (setf (cdr ending) (cons (list i j k l m n p) nil)) (setf ending (cdr ending)))))))) finally (pop res) (return res))) (defun factorialize-4 (factors) (let* ((radices (map 'vector #'length factors)) (combinations (reduce #'* radices)) (res (make-array (list combinations)))) (loop for enum = (multiple-radix-counter radices :terminate t) then (get-next enum) for index = 0 then (1+ index) for indices = (get-current enum) while enum do (setf (aref res index) (extract-by-multiple-radix factors indices)) finally (return res))))

Speed Testing

To make the testing as fair as possible, I started emacs fresh for each test run. Under these conditions, factorialize took 2.5 seconds, factorialize-2 took 3.7 seconds, factorialize-3 took 22 seconds, and factorialize-4 took 12 seconds.

A large amount of the time spent in these examples is spend in garbage collection. The factorialize-4 example could probably be improved by allocating a large chunk of memory in a 2-dimensional array and then the rest of the work involves a lot less memory allocation time. The land slide difference that marks factorialize off from the other methods appears to be the amount of shared memory it involves. Some reassignments of various locations of the resulting list, produce changes in other lists since there is shared cons cells among the lists. For my particular application this was proving to be a problem and so I have changed over to the factorialize-4 version of the function. Since my actual likely data is much smaller than that used in the speed tests of this post, I'm not overly concerned about the difference in speed.

An advantage of the method of factorialize-4, which uses an enumerator is that this method could be used to output data to a database or file in a way that didn't need to use very much run-time memory. Very likely in these cases, the time spent sending and saving data to persistent storage is much greater than the computational effort. The factorialize and factorialize-2 methods do not lend themselves to this as they do not generate complete tuples until all of the tuples are created. factorialize-4 creates complete tuples one at at time and these can be acted on immediately without waiting for all of the output to be generated.

Common Lisp Pipes→Enumerators

I've been plodding along through Peter Norvig's Paradigm's in Artificial Intelligence Programming and finding some helpful tips along the way. I especially enjoyed the discussion of pipes in chapter 9. I was intrigued by the pipes implementation of the sieve or Eratosthenes and wondered what else I could do with pipes.

Something that I didn't like about pipes is that they keep around a list of the results, when maybe you are actually done with those results. I was taking combinations of factors to produce a factorial experimental design and I decided to do so using something I have called multiple-radix-counting. Multiple-radix, meaning the radix (or base) for each digit is different. Imagine an odometer where each spinner has a different number of marks on it. Instead of always going from 0 to 9, some of the spinners might be 0 to 1 or 0 to 5. The sequencing is the same. When you get the end of the right most spinner, you wrap around on the first and advance the next spinner. Here's some sample output the shows the pattern:

(loop for enum = (multiple-radix-counter #(3 2 3) :terminate t) then (get-next enum) while enum do (print (get-current enum))) #(0 0 0) #(0 0 1) #(0 0 2) #(0 1 0) #(0 1 1) #(0 1 2) #(1 0 0) #(1 0 1) #(1 0 2) #(1 1 0) #(1 1 1) #(1 1 2) #(2 0 0) #(2 0 1) #(2 0 2) #(2 1 0) #(2 1 1) #(2 1 2) NIL

I have taken the definitions from PIAP and modified them to avoid hanging on to the part of the pipe that has gone past. I have renamed certain functions/macros and made minor changes to them to produce a result that behaves differently. Instead of make-pipe, I have make-enumerator, although the macro is identical. It's important that I have a new name for this macro that suits the different usage in case I decide to implement enumerators differently in the future. The function get-current and get-next are the replacements for head and tail, respectively.  The representation is very similar to that used for pipes. I use a cons cell where the car is the current value and the cdr is a function call.

(defmacro make-enumerator (head tail) `(cons ,head #'(lambda () ,tail))) (defun get-current (enumerator) (if (consp enumerator) (first enumerator) nil)) (defun get-next (enumerator) (when (functionp (rest enumerator)) (funcall (rest enumerator)))) (defun integer-enum (&optional (start 0) end) (if (or (null end) (<= start end)) (make-enumerator start (integer-enum (1+ start) end)) nil)) (defvar empty-indices '(nil)) ;; this is a non-destructive implmentation (defun multiple-radix-counter (radices &key indices terminate) (when (null indices) (setf indices (make-array (length radices) :initial-element 0))) (if (and terminate (equal indices empty-indices)) nil (make-enumerator indices (multiple-radix-counter radices :indices (loop with dest = (make-array (length indices) :initial-contents indices) for i from (1- (length indices)) downto 0 if (< (1+ (aref dest i)) (aref radices i)) do (incf (aref dest i)) (return dest) else do (setf (aref dest i) 0) finally (return (if (and terminate (< i 0)) empty-indices dest))) :terminate terminate)))) (defun extract-by-multiple-radix (source indices) (loop with res = (make-array (length indices)) for i from 0 to (1- (length indices)) do (setf (aref res i) (aref (aref source i) (aref indices i))) finally (return res)))

The purpose of the extract-by-multiple-radix is to take a selection out of source (an array of arrays) based on the indices that were specified. If you were doing multiplication of multiple term factors, you would take the terms by index from each factor and multiply them. To get the factors based on index, you would use extract-by-multiple-radix.