Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C Programming > The machine stack and the C language

Reply
Thread Tools

The machine stack and the C language

 
 
Malcolm McLean
Guest
Posts: n/a
 
      01-12-2008

"Tomás Ó hÉilidhe" <(E-Mail Removed)> wrote in message
> I never write recursive functions unless I really really really really
> have to. In 95% of cases, you can just use a loop.
>

I use recursion whenever the data structure is a tree, or, as in my Basic
interpreter, a disguised tree.

--
Free games and programming goodies.
http://www.personal.leeds.ac.uk/~bgy1mm

 
Reply With Quote
 
 
 
 
Flash Gordon
Guest
Posts: n/a
 
      01-12-2008
jacob navia wrote, On 12/01/08 20:13:

<snip>

> They use the ignorance of many people here about certain exotic
> environments, like, for instance, the IBM Mainframes. Specifically,
> Mr "Flash Gordon" said:
>
> <quote>
> it won't work on big iron (or even relatively small servers like those
> we run our accounts system on in my company)
> <end quote>.


The above was posted immediately under your sample code and was in
reference to it. I also pointed out that the reason it would fail on the
server my company uses is that the stack grew in the opposite direction
to that assumed by your code.
--
Flash Gordon
 
Reply With Quote
 
 
 
 
J. J. Farrell
Guest
Posts: n/a
 
      01-12-2008
Tomás Ó hÉilidhe wrote:
> jacob navia:
>
>> As has been pointed out several times, the support of recursive
>> functions in C implies a logical stack. One of the "implementations"
>> this people presented, didn't implement recursion and can't be counted
>> as a complete C implementation.

>
> You make a brilliant point Jacob. Taking the following program:


<recursive program snipped>

> In order for this program to work, I can't fathom any other method than
> using a stack. Of course, the C standard leaves the door wide open for
> the implementation to achieve the correct behaviour any way it wants,
> but the point to be made is that no person has yet to implement a method
> other than a stack (and how many decades has it been?).


SPARC has been around for over two decades. A recursive program needs
something which operates conceptually as a stack. It certainly doesn't
need a single contiguous piece of memory with a stack pointer which
walks up and down it. Whether or not C needs a stack depends solely on
how you choose to define "stack".

> ...

 
Reply With Quote
 
Tim Smith
Guest
Posts: n/a
 
      01-13-2008
In article <Xns9A23DF709EC7Atoelavabitcom@194.125.133.14>,
"Tomás Ó hÉilidhe" <(E-Mail Removed)> wrote:
> You make a brilliant point Jacob. Taking the following program:
>
> (Kindly excuse the typos and stupid erros)
>
> #include <stdio.h>
>
> extern unsigned GetUserInput(void); /* Defined elsewhere */
>
> void Recurse(unsigned const amount_times)
> {
> if (amount_times <= 1) return;
>
> printf("%u\n",amount_times);
>
> Recurse(i - 1);
> }
>
> int main(void)
> {
> Recurse( GetUserInput() );
>
> return 0;
> }
>
>
> In order for this program to work, I can't fathom any other method than
> using a stack. Of course, the C standard leaves the door wide open for


You could easily design a runtime that doesn't need a stack. The
function call system would work as follows:

1. When a function is called, it is passed a pointer to a block of
memory. This block of memory contains the return address for the call,
and the arguments to the function, and space for the return value. I'll
call this the argument block.

2. The first thing the function does is allocate a block of memory.
This block of memory is large enough to hold all the local variables of
the function, plus enough extra space to hold the largest argument block
the function needs for any calls it makes. I'll call this the
function's local block.

3. When a function returns, it frees its local block.

4. When a function needs to call another function, it fills in the
argument block as needed for the function it wants to call, and calls it.

5. A specific register is assigned for use in passing the pointer to the
argument block to the called function. The machine's equivalent of goto
is used to actually transfer control to the other function. Similarly,
goto is used to return.

--
--Tim Smith
 
Reply With Quote
 
CBFalconer
Guest
Posts: n/a
 
      01-13-2008
jacob navia wrote:
> Eric Sosman wrote:
>

