Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss

About checking stack-underflow/overflow in FORTH

418 views
Skip to first unread message

Choi Dong-Zin

unread,
Sep 14, 1999, 3:00:00 AM9/14/99
to
Hi, ALL.

I came across an idea about how to check stack-underflow/overflow in
FORTH.

Stack-underflow checking is, I think, very important in the FORTH system.
For example, if we type "0 . . <enter>" in the FORTH interpreter level,
nearly all FORTHs will report an error message indicating 'stack-underflow'
when executing the second dot (.). Then the control will be passed to the
error-handling functions such as ABORTQ or ABORT.

Traditionally, stack-overflow checking was recognized, I think, relatively
less important than the stack-underflow checking. The main reason for that
should be that the stack-overflow is rarely occurred. So the earlier FORTHs
were lack of it as far as I know. About nowadays FORTHs, I don't know.

The traditional skeme for stack checking is:
1. There shall be some marginal spaces below the bottom of the stack and/or
above the top of the stack.
2. The stack will not be examined too often for the efficiency reasons. The
stack is generally examined at the end of each source line.
3. The stack-underflow/overflow is checked by comparing the current stack
pointer(SP@) against the initial stack pointer(SP0 @), or by checking
whether or not the contents in the marginal spaces that were filled with
specific bytes (say, '0FFh') have been changed.

However, the microprocessors have changed. The 80386+, ARM7, and other
nowadays CPUs have the so-called protected mode. Each application has its
own memory space allocated under these processors. If an application tries
to access a memory outside of its own allocated space, a CPU interrupt(or
exception) will occur immediately. We can use this HARDWARE fact in the
checking of the stack-underflow/overflow when writing a FORTH under these
processors.

I love OS/2. In spite of its poor user interfaces, I do love the
programming environment of OS/2. And I love the Red Book, which explains, I
think, almost everything the kernel of the OS does. The OS/2 handles the
memory allocation in the unit of 4KB, which is called a page in OS/2. If an
application requests and gets allocated pages, it can freely access the
pages, but every attempt to access the outside of the allocated pages will
result in the hardware exception('page fault') the CPU autonomously
triggers.

Now let me introduce the new skeme of stack-checking in OS/2 under these
processors.
1. We don't need to allocate any maginal spaces just outside of the stack.
2. The stack size should be a multiple of 4KB.
3. We write an exception handler for the page fault, which determines
whether the exception has been triggered by a stack-underflow, by a
stack-overflow or by other reasons (say, referencing null pointer), displays
an appropriate message indicating what's wrong, initializes the stack, and
passes control to the main loop QUIT.
4. Now we don't have to check the stack manually. The hardware will,
instead.

That's all.

Finally I have a question. Currently I am writing a FORTH in WinNT. I have
told that the memory allocation skeme for Win95/NT is very similar to that
of OS/2. In Win95/NT, however, I have never seen any document like the Red
Book in OS/2 that explains the details. Any suggestion about this
information will be a great help for me.

Thanks.


Anton Ertl

unread,
Sep 14, 1999, 3:00:00 AM9/14/99
to
In article <7rkm12$pv0$1...@b5nntp2.channeli.net>,

"Choi Dong-Zin" <dzc...@lgic.co.kr> writes:
> Now let me introduce the new skeme of stack-checking in OS/2 under these
> processors.
> 1. We don't need to allocate any maginal spaces just outside of the stack.
> 2. The stack size should be a multiple of 4KB.
> 3. We write an exception handler for the page fault, which determines
> whether the exception has been triggered by a stack-underflow, by a
> stack-overflow or by other reasons (say, referencing null pointer), displays
> an appropriate message indicating what's wrong, initializes the stack, and
> passes control to the main loop QUIT.
> 4. Now we don't have to check the stack manually. The hardware will,
> instead.

Gforth does that on OSs that support memory allocation with mmap (most
Unices). The downside is that the error message is somewhat
misleading:

.s <0> ok
drop
:1
drop
^^^^
Error: Invalid memory address

This is because Gforth just sees a SIGSEGV (segmentation violation),
not where it occurs. Some OSs give you info where the fault occurs
via the SA_SIGINFO feature, and the current developmnent sources use
this feature to give better error messages on these OSs (e.g., Digital
Unix; if there's a Linux hacker looking for a small kernel project,
how about adding the SA_SIGINFO stuff for SIGSEGV and SIGFPE to
Linux?).

