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
+ David Sletten <·····@slytobias.com>:
| 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 <URL:http://www.math.ntnu.no/~hanche/>
- 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
+ Harald Hanche-Olsen <······@math.ntnu.no>:
| + David Sletten <·····@slytobias.com>:
|
| | 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 <URL:http://www.math.ntnu.no/~hanche/>
- 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
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
David Sletten <·····@slytobias.com> 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 '#<Compiled-function F (Non-Global) #x64EDBFE> 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
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
David Sletten <·····@slytobias.com> writes:
> 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.
I was thinking in terms of LABELS/FLET defining local functions, but
that doesn't seem to be the answer. I also had a look at 3.1
Evaluation to see if that could do a better job. But the way I read
it, an implementation could naively redefine local functions over and
over. It doesn't seem like something you have to worry about with
existing implementations though. I would go ahead and just use
LABELS/FLET as intended. Compilers are going to expect it.
--
An ideal world is left as an excercise to the reader.
--- Paul Graham, On Lisp 8.1
David Steuber wrote:
> I was thinking in terms of LABELS/FLET defining local functions, but
> that doesn't seem to be the answer. I also had a look at 3.1
> Evaluation to see if that could do a better job. But the way I read
> it, an implementation could naively redefine local functions over and
> over. It doesn't seem like something you have to worry about with
> existing implementations though. I would go ahead and just use
> LABELS/FLET as intended. Compilers are going to expect it.
>
Yeah, that's the pragmatic approach I'm going to apply. This is still
sort of on my list of unresolved questions though...
Thanks,
David Sletten
start quoting David Sletten :
> David Steuber wrote:
>
>
>> I was thinking in terms of LABELS/FLET defining local functions, but
>> that doesn't seem to be the answer. I also had a look at 3.1
>> Evaluation to see if that could do a better job. But the way I read
>> it, an implementation could naively redefine local functions over and
>> over. It doesn't seem like something you have to worry about with
>> existing implementations though. I would go ahead and just use
>> LABELS/FLET as intended. Compilers are going to expect it.
>>
>
> Yeah, that's the pragmatic approach I'm going to apply. This is still
> sort of on my list of unresolved questions though...
>
The Common Lisp specification doesn't define much in the way of compiler
efficiency, but as it has been showed, this particular optimization is
actually very simple.
You have to have some faith in the compiler; it would almost be harder *not*
to do this optimization than to do it, so you can probably assume it will
always be done.
David Sletten wrote:
[TR-1]
> (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)))
[TR-2A]
> (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)))
[TR-2B]
> (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.
It's not only hard for the programmer to find, but the Common Lisp
compiler is also not required to notice it, so code that calls
fibonacci-tr-2a may result in inefficient code.
> 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.
...that's because it's allowed to say (setf (symbol-function
'fibonacci-tr-aux) (lambda ...)), i.e. it's allowed to redefine
functions at runtime. IIRC, the compiler is allowed to ignore that under
some circumstances, but I think it's likely that CLISP does the double
indirection via the function cell.
This kind of redefinition of functions is not possible for local
functions because the local bindings of their names are not accessible.
Pascal
Pascal Costanza wrote:
> David Sletten wrote:
>
> [TR-1]
>
>> (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)))
>
>
> [TR-2A]
>
>> (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)))
>
>
> [TR-2B]
>
>> (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.
>
>
> It's not only hard for the programmer to find, but the Common Lisp
> compiler is also not required to notice it, so code that calls
> fibonacci-tr-2a may result in inefficient code.
>
>> 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.
>
>
> ...that's because it's allowed to say (setf (symbol-function
> 'fibonacci-tr-aux) (lambda ...)), i.e. it's allowed to redefine
> functions at runtime. IIRC, the compiler is allowed to ignore that under
> some circumstances, but I think it's likely that CLISP does the double
> indirection via the function cell.
>
> This kind of redefinition of functions is not possible for local
> functions because the local bindings of their names are not accessible.
>
>
> Pascal
Thanks Pascal. This fills in another piece of the puzzle:
When TR-1 is invoked it has to call TR-AUX. But first it must decide
"What is the current function TR-AUX?" (Could change at runtime.) It has
to look up that function before calling it.
On the other hand, TR-2 simply says "Call the local function that was
already compiled with me." There will never be any runtime variability
about what the local function is.
David Sletten
David Sletten <·····@slytobias.com> writes:
> Pascal Costanza wrote:
>
>> David Sletten wrote:
>> [TR-1]
>>
>>> (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)))
>> [TR-2A]
>>
>>> (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)))
>> [TR-2B]
>>
>>> (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.
>> It's not only hard for the programmer to find, but the Common Lisp
>> compiler is also not required to notice it, so code that calls
>> fibonacci-tr-2a may result in inefficient code.
>>
>>> 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.
>> ...that's because it's allowed to say (setf (symbol-function
>> fibonacci-tr-aux) (lambda ...)), i.e. it's allowed to redefine
>> functions at runtime. IIRC, the compiler is allowed to ignore that
>> under some circumstances, but I think it's likely that CLISP does
>> the double indirection via the function cell.
>> This kind of redefinition of functions is not possible for local
>> functions because the local bindings of their names are not
>> accessible.
>> Pascal
>
> Thanks Pascal. This fills in another piece of the puzzle: When TR-1
> is invoked it has to call TR-AUX. But first it must decide "What is
> the current function TR-AUX?" (Could change at runtime.) It has to
> look up that function before calling it.
You may, however, want to keep in mind the fact that Pascal aluded
to--that if fibonacci-tr-1 and fibonacci-tr-aux are defined in the
same file and you compile it with COMPILE-FILE, unless
fibonacci-tr-aux is declared NOT-INLINE it can be inlined in
fibonacci-tr-1 by the compiler.
-Peter
--
Peter Seibel ·····@javamonkey.com
Lisp is the red pill. -- John Fraser, comp.lang.lisp
Peter Seibel wrote:
> You may, however, want to keep in mind the fact that Pascal aluded
> to--that if fibonacci-tr-1 and fibonacci-tr-aux are defined in the
> same file and you compile it with COMPILE-FILE, unless
> fibonacci-tr-aux is declared NOT-INLINE it can be inlined in
> fibonacci-tr-1 by the compiler.
>
> -Peter
>
Good point. I've been thinking mostly in terms of the REPL, but that's
something to consider when compiling a file. The compiler may "freeze"
the definition of TR-AUX used by TR-1, eh? I guess it would be unusual
to redefine a global function in a running program. Obviously it happens
a lot during development though.
David Sletten
David Sletten wrote:
> Peter Seibel wrote:
>
>
>> You may, however, want to keep in mind the fact that Pascal aluded
>> to--that if fibonacci-tr-1 and fibonacci-tr-aux are defined in the
>> same file and you compile it with COMPILE-FILE, unless
>> fibonacci-tr-aux is declared NOT-INLINE it can be inlined in
>> fibonacci-tr-1 by the compiler.
>>
>> -Peter
>
> Good point. I've been thinking mostly in terms of the REPL, but that's
> something to consider when compiling a file. The compiler may "freeze"
> the definition of TR-AUX used by TR-1, eh? I guess it would be unusual
> to redefine a global function in a running program. Obviously it happens
> a lot during development though.
...and if you want to redefine a function at runtime, it's better to use
a generic function and modify its methods. Then you have a guarantee
that this always works as it should.
Pascal