.... snip ...
>
>> Ah, but here's where Jacob and I part ways again. C has *no*
>> mechanism for detecting stack overflow (sorry, "exhaustion of the
>> resources that keep track of auto variables and/or whatever's
>> needed to ensure that a function can return to its caller").

>
> Which C?


There is only one C - that described in the ISO C standard, or its
antecedants. Once the language is extended, it is no longer
portable C.

>
> POSIX has. Why is POSIX not considered as C?


POSIX is not a language specification. It is an OS specification.

--
[mail]: Chuck F (cbfalconer at maineline dot net)
[page]: <http://cbfalconer.home.att.net>
Try the download section.



--
Posted via a free Usenet account from http://www.teranews.com

 
Reply With Quote
 
CBFalconer
Guest
Posts: n/a
 
      01-13-2008
Tomás Ó hÉilidhe wrote:
>

.... snip ...
>
> #include <stdio.h>
> extern unsigned GetUserInput(void); /* Defined elsewhere */
>
> void Recurse(unsigned const amount_times) {
> if (amount_times <= 1) return;
> printf("%u\n",amount_times);
> Recurse(i - 1);
> }
>
> int main(void) {
> Recurse( GetUserInput() );
> return 0;
> }
>
> In order for this program to work, I can't fathom any other
> method than using a stack. Of course, the C standard leaves the
> door wide open for the implementation to achieve the correct
> behaviour any way it wants, but the point to be made is that no
> person has yet to implement a method other than a stack (and
> how many decades has it been?).


It doesn't need a 'stack'. It needs a means of getting and
releasing memory. As an example, malloc and free will suffice.

--
[mail]: Chuck F (cbfalconer at maineline dot net)
[page]: <http://cbfalconer.home.att.net>
Try the download section.


--
Posted via a free Usenet account from http://www.teranews.com

 
Reply With Quote
 
Richard Heathfield
Guest
Posts: n/a
 
      01-13-2008
CBFalconer said:

> jacob navia wrote:
>> Eric Sosman wrote:
>>

> ... snip ...
>>
>>> Ah, but here's where Jacob and I part ways again. C has *no*
>>> mechanism for detecting stack overflow (sorry, "exhaustion of the
>>> resources that keep track of auto variables and/or whatever's
>>> needed to ensure that a function can return to its caller").

>>
>> Which C?

>
> There is only one C - that described in the ISO C standard, or its
> antecedants.


That's already at least three Cs.

--
Richard Heathfield <http://www.cpax.org.uk>
Email: -http://www. +rjh@
Google users: <http://www.cpax.org.uk/prg/writings/googly.php>
"Usenet is a strange place" - dmr 29 July 1999
 
Reply With Quote
 
Pierre Asselin
Guest
Posts: n/a
 
      01-13-2008
CBFalconer <(E-Mail Removed)> wrote:

> [ Tomas' recursive example snipped ]
> It doesn't need a 'stack'. It needs a means of getting and
> releasing memory. As an example, malloc and free will suffice.


There would be a slight chicken-and-egg issue when calling malloc()
to implement the C run-time call mechanism... I'm sure it's doable.
(It helps that malloc isn't recursive.)

--
pa at panix dot com
 
Reply With Quote
 
Keith Thompson
Guest
Posts: n/a
 
      01-13-2008
jacob navia <(E-Mail Removed)> writes:
> Eric Sosman wrote:

[...]
>> Ah, but here's where Jacob and I part ways again. C has *no*
>> mechanism for detecting stack overflow (sorry, "exhaustion of the
>> resources that keep track of auto variables and/or whatever's
>> needed to ensure that a function can return to its caller").

>
> Which C?
>
> POSIX has. Why is POSIX not considered as C?

[...]

Should comp.unix.programmer be eliminated and merged into comp.lang.*,
since all Unix programming is done in some language?

C is defined by the C standard. That's why it's called the C
standard.

--
Keith Thompson (The_Other_Keith) <(E-Mail Removed)>
Nokia
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"
 
Reply With Quote
 
Keith Thompson
Guest
Posts: n/a
 
      01-13-2008
"Tomás Ó hÉilidhe" <(E-Mail Removed)> writes:
> =?UTF-8?q?Harald_van_D=C4=B3k?=:
>
>> It's called "tail call" optimisation, if you want to look it up, and in
>> this case, it's very easy for the compiler to do.
>>
>> In the general case, compilers do need something that can function as a
>> stack, but in your example, there is no need.

>
> I never write recursive functions unless I really really really really
> have to. In 95% of cases, you can just use a loop.
>
> For the cases though in which a loop won't do the job, I think you need
> a stack.

[...]

In other words, for recursive calls for which a tail-recursion
optimization can't be used (say, Ackermann's function), you need a
stack to implement the recursion. And since a stack is required in
this case, it's usually convenient for the implementation to use a
stack for (almost) all function calls (though optimizations are
possible for leaf functions, i.e., functions that don't call anything
else).

Yes, of course you need a stack, in the sense of a LIFO data
structure. You *don't* need what we've been calling a "hardware
stack", i.e., a contiguous region of memory that grows in a specific
direction and is typically managed via a dedicated hardware register
called a "stack pointer". The stack (LIFO data structure) can be
implemented in a number of ways; a "hardware stack" is merely one such
way. Another way is a linked list of heap-allocated activation
records, where different activation records are not necessarily
ordered in any particular way in memory.

The distinction between a "stack" (a generalized LIFO data structure)
and a "hardware stack" (a contiguous memory space) is exactly what
this whole argument is about. Ignoring that distinction is not
helpful.

--
Keith Thompson (The_Other_Keith) <(E-Mail Removed)>
Nokia
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Why does std::stack::pop() not throw an exception if the stack is empty? Debajit Adhikary C++ 36 02-10-2011 08:54 PM
Niue - a tiny, embeddable stack language and language toolkit forJava Vijay Mathew Java 0 03-23-2010 11:24 AM
C/C++ compilers have one stack for local variables and return addresses and then another stack for array allocations on the stack. Casey Hawthorne C Programming 3 11-01-2009 08:23 PM
stack frame size on linux/solaris of a running application stack Surinder Singh C Programming 1 12-20-2007 01:16 PM



Advertisments