This isn't a flame war, but it is an interesting discussion! On 06/10/2011 14:41, JMGross wrote: > > It depends on how you define a stack. Bascially, a stack is a LIFO buffer. > Being able to access elements on the stack that are not on top of the stack > is not a requirement for being a stack.
That's true. The requirements for a structure to be a "stack" are that you can add something to the top of it, and you can take something off the top (LIFO). In practice, most stacks have other operations, such as detecting stack overflow and underflow, or accessing data further down the stack (obviously that's /very/ useful for a stack holding local data). > (see the forth mathematical stack) > Also, the rotating SPARC register set also rotates the working registers of > the > processor, which definitely isn't the job of a stack at all. (You might know the following details, others reading might not.) The SPARC has 32 registers. 8 of them, %g0..%g7, are "normal" registers in that they hold the same data independent of function calls. Then you have "in" %i0 .. %i7, "local" %l0..%l7 and "out" %o0..%o7. These form a 24-register window onto the large register stack. When you make a function call, this window moves 16 registers in the stack so that the "in" registers point to the same register stack entries that were "out" before, and the "local" and "out" registers point to new registers. Grouping everything in blocks of 8 registers, we have: register stack: 0123456789 current window: ilo next window: ..ilo // after a function call next window: ....ilo // after a second function call (I may have got the "input" and "output" swapped - I can't remember whether SPARC talks about "input" going to the called function, or "input" coming from the callee function.) The implementation is in terms of a sliding register window moving over a large fixed register bank. But it is logically equivalent to a stack. To do a function call, the "i" registers and "l" registers are stacked, and the "o" registers are moved into the "i" registers. You have a LIFO structure - it's a stack. > >>> Writing a C compiler for this would be a PIA. I had to program it in >>> assembly (write a monitor that handled an overflow/underflow of the >>> "register wheel" when the code was nested too deep) >> That's always the problem with hardware stacks - you have a limit to >> their size, and if it's not big enough things get very inconvenient. > > So the MSPs stack is also a hardware stack. Once you need to grow it beyond > the (still very limited on some MSPs) size of RAM you'll get into trouble too. > So where ends a hardware stack and where begins a software stack and > what's is the effective difference. > I'd call it a "software stack" if it is in main memory (as is the case for the msp430), and "hardware stack" if it is in a dedicated hardware structure. But the difference can be a bit fuzzy. > But we both agree that there is no stack at all needed for local variables > (while it usually is used for them), and that not every stack is the same. Yes. > I don't want to start a flame war about implementations. I just try to fight > the impression that the commonly used implementation is the only > existing or possible one. > This often leads people into trouble, sometimes without even noticing it. > Fair enough. And there are no flames (as yet!) - we're having a discussion with some disagreement, that's all. >>> however, the concept of a stack is only one concept (even if a >>> successful and commonly used one) and one commonly used to store >>> local variables. But it is not the only one and not the only way to >>> deal with local variables. And if you don't have a stack, there is no >>> need to simulate one, just to do C. > >> Actually, you /do/ need to simulate one to do C - there is no other way >> to implement recursion (while you could, theoretically, use other >> structures such as lists or heaps, you would still be simulating a >> stack). Variable argument functions also require a stack to implement >> fully. And while these are features that are seldom used in embedded >> systems, they are still required for a C implementation. > > "No" to all of them. Sorry. This I have to challenge - either you are wrong, or I'm in danger of learning something... > Of course, if you define a stack as 'a stack is where local variables go', > then you're right by definition. But it is NOT the only way. And other > implementations, as scarce as they might be, do not automatically > implement a stack. > Take a look at vprintf(). It implements variable parameters without stack. > What you can do explicitely in your code to use vprintf could be done by > the compiler implicitely for printf. vprintf is not a C variable argument function. It is a function with two parameters - one points to a format string, the other is a structure holding information about a list of arguments. > In fact, the typical implementation of printf just passes the current stack > pointer to vprintf, where the parameters are handled completely > independent of the storage location. And where are the variable arguments stored? On the stack. If you /don't/ have a stack, where can you store them? In some cases, the compiler can determine in advance how many arguments there are and how much space is needed - it can then store them in statically allocated memory, in the same way that the PIC compiler does (and compilers for 8051 and other simple-minded processors). But if you can't determine the number of arguments at compile time, you have to put them in some sort of dynamically allocated memory. Your two choices are a stack structure, or a dynamic memory structure of some sort - the heap (I don't mean that in the rigid sense of a heap structure - it can be any sort of memory pool). If you are putting data like that in space on the heap, you are putting data in, then using it and clearing it out, in a LIFO fashion. You are using the space as a stack. > Even recursion is doable without a stack. Yet I agree (and already did) > that a stack is the easiest solution, so it is by far the most successful one. > /Sometimes/ recursion can be done without a stack - you (and therefore, at least theoretically, the compiler) can turn most recursive functions into loops. But in many cases doing so requires data to be saved at each step. And unless you know in advance the maximum depth of that data, you are going to end up with a logical stack. Re-entrant functions also typically need a logical stack (again, if the compiler can establish a maximum re-entrancy depth, it can be avoided). As you say, there is no doubt that a stack is the easiest way to hold data for such code. But I really am curious to know of any other solution that does not boil down to a logical stack. mvh., David > > > ----- Ursprüngliche Nachricht ----- > Von: Eric Decker > An: David Brown > Gesendet am: 06 Okt 2011 11:17:45 > >>>> Just like the idea that you need to have sex to get pregnant. Correct >>>> for the very most occurrences but not for all. And not knowing that >>>> there are exceptions to the rule makes you more prone to be a victim >>>> of these exceptions. >>> Perhaps I don't get out of the office enough, but I can't think how one >>> could get accidentally pregnant without sex! >> I beleive this a nod to the religious concept of immaculent conception. > > Not only. It is just the most prominent case. > After all, it depends on how wide you span the definition of 'having sex'. > If you extend it to 'having contact to a male, directly or indirectly', then > every possible situation is covered. > But the usual difinition is much narrower. For some very much narrower. > And if if you exclude cases of medical aid, there are enough other > possibilities, extending to using the same toilet (unlikely but not > completely impossible). > But since this is a public mailing list, I don't want to get into details for > the other (more likely) ways. :) > >>>> As for the PIC: >>> I've only programmed them in assembly. It was fun, in a perverse sort >>> of way. >> Definitely perverse. I used to write micro-code (the stuff below >> assembly), but then again I used to design 180 bit wide horizontal custom >> processors too. > > During my time at the university, I once built a 4 bit CPU, including > microcode, from plain TTL. Well, you don't get far with only 16 > instructions. No DOOM implementation or such. > It was just a side project to get a checkmark. > However, the whole bunch of TTL and wire-wrap worked well > with 400kHz clock speed and executed some calculation programs > (that made the LEDs attached to the accumulator register blink > a light show). > It's been looong ago. :) > >>> And it is no processor at all. [PIC] >> Depends on the definition of processor. > > Agreed. If you call everything a 'processor' that can process a list > of instructions, then it is. > >> And now back to our regularily scheduled program... :-) > > I second you with this. > > ------------------------------------------------------------------------------ > All the data continuously generated in your IT infrastructure contains a > definitive record of customers, application performance, security > threats, fraudulent activity and more. Splunk takes this data and makes > sense of it. Business sense. IT sense. Common sense. > http://p.sf.net/sfu/splunk-d2dcopy1 ------------------------------------------------------------------------------ All the data continuously generated in your IT infrastructure contains a definitive record of customers, application performance, security threats, fraudulent activity and more. Splunk takes this data and makes sense of it. Business sense. IT sense. Common sense. http://p.sf.net/sfu/splunk-d2dcopy1 _______________________________________________ Mspgcc-users mailing list Mspgcc-users@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/mspgcc-users
