| "Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com>: Apr 18 01:54AM +0200 On 18.04.2016 00:28, Jens Thoms Toerring wrote: >> old word that means a skirt; >> • in the context of restaurant kitchens, … > What's bitten you? Multiple people independently silly-asserting that C++ doesn't require a stack, on the same day. I think Fortran 77 didn't require a stack. Also, as I recall Knuth's MIX assembly language didn't require a stack. I liked the way he passed return addresses by modifying the code of the called function. Also it had the nice property that you couldn't really tell whether the hardware used binary or decimal. Very good for an assembly language targeting 1950's computers. And Knuth did much of this while he was a postdoc, I think it was, at Norsk Regnesentral, which is also the environment that produced the Simula language and object orientation, on which the C++ object orientation is based (and also OO in other language, mostly via Smalltalk, I think: Alan Key, of Smalltalk fame, got a tape with a compiler that he thought was Algol, and hey, it was Simula! – and the rest, as they say, is history). > some knowledge about common hardware know about (and some assume > to be the only way it can be done), i.e. the one that is made up > of (at least) a piece of memory and a stack pointer. Yes, I thought as much, hence my speculation in my reply, that that was what you meant. I think we can use the descriptive term "contiguous stack area" for this. And then we can say that neither C nor C++ require a contiguous stack area. Cheers!, - Alf |
| Jerry Stuckle <jstucklex@attglobal.net>: Apr 17 09:59PM -0400 On 4/17/2016 6:00 PM, Robert Wessel wrote: > family machines uses a stack structure very similar to that used by > typical x86 implementations. As do many of the implementations on > RISCs that also lack hardware stacks. I didn't say the compiler had to generate storage requests to the OS. It can easily do the same by subdividing an existing storage. It could easily use linked lists for this. When I worked for IBM, we did a lot of assembler this way, including recursive routines. And we almost never had to request more storage from the OS. And no, the R13 linked list format is *not* just used for functions that call or are called from the outside. It is used quite extensively with internal calls also - including setting up the above pseudo-stack. But either way, there is no hardware stack. I will agree it is an emulation. But C does not require a stack. Only a way to create a unique storage area when a function is called. -- ================== Remove the "x" from my email address Jerry Stuckle jstucklex@attglobal.net ================== |
| "Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com>: Apr 18 04:12AM +0200 On 18.04.2016 03:59, Jerry Stuckle wrote: > But C does not require a stack. Only a way to create a > unique storage area when a function is called. That is a stack. Similarly one can argue that people do not need air, only a way to keep the blood oxygenated, and /that/ only as long as the person is alive. Cheers & hth., - Alf (nonsense-fighter for the occasion) |
| Jerry Stuckle <jstucklex@attglobal.net>: Apr 17 10:24PM -0400 On 4/17/2016 10:12 PM, Alf P. Steinbach wrote: > the blood oxygenated, and /that/ only as long as the person is alive. > Cheers & hth., > - Alf (nonsense-fighter for the occasion) It is not a stack in the hardware sense. It is the emulation of a stack. There is no stack pointer register to increment/decrement as necessary, no push/pop instructions, not even call/return instructions. IOW, nothing that people normally associate with a stack. It is simply a linked list, entirely handled by software. Assume you have three horses and two cows. You tell people the cows are horses. How many horses do you have? The answer is still three. Calling a cow a horse does not make it a horse. -- ================== Remove the "x" from my email address Jerry Stuckle jstucklex@attglobal.net ================== |
| "Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com>: Apr 18 06:01AM +0200 On 18.04.2016 04:24, Jerry Stuckle wrote: > Assume you have three horses and two cows. You tell people the cows are > horses. How many horses do you have? The answer is still three. > Calling a cow a horse does not make it a horse. I hope you'll realize, sooner or later, that in C++ we still have STACK UNWINDING of this list that in your opinion isn't a stack. Cheers!, - Alf (still fighting nonsense) |
| David Brown <david.brown@hesbynett.no>: Apr 18 09:00AM +0200 On 18/04/16 01:54, Alf P. Steinbach wrote: > what you meant. > I think we can use the descriptive term "contiguous stack area" for this. > And then we can say that neither C nor C++ require a contiguous stack area. We can certainly agree that neither C nor C++ needs a "contiguous stack area" (though the great majority of modern practical implementations /do/ have such a stack). And we can certainly agree that in order to implement recursive functions, some sort of LIFO structure is necessary. (In compilers for microcontrollers with poor support for a "contiguous stack area", such as the 8051, recursive or re-entrant functions are strongly discouraged because they force the compiler to create a stack which is otherwise avoided.) All we disagree on, as far as I can tell, is what the unqualified term "stack" means in this discussion. And since it is clear what /you/ mean by "stack", and clear what /I/ (and a few others here) mean, we can probably leave that part of the discussion there without any need to tell people they are talking nonsense for using terms others feel are well understood within the context. The real point of interest for the OP to learn here, is that while the compiler might put data on a physical stack (of any sort) for convenience and efficiency, it is not actually fundamental to the language, and the ordering of data on the physical stack is not fundamental. It does not relate directly to the order of creation or destruction of the objects. C++ (but not C) has a /logical/ stack holding objects with automatic storage duration in declared order - when an exception is thrown, these are destroyed in reverse order by "stack unwinding". But the order on this virtual or logical stack does not need to match that of any physical stack - data can be in registers, at fixed addresses, or held in any other way as long as the compiler has enough information to do "stack unwinding". As far as I can tell, the C++ standards only refer to the term "stack" for "stack unwinding" on exceptions, and as a type of standard container. |
| David Brown <david.brown@hesbynett.no>: Apr 18 09:09AM +0200 On 17/04/16 23:27, Jerry Stuckle wrote: > list. There is no "stack pointer that indicates the current depth of > the stack". > But obviously you CAN run C programs (and even Linux) on these machines. What I said was that you /could/ use a linked list (or some other structure) in order to implement the LIFO needed for recursive functions in C - but that it is a good deal less efficient than using a simple contiguous stack block and stack pointer. I don't know anything much about the processors used on IBM mainframes, until the Power architecture was used. Certainly on a Power cpu, there is no problem using a contiguous stack block (they have addressing modes to efficiently implement code such as "x = *sp++; *sp-- = y; z = sp[4]"). These processors don't have a dedicated stack pointer register - you can use (almost) any general purpose register you like as a stack pointer, and can have as many stacks as you want. While I haven't used a Power cpu myself, I have used PowerPC processors which have most of the basic ISA in common - and C compilers for PPC work in the traditional manner with contiguous stacks. Of course, there could be other reasons for IBM mainframes not using such "normal" stacks - I don't know enough about them to say. |
| "Öö Tiib" <ootiib@hot.ee>: Apr 18 01:58AM -0700 On Monday, 18 April 2016 07:01:52 UTC+3, Alf P. Steinbach wrote: > > Calling a cow a horse does not make it a horse. > I hope you'll realize, sooner or later, that in C++ we still have STACK > UNWINDING of this list that in your opinion isn't a stack. C++ standard does not discuss call stack. Instead there are life-times, storages and scopes. Destroying objects in reverse order to construction when life-time of objects ends is called "stack unwinding". You are correct that some sort of LIFO has to be there for implementing that. OP did however hack with execution stack of thread and that is entirely left to be as internals of implementation. |
| Jerry Stuckle <jstucklex@attglobal.net>: Apr 18 12:19PM -0400 On 4/18/2016 12:01 AM, Alf P. Steinbach wrote: > UNWINDING of this list that in your opinion isn't a stack. > Cheers!, > - Alf (still fighting nonsense) So now you have to resort to personal attacks to get your point across? It must not be a very strong argument. Neither the C or C++ standards say ANYTHING about a stack. "Stack unwinding" is a process, and processes can be implemented in a number of ways. For instance, in a processor with no multiplication instruction, you can still multiply by repeated additions. A linked list is not a stack. But you can still implement a stack unwinding process using a linked list. -- ================== Remove the "x" from my email address Jerry Stuckle jstucklex@attglobal.net ================== |
| Jerry Stuckle <jstucklex@attglobal.net>: Apr 18 12:26PM -0400 On 4/18/2016 3:09 AM, David Brown wrote: > structure) in order to implement the LIFO needed for recursive functions > in C - but that it is a good deal less efficient than using a simple > contiguous stack block and stack pointer. It doesn't have to be "a good deal less efficient". A linked list, properly optimized for a specific case, can be almost efficient as a stack. And you can implement a linked list in any processor. You can't do that with a stack. > traditional manner with contiguous stacks. Of course, there could be > other reasons for IBM mainframes not using such "normal" stacks - I > don't know enough about them to say. When I worked for IBM, I did a lot of work on mainframes, both in assembler and machine code (sometimes we had to write patches for customers who didn't have the source code). Sure, you can emulate a stack on IBM mainframes using registers. But it is much easier to do so with linked lists. But the PowerPC is not the same as the IBM mainframes; they are entirely different architectures with entirely different instruction sets. -- ================== Remove the "x" from my email address Jerry Stuckle jstucklex@attglobal.net ================== |
| red floyd <no.spam@its.invalid>: Apr 18 11:24AM -0700 On 4/16/2016 6:33 PM, Ben Bacarisse wrote: > stack like structure -- function locals could be in statically allocated > storage. And if, like in your example, there is only one function, you > don't need even that small stack-like structure. In fact, I once created a compiler (for a very limited simulated machine) that supported recursion by copying static data onto the stack, and then using static locations for local variables. Thus each instance of the recursive function had the same addresses for its variables (please note, the toy language had no operators for dealing with pointers or addresses). |
| Gareth Owen <gwowen@gmail.com>: Apr 18 07:40PM +0100 > So now you have to resort to personal attacks to get your point across? > It must not be a very strong argument. Oh Bravo, Jerry! |
| David Brown <david.brown@hesbynett.no>: Apr 18 09:40PM +0200 On 18/04/16 18:26, Jerry Stuckle wrote: > properly optimized for a specific case, can be almost efficient as a > stack. And you can implement a linked list in any processor. You can't > do that with a stack. How do you have a processor that can efficiently implement a linked list, but cannot reasonably implement a plain stack? I am not denying that this is the case for the IBM mainframes you refer to - you have worked with them, and I have not. I am just curious what the cpu ISA looks like. For small microcontroller devices like the 8051, the COP8, PIC12, etc., a data stack is very inefficient. But a linked list would be even worse. These devices do not have good pointer registers or pointer access modes. To implement a basic stack operation such as "x = *sp++" you must perhaps do roughly: ld a, sp // sp is a variable in memory mv iLo, a // iLo + iHi are special memory-mapped registers ld a, sp+1 mv iHi, a ld a, indirect // memory-mapped register for mem[iHi:iLo] st a, x // x is variable in memory ld a, sp add a, #1 st a, sp ld a, sp+1 adc a, #0 st a, sp+1 You /can/ implement a stack, or a linked list, but with such a restricted instruction set and limited addressing modes, it is clearly going to be very inefficient. But I don't see how you could have an ISA that has reasonable registers, instructions, and addressing modes for working with linked lists, and not also be able to use these for accessing a stack. > is much easier to do so with linked lists. But the PowerPC is not the > same as the IBM mainframes; they are entirely different architectures > with entirely different instruction sets. OK. As I said, I am not familiar with the cpus IBM use in their big systems, other than the Power processors. |
| Vir Campestris <vir.campestris@invalid.invalid>: Apr 18 09:02PM +0100 On 18/04/2016 00:54, Alf P. Steinbach wrote: > I think Fortran 77 didn't require a stack. I'm older than that ;) I recall proving to myself that Fortran IV on a DECSystem10 didn't have a stack. Function A wasn't allowed to call itself, but it could call B which called A. Except you then found out they were using the same local variables, as if they were all what I now call static. Didn't learn C until many years later. Andy |
| Vir Campestris <vir.campestris@invalid.invalid>: Apr 18 09:07PM +0100 On 18/04/2016 03:12, Alf P. Steinbach wrote: >> But C does not require a stack. Only a way to create a >> unique storage area when a function is called. > That is a stack. Well, that could equally well be a heap. Which is of course a great place to put a linked list... For the OP's sake I think BTW it's worth pointing out that the direction the stack grows can be towards high, or towards low, addresses on different architectures. Some can go either way, and I've met some that will allow you to have multiple stacks going in different directions. Multiple stacks BTW can be handy if you're writing an interpreter - you can keep one for the interpreted program's data, and one for the interpreter. Andy |
| scott@slp53.sl.home (Scott Lurndal): Apr 18 08:20PM >that this is the case for the IBM mainframes you refer to - you have >worked with them, and I have not. I am just curious what the cpu ISA >looks like. Burroughs B4800. Three (later gens had 7) index registers make linked lists easy (there are even instructions that will search a linked list for one of 9 different conditions with a variable length key at a variable offset from the start of the list element). http://vseries.lurndal.org/doku.php?id=instructions:slt There is no SP. For the call stack, the processor will read the 6 digit value from address 40 relative to base register 0 and use that as the address in memory for the stack (also relative to base 0), and will update it as data is pushed on the stack. There are -zero- general purpose registers. Everything except the three (or 7) index registers (which are used for addressing) is memory-to-memory including all the arithmetic instructions (except for floating point which uses a single accumulator). >But I don't see how you could have an ISA that has reasonable registers, >instructions, and addressing modes for working with linked lists, and >not also be able to use these for accessing a stack. Registers? Who needs them :-). |
| "Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com>: Apr 19 12:39AM +0200 On 18.04.2016 22:07, Vir Campestris wrote: >>> unique storage area when a function is called. >> That is a stack. > Well, that could equally well be a heap. No, a heap doesn't have LIFO behavior. The LIFO behavior for the allocations and deallocations is forced by the languages' support for general recursion, which can generate arbitrary long chains of stack frames for the call stack. The C++ standard refers to it as a stack, and we use terms such as "stack frame" and "call stack", because it's a stack, regardless of the implementation details. Cheers & hth., - Alf (nonsense fighter) |
| You received this digest because you're subscribed to updates for this group. You can change your settings on the group membership page. To unsubscribe from this group and stop receiving emails from it send an email to comp.lang.c+++unsubscribe@googlegroups.com. |
No comments:
Post a Comment