If I create a function that calls lambda to make a closure each time,
am I effectively calling an optimizing compiler with each call to the
outer function? I realise this may be implementation specific, but
what is the typical runtime penalty? (e.g. CLisp, CMUCL)
KanZen
On Wed, Mar 03, 2004 at 11:22:37AM -0800, KanZen wrote:
> If I create a function that calls lambda to make a closure each time,
> am I effectively calling an optimizing compiler with each call to the
> outer function? I realise this may be implementation specific, but
> what is the typical runtime penalty? (e.g. CLisp, CMUCL)
Incorrect, closures are compiled efficiently and do not require the
compiler at run-time. Consider that many languages use the same
concept, including ones which do not offer run-time compilation support.
A function is a value, much like 1, #\A, or "Hello", and does not need
to be compiled at run-time any more than those values do.
--
; Matthew Danish <·······@andrew.cmu.edu>
; OpenPGP public key: C24B6010 on keyring.debian.org
; Signed or encrypted mail welcome.
; "There is no dark side of the moon really; matter of fact, it's all dark."
······@mail.com (KanZen) wrote in message news:<···························@posting.google.com>...
> If I create a function that calls lambda to make a closure each time,
> am I effectively calling an optimizing compiler with each call to the
> outer function?
No. A closure is an object that points to a piece of code and to an
object that holds the lexical environment: the bindings of free
variables.
Evaluating the same lambda expression multiple times produces a new
object each time. Each such object will point to the same code, and
some of them may point to the same bindings too, which is the case if
you evaluate the expression multiple times without leaving and
re-entering the scope.
> I realise this may be implementation specific, but
> what is the typical runtime penalty? (e.g. CLisp, CMUCL)
The actual evaluation of the lambda expression should be cheap, but
the lexical environment has to be prepared in a closure-friendly way,
because the bindings have indefinite extent.
Obviously, the captured variables cannot exist in an ordinary stack
frame, because that frame will be torn down when the scope is exited.
In languages that have only second-class closures (that can be passed
down into called code, but not returned), a pointer into the stack is
enough to access the lexical environment when the closure is called
back. The runtimes for such languages need just a little bit of added
complexity in the stack layout. Pascal's nested functions are like
this.
True closures require more complexity: the captured bindings have to
be heap-allocated, not stack allocated, so that they have indefinite
extent. Lexical variables that are not subject to capture can still go
onto regular, fast stack frames. The beauty of lexical scope is that a
compiler can see the entire scope at once, and translate it
efficiently. It can look at all the levels of nesting, analyze what
closures are made where and what free variable references they make.
It can also try to determine what closures ``escape'' (are returned
from) the environment in which they are made, and which do not.
Consequently, it can allocate variables to stack frames or
heap-allocated frames accordingly.
Kaz Kylheku wrote:
> The actual evaluation of the lambda expression should be cheap, but
> the lexical environment has to be prepared in a closure-friendly way,
> because the bindings have indefinite extent.
>
> Obviously, the captured variables cannot exist in an ordinary stack
> frame, because that frame will be torn down when the scope is exited.
What everyone has been missing in this thread is that non-null closures
cost _time_ to set up in addition to storage. If the closure is used as
a first-class object, that object must be allocated and associated with
its closed-over bindings. This consumes cycles whether the closure and
its associated binding storage are created on the stack or in the heap.
Creation time is zero only if the closure is a "null closure" (i.e.
actually references no bindings) or if the compiler can rewrite the
closure in some other way.
Finally, it is often the case that a reference to a closed-over binding
is slightly more expensive in cycles than a reference to a regular local
lexical variable (which is usually a refence to a fixed location in the
current stack frame). This might or might not be significant depending
on the nature of the function.
> It can also try to determine what closures ``escape'' (are returned
> from) the environment in which they are made, and which do not.
> Consequently, it can allocate variables to stack frames or
> heap-allocated frames accordingly.
The Franz compiler spends a lot of energy doing this, and it is quite
worthwhile for coding styles that create a lot of closures. Stack
allocation is be inferred and performed independently for the
closed-over bindings and for the closure function objects themselves.
But consideration whether a closure has only dynmic extent is not
dependent solely on whether the closure is `returned'. A closure can
be captured if passed as a first class object to another
non-lexically-related function. For example, consider
(let ((x ...))
...
(mapcar (lambda () ... x ...) ...)
...)
The anonymous lambda closes over x and is passed as a first class
object to mapcar. Now, the compiler may know that mapcar never captures
its first argument because mapcar is defined by the ANS, but if it were
some other function about which the compiler knows nothing, this usage
would prohibit inferring dynamic extent for the anonymous lambda closure.
The compiler can know that a particular argument to a function is not
captured if it has seen that function definition and that argument was
declared dynamic-extent, or if the compiler was able to infer that it
ws used only with dynamic-extent.
Implementationally, this is a big confusing wad of hair.
Been there, done that...
In article <·····················@newssvr25.news.prodigy.com>,
"Steven M. Haflich" <·················@alum.mit.edu> wrote:
> What everyone has been missing in this thread is that non-null closures
> cost _time_ to set up in addition to storage.
Everything you do in a computer program costs time. The OP was
concerned that it was re-compiling the function each time, so that it
would cost *alot* of time. It doesn't do that, and the real cost is
relatively minor, closer to a call to MAKE-ARRAY than COMPILE.
--
Barry Margolin, ······@alum.mit.edu
Arlington, MA
*** PLEASE post questions in newsgroups, not directly to me ***
"Steven M. Haflich" <·················@alum.mit.edu> writes:
> What everyone has been missing in this thread is that non-null closures
> cost _time_ to set up in addition to storage. If the closure is used as
> a first-class object, that object must be allocated and associated with
> its closed-over bindings. This consumes cycles whether the closure and
> its associated binding storage are created on the stack or in the heap.
This is true, but it is not necessarily a *significant* amount of time
(depending on the application, etc.) The bindings have to be
heap-allocated and a closure object has to be created. Creating the
bindings should be proportional to the number of bindings and should
be about as costly as creating a simple-vector of the same size. The
closure object should be fairly small and cost only about as much time
as creating a struct with a handful of slots.
> Finally, it is often the case that a reference to a closed-over binding
> is slightly more expensive in cycles than a reference to a regular local
> lexical variable (which is usually a refence to a fixed location in the
> current stack frame). This might or might not be significant depending
> on the nature of the function.
A closure is very much like a C++ instance. There is a pointer to the
code (the vtble in c++) and a set of bindings (the instance itself in
C++). Variable referencing in closures should be about as expensive
as instance variable references in C++.
> The Franz compiler spends a lot of energy [analyzing code to
> optimize closures] , and it is quite worthwhile for coding styles
> that create a lot of closures. Stack allocation is be inferred and
> performed independently for the closed-over bindings and for the
> closure function objects themselves.
This is what really amuses me. Closures are like C++ objects, but
every C++ compiler I've seen does a piss-poor job at the kind of
optimizations that lisp does on closures. Consequently, you will lose
a *lot* of performance if you naively translate code with closures to
code with C++ classes.
Joe Marshall wrote:
> A closure is very much like a C++ instance. There is a pointer to the
> code (the vtble in c++) and a set of bindings (the instance itself in
> C++). Variable referencing in closures should be about as expensive
> as instance variable references in C++.
Joe, I have a rather hoard time accepting this argument, and especially,
accepting performance conclusions based upon it. One might say that "my
love is like a red red rose" but that doesn't necessarily require that
it will wilt after 3-5 days.
> This is what really amuses me. Closures are like C++ objects, but
> every C++ compiler I've seen does a piss-poor job at the kind of
> optimizations that lisp does on closures. Consequently, you will lose
> a *lot* of performance if you naively translate code with closures to
> code with C++ classes.
Far be it from me to defend C++, but naive translations generally capture
neither the expressive potential of the target language nor its performance
potential. I don't see how C++ comparisons are particularly relevant to
understanding the efficiency of CL closures. If I missed some connection
(perhaps my news host dropped someone's post) please enlighten.
"Steven M. Haflich" <·················@alum.mit.edu> writes:
> Joe, I have a rather hoard time accepting this argument, and
> especially, accepting performance conclusions based upon it. One
> might say that "my love is like a red red rose" but that doesn't
> necessarily require that it will wilt after 3-5 days.
Shellack (sp?) does wonders.
--
David Magda <dmagda at ee.ryerson.ca>, http://www.magda.ca/
Because the innovator has for enemies all those who have done well under
the old conditions, and lukewarm defenders in those who may do well
under the new. -- Niccolo Machiavelli, _The Prince_, Chapter VI
"Steven M. Haflich" <·················@alum.mit.edu> writes:
> Joe Marshall wrote:
>
>> A closure is very much like a C++ instance. There is a pointer to the
>> code (the vtble in c++) and a set of bindings (the instance itself in
>> C++). Variable referencing in closures should be about as expensive
>> as instance variable references in C++.
>
> Joe, I have a rather hard time accepting this argument, and especially,
> accepting performance conclusions based upon it. One might say that "my
> love is like a red red rose" but that doesn't necessarily require that
> it will wilt after 3-5 days.
There are two parts to the argument.
First, a closure consists of a piece of code and a set of lexical
bindings. The code component is shared with all the closures created
by the same lambda while the environment part is different. This may
be implemented in several different ways, but when invoking a closure,
at some point you end up executing the body of the lambda and you have
access to the bound variables. Because the set of bound variables
will differ for different closures over the same lambda, an
indirection mechanism needs to be used. References to the variables
will occur via this indirection.
Different compilers may do it differently, but one common way is to
pass the binding set into the lambda as an `implicit' argument, either
in a register or on the stack.
This is *analagous* to the implicit `this' object in a C++ class. The
instance variables of a C++ instance are passed as an implicit
argument to the method.
When one calls a method in C++, the caller arranges for the instance
pointer to be passed. When the C++ method needs to refer to instance
variables, it must indirect through the `this' pointer.
The first part of the argument is that this mechanism is identifiable
in all implementations. Some details may differ, but you can find the
pieces.
The second part is that there is a deeper analogy that *requires*
these pieces and that lexical variable lookup and C++ instance varible
lookup are similar not due to coincidence but because they are at some
level the same thing.
>> This is what really amuses me. Closures are like C++ objects, but
>> every C++ compiler I've seen does a piss-poor job at the kind of
>> optimizations that lisp does on closures. Consequently, you will lose
>> a *lot* of performance if you naively translate code with closures to
>> code with C++ classes.
>
> Far be it from me to defend C++, but naive translations generally capture
> neither the expressive potential of the target language nor its performance
> potential. I don't see how C++ comparisons are particularly relevant to
> understanding the efficiency of CL closures. If I missed some connection
> (perhaps my news host dropped someone's post) please enlighten.
A naive implementation of CL closures would be to heap-allocate all
bindings and create a closure object every time a lambda-expression
was encountered. Most CL compilers are reasonably clever and can
perform such optimizations as omitting unused variables from the
closure threading the environment through the call path, stack
allocating the environment if possible, eliding the code pointer if
possible, etc. In the optimal case, a lambda expression in CL will be
folded into all the call sites and essentially disappear.
Now the analagous situation in C++ is allocating a class instance in
the current stack frame and passing it `downward' to another function.
In C++, this *always* allocates space on the stack, initializes the
slots, and passes the pointer to the callee. But if C++ were as
clever as CL, it should be able to reason about the use of the object
and be able create only enough of it for the purposes of the callee.
You can make `fake closures' in C++ by making a class that overloads
the () operator and whose instance variables are references to local
variables. This works just like a closure in the non-optimal case in
CL. But in CL, if the call site of the closure is known, much of the
overhead disappears. In C++, you get no optimization at all.
--
~jrm
Joe Marshall wrote:
> A closure is very much like a C++ instance. There is a pointer to the
> code (the vtble in c++) and a set of bindings (the instance itself in
> C++). Variable referencing in closures should be about as expensive
> as instance variable references in C++.
Steve Haflich responded:
> Joe, I have a rather hard time accepting this argument, and especially,
> accepting performance conclusions based upon it. One might say that "my
> love is like a red red rose" but that doesn't necessarily require that
> it will wilt after 3-5 days.
I didn't see anything remotely controversial in what Joe wrote.
Could you be more specific about your objections?
Will
William D Clinger wrote:
> Joe Marshall wrote:
>
>>A closure is very much like a C++ instance. There is a pointer to the
>>code (the vtble in c++) and a set of bindings (the instance itself in
>>C++). Variable referencing in closures should be about as expensive
>>as instance variable references in C++.
>
> Steve Haflich responded:
>
>>Joe, I have a rather hard time accepting this argument, and especially,
>>accepting performance conclusions based upon it. One might say that "my
>>love is like a red red rose" but that doesn't necessarily require that
>>it will wilt after 3-5 days.
>
> I didn't see anything remotely controversial in what Joe wrote.
> Could you be more specific about your objections?
There is nothing controversial in Joe's statement, and certain nothing
provocative, but I just don't accept the conclusion and don't see how the
conclusion follows from the stated facts. There are a great many
different language constraints between a CL closure and a C++ instance,
-- despite similarity in the semantics of closure storage -- and
the differences may have great effect on the realization on a given
architecture.
For example, here is one important difference: A C++ instance and a CL
closure are both first-class objects, so referencing either automatically
implies one has a handle for (pointer to) the object. But a C++ instance
is merely a structure hunk of memory, while a closure must _also_ have
the type and implementational structure of a function, since the only way
it can actually be used is via funcall and friends. (There is no concept
in CL if referencing a slot in a closure, as there is in C++.) The design
of mechanisms to maintain fast access to closed-over bindings may be
differently constrained in these very-different kinds of objects. The
constraints may be more severe on register-starved architectures.
I am certainly _not_ arguing against the use of closures. I am only
contesting unwarranted assumptions about the magnitude of their cost.
"Steven M. Haflich" wrote:
> I am certainly _not_ arguing against the use of closures. I am only
> contesting unwarranted assumptions about the magnitude of their cost.
I have posted the following text at
http://www.ccs.neu.edu/home/will/Research/closurecost.html
which contains links to the source code for the benchmarks.
Will
--------
On comp.lang.lisp, someone asked about the cost of closures. On 4 March
2004, Joe Marshall replied:
A closure is very much like a C++ instance. There is a
pointer to the code (the vtble in c++) and a set of bindings
(the instance itself in C++). Variable referencing in closures
should be about as expensive as instance variable references
in C++.
This was disputed.
Well, glarg. Let's just measure it, shall we?
I wrote a simple benchmark in which a closure makes 100 million tail
calls to a closure that happens to be itself but cannot be proved so
without whole program analysis. For each call this closure refers to
10 non-local variables, for a total of one billion variable references.
I also wrote a variant in which the tail calls are replaced by a loop
with assignments that are never executed. I translated this benchmark
into Scheme, Common Lisp, Java, and C++. I ran this benchmark on my
Sun Blade 100. Here are the elapsed times in seconds:
tail calls no tail calls
Larceny v0.50 9.791 8.413
Chez Scheme v6.1 9.817 13.447
Allegro Common Lisp v4.3.1 13.953 7.131
Sun Hotspot (Java) 33.835 6.267
Gnu C++ 34.320 5.431
These are the averages of three runs. There was very little variation
between runs. All programs were compiled for the fastest unsafe code.
Last updated 7 March 2004
William D Clinger wrote:
>
> tail calls no tail calls
> Larceny v0.50 9.791 8.413
> Chez Scheme v6.1 9.817 13.447
> Allegro Common Lisp v4.3.1 13.953 7.131
> Sun Hotspot (Java) 33.835 6.267
> Gnu C++ 34.320 5.431
>
> These are the averages of three runs. There was very little variation
> between runs. All programs were compiled for the fastest unsafe code.
>
> Last updated 7 March 2004
What is the meaning of "no tail calls", especially for the Scheme versions?
Cheers
Marco
Marco Antoniotti <·······@cs.nyu.edu> wrote:
> What is the meaning of "no tail calls", especially for the Scheme versions?
In that column, the tail calls are replaced by a DO loop.
In Scheme, the DO loop will no doubt be implemented by a
tail call, but it will be a tail call to a known procedure,
which should be faster than the tail calls to the unknown
closure.
On the other hand, the DO loop version contains assignments
to a local variable. Although none of these assignments are
ever actually executed during the benchmark, the compiler
can't possibly figure that out, and that is my guess as to
why Chez Scheme runs slower on the DO loop version. Larceny
would show the same slowdown if not for a CSE that optimizes
variable references. For the DO version, the main differences
between the machine code generated by g++ -O3 and the code
executed in Larceny are that Larceny has one unnecessary
register move per EQ comparison, and g++ gets the main trace
in order, which is likely to improve instruction-level
parallelism. ACL's trace ordering is better than Larceny's
but not as good as g++'s. Accessing a non-local variable
from a closure in Larceny and in ACL is a single load
instruction, just like fetching an instance variable in C++.
If you really want to know, you should read the source code
at http://www.ccs.neu.edu/home/will/Research/closurecost.html
Then compile it and disassemble the compiled code.
Will
In article <·····················@newssvr25.news.prodigy.com>,
"Steven M. Haflich" <·················@alum.mit.edu> writes:
> ...
> What everyone has been missing in this thread is that non-null closures
> cost _time_ to set up in addition to storage.
everything you do costs something. the important thing is the
relation of cost to benefit
> ...
> Finally, it is often the case that a reference to a closed-over binding
> is slightly more expensive in cycles than a reference to a regular local
> lexical variable (which is usually a refence to a fixed location in the
> current stack frame). This might or might not be significant depending
> on the nature of the function.
compare that to the effort you have to go through when you need the
functionality of a closure without having closures available.
besides, a good compiler can reduce the access code to something
equivalent to local variable access (at least if there is more than
one access to objects in the closure)
> ...
hs
--
Patriotism is the last refuge of the scoundrel
Samuel Johnson
Patriotism is your conviction that this country is superior to all
others because you were born in it
George Bernard Shaw
Hartmann Schaffer wrote:
> In article <·····················@newssvr25.news.prodigy.com>,
> "Steven M. Haflich" <·················@alum.mit.edu> writes:
>
>>...
>>What everyone has been missing in this thread is that non-null closures
>>cost _time_ to set up in addition to storage.
>
> everything you do costs something. the important thing is the
> relation of cost to benefit
Gosh!!!! How did you ever come up with this amazing observation? Have
you considered publishing it?????
>>Finally, it is often the case that a reference to a closed-over binding
>>is slightly more expensive in cycles than a reference to a regular local
>>lexical variable (which is usually a refence to a fixed location in the
>>current stack frame). This might or might not be significant depending
>>on the nature of the function.
>
> compare that to the effort you have to go through when you need the
> functionality of a closure without having closures available.
This second point too is worth a publication. How can the Lisp community
have survived so many years without realizing this?
> besides, a good compiler can reduce the access code to something
> equivalent to local variable access (at least if there is more than
> one access to objects in the closure)
Unfortunately, I cannot agree with this, your third point. Perhaps you
can explain how a sufficiently smart compiler (on a normal stack machine)
can do this. Yes, the compiler can optimize away many, perhaps most,
important cases: where the closure is not passed outside the lexical
extent; where the closure variables are never set; where a block
compiler can analyze how the closure is used outside its lexical
extent;e the closure only captures bindings from a single binding
contour, or where intermediate binding contours cannot be entered
independently.
Now, before you draft another irrelevant response, I did not say that
closures should not be used, and I did _not_ imply that in my earlier
message. (Your response implies that I did.) I did _not_ say that
the overhead of closure access is often significant in typical usage,
and I did _not_ imply that in my first message. (Your response implies
that I did.) I only wanted to establish that closures in general cases
do impose runtime overhead and sometimes that overhead may be significant.
This is not much different from just about any other feature in the
language.
"Steven M. Haflich" quoting Hartmann Schaffer:
> > besides, a good compiler can reduce the access code to something
> > equivalent to local variable access (at least if there is more than
> > one access to objects in the closure)
>
> Unfortunately, I cannot agree with this, your third point. Perhaps you
> can explain how a sufficiently smart compiler (on a normal stack machine)
> can do this.
Larceny's representation of closures is typical: a closure has
essentially the same representation as a Scheme vector. One
element of that vector-like structure points to the machine
code for the closure. Another element of that vector-like
structure points to a vector of the pointer constants that
are referred to by the closure, including global value cells.
The remaining elements of the closure hold the actual values
of lexical variables that occur free within the code and are
nowhere assigned, or pointers to the cells that represent free
lexical variables that are assigned.
The currently executing closure always resides in a register.
Thus any non-local, non-global variable that is not assigned
can be fetched by a single load instruction. Fetching the
value of a non-local, non-global variable that appears on the
left hand side of an assignment involves two dependent load
instructions.
Will
"Steven M. Haflich" <·················@alum.mit.edu> writes:
> [..] But consideration whether a closure has only dynmic extent is
> not dependent solely on whether the closure is `returned'. A
> closure can be captured if passed as a first class object to another
> non-lexically-related function. For example, consider
>
> (let ((x ...))
> ...
> (mapcar (lambda () ... x ...) ...)
> ...)
>
> The anonymous lambda closes over x and is passed as a first class
> object to mapcar. Now, the compiler may know that mapcar never
> captures its first argument because mapcar is defined by the ANS,
> [..]
Or, more generally, because mapcar may be inlined.
> [..] but if it were some other function about which the compiler
> knows nothing, this usage would prohibit inferring dynamic extent
> for the anonymous lambda closure.
I've written a little bit about this, and identified three kinds of
relevant extents for closures: Infinite (the "normal"), dynamic (as in
the dynamic-extent declaration), and "lexical extent" which is what
you're describing here: A closure of "lexical extent" is only used in
some lexical scope, or in other words is never captured with the
function special operator (or the result of this capture can be proven
not to escape the lexical scope, but this tends to amount to never
actually having to perform the function capture).
What's interesting I think is that a closure of lexical extent
corresponds to a subroutine at the assembly level. Or the compiler can
inline it as it would any other inlinable function call.
--
Frode Vatvedt Fjeld
On Wed, 03 Mar 2004 15:00:21 -0800, Kaz Kylheku wrote:
> True closures require more complexity: the captured bindings have to
> be heap-allocated, not stack allocated, so that they have indefinite
> extent. Lexical variables that are not subject to capture can still go
> onto regular, fast stack frames.
A compiler can also see which local variables are not assigned to, and
attach their values to the closure instead of materialized bindings.
--
__("< Marcin Kowalczyk
\__/ ······@knm.org.pl
^^ http://qrnik.knm.org.pl/~qrczak/
······@mail.com (KanZen) writes:
> If I create a function that calls lambda to make a closure each time,
> am I effectively calling an optimizing compiler with each call to the
> outer function?
No.
> I realise this may be implementation specific, but what is the
> typical runtime penalty? (e.g. CLisp, CMUCL)
A closure is usually represented as a code pointer + the free
vars, all in a little vector. This is a bit cheaper than the usual
representation of an object (pointer to class methods + instance vars,
which means one extra indirection when invoking a method).
Calling a closure should thus be SOMEWHAT CHEAPER than a ("virtual")
single-dispatch method invocation.
(Some compilers can do better than that in some special cases,
too. There's abundant literature on this, so I'll just refer you on to
it ...)
Best,
Thomas
--
Thomas Lindgren
"It's becoming popular? It must be in decline." -- Isaiah Berlin
······@mail.com (KanZen) writes:
> If I create a function that calls lambda to make a closure each
> time, am I effectively calling an optimizing compiler with each call
> to the outer function? I realise this may be implementation
> specific, but what is the typical runtime penalty? (e.g. CLisp,
> CMUCL)
No, the functions are compiled once. The only penalty is a little
consing to create space for the bindings you close over.
Regards,
--
Nils G�sche
"Don't ask for whom the <CTRL-G> tolls."
PGP key ID 0x0655CFA0
······@cartan.de (Nils G�sche) wrote in message news:<··············@cartan.de>...
> ······@mail.com (KanZen) writes:
>
> > If I create a function that calls lambda to make a closure each
> > time, am I effectively calling an optimizing compiler with each call
> > to the outer function? I realise this may be implementation
> > specific, but what is the typical runtime penalty? (e.g. CLisp,
> > CMUCL)
>
> No, the functions are compiled once. The only penalty is a little
> consing to create space for the bindings you close over.
>
> Regards,
Thanks to all who answered my question... but this naturally leads me
to a followup issue. If the code for the closure is only compiled
once, does that mean that it is not possible to write a lambda form
which has contents (i.e. the code to be executed) that can change at
runtime?
In article <····························@posting.google.com>,
······@mail.com (KanZen) wrote:
> Thanks to all who answered my question... but this naturally leads me
> to a followup issue. If the code for the closure is only compiled
> once, does that mean that it is not possible to write a lambda form
> which has contents (i.e. the code to be executed) that can change at
> runtime?
If you need to generate code at runtime you must invoke the compiler or
interpreter explicitly. This is what EVAL is for.
However, there are usually better techniques than this.
--
Barry Margolin, ······@alum.mit.edu
Arlington, MA
*** PLEASE post questions in newsgroups, not directly to me ***
······@mail.com (KanZen) writes:
> Thanks to all who answered my question... but this naturally leads
> me to a followup issue. If the code for the closure is only compiled
> once, does that mean that it is not possible to write a lambda form
> which has contents (i.e. the code to be executed) that can change at
> runtime?
Well, can you show us some code with a closure whose code you would
reasonably expect to change at run-time?
--
Frode Vatvedt Fjeld
······@mail.com (KanZen) writes:
> ······@cartan.de (Nils G�sche) wrote in message news:<··············@cartan.de>...
> > ······@mail.com (KanZen) writes:
> >
> > > If I create a function that calls lambda to make a closure each
> > > time, am I effectively calling an optimizing compiler with each
> > > call to the outer function? I realise this may be implementation
> > > specific, but what is the typical runtime penalty? (e.g. CLisp,
> > > CMUCL)
> > No, the functions are compiled once. The only penalty is a little
> > consing to create space for the bindings you close over.
> Thanks to all who answered my question... but this naturally leads
> me to a followup issue. If the code for the closure is only compiled
> once, does that mean that it is not possible to write a lambda form
> which has contents (i.e. the code to be executed) that can change at
> runtime?
I am not sure I understand what you mean. Compare these examples:
(defun make-adder-1 (n)
(lambda (x)
(+ x n)))
(defun make-adder-2 (n)
(compile nil `(lambda (x)
(+ x ,n))))
In the first example, we return an ordinary closure, nothing is
compiled at run time. In the second example, you actually construct
the code at run time, so it will have to be compiled at run time, too
(or it will run interpreted). This is not what people usually mean
when they speak of closures, though.
Regards,
--
Nils G�sche
"Don't ask for whom the <CTRL-G> tolls."
PGP key ID 0x0655CFA0
······@cartan.de (Nils G�sche) wrote in message news:<··············@cartan.de>...
> ······@mail.com (KanZen) writes:
>
> > ······@cartan.de (Nils G�sche) wrote in message news:<··············@cartan.de>...
> > > ······@mail.com (KanZen) writes:
> > >
> > > > If I create a function that calls lambda to make a closure each
> > > > time, am I effectively calling an optimizing compiler with each
> > > > call to the outer function? I realise this may be implementation
> > > > specific, but what is the typical runtime penalty? (e.g. CLisp,
> > > > CMUCL)
>
> > > No, the functions are compiled once. The only penalty is a little
> > > consing to create space for the bindings you close over.
>
> > Thanks to all who answered my question... but this naturally leads
> > me to a followup issue. If the code for the closure is only compiled
> > once, does that mean that it is not possible to write a lambda form
> > which has contents (i.e. the code to be executed) that can change at
> > runtime?
>
> I am not sure I understand what you mean. Compare these examples:
>
> (defun make-adder-1 (n)
> (lambda (x)
> (+ x n)))
>
> (defun make-adder-2 (n)
> (compile nil `(lambda (x)
> (+ x ,n))))
>
> In the first example, we return an ordinary closure, nothing is
> compiled at run time. In the second example, you actually construct
> the code at run time, so it will have to be compiled at run time, too
> (or it will run interpreted). This is not what people usually mean
> when they speak of closures, though.
>
> Regards,
I guess this is what I was thinking of. Nice to know it's possible.
KanZen
>>(defun make-adder-1 (n)
>> (lambda (x)
>> (+ x n)))
>>
>>(defun make-adder-2 (n)
>> (compile nil `(lambda (x)
>> (+ x ,n))))
While the above examples do point out that closures do not imply
compilation at run tmie, I think it is worth pointing out that the
second example above, invoking the compiler, does not have the same
semantics as a real closure. At least, it wouldn't in a more complex
example. Consider:
(defun make-adder-1 (n)
(list (lambda (x) (+ x n))
(lambda (new) (setq n new)))))
(defun make-adder-2 (n)
(list (compile nil `(lambda (x) (+ x ,n)))
(compile nil `(lambda (new) (setq ,n x)))))
These functions return a list of two functions: an adder and a
function that can change the added to a different value. The
closure version works -- the run-time compile version does not.
"Nils G�sche" <······@cartan.de> wrote in message
···················@cartan.de...
> ······@mail.com (KanZen) writes:
>
> > ······@cartan.de (Nils G�sche) wrote in message
news:<··············@cartan.de>...
> > > ······@mail.com (KanZen) writes:
> > >
> > > > If I create a function that calls lambda to make a closure each
> > > > time, am I effectively calling an optimizing compiler with each
> > > > call to the outer function? I realise this may be implementation
> > > > specific, but what is the typical runtime penalty? (e.g. CLisp,
> > > > CMUCL)
>
> > > No, the functions are compiled once. The only penalty is a little
> > > consing to create space for the bindings you close over.
>
> > Thanks to all who answered my question... but this naturally leads
> > me to a followup issue. If the code for the closure is only compiled
> > once, does that mean that it is not possible to write a lambda form
> > which has contents (i.e. the code to be executed) that can change at
> > runtime?
>
> I am not sure I understand what you mean. Compare these examples:
>
> (defun make-adder-1 (n)
> (lambda (x)
> (+ x n)))
>
> (defun make-adder-2 (n)
> (compile nil `(lambda (x)
> (+ x ,n))))
>
> In the first example, we return an ordinary closure, nothing is
> compiled at run time. In the second example, you actually construct
> the code at run time, so it will have to be compiled at run time, too
> (or it will run interpreted). This is not what people usually mean
> when they speak of closures, though.
>
> Regards,
> --
> Nils G�sche
> "Don't ask for whom the <CTRL-G> tolls."
>
> PGP key ID 0x0655CFA0
At least in Lispworks 4.3.6 (windows), whether the functions constructed are
compiled or
not depends on whether make-adder-1 is itself compiled:
CL-USER 8 > (defun make-adder-1 (n)
(lambda (x) (+ x n)))
MAKE-ADDER-1
CL-USER 9 > (make-adder-1 5)
#<interpreted closure (LAMBDA (X) (+ X N))>
CL-USER 10 > (compile 'make-adder-1)
MAKE-ADDER-1
NIL
NIL
CL-USER 11 > (make-adder-1 5)
#<closure (SUBFUNCTION 1 MAKE-ADDER-1) 20687B6A>
This is surely implementation dependent.
Jim Bushnell
>>>>> "kz" == kanzen <······@mail.com> writes:
[...]
kz> ... If the code for the closure is
kz> only compiled once, does that mean that it is not possible to
kz> write a lambda form which has contents (i.e. the code to be
kz> executed) that can change at runtime?
No it doesn't. You have the full language at runtime also (assuming you
did not build an image without a compiler). I am pretty sure there have
been many code samples posted here, but I could only find one discussion:
http://groups.google.com/groups?selm=3895F02C.269CBBCD%40fisec.com
(follow the thread for examples).
cheers,
BM
KanZen wrote:
> Thanks to all who answered my question... but this naturally leads me
> to a followup issue. If the code for the closure is only compiled
> once, does that mean that it is not possible to write a lambda form
> which has contents (i.e. the code to be executed) that can change at
> runtime?
Of course this is possible, as almost anything is in Common Lisp. ;)
However, for the following way to implement it, you need the Metaobject
Protocol which is not standardized, only "semi-standardized". The
following is in LispWorks 4.3 for Mac OS X.
(use-package :clos)
(defclass changeable-function ()
((clambda :accessor clambda :initarg :clambda))
(:metaclass funcallable-standard-class))
(defmethod initialize-instance :after
((instance changeable-function)
&key clambda
&allow-other-keys)
(set-funcallable-instance-function instance clambda))
(defmethod (setf clambda) :after
(newvalue (instance changeable-function))
(set-funcallable-instance-function instance newvalue))
(flet ((test-it (f)
(funcall f)
(setf (clambda f)
(lambda () (print 'changed)))
f))
(funcall (test-it (make-instance
'changeable-function
:clambda (lambda () (print 23))))))
==>
23
CHANGED
CHANGED
Pascal
--
1st European Lisp and Scheme Workshop
June 13 - Oslo, Norway - co-located with ECOOP 2004
http://www.cs.uni-bonn.de/~costanza/lisp-ecoop/