- anton
--
M. Anton Ertl Some things have to be seen to be believed
an...@mips.complang.tuwien.ac.at Most things have to be believed to be seen
http://www.complang.tuwien.ac.at/anton/home.html

Andrew Haley

unread,
Sep 15, 1999, 3:00:00 AM9/15/99
to
Anton Ertl (an...@mips.complang.tuwien.ac.at) wrote:
: if there's a Linux hacker looking for a small kernel project, how

: about adding the SA_SIGINFO stuff for SIGSEGV and SIGFPE to Linux?).

This has been in Linux for quite a while. However, there's a bug in
glibc which makes it difficult to use this feature in multithreaded
programs.

Andrew.


stephe...@my-deja.com

unread,
Sep 15, 1999, 3:00:00 AM9/15/99
to
In article <7rmdso$9f8$2...@news.tuwien.ac.at>,

an...@mips.complang.tuwien.ac.at (Anton Ertl) wrote:
> This is because Gforth just sees a SIGSEGV (segmentation violation),
> not where it occurs. Some OSs give you info where the fault occurs
> via the SA_SIGINFO feature, and the current developmnent sources use
> this feature to give better error messages on these OSs (e.g., Digital
> Unix; if there's a Linux hacker looking for a small kernel project,

> how about adding the SA_SIGINFO stuff for SIGSEGV and SIGFPE to
> Linux?).

I'd noticed the above but assumed it had been fixed by now (I'm
running a two year old kernel). My temporary fix was to pick
up the information I wanted (e.g. eip) directly off the stack.
This is/was easy since the Forth in question is completely
written in assembler and so I could avoid some of the gymnastics
it would require in C (it also does not link against libc which
means I can avoid any problems it might have). I found the
information I wanted about what is pushed where on the stack buried
in /usr/src/linux/arch/i386/kernel/signal.c in and around
the function setup_frame but this may have changed in more recent
kernels. Hopefully it will contain the information you want.

Have fun.


Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.

cLIeNUX user

unread,
Sep 20, 1999, 3:00:00 AM9/20/99
to
In article <7rkm12$pv0$1...@b5nntp2.channeli.net>, Choi Dong-Zin wrote:
> Hi, ALL.
>
> I came across an idea about how to check stack-underflow/overflow in
>
> Finally I have a question. Currently I am writing a FORTH in WinNT. I have
>told that the memory allocation skeme for Win95/NT is very similar to that
>of OS/2. In Win95/NT, however, I have never seen any document like the Red
>Book in OS/2 that explains the details. Any suggestion about this
>information will be a great help for me.
>
> Thanks.
>
>
>

Linux buffer cache is the same 4k scheme I believe. And there's 50 meg
of sourcecode in an unpacked kernel distro. Then there's libc, gcc, etc.

Rick Hohensee

oh, it's 4k on x86.


Anton Ertl

unread,
Sep 20, 1999, 3:00:00 AM9/20/99
to
In article <7rohvp$li1$1...@nnrp1.deja.com>,

stephe...@my-deja.com writes:
> In article <7rmdso$9f8$2...@news.tuwien.ac.at>,
> an...@mips.complang.tuwien.ac.at (Anton Ertl) wrote:
> > This is because Gforth just sees a SIGSEGV (segmentation violation),
> > not where it occurs. Some OSs give you info where the fault occurs
> > via the SA_SIGINFO feature, and the current developmnent sources use
> > this feature to give better error messages on these OSs (e.g., Digital
> > Unix; if there's a Linux hacker looking for a small kernel project,
> > how about adding the SA_SIGINFO stuff for SIGSEGV and SIGFPE to
> > Linux?).
>
> I'd noticed the above but assumed it had been fixed by now (I'm
> running a two year old kernel).

There's a start on the siginfo stuff, but it does not yet (at least
last time I looked (2.3.12)) work for SIGSEGV and SIGFPE.

> My temporary fix was to pick
> up the information I wanted (e.g. eip) directly off the stack.
> This is/was easy since the Forth in question is completely
> written in assembler and so I could avoid some of the gymnastics
> it would require in C (it also does not link against libc which
> means I can avoid any problems it might have).

