pardo@june.cs.washington.edu (David Keppel) (08/22/88)
smryan@garth.UUCP (Steven Ryan) writes: >I don't understand: the concept of a single big general purpose stack is >fundamental to any language that implements recursion. I think that coroutines for a recursive language are most naturally implemented in a language that has multiple stacks. ;-D on ( Vote for "None of the above" ) Pardo -- pardo@cs.washington.edu {rutgers,cornell,ucsd,ubc-cs,tektronix}!uw-beaver!june!pardo
dg@lakart.UUCP (David Goodenough) (08/23/88)
smryan@garth.UUCP (Steven Ryan) writes: >I don't understand: the concept of a single big general purpose stack is >fundamental to any language that implements recursion. And then there was BCPL. And FORTH. I disagree with Mr. Ryan, but I would suggest the following (I'm open to being corrected by those with more knowledge :-) AT LEAST ONE STACK is necessary for the implementation of a language that provides recursion, but having two (or more) stacks does not imply that it can't be done, it just changes the nature of how you do things. -- dg@lakart.UUCP - David Goodenough +---+ | +-+-+ ....... !harvard!cca!lakart!dg +-+-+ | +---+
smryan@garth.UUCP (Steven Ryan) (08/23/88)
>>I don't understand: the concept of a single big general purpose stack is >>fundamental to any language that implements recursion. > >I think that coroutines for a recursive language are most naturally >implemented in a language that has multiple stacks. Silly me, and I thought I was talking about C. Multitasking systems either give each task its own stack which is a single big general purpose stack, or convert the stack into a tree with each task only seeing a single unified stack. Even if the system requires a fixed size frame, local storage can be allocated on the heap, chained into the frame. Like other tricks, local storage need not be implemented in particular fashion as long as its semantics are fixed. Be careful not to confuse implementation with interface. ---------------------------------- talk about user hostile systems: File to include [none]? type *none* and it aborts.
pardo@june.cs.washington.edu (David Keppel) (08/24/88)
dg@lakart.UUCP (David Goodenough) writes: >[ suggestion: always need AT LEAST ONE stack for recursive languages ] Um, er, ah, well... Some C implementations, I'm told (haven't seen them personally) on older architectures (for which there is no explicit stack support) implement recursion by allocating call frames off of the heap and explicitly freeing them when done. I'd be willing to gamble a few alfalfa sprouts that Zeta-C uses the underlying hardware management for stacks, and if the underlying hardware supports non-LIFO stacks (e.g., Symbolics), then that's what gets used. Memories from theory: recursion and iteration are equivalent. => Proof by intimidation that any machine that can run iterative programs (which you will agree do not *need* stacks) can also run recursive programs, given a sufficient set of transformations. ;-D on ( Damn kids ) Pardo -- pardo@cs.washington.edu {rutgers,cornell,ucsd,ubc-cs,tektronix}!uw-beaver!june!pardo
tainter@ihlpb.ATT.COM (Tainter) (08/25/88)
In article <5542@june.cs.washington.edu> pardo@uw-june.UUCP (David Keppel) writes: >dg@lakart.UUCP (David Goodenough) writes: >>[ suggestion: always need AT LEAST ONE stack for recursive languages ] >Some C implementations, I'm told (haven't seen them personally) on >older architectures (for which there is no explicit stack support) >implement recursion by allocating call frames off of the heap and >explicitly freeing them when done. You haven't eliminated the stack in this case. You have just made it less obviously a stack. You will find that these frames still need to form a stack for call returns. > pardo@cs.washington.edu --j.a.tainter
bill@proxftl.UUCP (T. William Wells) (08/27/88)
In article <8604@ihlpb.ATT.COM> tainter@ihlpb.UUCP (55521-Tainter,J.A.) writes:
: You haven't eliminated the stack in this case. You have just made it
: less obviously a stack. You will find that these frames still need to
: form a stack for call returns.
Yes he has. A `stack', as he was using the term, refers to a
particular way of using memory. What he has is a linked list.
Both have the characteristics you need for implementing
recursion.
There is a use of `stack' that refers to any way of doing LIFO
but that use does *not* talk about implementation. Since the
original discussion was talking about stacks in the sense of
hardware stacks or memory set aside for a stack, this use is
irrelevant.
This is an example of a generic problem on the net: seeing
similarities at some level of description and then demanding that
the similar things be called by the same name. So, since a
linked list can be accessed on a last-in, first-out basis, as can
a stack, this notion would require calling both a stack. *A
linked list is not a stack.* Of course, this problem is
aggravated here because the concept of a data structure that
implements LIFO is also called a `stack'.
There was a similar sillyness recently where the words
`iteration' and `recursion' were confused.
Let's keep our concepts straight.
Please?
---
Bill
novavax!proxftl!billsmryan@garth.UUCP (Steven Ryan) (08/30/88)
>Yes he has. A `stack', as he was using the term, refers to a >particular way of using memory. What he has is a linked list. >Both have the characteristics you need for implementing >recursion. > >There is a use of `stack' that refers to any way of doing LIFO >but that use does *not* talk about implementation. Since the >original discussion was talking about stacks in the sense of >hardware stacks or memory set aside for a stack, this use is >irrelevant. Since I'm partly responsible, let me say I was talking about stacks as an abstract type not a PDP-11 style implementation. Before everybody gets all hot and botherred and say this is not a PDP-11 issue, may I remind you not all machines provide two address spaces for a task. If all code and data goes into a single address space, the stack implementation is inherently messy.