Subject: [clisp-list] strange macroexpansion...[long mail! But a real mindbuster!]

From: Stefan Kain <[email-masked]>
Date: Sun Apr 21 03:48:03 2002

Hi,

Originally I just wanted to test, if CLISP is
able to compile case- forms efficiently.
(With jump-tables instead of nested if-then-else or cond)

I have written the following macro which generates
a test function. The strange thing is, if you expand the
macro multiple times with the same parameters, the
resulting form grows and grows and....

Can you find the bug, or is there a bug in the macro-expansion?
Or is it evil to generate  (DEFUN ... ) - forms via DEFMACRO?
What am I missing?

(defmacro generate-test (fun-name (num-case chosen-case num-iter))  
   "fun-name:    name of the generated function
    num-case:    number of case-alternatives
    chosen-case: the case that is always chosen
    num-iter:    number of iterations (for better time-measurement))"
  `(defun ,fun-name () 
    (declare (special *bla*))
    (progn 
      (setf *bla* 0)
      (let ((i ,chosen-case)) 
        ,`(loop for j from 1 to ,num-iter do 
           ,(nconc 
             '(case i) 
             (loop for k from 1 to num-case collect 
                   `((,k) (setf *bla* (+ ,k j))))))))
    *bla*))

let's expand this macro:

[1]>  (macroexpand-1 '(generate-test test-case (10 10 10000)))
(DEFUN TEST-CASE NIL (DECLARE (SPECIAL *BLA*))
 (PROGN (SETF *BLA* 0)
  (LET ((I 10))
   (LOOP FOR J FROM 1 TO 10000 DO
    (CASE I ((1) (SETF *BLA* (+ 1 J))) ((2) (SETF *BLA* (+ 2 J))) ((3)
(SETF *BLA* (+ 3 J)))
     ((4) (SETF *BLA* (+ 4 J))) ((5) (SETF *BLA* (+ 5 J))) ((6) (SETF
*BLA* (+ 6 J)))
     ((7) (SETF *BLA* (+ 7 J))) ((8) (SETF *BLA* (+ 8 J))) ((9) (SETF
*BLA* (+ 9 J)))
     ((10) (SETF *BLA* (+ 10 J)))))))
 *BLA*) ;
T

OK, the point I wanted to show originally is that if you increase the
number
of case-forms and in the loop always choose the last case-form, the
time-complexity
should remain constant during runtime. For a slow
if-then-else-implementation,
the computation-time should grow proportional to the number of
case-forms.

In short, I planned to do this:
(generate-test test-case-10    (10 10 10000))
and run the resulting test-case-10

(generate-test test-case-100   (100 100 10000))
and run the resulting test-case-100

(generate-test test-case-1000  (1000 1000 10000)) 
and run the resulting test-case-10

(generate-test test-case-10000 (10000 100000 10000))
and run the resulting test-case-10

etc. 

the runtime should remain constant for each function-call.
I did not arrive at that due to some really weird expansion
behaviour.

Look what happens, if I expand the macro-call
multiple times with the _SAME_ parameters in the interactive loop:

First time: (as above)
[1]> (macroexpand-1 '(generate-test test-case-10 (10 10 10000)))
(DEFUN TEST-CASE-10 NIL (DECLARE (SPECIAL *BLA*))
 (PROGN (SETF *BLA* 0)
  (LET ((I 10))
   (LOOP FOR J FROM 1 TO 10000 DO
    (CASE I ((1) (SETF *BLA* (+ 1 J))) ((2) (SETF *BLA* (+ 2 J))) ((3)
(SETF *BLA* (+ 3 J)))
     ((4) (SETF *BLA* (+ 4 J))) ((5) (SETF *BLA* (+ 5 J))) ((6) (SETF
*BLA* (+ 6 J)))
     ((7) (SETF *BLA* (+ 7 J))) ((8) (SETF *BLA* (+ 8 J))) ((9) (SETF
*BLA* (+ 9 J)))
     ((10) (SETF *BLA* (+ 10 J)))))))
 *BLA*) ;
T

Second time:
[2]> (macroexpand-1 '(generate-test test-case-10 (10 10 10000)))
(DEFUN TEST-CASE-10 NIL (DECLARE (SPECIAL *BLA*))
 (PROGN (SETF *BLA* 0)
  (LET ((I 10))
   (LOOP FOR J FROM 1 TO 10000 DO
    (CASE I ((1) (SETF *BLA* (+ 1 J))) ((2) (SETF *BLA* (+ 2 J))) ((3)
(SETF *BLA* (+ 3 J)))
     ((4) (SETF *BLA* (+ 4 J))) ((5) (SETF *BLA* (+ 5 J))) ((6) (SETF
*BLA* (+ 6 J)))
     ((7) (SETF *BLA* (+ 7 J))) ((8) (SETF *BLA* (+ 8 J))) ((9) (SETF
*BLA* (+ 9 J)))
     ((10) (SETF *BLA* (+ 10 J))) ((1) (SETF *BLA* (+ 1 J))) ((2) (SETF
*BLA* (+ 2 J)))
     ((3) (SETF *BLA* (+ 3 J))) ((4) (SETF *BLA* (+ 4 J))) ((5) (SETF
*BLA* (+ 5 J)))
     ((6) (SETF *BLA* (+ 6 J))) ((7) (SETF *BLA* (+ 7 J))) ((8) (SETF
*BLA* (+ 8 J)))
     ((9) (SETF *BLA* (+ 9 J))) ((10) (SETF *BLA* (+ 10 J)))))))
 *BLA*) ;
T

n-th time:
[11]> (macroexpand-1 '(generate-test test-case-10 (10 10 10000)))
(DEFUN TEST-CASE-10 NIL (DECLARE (SPECIAL *BLA*))
 (PROGN (SETF *BLA* 0)
  (LET ((I 10))
   (LOOP FOR J FROM 1 TO 10000 DO
    (CASE I ((1) (SETF *BLA* (+ 1 J))) ((2) (SETF *BLA* (+ 2 J))) ((3)
(SETF *BLA* (+ 3 J)))
     ((4) (SETF *BLA* (+ 4 J))) ((5) (SETF *BLA* (+ 5 J))) ((6) (SETF
*BLA* (+ 6 J)))
     ((7) (SETF *BLA* (+ 7 J))) ((8) (SETF *BLA* (+ 8 J))) ((9) (SETF
*BLA* (+ 9 J)))
     ((10) (SETF *BLA* (+ 10 J))) ((1) (SETF *BLA* (+ 1 J))) ((2) (SETF
*BLA* (+ 2 J)))
     ((3) (SETF *BLA* (+ 3 J))) ((4) (SETF *BLA* (+ 4 J))) ((5) (SETF
*BLA* (+ 5 J)))
     ((6) (SETF *BLA* (+ 6 J))) ((7) (SETF *BLA* (+ 7 J))) ((8) (SETF
*BLA* (+ 8 J)))
         ........
          ......
     ((4) (SETF *BLA* (+ 4 J))) ((5) (SETF *BLA* (+ 5 J))) ((6) (SETF
*BLA* (+ 6 J)))
     ((7) (SETF *BLA* (+ 7 J))) ((8) (SETF *BLA* (+ 8 J))) ((9) (SETF
*BLA* (+ 9 J)))
     ((10) (SETF *BLA* (+ 10 J))) ((1) (SETF *BLA* (+ 1 J))) ((2) (SETF
*BLA* (+ 2 J)))
     ((3) (SETF *BLA* (+ 3 J))) ((4) (SETF *BLA* (+ 4 J))) ((5) (SETF
*BLA* (+ 5 J)))
     ((6) (SETF *BLA* (+ 6 J))) ((7) (SETF *BLA* (+ 7 J))) ((8) (SETF
*BLA* (+ 8 J)))
     ((9) (SETF *BLA* (+ 9 J))) ((10) (SETF *BLA* (+ 10 J)))))))
 *BLA*) ;
T

Hmmm, if I reevaluate the (defmacro...) form again and then expand it
again, everything
is fine again...

[14]> (defmacro generate-test (fun-name (num-case chosen-case num-iter))
          ....... bla bla ....bla
GENERATE-TEST

[15]> (macroexpand-1 '(generate-test test-case-10 (10 10 10000)))
(DEFUN TEST-CASE-10 NIL (DECLARE (SPECIAL *BLA*))
 (PROGN (SETF *BLA* 0)
  (LET ((I 10))
   (LOOP FOR J FROM 1 TO 10000 DO
    (CASE I ((1) (SETF *BLA* (+ 1 J))) ((2) (SETF *BLA* (+ 2 J))) ((3)
(SETF *BLA* (+ 3 J)))
     ((4) (SETF *BLA* (+ 4 J))) ((5) (SETF *BLA* (+ 5 J))) ((6) (SETF
*BLA* (+ 6 J)))
     ((7) (SETF *BLA* (+ 7 J))) ((8) (SETF *BLA* (+ 8 J))) ((9) (SETF
*BLA* (+ 9 J)))
     ((10) (SETF *BLA* (+ 10 J)))))))
 *BLA*) ;
T

Help!!!!!!! :-)

BTW, CLISP seems to compile case-forms efficiently via jump-table. (if I
reevaluate
the (defmacro ...) everything works as expected):

[16-23] repetition of (defmacro...) (generate-test...) ...
then:
[24]> (compile 'test-case-10)
TEST-CASE-10 ;
NIL ;
NIL
[25]> (compile 'test-case-100)
TEST-CASE-100 ;
NIL ;
NIL
[26]> (compile 'test-case-1000)
TEST-CASE-1000 ;
NIL ;
NIL
[27]> (compile 'test-case-10000)
TEST-CASE-10000 ;
NIL ;
NIL
[28]> (test-case-10)    | Each call needs the same amount of time
10010                   |
[29]> (test-case-100)   |          -"-
10100                   |
[30]> (test-case-1000)  |          -"-
11000                   |
[31]> (test-case-10000) |          -"-
20000

You can see the jump-table via (disassemble 'test-case-...).

But this macroexpansion is really strange...

P.S. It is irrelevant if you supply the same parameters every time. The
list of
case-forms grows each  macroexpansion-time, no matter what arguments you
supply.

Bye,
Stefan

---

From: Stefan Kain <[email-masked]>
Date: Sun Apr 21 03:57:01 2002

Hi,

damn typos...

Stefan Kain wanted to write: ;-)
> and run the resulting test-case-1000
> 
> (generate-test test-case-10000 (10000 10000 10000))
> and run the resulting test-case-10000

---

From: Stefan Kain <[email-masked]>
Date: Sun Apr 21 04:22:02 2002

Well, ahem,

I have found the culprit. He is sitting right
in front of the screen...

>         ,`(loop for j from 1 to ,num-iter do
               ^^^^^^^ !!!!!!!!!!!!!! 
              "append" is your friend...

Now each macroexpansion of  generate-test works without "side-effect"...

Aftermath:
Beware of destructive operations!!
(As usual, I used nconc in order to save a few conses... (How stupid))

This springs to my mind: "Premature optimisation is the root of all
evil..."

:-)
Sorry for bothering the mailing list. 

Bye,
Stefan