&rest [discussion] replacement/addition

[William D. Gooch <gooch@CHANGABANG.CAD.MCC.COM>]

I have a simple anagram generator which, being highly recursive, is an
interesting test of &rest behavior.  (If you already believe me, you may
skip to the tables at the end of this message.)  This is a toy program,
but it may provide some insight.

The approach taken is to find a word made up of characters from the
input string, then recur on the unused characters.  One argument to the
recursive call is a list of previously found words; when an anagram that
exactly uses all the characters is identified, it is saved and/or
printed from within the innermost stack frame in the recursion.

The previous-words argument data can be dealt with in a straightforward
fashion using &rest.  For example (oversimplified for the purpose of
illustration): 

(defun anagrams (string &rest previous-words)
   (let ((chars (unused-characters string previous-words)))
      (if chars
	  ;; there are unused characters left
	  (let ((new-word (find-word chars)))
	     (when new-word
		 ;; found a new word
		 (apply #'anagrams string new-word previous-words)
		 ;; if no new word could be found, just return  
		 ))
	  ;; all characters are used by previous-words, we have a weiner
	  (save-and/or-print-anagram string previous-words)
	  )))

Note that there are no undesirable side-effects of list sharing since
the list isn't changed except when it grows at the time of recursion. 
The same end can of course be accomplished by other means (see below). 

The runtime results in the table below were obtained using the form
(without-interrupts (time (do-anagrams "<input string>" NIL))) -- the
final argument of NIL specifies that results should be saved in a data
structure rather than printed as they are identified.

I ran the test with some variations on argument passing: (1) no use of
&rest in the code at all.  Instead I used a list whose length equalled
the number of characters in the input string, added new words via (setf
(car (nthcdr nwords previous-words)) new-word) and passed it through as
a single argument on recursion.  Variation (2) used &rest in the fashion
shown above, with the default behavior (on a Symbolics, this is stack
consing).  For variation (3), I just added the form (setf previous-words
(copy-list previous-words)) at the beginning of the function to simulate
a gratuitously-consing &rest implementation.

Anagram timings -- Symbolics Genera 7.1 on a 3600 running 3670 microcode

input string	code version	     runtime (sec)   list consing (words)
-------------------------------------------------------------------------
hi there     (1) no &rest		14.38		144
hi there     (2) &rest, no copy		14.29		144
hi there     (3) &rest, copy		14.35		1428

ian gooch    (1) no &rest		138.7		464
ian gooch    (2) &rest, no copy		138.5		464
ian gooch    (3) &rest, copy		138.7		6913

Two more variations are also interesting.  To reorder the characters
without consing, it was convenient to add some intermediate levels of
recursion which don't appear in the above example.  When I use &rest and
apply for the reordering function as well as in the function anagrams as
shown above, I get the following:

input string	code version	     runtime (sec)   list consing (words)
-------------------------------------------------------------------------
hi there	all &rest, no copy	14.28		144
hi there	all &rest, copy		14.77		6814

ian gooch	all &rest, no copy	138.4		464
ian gooch	all &rest, copy		140.0		30777

paul gooch	all &rest, no copy	1018		820
paul gooch	all &rest, copy		1020		33770


I would include more results, but they are all pretty consistent. 

Draw your own conclusions.  I'm not advocating a particular point of
view here, although I think &rest should always have a form which allows
its user to control consing, regardless of how performance might or
might not be affected.

  -- William D. Gooch