From: Kaelin Colclasure
Subject: labels vs. flet
Date: 
Message-ID: <q7aeu180bj.fsf@himalia.talarian.com>
Is there ever any good reason to use flet instead of labels? I understand
that, if you need recursion, you *must* use labels. But is there enough
expense associated with this form to justify the existance (and use) of
flet?

Also, is there any significant difference in cost between a labels/flet
form and an anonymous lambda (again, assuming a scenario where any of the
three could be used)?

From: Kent M Pitman
Subject: Re: labels vs. flet
Date: 
Message-ID: <sfwd7yw4uny.fsf@world.std.com>
Kaelin Colclasure <······@himalia.talarian.com> writes:

> Is there ever any good reason to use flet instead of labels? I understand
> that, if you need recursion, you *must* use labels. But is there enough
> expense associated with this form to justify the existance (and use) of
> flet?

It's not an expense thing, it's a semantics thing.  You can use either
(and many do) when it doesn't matter.  Consider:

  (flet ((foo (x) (+ x 3)))
    (flet ((foo (x) (+ (foo x) 0.1)))
      (foo 1)))

Using LABELS would produce a very different result [actually, an infinite
recursion].  FLET also avoids mutual recursion, as in:

 (flet ((foo (x) (+ x 1))
        (bar (x) (- x 1)))
   (flet ((foo (x) (- (bar x)))
	  (bar (x) (- (foo x))))
     ...))

The issue is not that recursion is "too expensive" but rather that it's
"not always what you're trying to say".

> Also, is there any significant difference in cost between a labels/flet
> form and an anonymous lambda (again, assuming a scenario where any of the
> three could be used)?