Well, this stuff is available through sigcontext in C, but it depends
on the architecture, possibly on the OS (and maybe even on the kernel
version). So we would have to do this repeatedly and differently for
a lot of platforms, and so would other programs. Better fix this in
one place: in the kernel.

Moreover, looking at the Linux-Intel sigcontext, I actually don't
see where the failing address for a SIGSEGV would reside.

Andrew Haley

unread,
Sep 20, 1999, 3:00:00 AM9/20/99
to
Anton Ertl (an...@mips.complang.tuwien.ac.at) wrote:
: There's a start on the siginfo stuff, but it does not yet (at least

: last time I looked (2.3.12)) work for SIGSEGV and SIGFPE.

It works well for me.

: Moreover, looking at the Linux-Intel sigcontext, I actually don't


: see where the failing address for a SIGSEGV would reside.

For the x86, the pc is in /usr/include/sys/ucontext.h:

/* Userlevel context. */
typedef struct ucontext
{
unsigned long int uc_flags;
struct ucontext *uc_link;
stack_t uc_stack;
mcontext_t uc_mcontext;
__sigset_t uc_sigmask;
struct _fpstate __fpregs_mem;
} ucontext_t;

and the program counter is context->uc_mcontext.gregs[EIP]

I don't think that CR2 is in the user context, but all we need to do
is examine the failing insn to see if it was a stack access and extend
the stack.

Andrew.

Bernd Paysan

unread,
Sep 20, 1999, 3:00:00 AM9/20/99
to
Anton Ertl wrote:
> Well, this stuff is available through sigcontext in C, but it depends
> on the architecture, possibly on the OS (and maybe even on the kernel
> version). So we would have to do this repeatedly and differently for
> a lot of platforms, and so would other programs. Better fix this in
> one place: in the kernel.

Indeed. It's not that awful in Linux (the kernel versions don't matter
;-). I use sigcontext in bigFORTH to unwind the debug exception (and to
provide more detailed informations on other signals). The only thing I
have to do once in a while is to slap on the fingers of the kernel
developers *not* to disallow a process to debug itself. They did that
once.

The faulting address (on Intel) for a SIGSEGV is in the cr2 register
part of the sigcontext frame.

--
Bernd Paysan
"If you want it done right, you have to do it yourself"
http://www.jwdt.com/~paysan/

stephe...@my-deja.com

unread,
Sep 21, 1999, 3:00:00 AM9/21/99
to
In article <7s5u8h$t19$1...@news.tuwien.ac.at>,

an...@mips.complang.tuwien.ac.at (Anton Ertl) wrote:
> Moreover, looking at the Linux-Intel sigcontext, I actually don't
> see where the failing address for a SIGSEGV would reside.

Andrew has already replied and seems to have a more up to date system
than me so his suggestion is probably the best if you are running a
recent kernel. In the one I'm running, the following is pushed on the
stack before the signal handler is called :-

struct sigcontext {
unsigned short gs, __gsh;
unsigned short fs, __fsh;
unsigned short es, __esh;
unsigned short ds, __dsh;
unsigned long edi;
unsigned long esi;
unsigned long ebp;
unsigned long esp;
unsigned long ebx;
unsigned long edx;
unsigned long ecx;
unsigned long eax;
unsigned long trapno;
unsigned long err;
unsigned long eip;
unsigned short cs, __csh;
unsigned long eflags;
unsigned long esp_at_signal;
unsigned short ss, __ssh;
struct _fpstate * fpstate;
unsigned long oldmask;
unsigned long cr2;
};

Assuming that the cr2 value is correct then it is the address you
want. If it is not set correctly then as Andrew notes there is
always the approach of decoding the instruction at EIP. Admittedly
a bit tedious on an x86 but certainly doable.

Andrew Haley

unread,
Sep 21, 1999, 3:00:00 AM9/21/99
to
stephe...@my-deja.com wrote:
: In article <7s5u8h$t19$1...@news.tuwien.ac.at>,

: an...@mips.complang.tuwien.ac.at (Anton Ertl) wrote:
: > Moreover, looking at the Linux-Intel sigcontext, I actually don't
: > see where the failing address for a SIGSEGV would reside.

: Andrew has already replied and seems to have a more up to date system
: than me so his suggestion is probably the best if you are running a
: recent kernel. In the one I'm running, the following is pushed on the
: stack before the signal handler is called :-

