Hi folks,
This may be a stupid question, but I'm no computer scientist, so hear
goes.
What is the difference between the heap and the stack, and how does one
control whether memory is allocated on the heap or the satck. Graham's
ANSI Lisp book seems to suggest that dynamically scoped variables are
allocated on the stack, while lexically (i.e., non-dynamically) scoped
variables are allocated on the heap. Is this correct?
Is it always preferable to allocate large data structures on the heap
rather than the stack (i.e., as global variables rather than as local
variables)?
My problem arises in CMU Lisp where some of my code seems to be
overflowing the stack (> 2 Mbytes are on the stack when things crash). I
should note that the same code runs without a problem using CLISP. I
realize that the problem with my code may have nothing to do with the
heap or the stack, but I'd like to clarify this issue anyway.
Thanks.
-bruce
Bruce L. Lambert, Ph.D.
Department of Pharmacy Administration
University of Illinois at Chicago
········@uic.edu
http://ludwig.pmad.uic.edu/~bruce/
Phone: +1 (312) 996-2411
Fax: +1 (312) 996-0868
In article <············@piglet.cc.uic.edu>, "Bruce L. Lambert, Ph.D."
<········@uic.edu> wrote:
> This may be a stupid question, but I'm no computer scientist, so hear
> goes.
There are no stupid questions, just stupid answers.
> What is the difference between the heap and the stack, and how does one
> control whether memory is allocated on the heap or the satck.
A stack and a heap are both chunks of memory in which objects get stored.
The difference is that in a heap objects can be discarded (and the memory
they use freed for other uses) at any time, whereas in a stack objects
are always discarded in the reverse order in which they were allocated.
(Stacks are sometimes called FILO or LIFO queues -- First-In-Last-Out,
or vice versa.)
Heaps are more versatile, but difficult to maintain. Stacks are more
constrained, but easier (in fact trivial) to maintain and therefore
more efficient.
> Graham's
> ANSI Lisp book seems to suggest that dynamically scoped variables are
> allocated on the stack, while lexically (i.e., non-dynamically) scoped
> variables are allocated on the heap. Is this correct?
No. Usually, *all* variables (except global variables, i.e. symbols) are
stored on the stack, while the data structures thay they point to are
stored on the heap.
>My problem arises in CMU Lisp where some of my code seems to be
>overflowing the stack
What may be happening to you is that the CMU compiler is too good:
In general storing things on the stack is more efficient, but it is a lot
of work for the compiler to figure out when this is OK to do. CMUCL does
this work; CLISP doesn't. My guess is that CMUCL is storing some data
structures on the stack that CLISP puts on the heap, and that is causing
your stack overflow.
E.
--
Erann Gat ···@jpl.nasa.gov ···@power.net
In article <················@milo.jpl.nasa.gov>,
Erann Gat <···@jpl.nasa.gov> wrote:
..
>> Graham's
>> ANSI Lisp book seems to suggest that dynamically scoped variables are
>> allocated on the stack, while lexically (i.e., non-dynamically) scoped
>> variables are allocated on the heap. Is this correct?
>
>No. Usually, *all* variables (except global variables, i.e. symbols) are
>stored on the stack, while the data structures thay they point to are
>stored on the heap.
Eh? Maybe in languages without closures, but Lisp isn't one of those.
For example, in the below var1, var2, and var3 can't be allocated on the
"stack", for they persist after the call to the function is done.
(defun closure-maker ( var1 var2 var3 )
(let (( closure #'(lambda ( x ) (if (evenp var1 )
(+ var2 x)
(+ var3 x) ) ) ) )
(incf var2)
(incf var3)
closure))
(funcall (closure-maker 2 10 20 ) 100 ) ==> 111
(funcall (closure-maker 1 10 20 ) 100 ) ==> 121
So unless the compiler is going to do some sort of closure capture analysis
the default will be that NO variables (references to values) are kept on the
stack. Each variable is keep in a heap allocated "environment" data
structure. The reference to this environment is kept on the stack... but
will not be deallocated if there is some other reference to it ( i.e. not
LIFO)
>What may be happening to you is that the CMU compiler is too good:
...
>structures on the stack that CLISP puts on the heap, and that is causing
>your stack overflow.
Most likely true. You might also convert to tail recursion if possible
that way the optimizations that CMULISP would perform would negate having
to use the stack much at all.
--
Lyman S. Taylor "Computers are too reliable to replace
(·····@cc.gatech.edu) humans effectively."
Commander Nathan Spring, "Starcops"