Sometimes in practice yes, though the language definition doesn't
address the efficiency per se.  For example, in most implementations,
this is suboptimal if you are being super-efficiency-conscious:

 (defmacro with-foo (&body forms)
   `(call-with-foo #'(lambda () ,@forms)))

because this:

 (defmacro with-foo (&body forms)
   (let ((temp (gensym)))
     `(flet ((,temp () ,@forms))
        (declare (dynamic-extent #',temp))
        (call-with-foo #',temp))))

is usually much more heavily optimized.  The issue is that
the language offers you no way to say an equivalent thing about the
anonymous lambda; dynamic-extent declarations can only refer to named
functions and variables, not to anonymous objects.  The with-foo
definitions mean the same and both are semantically correct, but the
second one probably conses a lot less in good implementations.
From: David Bakhash
Subject: Re: labels vs. flet
Date: 
Message-ID: <cxjr9nc2scn.fsf@acs5.bu.edu>
Kent M Pitman <······@world.std.com> writes:

>  (defmacro with-foo (&body forms)
>    (let ((temp (gensym)))
>      `(flet ((,temp () ,@forms))
>         (declare (dynamic-extent #',temp))
>         (call-with-foo #',temp))))
> 
> is usually much more heavily optimized.  The issue is that
> the language offers you no way to say an equivalent thing about the
> anonymous lambda; dynamic-extent declarations can only refer to named
> functions and variables, not to anonymous objects.  The with-foo
> definitions mean the same and both are semantically correct, but the
> second one probably conses a lot less in good implementations.

Kent,

would you mind explaining why your dynamic-extent declaration makes sense here
and not in the average use of flet?  Obviously, this declaration (that I
admittedly do not understand after reading the HyperSpec) can optimize in
certain situations, but I would like to know when it may be used.

thanks,
dave
From: David Bakhash
Subject: Re: labels vs. flet
Date: 
Message-ID: <cxjogig2qkf.fsf@acs5.bu.edu>
I feel that I didn't provide enough background to why I am confused about what
KP said.

Suppose you have this code:

(defvar *set-of-stuff* '(that that other))

(defun find-stuff (list)
  (find *set-of-stuff* list
	:test #'(lambda (x y)
		  (member y x))))

Is there some more efficient way using flet?  i.e. construct the function

declaration?

My hopes are that the above compiles as efficiently as the flet would.


dave
From: Kent M Pitman
Subject: Re: labels vs. flet
Date: 
Message-ID: <sfwbteghu7u.fsf@world.std.com>
David Bakhash <·····@bu.edu> writes:

> I feel that I didn't provide enough background to why I am confused about what
> KP said.

(I'd prefer you referred to me as KMP for search reasons, btw.)

> Suppose you have this code:
> 
> (defvar *set-of-stuff* '(that that other))
> 
> (defun find-stuff (list)
>   (find *set-of-stuff* list
> 	:test #'(lambda (x y)
> 		  (member y x))))
> 
> Is there some more efficient way using flet?  i.e. construct the function
> 
> declaration?
> 
> My hopes are that the above compiles as efficiently as the flet would.

It might.  But only if the compiler has special knowledge of FIND
that lets it know that FIND will not store or return the functional
argument given as the test.  If it knows that fact, it can allocate
the closure on the stack.  Otherwise, it must heap-cons it just in case,
since if FIND were FOO instead, the compiler would have no reason to know
what FOO will do with its arg, nor would FOO have any way of doing the
right thing with a stack-consed argument.  (Of course, you could slow down
all stores into the heap by checking to see if they were stack pointers,
but absent special hardware, I wouldn't recommend that.)  

Also, your example is contrived and so I'm ignoring the fact that 
 #'(lambda (x y) (member y x))
doesn't produce a closure since there are no free variables and most
compilers will compile this in a way that doesn't cons at all at runtime,
so I'm assuming you meant to ask about #'(lambda (x y) (funcall z x y))
for some closure over z.

However, a compiler will do better compiling the following than the
above:

 (defun find-stuff (z list)
   (flet ((xmember (y x) (funcall z x y)))
     (declare (dynamic-extent #'xmember))
     (my-find *set-of-stuff* list :test #'xmember)))

than

 (defun find-stuff (z list)
   (my-find *set-of-stuff* list 
        :test #'(lambda (y x) (funcall z x y))))

The Lisp Machine had a declaration:

 (defun find-stuff (z list)
   (my-find *set-of-stuff* list 
        :test #'(lambda (y x)
                  (declare (sys:downward-function))
                  (funcall z x y))))

which did this, but that was a bit semantically messy.  For example,
consider:

 (defun find-stuff (z list)
   (let ((foo #'(lambda (y x)
                  (declare (sys:downward-function))
                  (funcall z x y))))
     (my-find *set-of-stuff* list 
        :test foo)))

The question is whether the closure is returned "up" (into the LET)
before going back "down" into the call to MY-FIND, and so there needs to
be a bound against which you are sure you're measuring the downwardness.
FLET provides that by having a bounding set of parens around the FLET
form that contains both the lambda expression and the call.
From: vincent
Subject: Re: labels vs. flet
Date: 
Message-ID: <7k8iae$obu$1@nnrp1.deja.com>
In article <···············@world.std.com>,
  Kent M Pitman <······@world.std.com> wrote:
> Kaelin Colclasure <······@himalia.talarian.com> writes:
>
> > Is there ever any good reason to use flet instead of labels? I
understand
> > that, if you need recursion, you *must* use labels. But is there
enough
> > expense associated with this form to justify the existance (and use)
of
> > flet?
>
> It's not an expense thing, it's a semantics thing.  You can use either
> (and many do) when it doesn't matter.  Consider:
>
>   (flet ((foo (x) (+ x 3)))
>     (flet ((foo (x) (+ (foo x) 0.1)))
>       (foo 1)))
>
> Using LABELS would produce a very different result [actually, an
infinite
> recursion].  FLET also avoids mutual recursion, as in:
>
>  (flet ((foo (x) (+ x 1))
>         (bar (x) (- x 1)))
>    (flet ((foo (x) (- (bar x)))
> 	  (bar (x) (- (foo x))))
>      ...))
>
> The issue is not that recursion is "too expensive" but rather that
it's
> "not always what you're trying to say".
>
> > Also, is there any significant difference in cost between a
labels/flet
> > form and an anonymous lambda (again, assuming a scenario where any
of the
> > three could be used)?
>
> Sometimes in practice yes, though the language definition doesn't
> address the efficiency per se.  For example, in most implementations,
> this is suboptimal if you are being super-efficiency-conscious:
>
>  (defmacro with-foo (&body forms)
>    `(call-with-foo #'(lambda () ,@forms)))
>
> because this:
>
>  (defmacro with-foo (&body forms)
>    (let ((temp (gensym)))
>      `(flet ((,temp () ,@forms))
>         (declare (dynamic-extent #',temp))
>         (call-with-foo #',temp))))
>
> is usually much more heavily optimized.  The issue is that
> the language offers you no way to say an equivalent thing about the
> anonymous lambda; dynamic-extent declarations can only refer to named
> functions and variables, not to anonymous objects.  The with-foo
> definitions mean the same and both are semantically correct, but the
> second one probably conses a lot less in good implementations.
>


Couldn't you just keep the first version and say instead:

(defun call-with-foo (function)
  (declare (ftype (function () t) function)
           (dynamic-extent function))
  ...)

?


Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
From: Kent M Pitman
Subject: Re: labels vs. flet
Date: 
Message-ID: <sfwaeu0hu39.fsf@world.std.com>
vincent <···········@my-deja.com> writes:

> Couldn't you just keep the first version and say instead:
> 
> (defun call-with-foo (function)
>   (declare (ftype (function () t) function)
>            (dynamic-extent function))
>   ...)
> 
> ?
No.  This declaration is at time-of-receipt, not time of call.
Some compilers if they see this will assume that compilations
that follow call-with-foo should be compiled unsafely, but consider
what would happen if you redefined call-with-foo to not have this
declaration.  Callers would not get recompiled, and bad things 
would happen. CL does not prescribe any effect of the declaration
that transcends the lexical scope in which it appears.  If you
had a "block compiler", of course, it can do that because it is
working with a closed-world model.  But a normal Lisp compiler assumes
independent functions might be redefined and that the system needs to still
function correctly.  All of the language definition is about this.
The operators (like DEFCONSTANT) that work against this are plainly 
documented.  We could, I suppose,k document such a beahvior for
dynamic-extent, but we have not.
From: Stig Hemmer
Subject: Smart compilers.  Overly smart?
Date: 
Message-ID: <ekvogifx5m6.fsf_-_@gnoll.pvv.ntnu.no>
[Snipping context and changing subject since I'm wondering about a
 wider context than the original]
Kent M Pitman <······@world.std.com> writes:
> If you had a "block compiler", of course, it can do that because it
> is working with a closed-world model.  But a normal Lisp compiler
> assumes independent functions might be redefined and that the system
> needs to still function correctly.  All of the language definition
> is about this.

This is of course true, but it seems like a bother for the Lisp system
to have to be that careful all the time.

A smart system could remember that "If FOO is changed, I need to check
is condition X still holds, if not, I need to recompile FOOs callers
too, and its callers are BAR and BAZ."  This would open possibilites
for all sorts of optimalizations.

A _really_ smart system could do variable usage analysis and squeeze
in an extra optimalization or two.

Would this be legal?  An ideal implementation of this should not
differ from a standard implmentation in anything but compile
speed(slower) and runtime speed(faster).  But can that be achieved?

Does any implementation do anything like this?  (Much implementation
work for little benefit, I know...)

Stig Hemmer,
Jack of a Few Trades.
From: Jeffrey Mark Siskind
Subject: Re: Smart compilers.  Overly smart?
Date: 
Message-ID: <yq7674ng31y.fsf@qobi.nj.nec.com>
> A smart system could remember that "If FOO is changed, I need to check
> is condition X still holds, if not, I need to recompile FOOs callers
> too, and its callers are BAR and BAZ."  This would open possibilites
> for all sorts of optimalizations.

> Does any implementation do anything like this?  (Much implementation
> work for little benefit, I know...)

For the limited case of determinism analysis Screamer does this. Screamer
extends Common Lisp portably to allow nondeterministic functions
(i.e. backtracking). Nondeterministic functions must be converted to CPS
before compilation. But incremental redefinition can allow a deterministic
function to become nondeterministic and vice versa. Screamer keeps track of
the call graph and (behind your back) recompiles the necessary functions.

    Jeff (http://www.neci.nj.nec.com/homepages/qobi)
From: Kent M Pitman
Subject: Re: Smart compilers.  Overly smart?
Date: 
Message-ID: <sfwyahjtoxa.fsf@world.std.com>
Stig Hemmer <····@pvv.ntnu.no> writes:

> ... it seems like a bother for the Lisp system
> to have to be that careful all the time.
> 
> A smart system could remember that "If FOO is changed, I need to check
> is condition X still holds, if not, I need to recompile FOOs callers
> too, and its callers are BAR and BAZ."  This would open possibilites
> for all sorts of optimalizations.

Um... yes, and no.  In some sense, Lisp has traditionally been an
exercise in using its own typing model to implement data connecivity.
That is, the whole point to "redefinition ok" is the idea that there
is a constant factor of cost when you make an incremental change, so that
snapping a new definition in is as simple as a pointer update, same
as assigning a variable.  You can indeed without changing the semantics
make this more complicated, so that redefinition carries a high price
but you get faster code in exchange for doing it that way.  I'm not 
saying you should or shouldn't do it that way, nor does the language
prescribe a particular implementation, but I guess I'd just observe
it hasn't traditionally been done that way much.  And, moreover, what
you suggest is not really saying the opposite of what I said--in a sense,
you're saying "it's ok to violate the rule I gave as long as you make
sure no one can detect the violation".
 
> A _really_ smart system could do variable usage analysis and squeeze
> in an extra optimalization or two.
>
> Would this be legal?

A little sketchy on the question, but I think so.

> An ideal implementation of this should not
> differ from a standard implmentation in anything but compile
> speed(slower) and runtime speed(faster).  But can that be achieved?

No, I think you're omitting one other way it differs:  the distribution
of cost is different.  For example, a runtime redefinition, if such
occurs, may cost proportionally more, too.  You can't just call that
compile-time, except in the trivial sense that a non-compile action
might cause the need to compile and so (trivially) increases compile-time
(by causing it to happen).

> Does any implementation do anything like this?  (Much implementation
> work for little benefit, I know...)

Maclisp used to do something similar.  Its "uuo links" facility is what
I'm thinking about.  I won't explain now.  It's late. Maybe someone else
will. Or maybe I will on another day.
 
> Stig Hemmer,
> Jack of a Few Trades.
> 
From: Kaelin Colclasure
Subject: Re: labels vs. flet
Date: 
Message-ID: <q7674n9al7.fsf@himalia.talarian.com>
Kent M Pitman <······@world.std.com> writes:

> Kaelin Colclasure <······@himalia.talarian.com> writes:
> 
> > Is there ever any good reason to use flet instead of labels? I understand
> > that, if you need recursion, you *must* use labels. But is there enough
> > expense associated with this form to justify the existance (and use) of
> > flet?
> 
> It's not an expense thing, it's a semantics thing.  You can use either
> (and many do) when it doesn't matter.  Consider:
> 
>   (flet ((foo (x) (+ x 3)))
>     (flet ((foo (x) (+ (foo x) 0.1)))
>       (foo 1)))

Ahh, interesting. I never thought of that particular usage. And I probably
should have, since a similar discussion of the behavior of Dylan's let form
went on just a few weeks ago. The parellels to CL let vs. let* are apparent.
Hmmm, so why not flet*? (I suspect the answer is compatibility with some
pre-CL dialect of Lisp.)