This frame is still supported on the new kernels if you don't ask for
sigcontext, so it's probably the best thing to use for portable code.

: Assuming that the cr2 value is correct then it is the address you
: want.

Yes, indeed! I hadn't noticed that cr2 was in that struct.
Excellent.

Andrew.


jf...@ricochet.net

unread,
Sep 22, 1999, 3:00:00 AM9/22/99
to
I discussed this topic with Chuck Moore a couple of years ago.
He said that this was not just problem for Forth but for
other languages as well and one that he had struggled
with for twenty years before finding the solution ten years
ago.

His take was that buggy code would expose this problem with
both hardware and software and that everyone had been struggling
for effective solutions since the beginning. He said that
software solutions had become quite ugly.

In article <7rkm12$pv0$1...@b5nntp2.channeli.net>,


"Choi Dong-Zin" <dzc...@lgic.co.kr> wrote:
>
> I came across an idea about how to check stack-underflow/overflow in

> FORTH. \ ... \

> The traditional skeme for stack checking is: \ ... \

So hardware designers stepped in and added extra hardware to
help deal with the problem. It made the hardware more complex
and more expensive and sometimes slower and in some cases
added to the complexity of the software solutions. It also
made the attempted patches to fix the problem non-portable.

> However, the microprocessors have changed. \ ... \

From a hardware designer's point of view these things looked
just as ugly. Now instead of just paying a huge software
cost you could not pay for both hardware and software to
attack the problem. It is one of the many sources of
sprialing complexity. It resulted in much bigger code
solutions that allowed more stack overflow/underflow
bugs into the code.

( my own take is that DEPTH is a sign of bugs in the
code. The designer or the software should know the
depth of the stacks. If the program has lost track
of the depth it is already out of control. ;-)

After twenty years of looking for a solution he said he
was very pleased to find one. He decided to make the
stacks circular. Stacks cannot overflow or underflow,
the wrap. He said, "Problem solved once and for all."

I think he would also say that the problem really should
be addressed at design and compile time rather than writing
buggy code and then adding runtime overhead in hardware
and software to catch the bugs that were designed into the
program. Chuck has said that Forth was designed to avoid
the unsolvable problems in comp sci and that there would
always be people trying (unsucessfully) to solve these
problems, even in Forth. This is one of the many examples.

He also feels that a depth of a half dozen cells is quite
sufficient for well written code. He felt the 18 and 17
cell deep stacks on F21 were larger than they need to be
and referes to that size as virtually infinite.

In other languages where they freely mix the ideas of stacks,
arrays, and structures then large arrays in memory are called
stacks. I prefer the comp sci def for a stack, that it is
accessed from the top. It is an explanation for why PICK and
ROLL are not really Forth since they are not stack operations.
If you graft concepts from other languages like stack frames
and locals into Forth then you get locked into the same
problems as other languages.

In the last fifteen years Chuck has worked to clean up his
Forths, remove the words that were sources of bugs and
complexity and make it smaller and faster and in short a
more productive tool. In that same period most of the Forth
community has worked to standardize on all the practices
not only in Forth but in other languages from fifteen years
ago.

--
Jeff Fox UltraTechnology
www.UltraTechnology.com

Andrew Haley

unread,
Sep 22, 1999, 3:00:00 AM9/22/99
to
jf...@ricochet.net wrote:
: He also feels that a depth of a half dozen cells is quite

: sufficient for well written code. He felt the 18 and 17
: cell deep stacks on F21 were larger than they need to be
: and referes to that size as virtually infinite.

This is an excellent point. I've worked on large Forth systems and
I've always been totally amazed at how little stack was needed!

Andrew.


Gary Chanson

unread,
Sep 22, 1999, 3:00:00 AM9/22/99
to

<jf...@ricochet.net> wrote in message news:7sb0fq$ggt$1...@nnrp1.deja.com...

>
> After twenty years of looking for a solution he said he
> was very pleased to find one. He decided to make the
> stacks circular. Stacks cannot overflow or underflow,
> the wrap. He said, "Problem solved once and for all."

Wishful thinking! When the stack pointer wraps around, you start
corrupting the data on the stack. You probably won't notice this until you
un-nest and try to use the corrupted data, which means that the problem has
gotten harder to identify. WONDERFUL SOLUTION!

