I've been wondering why stack space is so limited in some lisps.
(Stopping coders from recursing on cdr's of arbitrary lists.) Does
anyone know where I can learn why?
I've looked through a few books which mention a couple small
optimizations, and my guess is that it's more portable for lisp
implementations to accept this limitation, and not enough customers
have complained. And maybe some platforms penalize compilers that
don't use the limited stack. However, Stackless Python promises to do
this, and probably Schemes do this too. So I wonder what the
tradeoffs are. (And are there hidden traps using full recusion even
in Stackless Python/Schemes?)
Thanks for any help, this is a headscratcher for me.
··········@yahoo.com (Tayss) writes:
> I've been wondering why stack space is so limited in some lisps.
> (Stopping coders from recursing on cdr's of arbitrary lists.) Does
> anyone know where I can learn why?
>
> I've looked through a few books which mention a couple small
> optimizations, and my guess is that it's more portable for lisp
> implementations to accept this limitation, and not enough customers
> have complained. And maybe some platforms penalize compilers that
> don't use the limited stack. However, Stackless Python promises to do
> this, and probably Schemes do this too. So I wonder what the
> tradeoffs are. (And are there hidden traps using full recusion even
> in Stackless Python/Schemes?)
Are you talking abou limited in the sense of "finite vs. infinite?"
> Thanks for any help, this is a headscratcher for me.
I only want to add a bit of additinal info: here is an article
covering Stackless Python:
http://www.stackless.com/spcpaper.htm
So it seems that Python will have continuations.
Mario S. Mommer <········@yahoo.com> wrote in message news:<··············@cupid.igpm.rwth-aachen.de>...
> Are you talking abou limited in the sense of "finite vs. infinite?"
To be more specific, why the function stack isn't heap-allocated, as
Pascal Bourguignon asks. Searching usenet, I would find threads like
this:
http://groups.google.com/groups?hl=en&lr=&ie=UTF-8&oe=UTF-8&safe=off&threadm=39ABBC41.480E300B%40bbn.com&rnum=8&prev=/groups%3Fhl%3Den%26lr%3D%26ie%3DUTF-8%26oe%3DUTF-8%26safe%3Doff%26q%3Drecursion%2Bstack%26btnG%3DGoogle%2BSearch%26meta%3Dgroup%253Dcomp.lang.lisp.*
where people explained that we had to worry about stack overflow. In
the best of all universes, I'd like memory to store any growth of
state, and not have arbitrary limits.
Maybe there's a good reason; hard to write a high-performance lisp?
Not portable?
··········@yahoo.com (Tayss) wrote in message news:<····························@posting.google.com>...
> Mario S. Mommer <········@yahoo.com> wrote in message news:<··············@cupid.igpm.rwth-aachen.de>...
> > Are you talking abou limited in the sense of "finite vs. infinite?"
>
> To be more specific, why the function stack isn't heap-allocated, as
Because Lisp is a real language that can be compiled to real machine
code that uses the real stack features that your CPU designers
provided? Doh?
Allocating and liberating on the stack involves simple pointer
increments. Many processors have a dedicated register that serves as a
stack pointer, and some helper instructions to manage it more
efficiently; for instance, deluxe instruction to set up or tear down
frames in one apparent step.
> Pascal Bourguignon asks. Searching usenet, I would find threads like
> this:
What platform are you running on? On the general purpose desktop
operating systems, you have generous stack space. For example, the
default stack size for the main thread on Linux is 8 megabytes. I seem
to recall that on Windows, the .EXE file contains something in its
header that specifies how much stack size it should get. On a virtual
memory OS, the stack is just another memory mapping.
These days, stack size is a concern primarily in embedded programming.
If you can't figure out how to avoid blowing an 8 megabyte stack,
maybe this software development thing isn't your cup of tea.
Well, in any case I wish it were possible to tell the compiler, "In
case of stack overflow, please put this function's bookkeeping on the
heap. I promise not to interop with other languages, need lots of
speed, or whatever."
···@ashi.footprints.net (Kaz Kylheku) wrote in message news:<····························@posting.google.com>...
> If you can't figure out how to avoid blowing an 8 megabyte stack,
> maybe this software development thing isn't your cup of tea.
[...]
> Because Lisp is a real language that can be compiled to real machine
> code that uses the real stack features that your CPU designers
> provided? Doh?
I didn't ask for their white elephant, and I didn't want it. ;) I
bought lots of quality RAM for a reason -- I thought my computer would
store things in it. Seriously, thanks for the analysis.
From: Duane Rettig
Subject: Re: Why do lisps have stack limits?
Date:
Message-ID: <4llq5u2q3.fsf@franz.com>
···@ashi.footprints.net (Kaz Kylheku) writes:
> ··········@yahoo.com (Tayss) wrote in message news:<····························@posting.google.com>...
> > Mario S. Mommer <········@yahoo.com> wrote in message news:<··············@cupid.igpm.rwth-aachen.de>...
> > > Are you talking abou limited in the sense of "finite vs. infinite?"
> >
> > To be more specific, why the function stack isn't heap-allocated, as
>
> Because Lisp is a real language that can be compiled to real machine
> code that uses the real stack features that your CPU designers
> provided? Doh?
It's true, but it's not necessarily a "doh" (or "duh"?). We did a lot
of experimenting when we did our first (non-Procyon-based) NT/win95 port
to find out what we could do with stacks and what we coldn't do. It
became clear what the operating system wanted and assumed, but those
assumptions were not documented anywhere.
> Allocating and liberating on the stack involves simple pointer
> increments. Many processors have a dedicated register that serves as a
> stack pointer, and some helper instructions to manage it more
> efficiently; for instance, deluxe instruction to set up or tear down
> frames in one apparent step.
Given a large enough specilized array, I could easily simulate this
by having a "stack-pointer" which does the same thing, And in fact,
since the stack-pointer is usually restricted to a word-size, and given
the nature of fixnums in many CL implementations, I could represent
the actual pointer to the stack as a fixnum of the stack-address shifted
right by two bits (on a 32-bit system) or by three bits ( on a 64-bit
system).
The problem is that for most generational allocators/collectors, this
array could not be in the normal heap, because it will tend to move
around, and that would invalidate the intra-stack pointers that are
inevitable in any stack-frame design. Of course, these pointers could
also be in the form of offsets rather than hard addresses, but then
access time would be slower due to an extra addition to convert an
offset into a pointer.
> > Pascal Bourguignon asks. Searching usenet, I would find threads like
> > this:
>
> What platform are you running on? On the general purpose desktop
> operating systems, you have generous stack space. For example, the
> default stack size for the main thread on Linux is 8 megabytes. I seem
> to recall that on Windows, the .EXE file contains something in its
> header that specifies how much stack size it should get. On a virtual
> memory OS, the stack is just another memory mapping.
>
> These days, stack size is a concern primarily in embedded programming.
It's also a concern on 32-bit machines for programming involving many
threads. Since you mention an 8 Mb stack size below (which is indeed
a typical stack size) the practical limit on the number of threads
in a real application tends to hover around 100, when you consider
the hardware/kernel issues involved with stack-overflow detection
and stack placement. If you want to increase the number of stacks
available, you must decrease the average stack size, and a new typical
thread-stack-size becomes 2 Mb or less. This does indeed become a
concern.
> If you can't figure out how to avoid blowing an 8 megabyte stack,
> maybe this software development thing isn't your cup of tea.
--
Duane Rettig ·····@franz.com Franz Inc. http://www.franz.com/
555 12th St., Suite 1450 http://www.555citycenter.com/
Oakland, Ca. 94607 Phone: (510) 452-2000; Fax: (510) 452-0182
···@ashi.footprints.net (Kaz Kylheku) wrote:
> Because Lisp is a real language that can be compiled to real machine
> code that uses the real stack features that your CPU designers
> provided? Doh?
>
> Allocating and liberating on the stack involves simple pointer
> increments. Many processors have a dedicated register that serves as a
> stack pointer, and some helper instructions to manage it more
> efficiently; for instance, deluxe instruction to set up or tear down
> frames in one apparent step.
Quite a few systems have demonstrated that one can use these machine
registers and instructions for their intended purposes without
limiting stacks to sizes that are substantially smaller than the
available heap storage.
Will
···@ashi.footprints.net (Kaz Kylheku) writes:
> ··········@yahoo.com (Tayss) wrote in message news:<····························@posting.google.com>...
> > Mario S. Mommer <········@yahoo.com> wrote in message news:<··············@cupid.igpm.rwth-aachen.de>...
> > > Are you talking abou limited in the sense of "finite vs. infinite?"
> >
> > To be more specific, why the function stack isn't heap-allocated, as
>
> Because Lisp is a real language that can be compiled to real machine
> code that uses the real stack features that your CPU designers
> provided? Doh?
>
> Allocating and liberating on the stack involves simple pointer
> increments. Many processors have a dedicated register that serves as a
> stack pointer, and some helper instructions to manage it more
> efficiently; for instance, deluxe instruction to set up or tear down
> frames in one apparent step.
>
> > Pascal Bourguignon asks. Searching usenet, I would find threads like
> > this:
>
> What platform are you running on? On the general purpose desktop
> operating systems, you have generous stack space.
Unfortunately, this isn't true:
[···@Cannon]~$ uname -sr
Darwin 6.8
[···@Cannon]~$ ulimit -s
512
On OS X, unless you ask for more, you get a 512K stack limit.
Fortunately, I start my lisps with shell scripts anyway, so I just
added a call to ulimit, but it *can* make for a rather unpleasant
surprise at first.
--
/|_ .-----------------------.
,' .\ / | No to Imperialist war |
,--' _,' | Wage class war! |
/ / `-----------------------'
( -. |
| ) |
(`-. '--.)
`. )----'
···@ashi.footprints.net (Kaz Kylheku) writes:
> What platform are you running on? On the general purpose desktop
> operating systems, you have generous stack space. For example, the
> default stack size for the main thread on Linux is 8 megabytes. I seem
> to recall that on Windows, the .EXE file contains something in its
> header that specifies how much stack size it should get. On a virtual
> memory OS, the stack is just another memory mapping.
>
> These days, stack size is a concern primarily in embedded programming.
You're forgething multithreading: each thread needs its own
stack. Fork 1000 threads and suddenly your 4e9 addressing spaces looks
more like 4e6 per thread, and even less if you remove various
limitations such as shared library space and other OS restrictions.
> If you can't figure out how to avoid blowing an 8 megabyte stack,
> maybe this software development thing isn't your cup of tea.
That's the whole point. You can come very easily with clean recursive
algorithms that are O(N) (or even less) in stack space. 8MB stack is
nothing. But because of implementation limitations, you must change
your source, derecursive and put the stack on the heap by hand, all of
which is low level uninteresting stuff. And remember, each thread may
need to do the same.
--
__Pascal_Bourguignon__ http://www.informatimago.com/
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Living free in Alaska or in Siberia, a grizzli's life expectancy is 35 years,
but no more than 8 years in captivity. http://www.theadvocates.org/
··········@yahoo.com (Tayss) writes:
> I've been wondering why stack space is so limited in some lisps.
> (Stopping coders from recursing on cdr's of arbitrary lists.) Does
> anyone know where I can learn why?
>
> I've looked through a few books which mention a couple small
> optimizations, and my guess is that it's more portable for lisp
> implementations to accept this limitation, and not enough customers
> have complained. And maybe some platforms penalize compilers that
> don't use the limited stack. However, Stackless Python promises to do
> this, and probably Schemes do this too. So I wonder what the
> tradeoffs are. (And are there hidden traps using full recusion even
> in Stackless Python/Schemes?)
>
> Thanks for any help, this is a headscratcher for me.
Stack sizes are usually limited because it's hard to allocate them
dynamically and to move them. Stack space may be needed at any
inconvenient time such as upon an interrupt. And each thread needs
its own stack, so you must share the 4GB of virtual memory (on 32-bit
processors) amongst all the threads and the heap.
With respect to Lisp, what I wonder is why lisps don't generally store
the stack in the heap? And use the processor stack only for low-level
machinery; a fixed low-level stack space would be enough: just what
that is needed for interrupts and system calls and one or two function
calls; all parameters would be passed either in register or on the
heap allocated "stack" frames.
--
__Pascal_Bourguignon__
http://www.informatimago.com/
Pascal Bourguignon wrote:
> With respect to Lisp, what I wonder is why lisps don't generally store
> the stack in the heap? And use the processor stack only for low-level
> machinery; a fixed low-level stack space would be enough: just what
> that is needed for interrupts and system calls and one or two function
> calls; all parameters would be passed either in register or on the
> heap allocated "stack" frames.
I think most implementations of Scheme use a stack cache of fixed
size, but handle stack cache overflow and underflow so the effective
size of the stack is bounded only by the availability of heap storage.
This isn't often done in Common Lisp, probably because the implementor
would end up doing most of the work needed to support first class
continuations without giving the Common Lisp programmer all of their
benefits.
Sorry, I forgot this is comp.lang.lisp. I meant to say "without giving
the programmer all of their disadvantages".
Will
On 23 Nov 2003 18:03:33 +0100, Pascal Bourguignon
<····@thalassa.informatimago.com> wrote:
>Stack sizes are usually limited because it's hard to allocate them
>dynamically and to move them. Stack space may be needed at any
>inconvenient time such as upon an interrupt. And each thread needs
>its own stack, so you must share the 4GB of virtual memory (on 32-bit
>processors) amongst all the threads and the heap.
>
Actually, in most OSes any process can ask for and reserve the full
possible range of virtual addresses - ie. the address space is itself
virtualized and each process gets 4GB (or whatever) of virtual
addresses to play with. The problems come when the system trys to
associate physical storage (RAM or backing store) to the virtual
addresses and runs out of resources.
Standard OS allocation functions reserve address space and commit
storage in the same call and so they barf immediately if resources are
exhausted. You can get around this in most OSes by directly using low
level virtual memory functions which separate address space
manipulation from storage commitment ... but you then take
responsibility for managing the application's virtual memory use. You
would do this, for example, to create your own Lisp system.
I read a paper long ago about a (maybe experimental) 32-bit OS whose
virtual memory system directly indexed up to 2^32 virtual memory pages
as raw data blocks on the backing store. Because process address
space was limited to 2^32 bytes, you could, conceptually at least, run
multiple processes each with a fully committed address space.
I don't know whether this works in any modern 32-bit OSes ... I've
never tried it and have yet to even configure a system with 4GB of
virtual memory ( the biggest so far had 1920MB total ). I've rarely
had occasion to use VM directly in an application (I've done a couple
of device drivers) and never cared enough to investigate the internals
of the various implementions beyond their APIs.
George
From: Joe Marshall
Subject: Re: Why do lisps have stack limits?
Date:
Message-ID: <k75lkdqx.fsf@comcast.net>
George Neuner <········@no.comcast.spam.net> writes:
> Actually, in most OSes any process can ask for and reserve the full
> possible range of virtual addresses - ie. the address space is itself
> virtualized and each process gets 4GB (or whatever) of virtual
> addresses to play with.
It really depends on the OS. Under Windows, you used get 2GB, the
upper 2GB is reserved for the OS and (I think) shared memory. Lately,
you can configure Windows with 3GB of directly addressable memory per
process. Then there are the virtual address extensions that work sort
of like `extended memory' in DOS. You can request space out in this
range if you want to manage the address swapping yourself. It's a
kludge to push beyond the 3 MB limit.
Under Unix (again depending on flavor) it can be as low as 1GB per
process, but I think that 2GB is more common. Under Unix, you have to
be careful because there are two mechanisms for reserving address
space: SBRK and MMAP. SBRK is the older of the two and simply `grows'
the address space linearly, while MMAP allows you to grab arbitrary
regions. I have seen Unix systems that warn that SBRK and MMAP do
not play well together and advise the user to use one or the other,
but never both (they apparently did not think through the implications
of this advice!)
--
~jrm
On Thu, 27 Nov 2003 15:55:19 GMT, Joe Marshall
<·············@comcast.net> wrote:
>George Neuner <········@no.comcast.spam.net> writes:
>
>> Actually, in most OSes any process can ask for and reserve the full
>> possible range of virtual addresses - ie. the address space is itself
>> virtualized and each process gets 4GB (or whatever) of virtual
>> addresses to play with.
>
>It really depends on the OS. Under Windows, you used get 2GB, the
>upper 2GB is reserved for the OS and (I think) shared memory. Lately,
>you can configure Windows with 3GB of directly addressable memory per
>process. Then there are the virtual address extensions that work sort
>of like `extended memory' in DOS. You can request space out in this
>range if you want to manage the address swapping yourself. It's a
>kludge to push beyond the 3 MB limit.
>
>Under Unix (again depending on flavor) it can be as low as 1GB per
>process, but I think that 2GB is more common. Under Unix, you have to
>be careful because there are two mechanisms for reserving address
>space: SBRK and MMAP. SBRK is the older of the two and simply `grows'
>the address space linearly, while MMAP allows you to grab arbitrary
>regions. I have seen Unix systems that warn that SBRK and MMAP do
>not play well together and advise the user to use one or the other,
>but never both (they apparently did not think through the implications
>of this advice!)
Those are examples of what I call soft limits - the system allocator
permanently reserves part of the address space so that kernel code can
be mapped at the same address in every application and may also
reserve space so commonly used dynamic libraries can be loaded without
the expense of relocation.
SBRK and MMAP are high level APIs that allow management only of
committed storage. AFAIK, there is no portable way in Unix to write
an application that directly manages virtual memory. Note that I'm
also excluding the "k*" kernel and "kvm(d)?_*" device drivers
functions - they also are high level in my meaning because they manage
only committed storage. The raw VM API differs from system to system,
and is typically documented only in the kernel source.
Win32 is interesting because there is a standard, documented API for
raw VM management which any application can use - see "VirtualAlloc"
and it's associated functions for details.
The Address Windowing Extensions, which I believe you were referring
to above, reimplement the old DOS expanded memory on Win32 and
provide a way for applications to use RAM beyond the normal OS limits.
They are not really relevent to this discussion because the memory
they control is outside the scope of the VMM system.
George
George Neuner <········@no.comcast.spam.net> writes:
> On Thu, 27 Nov 2003 15:55:19 GMT, Joe Marshall
> <·············@comcast.net> wrote:
>>process. Then there are the virtual address extensions that work sort
>>of like `extended memory' in DOS. You can request space out in this
>>range if you want to manage the address swapping yourself. It's a
>>kludge to push beyond the 3 MB limit.
> The Address Windowing Extensions, which I believe you were referring
> to above, reimplement the old DOS expanded memory on Win32 and
> provide a way for applications to use RAM beyond the normal OS limits.
> They are not really relevent to this discussion because the memory
> they control is outside the scope of the VMM system.
_I_ think Joe was referring to the Page Address Extensions: 36 bits
worth of memory, but still only 32 bit pointers, necessitating that
the OS do some kind of EMS-like bank switching
http://www.microsoft.com/whdc/hwdev/platform/server/pae/pae_os.mspx
But anyway, I'm not aware of any way you can use these to get at >32
bits in a single process, so your point insofar as I understood it
still stands. icbw
-dan
--
http://web.metacircles.com/ - Open Source software development and support
Doh! I just realized that you were speaking about threads rather than
processes. I should learn not to read these things at 2am.
However, address space could just as easily be owned and shared by
threads - the "process" would then be the shared context of a group of
threads. Context switching would be more expensive but such a system
might have interesting properties.
George
From: james anderson
Subject: Re: Why do lisps have stack limits?
Date:
Message-ID: <3FC0F388.6868CE2C@setf.de>
if you look in the info-mcl list, you will find some discussion of the issues
related to stack size and contiguity.
start with
http://search.gmane.org/search.php?query=stack&group=gmane.lisp.mcl.general
and look for gary byers.
...
Tayss wrote:
>
> I've been wondering why stack space is so limited in some lisps.
> (Stopping coders from recursing on cdr's of arbitrary lists.) Does
> anyone know where I can learn why?
>
> I've looked through a few books which mention a couple small
> optimizations, and my guess is that it's more portable for lisp
> implementations to accept this limitation, and not enough customers
> have complained. And maybe some platforms penalize compilers that
> don't use the limited stack. However, Stackless Python promises to do
> this, and probably Schemes do this too. So I wonder what the
> tradeoffs are. (And are there hidden traps using full recusion even
> in Stackless Python/Schemes?)
>
> Thanks for any help, this is a headscratcher for me.
From: Duane Rettig
Subject: Re: Why do lisps have stack limits?
Date:
Message-ID: <4u14u8ejg.fsf@franz.com>
··········@yahoo.com (Tayss) writes:
> I've been wondering why stack space is so limited in some lisps.
> (Stopping coders from recursing on cdr's of arbitrary lists.) Does
> anyone know where I can learn why?
It's easy enough to simulate stacks in Common Lisp interpreters
(push/pop are in fact stack-like in operation), though it is usually
wise to try to optimize simulated stacks to at least approximate
the random-access that system stacks tend to provide. These can
easily be done in the heap.
However, I suspect that your question really deals with the use of
system stacks in _compiled_ code (which in fact might include the
inner workings of an interpreter, if implemented procedurally and
recursively). The reason to use system stacks (and indeed to
approximate the standard C calling conventions when possible,
even for lisp calls), is to provide an other-language-friendly
environment on which to run CL code [here, "other languages"
refer to languages which also adhere to the standard calling
conventions of the machine].
In Allegro CL, we include unwinding as part of this good-neighbor
policy. When a callback is defined, it is possible to throw over
C or C++ code either by tearing off stack space, or by returning
a code to the caller. In this way, CL code is able to honor
try/excpt blocks in C++, and C++ can execute its own version of
unwind-protection. The newer Calling standards I've seen even
have unwind libraries that apparently allow the C++ code to be
friendly to other languages (ones which also assume the same
stack) but I have not tried any of these out, nor am I aware of
any who have made use of these.
Bottom line is that the commonality of the stack tends to bring
the languages closer together, allowing cross-language calling
to be fairly efficient and tight.
> I've looked through a few books which mention a couple small
> optimizations, and my guess is that it's more portable for lisp
> implementations to accept this limitation, and not enough customers
> have complained.
Most operating systems allow stack sizes to be regulated, although
a proliferation of threads can become a problem 32-bit architectures.
An obvious reason for implementing a stack in the heap is that the
stack memory is more easily managed as a part of a single whole,
rather than being broken up into many pieces in a linear address
space in the form of multiple stacks. However, for the most part
we find that the stacks which hardware and operating systems
maintain are optimized for the tasks which their standard calling
conventions are created (and for tasks which the languages that
use these conventions allow) and so we tend to ride that bandwagon
and I think that the benefits outweigh the limitations, which are
themselves can be mitigated, depending on the flexibility of the
operating system.
> And maybe some platforms penalize compilers that
> don't use the limited stack.
I think that the "penalization" you refer to is really only a
pessimization due to the created stack either being emulated as
random-access data (a stack, though usually random access, tends
to be used on a LIFO basis and is thus optimizable by the kernel)
or else not being recognized as a stack by the operating system,
thus not carrying with it any exception handling required by the
main of the program. Some operating systems are more lenient than
others in this regard.
> However, Stackless Python promises to do
> this, and probably Schemes do this too. So I wonder what the
> tradeoffs are. (And are there hidden traps using full recusion even
> in Stackless Python/Schemes?)
>
> Thanks for any help, this is a headscratcher for me.
--
Duane Rettig ·····@franz.com Franz Inc. http://www.franz.com/
555 12th St., Suite 1450 http://www.555citycenter.com/
Oakland, Ca. 94607 Phone: (510) 452-2000; Fax: (510) 452-0182
Duane Rettig <·····@franz.com> wrote in message news:<·············@franz.com>...
> However, I suspect that your question really deals with the use of
> system stacks in _compiled_ code (which in fact might include the
> inner workings of an interpreter, if implemented procedurally and
> recursively). The reason to use system stacks (and indeed to
> approximate the standard C calling conventions when possible,
> even for lisp calls), is to provide an other-language-friendly
> environment on which to run CL code [here, "other languages"
> refer to languages which also adhere to the standard calling
> conventions of the machine].
Ahh, it makes so much sense. Having to be social with other languages
is so annoying. ;) Thanks for the clear explanation. (And to
everyone else that helped shed light.)
Ok, now I can use iteration more freely now that I know the reason. I
wish lisp books mentioned this caveat in footnotes, especially since
there's something bothering about limitations that one doesn't
understand the reason for.
Duane Rettig <·····@franz.com> writes:
> Bottom line is that the commonality of the stack tends to bring
> the languages closer together, allowing cross-language calling
> to be fairly efficient and tight.
Yes, but this still makes it sound like it's an error that other
languages use stacks and that we just tolerate it.
I think additionally you could say that infinite stack is not needed
in most cases, and that finite stack is a way of stopping programs in
finite time when they are running out of control. Otherwise, they
would consume the whole machine's memory after a while. (Some would say
this wouldn't happen if there was reliable tail call elimination, but then
all you'd get is a tight use that used all the user's time instead of all
the user's memory, which I'm not sure is any better if the program is,
indeed, errant.)
I guess you were alluding somewhat to this here below, but again you
weren't overt about the reason why regulation is desirable and not a
mere accomodation to bad programming style (as we might sometimes say
finite length string buffers and their associated buffer overruns
are).
> Most operating systems allow stack sizes to be regulated, although
> a proliferation of threads can become a problem 32-bit architectures.
> An obvious reason for implementing a stack in the heap is that the
> stack memory is more easily managed as a part of a single whole,
> rather than being broken up into many pieces in a linear address
> space in the form of multiple stacks. However, for the most part
> we find that the stacks which hardware and operating systems
> maintain are optimized for the tasks which their standard calling
> conventions are created (and for tasks which the languages that
> use these conventions allow) and so we tend to ride that bandwagon
> and I think that the benefits outweigh the limitations, which are
> themselves can be mitigated, depending on the flexibility of the
> operating system.
From: Duane Rettig
Subject: Re: Why do lisps have stack limits?
Date:
Message-ID: <4he0ttujq.fsf@franz.com>
Kent M Pitman <······@nhplace.com> writes:
> Duane Rettig <·····@franz.com> writes:
>
> > Bottom line is that the commonality of the stack tends to bring
> > the languages closer together, allowing cross-language calling
> > to be fairly efficient and tight.
>
> Yes, but this still makes it sound like it's an error that other
> languages use stacks and that we just tolerate it.
Well, I guess I view CL as a very tolerant and friendly language, and
so I view this tolerance as a Good Thing. It also tends to allow
for the use of the op-sys's automations that are already in place
for stacks, which may include hard or soft detection of stack overflows
and semi-automatic (i.e. under program control) extensions of the stack
when it overflows, automatic instantiation of the swap to back up a
growing stack (rather than having to allocate that swap all at once
when the max stack size is determined), plus standard unwindability for
debuggers.
> I think additionally you could say that infinite stack is not needed
> in most cases, and that finite stack is a way of stopping programs in
> finite time when they are running out of control. Otherwise, they
> would consume the whole machine's memory after a while. (Some would say
> this wouldn't happen if there was reliable tail call elimination, but then
> all you'd get is a tight use that used all the user's time instead of all
> the user's memory, which I'm not sure is any better if the program is,
> indeed, errant.)
>
> I guess you were alluding somewhat to this here below,
[discussion of memory layout and linmitations ...]
Yes, partially.
> but again you
> weren't overt about the reason why regulation is desirable and not a
> mere accomodation to bad programming style (as we might sometimes say
> finite length string buffers and their associated buffer overruns
> are).
But who's to say what is bad programming style and what is simply
a large (deeply recursive, in this case) problem to solve? And
although obviously all stack resource usage can be translated into
heap resourse usage, and since the transformation of a stack into
a heap-stack is simply a translation of one finite resource into a
larger (but still finite) resource, who's to say whether a program
that uses up _all_ of those resources is a badly-written program,
or simply a program which is operating on a very large problem?
Several employers ago, when I was running a Spice program to simulate
some electronic components in a test harness I was building (this
was before the old bed-of-nails testers had been popularized) I got
some tongue-lashings from the operators of the "big" Univac 1108
I was running the Spice simulations on, because my jobs, even though
they were batch jobs, were taking up too much memory. I was lectured
to about the need to reduce my program size, because of course the
use of 100 Kbytes of core memory indicated a bad program. In fact,
they were right, but not because my program was bad (it was a standard,
fairly well-tested program), but because I had been submitting these
jobs during the daytime, when resources were tight. Submitting the
jobs at night solved the problem for me. The moral? The
appropriateness of a program's resource usage is not necessarily
proportional to the program's well-written-ness.
--
Duane Rettig ·····@franz.com Franz Inc. http://www.franz.com/
555 12th St., Suite 1450 http://www.555citycenter.com/
Oakland, Ca. 94607 Phone: (510) 452-2000; Fax: (510) 452-0182
Duane Rettig <·····@franz.com> writes:
> But who's to say what is bad programming style and what is simply
> a large (deeply recursive, in this case) problem to solve?
Well, indeed. My real point here was that the original post seemed to
have as its implication that stack limits were bad, and I wanted to
point out that whether they are is subjective. There are indeed some
reasons for wanting deep recursion, and for this one can just write a
handler that extends the stack (in implementations that allow it), or
pre-allocate lots of stack (for other implementations). But infinitely
deep stacks are no substitute for tail call elimination if the calls are
supposed to be getting cleaned up and are not. And calling functions
recursively when the language or implementation doesn't assure you that
tail call elimination will occur is no substitute for writing a loop.
So I wasn't meaning to take a political stance here other than to say
that whether there was even a problem in the first place is already
subjective.
> The moral? The appropriateness of a program's resource usage is not
> necessarily proportional to the program's well-written-ness.
Yes. But to this I'll add: well-written-ness is not an absolute. It
is relative to a context. The implementation and/or language spec
generally precedes the program, and the program is written in the
context of resource limitations. In a small address space, these
things were of concern and well-written programs _for that context_
did not do that, _even if_ the context did not promote the kinds of
programs we hoped to be writing in the long run...