Hi!
While trying to learn Lisp, I've been working on a little program to
solve "Einstein's Riddle" which involves macros that create functions
on-the-fly. I have noticed significant differences when using COMPILE
compared to COMPILE-FILE:
1. LispWorks on Win2k
1.1. Interpreted: more than 15 seconds
1.2. Compiled manually: about 19 seconds (!!!)
1.3. Compiled the whole file: less than 1 second
2. CMUCL on FreeBSD
1.1. Interpreted: about 140 seconds
1.2. Compiled manually: almost 100 seconds
1.3. Compiled the whole file: about 0.6 seconds
The file that I've been using can be found at
http://www.weitz.de/files/quiz.lisp
In the first case, I just loaded the file and executed the function
SOLVE. In the second case, I loaded the file and manually compiled
PERMUTE, POSSIBLE-P, all functions in *CONDITION-LIST*, and SOLVE before
executing SOLVE. In the third case, I issued (COMPILE-FILE "quiz.lisp")
and then loaded the compiled file prior to calling SOLVE.
I wonder what COMPILE-FILE does that so dramatically decreases the
executing time of the program (and that could be accomplished by
manually compiling all the functions involved).
Also, two related questions: Why is LispWorks faster with interpreted
code than with code that was manually compiled? And why is CMUCL's
compiled code faster than LispWork's while the interpreted version in
LispWorks is almost ten times as fast as CMUCL's version?
Thanks in advance for your hints.
Dr. Edmund Weitz
Hamburg
Germany
http://www.weitz.de/
From: Tim Moore
Subject: Re: Why is COMPILE-FILE better than COMPILE?
Date:
Message-ID: <9k7h9q$575$0@216.39.145.192>
On Wed, 1 Aug 2001, Dr. Edmund Weitz wrote:
> Hi!
>
> While trying to learn Lisp, I've been working on a little program to
> solve "Einstein's Riddle" which involves macros that create functions
> on-the-fly. I have noticed significant differences when using COMPILE
> compared to COMPILE-FILE:
[...]
> http://www.weitz.de/files/quiz.lisp
>
> In the first case, I just loaded the file and executed the function
> SOLVE. In the second case, I loaded the file and manually compiled
> PERMUTE, POSSIBLE-P, all functions in *CONDITION-LIST*, and SOLVE before
> executing SOLVE. In the third case, I issued (COMPILE-FILE "quiz.lisp")
> and then loaded the compiled file prior to calling SOLVE.
>
> I wonder what COMPILE-FILE does that so dramatically decreases the
> executing time of the program (and that could be accomplished by
> manually compiling all the functions involved).
When you used COMPILE none of your defstruct accessors were compiled.
>
> Also, two related questions: Why is LispWorks faster with interpreted
> code than with code that was manually compiled? And why is CMUCL's
> compiled code faster than LispWork's while the interpreted version in
> LispWorks is almost ten times as fast as CMUCL's version?
CMUCL has a very good compiler and a not-so-great interpreter.
>
> Thanks in advance for your hints.
If you're going to write out-of-control macros, you might be interested in
learning to use nested backquote forms. For example, your form that looks
like:
`(progn
(defstruct (unit (:conc-name nil) (:type vector))
,@accessor-list)
(setf *condition-list* nil)
(defmacro build-solver ()
(list 'progn
',possible-p-definition
',solve-definition)))
could be written more succintly IMHO as:
`(progn
(defstruct (unit (:conc-name nil) (:type vector))
,@accessor-list)
(setf *condition-list* nil)
(defmacro build-solver ()
`(progn
,',possible-p-definition
,',solve-definition)))
Tim
In article <············@216.39.145.192>, ·····@herschel.bricoworks.com
says...
> If you're going to write out-of-control macros, you might be interested in
> learning to use nested backquote forms. For example, your form that looks
> like:
>
> `(progn
> (defstruct (unit (:conc-name nil) (:type vector))
> ,@accessor-list)
> (setf *condition-list* nil)
> (defmacro build-solver ()
> (list 'progn
> ',possible-p-definition
> ',solve-definition)))
>
> could be written more succintly IMHO as:
> `(progn
> (defstruct (unit (:conc-name nil) (:type vector))
> ,@accessor-list)
> (setf *condition-list* nil)
> (defmacro build-solver ()
> `(progn
> ,',possible-p-definition
> ,',solve-definition)))
Thanks. I was trying to achieve something like this but I had problems
with the syntax. In fact, I originally wanted to get rid of the LET
statement that defines POSSIBLE-P-DEFINITION and SOLVE-DEFINITION at all
but I didn't get it. Which combination of commas, quotes and backquotes
do I have to use to directly embed the definitions of these two
functions into the BUILD-SOLVER macro? (I'm kinda puzzled...)
Thanks in advance,
Edi.
From: Tim Moore
Subject: Re: Why is COMPILE-FILE better than COMPILE?
Date:
Message-ID: <9k9brt$3ia$0@216.39.145.192>
On Wed, 1 Aug 2001, Dr. Edmund Weitz wrote:
> In article <············@216.39.145.192>, ·····@herschel.bricoworks.com
> says...
>
> Thanks. I was trying to achieve something like this but I had problems
> with the syntax. In fact, I originally wanted to get rid of the LET
> statement that defines POSSIBLE-P-DEFINITION and SOLVE-DEFINITION at all
> but I didn't get it. Which combination of commas, quotes and backquotes
> do I have to use to directly embed the definitions of these two
> functions into the BUILD-SOLVER macro? (I'm kinda puzzled...)
Here's my crack at it below. The nested backquote usage is fairly simple
here; values that exist at the time of the outer backquote are used
literally in the inner backquote, so we only see ,',foo and ,@',foo.
Things become a bit more twisted when referring to "values of values" of
variables defined in the outer expansion -- a common occurence in
macro-writing macros. Then we'd see usage like ,,foo and ,,@foo. The
appendix of CLTL2 that explores backquote in great detail is essential
reading.
I don't mind showing off with nested backquotes, but I have to ask: why
are the defuns of POSSIBLE-P and SOLVE nested inside BUILD-SOLVER? That
doesn't buy you anything at all.
Oh yeah, one other critique: in your BUILD-BACKTRACKING function,
(<= (length property-descriptor-list) 1) is not good style. That function
would be clearer if your base case was (null property-descriptor-list);
then you could do away with the duplication of the DOLIST cruft across
both branches of the IF.
Tim
(defmacro initialize (property-descriptor-list)
(labels ((name (property-descriptor) (first property-descriptor))
(args (property-descriptor) (second property-descriptor))
(plural (name choices &key plural-name)
(declare (ignore choices))
(if plural-name
plural-name
(intern (concatenate 'string (symbol-name name) "S"))))
(keyword (name) (intern (symbol-name name) "KEYWORD"))
(permutation-name (name)
(intern (concatenate 'string
(symbol-name name)
"-PERMUTATIONS"))))
(let ((problem-size (length property-descriptor-list))
(accessor-list (mapcar #'name property-descriptor-list))
(plural-list (mapcar #'(lambda (property-descriptor)
(apply #'plural property-descriptor))
property-descriptor-list))
(permutation-list (mapcar #'(lambda (property-descriptor)
(list (permutation-name (name property-descriptor))
(list 'permute (args property-descriptor))))
property-descriptor-list)))
(labels ((build-backtracking (property-descriptor-list &optional (accum-list nil))
(let* ((property-descriptor
(first property-descriptor-list))
(plural-name
(apply #'plural property-descriptor))
(new-accum-list
(append accum-list (list plural-name))))
(if (<= (length property-descriptor-list) 1)
`(dolist (,plural-name
,(permutation-name (name property-descriptor)))
(let ((result
(possible-p ,@plural-list)))
(when result
(pprint result))))
`(dolist (,plural-name
,(permutation-name (name property-descriptor)))
(when (possible-p ,@new-accum-list)
,(build-backtracking (cdr property-descriptor-list)
new-accum-list)))))))
`(progn
(defstruct (unit (:conc-name nil) (:type vector))
,@accessor-list)
(setf *condition-list* nil)
(defmacro build-solver ()
`(progn
(defun possible-p (&optional
,@',(mapcar #'(lambda (property-descriptor)
`(,(apply #'plural property-descriptor)
(make-list ,problem-size :initial-element nil)))
property-descriptor-list))
(let ((selection (mapcar #'(lambda ,',accessor-list
(make-unit
,@',(mapcan #'(lambda (property-descriptor)
(let ((name (name property-descriptor)))
(list (keyword name) name)))
property-descriptor-list)))
,@',plural-list)))
(when (and-all-conditions selection)
selection)))
(defun solve ()
(let ,',permutation-list
,',(build-backtracking property-descriptor-list)
(values))))))))))
In article <············@216.39.145.192>, ·····@herschel.bricoworks.com
says...
> Here's my crack at it below. The nested backquote usage is fairly simple
> here; values that exist at the time of the outer backquote are used
> literally in the inner backquote, so we only see ,',foo and ,@',foo.
> Things become a bit more twisted when referring to "values of values" of
> variables defined in the outer expansion -- a common occurence in
> macro-writing macros. Then we'd see usage like ,,foo and ,,@foo. The
> appendix of CLTL2 that explores backquote in great detail is essential
> reading.
Thank you very much for your help. I'll check CLTL2.
> I don't mind showing off with nested backquotes, but I have to ask: why
> are the defuns of POSSIBLE-P and SOLVE nested inside BUILD-SOLVER? That
> doesn't buy you anything at all.
The idea is that the outer macro INITIALIZE will prepare the macro
BUILT-SOLVER which will in turn define SOLVE. SOLVE cannot be built at
this time because the user will first have to fill *CONDITION-LIST* (and
call BUILT-SOLVER afterwards). SOLVE relies on the macro AND-ALL-
CONDITIONS and would yield wrong results if compiled with an empty
*CONDITION-LIST*. [I think this will only be a problem with compiled
code, not with interpreted code.]
> Oh yeah, one other critique: in your BUILD-BACKTRACKING function,
> (<= (length property-descriptor-list) 1) is not good style. That function
> would be clearer if your base case was (null property-descriptor-list);
> then you could do away with the duplication of the DOLIST cruft across
> both branches of the IF.
The base case is in fact (= (length property-descriptor-list) 1). I have
no idea how to change the code to make (null property-descriptor-list)
the base case. Maybe you'd like to take a look at
http://www.weitz.de/einstein.html
to see what was intended with the code. I'd be glad if it could be
further simplified (and I could learn something from it).
Thanks again for your time,
Edi.
From: Tim Moore
Subject: Re: Why is COMPILE-FILE better than COMPILE?
Date:
Message-ID: <9k9l66$b1n$0@216.39.145.192>
On Wed, 1 Aug 2001, Dr. Edmund Weitz wrote:
> In article <············@216.39.145.192>, ·····@herschel.bricoworks.com
> says...
> > I don't mind showing off with nested backquotes, but I have to ask: why
> > are the defuns of POSSIBLE-P and SOLVE nested inside BUILD-SOLVER? That
> > doesn't buy you anything at all.
>
> The idea is that the outer macro INITIALIZE will prepare the macro
> BUILT-SOLVER which will in turn define SOLVE. SOLVE cannot be built at
> this time because the user will first have to fill *CONDITION-LIST* (and
> call BUILT-SOLVER afterwards). SOLVE relies on the macro AND-ALL-
> CONDITIONS and would yield wrong results if compiled with an empty
> *CONDITION-LIST*. [I think this will only be a problem with compiled
> code, not with interpreted code.]
OK, I see what you're trying to do, but in going down this very hairy path
you've built in a lot of weird dependencies between macro-expand
time, compile time and run time. Have you tried to compile this in a
fresh Lisp in which you haven't previously loaded quiz.lisp? In order to
compile this properly you're going to wrap (eval-when (:compile-toplevel
:load-toplevel :execute) ...) around all your defun and initializing
forms. Instead of listing the position and neighbor conditions at top
level in your file, a more recommended style would be to define a
define-condition-problem macro or something that would take the condition
clauses as arguments and do all the required macro definition within the
context of that macro. This makes it easier to control (and seperate)
what gets done at macroexpansion time vs. run time.
Your comment about compiled code vs. interpreted code is in general not
true. Many (most?) modern Lisp interpreters perform macroexpansion once
when forms are first encountered.
> > Oh yeah, one other critique: in your BUILD-BACKTRACKING function,
> > (<= (length property-descriptor-list) 1) is not good style. That function
> > would be clearer if your base case was (null property-descriptor-list);
> > then you could do away with the duplication of the DOLIST cruft across
> > both branches of the IF.
>
> The base case is in fact (= (length property-descriptor-list) 1). I have
> no idea how to change the code to make (null property-descriptor-list)
> the base case. Maybe you'd like to take a look at
OK, I see on further inspection that you do want the base case to have one
remaining element. The proper idiom for that is (null (cadr
property-descriptor-list)) (or second if you prefer). LENGTH has to
traverse the entire list, so you get n^2 behavior if you use that.
I'd still recommend factoring out the common branches of BUILD-BACTRACKING
so that the guts of that function look like:
'(dolist (,plural-name
,(permutation-name (name property-descriptor)))
,(if (cadr property-descriptor-list)
`(when (possible-p ,@new-accum-list)
,(build-backtracking (cdr property-descriptor-list)
new-accum-list))
`(let ((result (possible-p ,@plural-list)))
(when result
(pprint result)))))
I hope you don't mind all the nit-picking; it's an interesting chunk of
code to play around with.
Tim
In article <············@216.39.145.192>, ·····@herschel.bricoworks.com
says...
> OK, I see what you're trying to do, but in going down this very hairy path
> you've built in a lot of weird dependencies between macro-expand
> time, compile time and run time. Have you tried to compile this in a
> fresh Lisp in which you haven't previously loaded quiz.lisp? In order to
> compile this properly you're going to wrap (eval-when (:compile-toplevel
> :load-toplevel :execute) ...) around all your defun and initializing
> forms. Instead of listing the position and neighbor conditions at top
> level in your file, a more recommended style would be to define a
> define-condition-problem macro or something that would take the condition
> clauses as arguments and do all the required macro definition within the
> context of that macro. This makes it easier to control (and seperate)
> what gets done at macroexpansion time vs. run time.
I see where you're heading at. I have to admit that I wasn't entirely
happy with my solution - separating the INITIALIZE and the SOLVE phase -
which looked a bit unnatural to me. I will think about it a little bit
more - and I will have to read about a couple of things that I don't
seem to understand completely now (like the compile time, run time and
macro-expand time phases you're talking about).
[And yes - it's true that CMUCL chokes when I try to do COMPILE-FILE in
a fresh image. LispWorks doesn't if my memory serves me right.]
> OK, I see on further inspection that you do want the base case to have one
> remaining element. The proper idiom for that is (null (cadr
> property-descriptor-list)) (or second if you prefer). LENGTH has to
> traverse the entire list, so you get n^2 behavior if you use that.
>
> I'd still recommend factoring out the common branches of BUILD-BACTRACKING
> so that the guts of that function look like:
>
> '(dolist (,plural-name
> ,(permutation-name (name property-descriptor)))
> ,(if (cadr property-descriptor-list)
> `(when (possible-p ,@new-accum-list)
> ,(build-backtracking (cdr property-descriptor-list)
> new-accum-list))
> `(let ((result (possible-p ,@plural-list)))
> (when result
> (pprint result)))))
Just about ten minutes before I read this posting of your's I came up
with another solution for BUILD-BACKTRACKING that tests on NULL instead
of CADR (see http://www.weitz.de/files/quiz.lisp). You were right, of
course. Looks like I was just too lazy to think about it a little bit
more.
Also, thanks about the comment about LENGTH. I wasn't aware of this
efficiency issue. (It doesn't matter in this case but it might help me a
lot in my next project.)
> I hope you don't mind all the nit-picking; it's an interesting chunk of
> code to play around with.
I don't mind at all! I'm learning a lot during this conversation.
Thanks,
Edi.
PS: BTW, I was developing all this in LispWorks. I initially tried to
work with nested backquotes but I gave up (until you came in) when it
didn't work and LispWorks' MACROEXPAND-1 only showed weird things like
SYSTEM::BQ-LIST* which didn't help me at all. Only this evening I found
out that CMUCL's MACROEXPAND facility produces much prettier code -
exactly the way I expected it.
[This followup was posted to comp.lang.lisp and a copy was sent to the
cited author.]
In article <············@216.39.145.192>, ·····@herschel.bricoworks.com
says...
> OK, I see what you're trying to do, but in going down this very hairy path
> you've built in a lot of weird dependencies between macro-expand
> time, compile time and run time. Have you tried to compile this in a
> fresh Lisp in which you haven't previously loaded quiz.lisp? In order to
> compile this properly you're going to wrap (eval-when (:compile-toplevel
> :load-toplevel :execute) ...) around all your defun and initializing
> forms. Instead of listing the position and neighbor conditions at top
> level in your file, a more recommended style would be to define a
> define-condition-problem macro or something that would take the condition
> clauses as arguments and do all the required macro definition within the
> context of that macro. This makes it easier to control (and seperate)
> what gets done at macroexpansion time vs. run time.
I did it. I more or less completely rewrote the outer macro which now
IMHO is much easier to understand and also has a more flexible condition
definition facility. (It's slightly slower in LispWorks with no
noticable difference in CMUCL.)
The new version is at
http://www.weitz.de/einstein.html
Let me add that I really enjoyed this conversation with you and I think
it helped me a lot in writing a better program!
Take care,
Edi.
From: DiG
Subject: Re: Why is COMPILE-FILE better than COMPILE?
Date:
Message-ID: <3B6D808C.9070001@mail.com>
Dr. Edmund Weitz wrote:
> [This followup was posted to comp.lang.lisp and a copy was sent to the
> cited author.]
>
> In article <············@216.39.145.192>, ·····@herschel.bricoworks.com
> says...
>
>
>>OK, I see what you're trying to do, but in going down this very hairy path
>>you've built in a lot of weird dependencies between macro-expand
>>time, compile time and run time. Have you tried to compile this in a
>>fresh Lisp in which you haven't previously loaded quiz.lisp? In order to
>>compile this properly you're going to wrap (eval-when (:compile-toplevel
>>:load-toplevel :execute) ...) around all your defun and initializing
>>forms. Instead of listing the position and neighbor conditions at top
>>level in your file, a more recommended style would be to define a
>>define-condition-problem macro or something that would take the condition
>>clauses as arguments and do all the required macro definition within the
>>context of that macro. This makes it easier to control (and seperate)
>>what gets done at macroexpansion time vs. run time.
>>
>
> I did it. I more or less completely rewrote the outer macro which now
> IMHO is much easier to understand and also has a more flexible condition
> definition facility. (It's slightly slower in LispWorks with no
> noticable difference in CMUCL.)
>
> The new version is at
> http://www.weitz.de/einstein.html
>
> Let me add that I really enjoyed this conversation with you and I think
> it helped me a lot in writing a better program!
>
> Take care,
> Edi.
>
I've read about this problem in http://www.norvig.com/paip.html book.
There is also sotution to it in Lisp. You might be interested to look at
the page 373. (unfortunately it is not in the source files on the web site).
Regards,
DIG
--
And now I see with eye serene
The very pulse of the machine.
-- William Wordsworth,
She Was a Phantom of Delight (1804)