> I think he would also say that the problem really should
> be addressed at design and compile time rather than writing
> buggy code and then adding runtime overhead in hardware
> and software to catch the bugs that were designed into the
> program. Chuck has said that Forth was designed to avoid
> the unsolvable problems in comp sci and that there would
> always be people trying (unsucessfully) to solve these
> problems, even in Forth. This is one of the many examples.

More wishful thinking...

> He also feels that a depth of a half dozen cells is quite
> sufficient for well written code. He felt the 18 and 17
> cell deep stacks on F21 were larger than they need to be
> and referes to that size as virtually infinite.

Fine for SOME programs...

--

-GJC
-gcha...@shore.net

Kevin Knight

unread,
Sep 22, 1999, 3:00:00 AM9/22/99
to
>After twenty years of looking for a solution he said he
>was very pleased to find one. He decided to make the
>stacks circular. Stacks cannot overflow or underflow,
>the wrap. He said, "Problem solved once and for all."


I do not see how this solves the problem. There might be no error as the
stack grows and wraps round, but when unrolling the incorrect data will be
recovered and used. This will cause the program to fail. Is this not the
same as overflow/underflow errors?

Kevin Knight
An interested Forth'er.

Jonah Thomas

unread,
Sep 22, 1999, 3:00:00 AM9/22/99
to
"Gary Chanson" <gcha...@no.spam.shore.net> wrote:
><jf...@ricochet.net> wrote in message news:7sb0fq$ggt$1...@nnrp1.deja.com...

>> After twenty years of looking for a solution he said he


>> was very pleased to find one. He decided to make the
>> stacks circular. Stacks cannot overflow or underflow,
>> the wrap. He said, "Problem solved once and for all."

> Wishful thinking! When the stack pointer wraps around, you start


>corrupting the data on the stack. You probably won't notice this until you
>un-nest and try to use the corrupted data, which means that the problem has
>gotten harder to identify. WONDERFUL SOLUTION!

Yes, but it's more likely than before that nothing will be corrupted except
your data. Not like a stack overflow that corrupts the return stack, or
important areas of memory.

Of course if you're keeping xt's on the stack then when you execute
garbage later you're likely to crash. And if you're keeping addresses
on the stack where things will later be stored then there's no telling
what you'll corrupt when you use them. But a third of the problem is
solved for essentially no overhead, or maybe negative overhead.

Solving a third of the problem is a good start.


Marcel Hendrix

unread,
Sep 22, 1999, 3:00:00 AM9/22/99
to

Jonah wrote:

> Solving a third of the problem is a good start.

Not if it took you twenty years to find the solution :-)
I assume that Chuck already takes for granted there are no bugs in the code
(how many bugs can there be in 1K anyway?). A wrap-around stack indeed has
some nice properties, e.g. overflow when buffering a serial line, resetting
stacks in QUIT etc.

-marcel

jf...@ricochet.net

unread,
Sep 23, 1999, 3:00:00 AM9/23/99
to
In article <0m8G3.63$jj....@news.shore.net>,
"Gary Chanson" <gcha...@no.spam.shore.net> wrote:

> > stacks circular. Stacks cannot overflow or underflow,

> > they wrap. He said, "Problem solved once and for all."
>
> Wishful thinking!

I have tested it and been working with it for ten years.
I am speaking from experience not wishful thinking.

> When the stack pointer wraps around, you start
> corrupting the data on the stack. You probably won't notice
> this until you
> un-nest and try to use the corrupted data, which means
> that the problem has gotten harder to identify.
> WONDERFUL SOLUTION!

No it means that you overflow and underflow the stacks
any time you want to. The top or bottom of the stack
is anywhere you want it to be. It doesn't mean that it is
impossible to have bugs in a program.

I think you missed the idea. If stacks are unlimited
arrays in memory when they overflow or underflow due to
bugs in the programs they can corrupt everything and
on some systems even corrupt code. The data is still
there in memory but the system has crashed. The
solutions to keep the system from crashing add so
much complexity that they introduce more bugs.

This idea does not remove all bugs, however as Chuck
has said as a result of using it a "quite different
style of programming falls out." It reduces the
number of bugs that enter and it means that stack
overflow and underflow has built in memory protection.

