|
|
 | | From: | David Sletten | | Subject: | FLET/LABELS question | | Date: | Sun, 23 Jan 2005 09:00:07 GMT |
|
|
 | The special operators LABELS and FLET can be used to define local
functions. However, under certain circumstances they appear to do their
work at compile time rather than runtime. By contrast, other special
operators must always do work at runtime:
(if (> x 5) 'foo 'bar)
Here IF must respond conditionally to the value of X. But the following
examples seem to suggest that LABELS doesn't always define a function at
runtime.
Consider a tail-recursive Fibonacci sequence definition:
(defun fibonacci-tr-1 (n)
(fibonacci-tr-aux n 1 0))
(defun fibonacci-tr-aux (n f1 f2)
(if (zerop n)
f1
(fibonacci-tr-aux (1- n) (+ f1 f2) f1)))
The auxiliary function does all of the main work but shouldn't
necessarily be exposed this way. Instead we can tuck it away inside the
main function:
(defun fibonacci-tr-2 (n)
(labels ((fibonacci-tr-aux (n f1 f2)
(if (zerop n)
f1
(fibonacci-tr-aux (1- n) (+ f1 f2) f1))))
(fibonacci-tr-aux n 1 0)))
Based on my understanding of LABELS, however, I thought that this would
redefine the auxiliary function each time FIBONACCI-TR-2 was called. The
alternative seemed to be this awkward code:
(labels ((fibonacci-tr-aux (n f1 f2)
(if (zerop n)
f1
(fibonacci-tr-aux (1- n) (+ f1 f2) f1))))
(defun fibonacci-tr-2a (n)
(fibonacci-tr-aux n 1 0)))
This seems less than ideal since the DEFUN is harder to find.
When I timed these functions I expected TR-1 or TR-2A to be fastest
since they did less work by not having to define the auxiliary function
each time. However, in both SBCL and CLISP TR-2 and TR-2A perform about
the same. In fact, with CLISP, TR-1 is substantially slower than either
of the other two. It is evident that the LABELS in TR-2 is _not_
creating a new function at runtime, but rather freezes the definition
when the enclosing function is compiled.
There is a further case which seemed to me even more obvious that LABELS
would have to redefine a function at runtime. This is the situation
where the LABELS function creates a closure over a local variable of the
enclosing function:
(defun fibonacci-tr-3 (n)
(labels ((fibonacci-tr-aux (i f1 f2)
(if (= i n)
f1
(fibonacci-tr-aux (1+ i) (+ f1 f2) f1))))
(fibonacci-tr-aux 0 1 0)))
Here the parameter N could change on each invocation of FIBONACCI-TR-3,
so it seemed that LABELS couldn't generate a fixed auxiliary function.
However, this function is just as fast as the others. Perhaps the
compiler is smart enough to ensure references to N in the LABELS
function simply point to whatever storage has been allocated for the
outer function?
I guess the issue is more general than just LABELS/FLET. The following
seemed to be the same problem:
(defun add-to-elts (n l)
(mapcar #'(lambda (elt)
(+ n elt))
l))
The LAMBDA function creates a closure over ADD-TO-ELTS' parameter N.
Rather than creating a new LAMBDA function each time ADD-TO-ELTS is
called perhaps the compiler arranges things as above with FIBONACCI-TR-3.
Finally, there are cases where LABELS or LAMBDA _must_ generate
functions at runtime:
(defun counter-maker (n)
#'(lambda ()
(incf n)))
Here, two separate invocations of COUNTER-MAKER generate functions which
are never EQ.
Have I got things straightened out here? In particular, is this behavior
implementation-specific? Or is it so widespread as to be expected? Is
defensive coding such as TR-2A a good idea?
Thanks,
David Sletten
|
|
| | From: | Harald Hanche-Olsen | | Subject: | Re: FLET/LABELS question | | Date: | 23 Jan 2005 13:13:03 +0100 |
|
|
| + David Sletten :
| The special operators LABELS and FLET can be used to define local
| functions. However, under certain circumstances they appear to do
| their work at compile time rather than runtime.
Sure. They are compile-time concepts, after all, no? There is no
need for the compiler to create anything recognizable as a function,
unless of course the user chooses to expose the function using
(function foo). Otherwise, all that is needed is a bit of machine
code implementing. The knowledge on how to call it can be local to
the LABELS form.
| (defun fibonacci-tr-2 (n)
| (labels ((fibonacci-tr-aux (n f1 f2)
| (if (zerop n)
| f1
| (fibonacci-tr-aux (1- n) (+ f1 f2) f1))))
| (fibonacci-tr-aux n 1 0)))
|
| Based on my understanding of LABELS, however, I thought that this
| would redefine the auxiliary function each time FIBONACCI-TR-2 was
| called.
I think you are thinking about this in a much too literal form. What
it really means is that the form (fibonacci-tr-aux n 1 0) compiles
into machine code to call the machine code that resulted from
compiling the body of fibonacci-tr-aux. In the case of interpreted
code, it might be different - but I believe that even then, the
interpreter may choose to do the necessary optimization while
processing the definition of fibonacci-tr-2.
| When I timed these functions I expected TR-1 or TR-2A to be fastest
| since they did less work by not having to define the auxiliary
| function each time. However, in both SBCL and CLISP TR-2 and TR-2A
| perform about the same.
Why do you care about what timing tells you? (Apart from the ovious
goal of writing optimal code, of course.) The only relevant question
is whether the different implementation choices would result in
different values being computed.
| (defun fibonacci-tr-3 (n)
| (labels ((fibonacci-tr-aux (i f1 f2)
| (if (= i n)
| f1
| (fibonacci-tr-aux (1+ i) (+ f1 f2) f1))))
| (fibonacci-tr-aux 0 1 0)))
|
| Here the parameter N could change on each invocation of
| FIBONACCI-TR-3, so it seemed that LABELS couldn't generate a fixed
| auxiliary function. However, this function is just as fast as the
| others. Perhaps the compiler is smart enough to ensure references to
| N in the LABELS function simply point to whatever storage has been
| allocated for the outer function?
Precisely. The compiler is /allowed/ to be smart, so long as it
produces correct code.
| Finally, there are cases where LABELS or LAMBDA _must_ generate
| functions at runtime:
| (defun counter-maker (n)
| #'(lambda ()
| (incf n)))
|
| Here, two separate invocations of COUNTER-MAKER generate functions
| which are never EQ.
But even here, the body of the lambda will typically be compiled at
compile-time. All that remains at runtime is to create a closure,
which will involve creating a small data structure with space for the
variable n together with a link to the compiled code.
| Have I got things straightened out here? In particular, is this
| behavior implementation-specific?
No, and yes. Implementations are free to do whatever they please, so
long as they produce correct code. The point is that you should not
be able to detect any difference, other than through timing or playing
with compiled-function-p.
| Is defensive coding such as TR-2A a good idea?
I don't see why it should be.
--
* Harald Hanche-Olsen
- Debating gives most of us much more psychological satisfaction
than thinking does: but it deprives us of whatever chance there is
of getting closer to the truth. -- C.P. Snow
|
|
| | From: | David Sletten | | Subject: | Re: FLET/LABELS question | | Date: | Sun, 23 Jan 2005 22:20:32 GMT |
|
|
| Harald Hanche-Olsen wrote:
>
> I think you are thinking about this in a much too literal form. What
> it really means is that the form (fibonacci-tr-aux n 1 0) compiles
> into machine code to call the machine code that resulted from
> compiling the body of fibonacci-tr-aux. In the case of interpreted
> code, it might be different - but I believe that even then, the
> interpreter may choose to do the necessary optimization while
> processing the definition of fibonacci-tr-2.
>
> | When I timed these functions I expected TR-1 or TR-2A to be fastest
> | since they did less work by not having to define the auxiliary
> | function each time. However, in both SBCL and CLISP TR-2 and TR-2A
> | perform about the same.
>
> Why do you care about what timing tells you? (Apart from the ovious
> goal of writing optimal code, of course.) The only relevant question
> is whether the different implementation choices would result in
> different values being computed.
>
Thanks for your reply Harald. The reason I cared about timing is
precisely because it appears to have disproved my hypothesis. LABELS is
_not_ doing extra work at runtime. Consequently, the awkward style of
TR-2A is unnecessary. (Good news--I'm not used to Lisp making me bend
over backwards.) How else would I as a programmer, rather than an
implementer, gain any insight beyond my 'too literal' understanding? Is
there a section in the standard that clarifies this?
Based on my timing results and your comments I would now conclude that
TR-2 might be faster than TR-1 (rather than slower as I expected)
because the compiler can maybe inline the auxiliary function. TR-1 has
to rely on an explicit call to a second function.
> | Finally, there are cases where LABELS or LAMBDA _must_ generate
> | functions at runtime:
> | (defun counter-maker (n)
> | #'(lambda ()
> | (incf n)))
> |
> | Here, two separate invocations of COUNTER-MAKER generate functions
> | which are never EQ.
>
> But even here, the body of the lambda will typically be compiled at
> compile-time. All that remains at runtime is to create a closure,
> which will involve creating a small data structure with space for the
> variable n together with a link to the compiled code.
>
This was especially counterintuitive, but your explanation makes perfect
sense. The compiler just creates a generic function whose details are
plugged in with a specific environment at runtime.
Thanks,
David Sletten
|
|
| | From: | David Steuber | | Subject: | Re: FLET/LABELS question | | Date: | 24 Jan 2005 01:11:21 -0500 |
|
|
| David Sletten writes:
> Thanks for your reply Harald. The reason I cared about timing is
> precisely because it appears to have disproved my hypothesis. LABELS
> is _not_ doing extra work at runtime. Consequently, the awkward style
> of TR-2A is unnecessary. (Good news--I'm not used to Lisp making me
> bend over backwards.) How else would I as a programmer, rather than an
> implementer, gain any insight beyond my 'too literal' understanding?
> Is there a section in the standard that clarifies this?
You should take another look at:
http://www.lispworks.com/documentation/HyperSpec/Body/s_flet_.htm
Also, you might find DISASEMBLE to be of interest:
CL-USER> (defun factorial (n)
(labels ((f (x)
(if (< x 2)
x
(* x (f (1- x))))))
(f n)))
FACTORIAL
CL-USER> (factorial 6)
720
CL-USER> (disassemble 'factorial)
(TWNEI NARGS 4)
(MFLR LOC-PC)
(BLA .SPSAVECONTEXTVSP)
(VPUSH ARG_Z)
(LWZ ARG_Z 0 VSP)
(SET-NARGS 1)
(LWZ TEMP2 '# FN)
(BLA .SPRESTORECONTEXT)
(MTLR LOC-PC)
(LWZ TEMP0 -2 TEMP2)
(MTCTR TEMP0)
(BCTR)
; No value
Rather than trying to use timings to see what the code does, have a
look at the generated code to see what the code does.
CL-USER> (defun factorial (n)
(if (< n 2)
n
(* n (factorial (1- n)))))
FACTORIAL
CL-USER> (factorial 6)
720
CL-USER> (disassemble 'factorial)
L0
(TWNEI NARGS 4)
(MFLR LOC-PC)
(BLA .SPSAVECONTEXTVSP)
(:REGSAVE SAVE0 0)
(VPUSH SAVE0)
(MR SAVE0 ARG_Z)
(MR ARG_Y SAVE0)
(LI ARG_Z '2)
(BLA .SPBUILTIN-LT)
(CMPWI ARG_Z NIL)
(BEQ L52)
(MR ARG_Z SAVE0)
(LWZ SAVE0 0 VSP)
(BA .SPPOPJ)
L52
(MR ARG_Y SAVE0)
(LI ARG_Z '1)
(BLA .SPBUILTIN-MINUS)
(SET-NARGS 1)
(MR TEMP2 FN)
(BL L0)
(MR ARG_Y SAVE0)
(LWZ SAVE0 0 VSP)
(BLA .SPRESTORECONTEXT)
(MTLR LOC-PC)
(BA .SPBUILTIN-TIMES)
; No value
CL-USER> (defun factorial (n)
(do ((f n (* f n)))
((< n 2) (max f 1))
(decf n)))
FACTORIAL
CL-USER> (factorial 6)
720
CL-USER> (disassemble 'factorial)
(TWNEI NARGS 4)
(MFLR LOC-PC)
(BLA .SPSAVECONTEXTVSP)
(:REGSAVE SAVE1 0)
(VPUSH SAVE0)
(VPUSH SAVE1)
(MR SAVE0 ARG_Z)
(MR SAVE1 SAVE0)
(B L64)
L32
(MR ARG_Y SAVE0)
(LI ARG_Z '1)
(BLA .SPBUILTIN-MINUS)
(MR SAVE0 ARG_Z)
(MR ARG_Y SAVE1)
(MR ARG_Z SAVE0)
(BLA .SPBUILTIN-TIMES)
(MR SAVE1 ARG_Z)
L64
(MR ARG_Y SAVE0)
(LI ARG_Z '2)
(BLA .SPBUILTIN-LT)
(CMPWI ARG_Z NIL)
(BEQ L32)
(MR ARG_Y SAVE1)
(LI ARG_Z '1)
(BLA .SPBUILTIN-GT)
(CMPWI ARG_Z NIL)
(BEQ L112)
(MR ARG_Z SAVE1)
(B L116)
L112
(LI ARG_Z '1)
L116
(LWZ SAVE1 0 VSP)
(LWZ SAVE0 4 VSP)
(BA .SPPOPJ)
; No value
CL-USER>
--
An ideal world is left as an excercise to the reader.
--- Paul Graham, On Lisp 8.1
|
|
| | From: | David Sletten | | Subject: | Re: FLET/LABELS question | | Date: | Mon, 24 Jan 2005 07:49:29 GMT |
|
|
| David Steuber wrote:
>
> You should take another look at:
>
> http://www.lispworks.com/documentation/HyperSpec/Body/s_flet_.htm
>
What is it that I am missing which is clarified on that page? I've read
it many times but don't see anything relevant to my question.
> Also, you might find DISASEMBLE to be of interest:
>
Yes, clearly this is useful. However, it is also obviously _completely_
implementation specific. I was curious about whether I can rely on this
behavior (LABELS finished at compile time) in any Common Lisp system.
Thanks anyway...
David Sletten
|
|
| | From: | Harald Hanche-Olsen | | Subject: | Re: FLET/LABELS question | | Date: | 23 Jan 2005 13:24:23 +0100 |
|
|
| + Harald Hanche-Olsen :
| + David Sletten :
|
| | The special operators LABELS and FLET can be used to define local
| | functions. However, under certain circumstances they appear to do
| | their work at compile time rather than runtime.
|
| Sure. They are compile-time concepts, after all, no? There is no
| need for the compiler to create anything recognizable as a function,
except to the debugger of course. But nothing stops the debugger from
having access to all sorts of extra information about which piece of
machine code corresponds to what.
| unless of course the user chooses to expose the function using
| (function foo). Otherwise, all that is needed is a bit of machine
| code implementing
foo. (forgot a word, but I hope the meaning was clear).
--
* Harald Hanche-Olsen
- Debating gives most of us much more psychological satisfaction
than thinking does: but it deprives us of whatever chance there is
of getting closer to the truth. -- C.P. Snow
|
|
|
