·········@aol.com (ALBINALI4) writes:
> Hi,
> What determines wether an object is allocated statically, on the
> stack or on the heap in Lisp?
When writing code to solve a problem, you first care to get it right
and then to get it fast. Hence the answer is
"in CL, you may avoid to think to such low level issues, and take care
of them only after extensive profiling of your application
bottlenecks".
Of course, your application may turn out to be just "fast enough", in
which case you are home free.
Once you get past profiling and you have determined that in some
places, stack allocation may speed up your code, the DYNAMIC-EXTENT
declaration, and a knowledge of the implementation you are using are
your friends.
> Thank you.
You are welcome.
Cheers
--
Marco Antoniotti ========================================================
NYU Courant Bioinformatics Group tel. +1 - 212 - 998 3488
719 Broadway 12th Floor fax +1 - 212 - 995 4122
New York, NY 10003, USA http://bioinformatics.cat.nyu.edu
"Hello New York! We'll do what we can!"
Bill Murray in `Ghostbusters'.
In article <·····························@mb-me.aol.com>, ALBINALI4 wrote:
> What determines wether an object is allocated statically, on the
> stack or on the heap in Lisp?
Why do you care about where it is allocated? It depends very much
on the compiler you're using and it's optimization settings.
Regards,
--
Nils Goesche
"Don't ask for whom the <CTRL-G> tolls."
PGP key ID 0x42B32FC9
* albinali4 wrote:
> What determines wether an object is allocated statically, on the stack or on
> the heap in Lisp?
To first order, everything is heap allocated. Things may be stack
allocated if you either say they can be, they are defined in such a
way as to be stack allocatable (restarts), or if the compiler can
prove that stack allocation is safe.
I don't really know what static allocation is.
--tim
Tim Bradshaw <···@cley.com> writes:
> * albinali4 wrote:
>
> > What determines wether an object is allocated statically, on the stack or on
> > the heap in Lisp?
>
> To first order, everything is heap allocated. Things may be stack
> allocated if you either say they can be, they are defined in such a
> way as to be stack allocatable (restarts), or if the compiler can
> prove that stack allocation is safe.
>
> I don't really know what static allocation is.
In a generational GC (or any GC that copies, for that matter) it is
sometimes important to know that an object is not going to move.
This usually occurs in FFIs where you are converting a lisp object to
a foreign pointer, and it is important for that pointer to continue to
point to the same object at all times during the foreign call. If
the object is heap allocated, then the pointer becomes invalid if
the object moves out from under it during a GC, because the pointer
has been captured by the foreign language and is thus not affected
by the GC. A static object removes any chance of the object moving
out from under a pointer in that manner.
Allegro CL provides for static objects, usually arrays (make-array
has an :allocation keyword as an extension, which can accept among other
things :static as its value) or foreign object types, which can be
specified as being in static (immovable) space. In all cases, the
programmer makes the judgement that an object will be static as opposed
to the heap.
Also, stack-allocated objects can be considered static, though not
of indefinite scope like statically allocated objects.
--
Duane Rettig Franz Inc. http://www.franz.com/ (www)
1995 University Ave Suite 275 Berkeley, CA 94704
Phone: (510) 548-3600; FAX: (510) 548-8253 ·····@Franz.COM (internet)
* Duane Rettig wrote:
> In a generational GC (or any GC that copies, for that matter) it is
> sometimes important to know that an object is not going to move.
> This usually occurs in FFIs where you are converting a lisp object to
> a foreign pointer, and it is important for that pointer to continue to
> point to the same object at all times during the foreign call. If
> the object is heap allocated, then the pointer becomes invalid if
> the object moves out from under it during a GC, because the pointer
> has been captured by the foreign language and is thus not affected
> by the GC. A static object removes any chance of the object moving
> out from under a pointer in that manner.
Yes, that's what I'd assume is meant normally in the context of Lisp
(except you've put it better than I would have). But I am wondering,
in the context of the question, whether the person meant something
more like what C's `static' keyword does, which you'd typically
achieve in CL by either #. or LOAD-TIME-VALUE, I think:
(defun foo (n &optional m)
(let ((v (load-time-value (make-array 10 :element-type 'real :initial-element 0))))
(if (null m)
(aref v n)
(setf (aref v n) m))))
or something like that, anyway. Of course this is, I guess, just heap
allocation at load time - I just thought that might be what they were
after, though I'm not sure.
--tim
Tim Bradshaw <···@cley.com> writes:
> * Duane Rettig wrote:
>
> > In a generational GC (or any GC that copies, for that matter) it is
> > sometimes important to know that an object is not going to move.
> > This usually occurs in FFIs where you are converting a lisp object to
> > a foreign pointer, and it is important for that pointer to continue to
> > point to the same object at all times during the foreign call. If
> > the object is heap allocated, then the pointer becomes invalid if
> > the object moves out from under it during a GC, because the pointer
> > has been captured by the foreign language and is thus not affected
> > by the GC. A static object removes any chance of the object moving
> > out from under a pointer in that manner.
>
> Yes, that's what I'd assume is meant normally in the context of Lisp
> (except you've put it better than I would have). But I am wondering,
> in the context of the question, whether the person meant something
> more like what C's `static' keyword does, which you'd typically
> achieve in CL by either #. or LOAD-TIME-VALUE, I think:
Well, the "static" storage specifier in C basically means 'this is not
on the stack'.
Any variable taht's declared outside a function (global scope, as it
were) is by default static and can most easily be modelled by DEFVAR
or DEFPARAMETER, I think.
Something like:
int bad_incrementer (void)
{
int n=0;
return n++;
}
can most easily be turned into:
(LET ((n 0))
(DEFUN bad-incrementer ()
(INCF n)))
> (defun foo (n &optional m)
> (let ((v (load-time-value (make-array 10 :element-type 'real :initial-element 0))))
> (if (null m)
> (aref v n)
> (setf (aref v n) m))))
LOAD-TIME-VALUE works for arrays, but works less well for other things.
//Ingvar
--
"I'm in 386 enchanted mode."
* Ingvar Mattsson wrote:
> Well, the "static" storage specifier in C basically means 'this is not
> on the stack'.
Not really. It also tells you things about the visibility for globals.
> Any variable taht's declared outside a function (global scope, as it
> were) is by default static and can most easily be modelled by DEFVAR
> or DEFPARAMETER, I think.
Yes, but the interesting case is static *within* functions.
> Something like:
> int bad_incrementer (void)
> {
> int n=0;
> return n++;
> }
Do you mean to have a `static' here? Otherwise I can't understand the
below.
> (LET ((n 0))
> (DEFUN bad-incrementer ()
> (INCF n)))
Or, alternatively, this:
(defun bad-incrementor ()
(let ((x (load-time-value (list 0))))
(incf (car x))))
> LOAD-TIME-VALUE works for arrays, but works less well for other things.
Anything immutable (like a number) needs to be wrapped in a mutable
container, I agree.
--tim
Tim Bradshaw <···@cley.com> writes:
> * Ingvar Mattsson wrote:
> > Well, the "static" storage specifier in C basically means 'this is not
> > on the stack'.
>
> Not really. It also tells you things about the visibility for globals.
That too, but I was quite sure taht the C standard said "the storage
class for variables defined in a global scope is ``static''". *shug*
C is quite often a bizarre language.
> > Any variable taht's declared outside a function (global scope, as it
> > were) is by default static and can most easily be modelled by DEFVAR
> > or DEFPARAMETER, I think.
>
> Yes, but the interesting case is static *within* functions.
Yup.
> > Something like:
> > int bad_incrementer (void)
> > {
> > int n=0;
>
> > return n++;
> > }
>
> Do you mean to have a `static' here? Otherwise I can't understand the
> below.
Yep, "static int n=0;". Lack of proof-reading and a spine saying
"static inside a function, are you *sure* this is the right thing?".
> > (LET ((n 0))
> > (DEFUN bad-incrementer ()
> > (INCF n)))
>
> Or, alternatively, this:
>
> (defun bad-incrementor ()
> (let ((x (load-time-value (list 0))))
> (incf (car x))))
>
> > LOAD-TIME-VALUE works for arrays, but works less well for other things.
>
> Anything immutable (like a number) needs to be wrapped in a mutable
> container, I agree.
Indeed. Though I still think the LET-wrapped defun is a closer
analogy. The latter feels more like poking at a struct. Not that it
makes a difference in the end, though.
//Ingvar
--
When the SysAdmin answers the phone politely, say "sorry", hang up and
run awaaaaay!
Informal advice to users at Karolinska Institutet, 1993-1994
* Ingvar Mattsson wrote:
> That too, but I was quite sure taht the C standard said "the storage
> class for variables defined in a global scope is ``static''". *shug*
> C is quite often a bizarre language.
Yes, I think it may say that - it may be that static means a whole
load of things (which it kind of does - non-top-level static is
already sort of different than top-level static...). I don't have
access to anything newer than a 2nd edition K&R to check unfortunately...
> Indeed. Though I still think the LET-wrapped defun is a closer
> analogy. The latter feels more like poking at a struct. Not that it
> makes a difference in the end, though.
Yes, I think it is sort of better. The load-time-value thing really
just shows that you can get the behaviour of a local variable which is
initialised once, at load-time though, without doing thing that I
suspect people who aren't comfortable with closures might find
uncomfortable.
--tim
Tim Bradshaw <···@cley.com> writes:
> * Ingvar Mattsson wrote:
>
> > That too, but I was quite sure taht the C standard said "the storage
> > class for variables defined in a global scope is ``static''". *shug*
> > C is quite often a bizarre language.
>
> Yes, I think it may say that - it may be that static means a whole
> load of things (which it kind of does - non-top-level static is
> already sort of different than top-level static...). I don't have
> access to anything newer than a 2nd edition K&R to check unfortunately...
Yup. Strange language. last time I started writing something
approaching "not small" in C, it took me all of 2-3 hours to write a
linked-list library I called "llist" (no, it's "lisp list").
> > Indeed. Though I still think the LET-wrapped defun is a closer
> > analogy. The latter feels more like poking at a struct. Not that it
> > makes a difference in the end, though.
>
> Yes, I think it is sort of better. The load-time-value thing really
> just shows that you can get the behaviour of a local variable which is
> initialised once, at load-time though, without doing thing that I
> suspect people who aren't comfortable with closures might find
> uncomfortable.
Yup. And I think DEFUN is only guaranteed to portably work on top-level
lisp anyhow. Or was that "only guaranteed read-time"? Ah, well.
//Ingvar
--
When in doubt, debug-on-entry the function you least suspect have
anything to do with something.
On 25 Jan 2002 16:59:04 +0000, Ingvar Mattsson <······@cathouse.bofh.se> wrote:
>Tim Bradshaw <···@cley.com> writes:
>>
>> Yes, I think it is sort of better. The load-time-value thing really
>> just shows that you can get the behaviour of a local variable which is
>> initialised once, at load-time though, without doing thing that I
>> suspect people who aren't comfortable with closures might find
>> uncomfortable.
>
>Yup. And I think DEFUN is only guaranteed to portably work on top-level
>lisp anyhow. Or was that "only guaranteed read-time"? Ah, well.
DEFUN is guaranteed to work at not-top-level too in ANSI Common Lisp,
as are all the other defining forms.
Tim
In article <·····························@mb-me.aol.com>, ALBINALI4 wrote:
>Hi,
> What determines wether an object is allocated statically, on the stack or on
>the heap in Lisp?
Lisp isn't defined in terms of these concepts. An object's lifetime
is called its extent. The extent can be dynamic or indefinite.
Dynamic extent means that an object disappears when the expression in
which it was created terminates. This is obviously bad if the program
continues to refer to the object after that! So dynamic extent isn't
done if the programmer doesn't explicitly request it with a declaration,
and might not be done even if the programmer does request it. Blowing away
dynamic-extent objects is a matter of compiler optimization. The reason
Lisp programmers sometimes declare objects to have dynamic-extent is
simply for performance reasons; it may be possible to allocate the object
more efficiently, and generate less garbage or none at all.
Indefinite extent means that an object persists for as long as it cannot
be proven that the program can no longer refer to it. Indefinite extent
is the norm for objects things in Lisp, including lexical variable
bindings. Thus even if a function terminates, its local variables can
still be used, their values intact. This property is very important
to closures.
To get an effect similar to static variables in other programming
languages, you have two options.
One is to use special variables, which are Lisp's globals. When you assign
a value to some symbol that is not lexically bound, a global binding
is set up which persists until a different value is assigned. Using
a variable binding construct such as let causes a local binding to be
established which shadows any global ones or less enclosed local ones.
If you want a variable that is associated with some functions, whose
value persists across function calls, but is only known to those function,
you can surround function definitions in a lexical variable binding
construct:
(let ((count 0))
(defun counting-function ()
(incf count))
;; ... possibly other functions
)
(counting-function) ==> 1
(counting-function) ==> 2
(setf count 0)
(counting-function) ==> 3
Here, count is not a global variable; as you can see by the lack of
effect that the (setf count 0) assignment has on the value computed
by counting-function. Rather, it is a lexical variable binding that
is captured by a closure. The (let ...) form is evaluated at the top
level right after it is read and establishes a local variable. The
functions defined within that form capture that variable's binding.
That binding has indefinite extent which allows it to persist
from one function call to the next.
Thanks, Kaz, for your long and detailed articles.
"Kaz Kylheku" <···@accton.shaw.ca> wrote in message
···························@news1.calgary.shaw.ca...
> Indefinite extent means that an object persists for as long as it cannot
> be proven that the program can no longer refer to it. Indefinite extent
> is the norm for objects things in Lisp, including lexical variable
> bindings. Thus even if a function terminates, its local variables can
> still be used, their values intact. This property is very important
> to closures.
I was wondering about the above. Is it just not worded very carefully, or is
there something for me to learn here. How can a function's local variables be
accessed? (unless in (let (foo) (defun bar() foo)) foo can correctly be called
"local")
--
Coby
(remove #\space "coby 101 @ bigpond . com")
>>>>> "CB" == Coby Beck <·····@mercury.bc.ca> writes:
CB> Kylheku" <···@accton.shaw.ca> wrote in message
[...]
>> Indefinite extent means that an object persists for as long as
>> it cannot be proven that the program can no longer refer to
>> it. Indefinite extent is the norm for objects things in Lisp,
>> including lexical variable bindings. Thus even if a function
>> terminates, its local variables can still be used, their values
>> intact. This property is very important to closures.
CB> I was wondering about the above. Is it just not worded very
CB> carefully, or is there something for me to learn here.
I don't know, but based on what you say below it might be that you are
confusing scope and extent. I was going to write an ill-worded paragragh
and possibly cause Kent to come out here, but I am lazy so I googled:
http://www.psg.com/~dlamkins/sl/chapter08.html
appears very lucid.
CB> How
CB> can a function's local variables be accessed? (unless in (let
CB> (foo) (defun bar() foo)) foo can correctly be called "local")
(defun foo (x)
(let (y)
; ... something
(list x y)))
you are returning y even though y is invisible outside foo. This may appear
natural in CL but some languages don't allow thingsequivalent to this.
Eg in C:
int * foo (int x)
{
int y;
// something
return &y;
}
is not kosher as &y makes no sense outside foo. You can use 'static' to get
the semantics of your example or explicitly malloc the storage for the value
of y to give it indefinite extent (until free is called).
cheers,
BM
* Coby Beck wrote:
> I was wondering about the above. Is it just not worded very carefully, or is
> there something for me to learn here. How can a function's local variables be
> accessed? (unless in (let (foo) (defun bar() foo)) foo can correctly be called
> "local")
Well, a better example is something like the standard kar/kons/kdr
thing (untested code, or perhaps kode).
(defun kons (car cdr)
#'(lambda (key &optional val)
(ecase key
((kar) car)
((set-kar) (setf car val))
((kdr) cdr)
((set-kdr) (setf cdr va)))))
(defun kar (kons)
(funcall kons 'kar))
(defun kdr (kons)
(funcall kons 'kdr))
(defun (setf kar) (new kons)
(funcall kons 'set-kar new))
(defun (setf kdr) (new kons)
(funcall kons 'set-kdr new))
where the local variables of KONS remain accessible by the closure it
returns.
--tim