It does not automatically make poor programmers into good
programmers and mean that they cannot write buggy
code. It is way to reduce the bugs going in and
make then less dangerous. It is also a feature
that can be exploited by clever programmers.

> > I think he would also say that the problem really should
> > be addressed at design and compile time rather than writing
> > buggy code and then adding runtime overhead in hardware
> > and software to catch the bugs that were designed into the
> > program. Chuck has said that Forth was designed to avoid
> > the unsolvable problems in comp sci and that there would
> > always be people trying (unsucessfully) to solve these
> > problems, even in Forth. This is one of the many examples.
>
> More wishful thinking...

Basic Forth thinking. People who don't believe that Forth
has solutions and want to bend it to look like the languages
that they learned in comp sci just introduce the problems
they had in other languages to Forth. I could give a list
of examples, but Chuck has done it many times.

Maybe you could call it wishful thinking fifteen years ago
before it was tried and was only an idea. After the
experiments were done and many years of results were
examined it is easy to see that it worked out well. I
report the results of the experiments to people, both
those that worked and those that failed. I know that
the results are not what most people would expect and
that many peole would rather dismiss it as just "wishful
thinking." ;-)

> > He also feels that a depth of a half dozen cells is quite
> > sufficient for well written code. He felt the 18 and 17
> > cell deep stacks on F21 were larger than they need to be
> > and referes to that size as virtually infinite.
>
> Fine for SOME programs...

Yes, well written programs. Not fine for all programs. There
is a rule that (most) humans can only keep track of about a
half dozen things at one time. A good rule of thumb is that
if you can't keep a clear picture in your mind of what is
on the stack at any time you are headed for trouble. Chuck
has even said that he has come to the conclusion that even
stack diagrams are a sign of your stacks getting too cluttered.

Gary Chanson

unread,
Sep 23, 1999, 3:00:00 AM9/23/99
to

<jf...@ricochet.net> wrote in message news:7sdhgk$ann$1...@nnrp1.deja.com...
> In article <0m8G3.63$jj....@news.shore.net>,

>
> Yes, well written programs. Not fine for all programs. There
> is a rule that (most) humans can only keep track of about a
> half dozen things at one time. A good rule of thumb is that
> if you can't keep a clear picture in your mind of what is
> on the stack at any time you are headed for trouble. Chuck
> has even said that he has come to the conclusion that even
> stack diagrams are a sign of your stacks getting too cluttered.

Apparently you've never heard of "recursion".

--

-GJC
-gcha...@shore.net

Bernd Paysan

unread,
Sep 23, 1999, 3:00:00 AM9/23/99
to
Andrew Haley wrote:
> This is an excellent point. I've worked on large Forth systems and
> I've always been totally amazed at how little stack was needed!

I can second that. The most astonishing thing I experienced when I
started to use C libraries using the Forth stack of a task (it was quite
luxurious for Forth). Instant stack overflow. I now plan to use the
system's stack (separated and huge) instead and change my C interface to
switch stacks and copy the arguments before.

Mark A. Flacy

unread,
Sep 23, 1999, 3:00:00 AM9/23/99
to
>>>>> "Gary" == Gary Chanson <gcha...@no.spam.shore.net> writes:
Gary>
Gary> Apparently you've never heard of "recursion".

Oh, I think that he HAS heard of it. Not all languages support
recursion. No problem absolutely has to have it as a solution.

jf...@ricochet.net

unread,
Sep 24, 1999, 3:00:00 AM9/24/99
to
In article <REuG3.174$jj.3...@news.shore.net>,
"Gary Chanson" <gcha...@no.spam.shore.net> wrote:

> Apparently you've never heard of "recursion".

I guess you must think I am an idiot. You must also
think that Chuck Moore has also never heard of recursion.
Apparently you haven't followed what Chuck has done with
Forth in the last fifteen years. Recursion was the only
looping mechansim in Color Forth for a long time.
Your argument seems to based on a total misunderstanding
of what I have been talking about.

--
Jeff Fox UltraTechnology
www.UltraTechnology.com


Sent via Deja.com http://www.deja.com/

Before you buy.

Jerry Avins

unread,
Sep 25, 1999, 3:00:00 AM9/25/99
to

My experience is limited, but I never saw a problem solved with
recursion that couldn't be solved more efficiently (if less elegantly)
without it. One can calculate the nth Fibbonacci number more quickly
with direct calculation than is possible with recursion, especially for
n greater than about 40. Calculating Fibbonacci numbers is often cited
as a problem that can be solved only by recursion, or by an equivalent
regression formula. It is possible to calculate the 200th without
knowing the 199th.

Jerry
--
Engineering is the art of making what you want from things you can get.
-----------------------------------------------------------------------

John Passaniti

unread,
Sep 25, 1999, 3:00:00 AM9/25/99
to

Marcel Hendrix <m...@iaehv.iae.nl> wrote in message
news:7sb7g9$ic8$1...@news.IAEhv.nl...

> I assume that Chuck already takes for granted
> there are no bugs in the code (how many bugs
> can there be in 1K anyway?).

It's easy to calculate the number of possible bugs in a span of code: You
simply multiply the program size by the number of instructions per word.

John Passaniti

unread,
Sep 25, 1999, 3:00:00 AM9/25/99
to

Jerry Avins <j...@ieee.org> wrote in message news:37ED89...@ieee.org...

> My experience is limited, but I never saw a
> problem solved with recursion that couldn't
> be solved more efficiently (if less elegantly)
> without it.

Depending on how clever the language (or optimizer) is, recursion can be
identified and optimized-- sometimes optimized right out. Tail recursion
can always be replaced by iteration, and reportedly there are various
langauges (and optimizers) that make this optimization. I've used a C
compiler for the 8051 (a microcontroller with limited hardware stack) that
identifies recursive functions and generates different code for them--
essentially it uses a software stack only for those functions identified as
self or mutually recursive. This gave a fast hardware stack for
non-recursive functions, and a slower (but necessary) software stack for
recusive functions.

Regardless, I have to make my standard comment about the word efficiency.
It's my pet peeve. To most people (especially in the Forth community),
efficiency is measured in processor cycles and/or memory usage. When
that's appropriate, that's the proper way to measure efficiency. But
efficiency can also be measured in programmer time and/or how long it takes
to express code to others.

I make this point because I've seen both sides. I've seen programmers who
seem to go out of their way to use recursion-- even when it doesn't make
sense. Here's an example of that mentality that I ran across from a C
programmer who those the following was "elegant":

int strlen(const char* s) {
return (*s) ? 1 + strlen(s+1) : 0;
}

Duh. But it can also work the other way too. There are some algorithms
that should be expressed recursively (assuming the language supports it)
because the recursive form of the algorithm is more comprehensible and more
efficient in terms of the programmer's time. While it is always possible
to recast these algorithms in other forms, doing so can obscure the
algorithm if taken too extremes.

Like any tool, recursion can be used correctly or incorrectly. The key is
know when it is appropriate.


William Tanksley

unread,
Sep 26, 1999, 3:00:00 AM9/26/99
to

You're an optimist. That's a huge undercount; you didn't count the
possibility of the program being too short or too long. Not to mention
the possibility of right instructions, wrong order.

And so on.

:-)

--
-William "Billy" Tanksley

Marcel Hendrix

unread,
Sep 26, 1999, 3:00:00 AM9/26/99
to

Jerry writes:

> My experience is limited, but I never saw a problem solved with recursion
> that couldn't be solved more efficiently (if less elegantly) without it.

OK, write a non-recursive version of Anton Ertl's Gray parser generator
then. This program is known to use over 300 stack positions for typical
problems, which makes it a nuisance in Standard Forth.

There is a difference between "theoretically possible" and "practical to do"
that should be obvious to any engineer.

-marcel

Eugene Leitl

unread,
Sep 27, 1999, 3:00:00 AM9/27/99
to comp.la...@list.deja.com

Has anybody tried using circular buffers hardware-supported by some
DSPs for implementing stacks?

Is it worth the effort?

jf...@ricochet.net writes:
> I think you missed the idea. If stacks are unlimited
> arrays in memory when they overflow or underflow due to
> bugs in the programs they can corrupt everything and
> on some systems even corrupt code. The data is still
> there in memory but the system has crashed. The
> solutions to keep the system from crashing add so
> much complexity that they introduce more bugs.

Sent via Deja.com http://www.deja.com/

0 new messages