Processors who's stack grows up

And, for completeness, an architecture that was if not quite descended from at least inspired by the HP 3000, Tandem^WCompaq^WHP NonStop, which was still built and sold as recently as IIRC 1992, and userland software for which is still supported in emulation on the successor TNS/R systems since Tandem shops tend to be very slow to change their business-critical applications. But the OS now is all 'native' MIPS with downward stack, and even in the days of TNS hardware no one with sense would have bought it to run a non-Tandem OS and throw away the fault-tolerance and support features they paid a hefty premium for.

Also, equally irrelevantly, the PDP-10 doesn't have any "hardware" stack for interrupts, but can use any GPR (except R0? I forget) as a pointer to an upward-growing and (optionally) length-checked stack. According to the folks in alt.sys.pdp10 there are actually a few clone hardware systems still in use, as well as rather more folks using (several) emulators, but again those systems are kept in existence (only) to run old software and they wouldn't want to run Nucleus.

- David.Thompson1 at worldnet.att.net

If the MIPS doen't have a notion of a stack, do they have call/ret instructions? What about interrupts? The interrupted location must be saved somewhere.

- Heinz

In RISC processors it is a common method to have special registers which save the interrupted state, including the return location.

As an example, in ARM processors there are saved PSR and exception state link registers to save the previous processor status and return location.

The interrupt handler software may decide to still save the state into a stack, but it is then entirely managed by the software handler.

--

Tauno Voipio
tauno voipio (at) iki fi

They get younger every year ...

The stack, as in "SP->memory", in a non-Burroughs* machine (see below) is a recent circa 1970 creation.

The traditional method (like we got traditions in computer design) of returning from subroutines was by forming a linked list. Sometimes by such subtle methods as writing a JMP instruction to the caller's "return-to" address at the end of the called subroutine - remember all code was in core ("RAM" for the young'ns) - this method is not recommended for recursion.

IBM (?) came up with the idea of linking registers rather than using code modification when subroutines are called.

Register linkage re-appeared in the TI-9900 micro (others?) and some modern primitive instruction set micros as MIPS (above).

• The early Burroughs machines are a must see:

A machine designed to run Algol, c. 1958.

--
Nicholas O. Lindan, Cleveland, Ohio
Consulting Engineer:  Electronics; Informatics; Photonics.
Remove spaces etc. to reply: n o lindan at net com dot com
psst.. want to buy an f-stop timer? nolindan.com/da/fstop/

Or you get older every year ;-)

Yes, I'm too young to know that (was 10 years old that year). Thank's for this historic infos.

- Heinz

That would require the caller to know the end of the subroutine.

You are probably referring to the CDC. It would write a jump back to the caller at the *first* word of the callee and begin execution at the 2nd word.

I believe a pdp 8 did the same thing. The return was an indirect jump to the first word.

I remember that from the days not so long ago when the UofMinn used to torture students by making them program on a 6600. I always wondered how one did recursion or re-entrancy on a 6600, but the professor who taught that class wasn't really up on modern stuff like that. He had also never heard of passing parameters by value.

--
Grant Edwards                   grante             Yow!  YOW!! The land of the
                                  at               rising SONY!!
                               visi.com

And? The caller has to know the entry point, yah? Knowing the exit point is somehow interdict?

No, I am not. Why, because as you so state:

This was an improvement, for modern day dilettantes.

--
Nicholas O. Lindan, Cleveland, Ohio
Consulting Engineer:  Electronics; Informatics; Photonics.
Remove spaces etc. to reply: n o lindan at net com dot com
psst.. want to buy an f-stop timer? nolindan.com/da/fstop/
.

Yes,

SUBR: +0 ... JMP I SUBR

(we only had ASR33s, no idea if PAL III would have accepted lower case!)

--
Simon Wright                               100% Ada, no bugs.

"A traditional ..." would have been a better choice of words.

I should not these methods are all software implementations. Where the return address and parameters are stored in older [and some newer] machines is a matter of software convention.

Whirlwind, CDC, PDP-8 ... methods can be used on [almost] any processor. PPP [People who Program Pics] know of even more bizarre methods.

--
Nicholas O. Lindan, Cleveland, Ohio
Consulting Engineer:  Electronics; Informatics; Photonics.
Remove spaces etc. to reply: n o lindan at net com dot com
psst.. want to buy an f-stop timer? nolindan.com/da/fstop/

Plenty of the PIC bizarrities are directly from the minis of the sixties: PDP-8, HP-2116, Honeywell DDP-312 and DDP-516 & co.

--

The method of storing the return address at the
subroutine entry location and starting the execution
at the next instruction was an industry standard
in the minis of those times. The notable exceptions
were Data General Nova and Digital PDP-11 which
stored the return address in a register.

I figure that having to know both the entry point and the exit point is twice as much work as having to know the entry point only, but ...

.. I stand corrected

That was done in software. The prelude of the called function would save the value written by the return jump on the (software) stack.

While it is technically correct to say that PDP-11 stored in the return address in a register and it was also used extensively in some older code when using R0 .. R5 as the link register, in which case it was easy to use the link register to access the in-line parameters. However, some compiler generated code pushed the parameters on the SP stack and then called the subroutine, using the PC as the link register, which effectively pushed the return address on top of the stack, thus creating a pure stack architecture.

IMHO, recursion is highly overrated, some people even want to convert a simple loop to a recursion :-).

Languages which were commonly used in 1960/70, such as Cobol and Fortran did not even support recursion. This caused some problems in some very rare cases .e.g. when evaluating complex arithmetic expressions with complex function parameter list, but it is definitively doable, while of course this would be easier to do with recursion.

In high reliability systems (which are often discussed in these newsgroups), it is not acceptable that the thread/process stack would _ever_ overflow. If recursion is used on such systems, there must be a well defined absolute maximum number of recursions that can occur, in order to fit into the allocated stack.

For instance walking through a binary tree with a recursive routine is nice, but what if the binary tree is due to the creation order actually a simple linear linked list, then the levels of recursions is the same as the number of elements in the linked list. With a large stack frame in the recursive routine, the stack size requirement can be larger than the size of the linked list.

Thus, in order to use a recursive binary tree routine, some precautions must be done to reorganise (balance) the tree to avoid such pathological cases as the binary tree becoming a linear linked list, before calling the recursive binary tree walker routine.

Paul

Fortran not supporting recursion is an industry myth probably a side-effect of early implementation techniques. There is nothing in the ANSI Fortran standard which precludes a stack-oriented implementation thus allowing recursion.

Recursion aside, it's re-entrancy that really matters. I suppose if the OS doesn't support multiple processes, then that doesn't matter either.

--
Grant Edwards                   grante             Yow!  It's OKAY -- I'm an
                                  at               INTELLECTUAL, too.
                               visi.com

recursion

to

I just proted a compile and virtual machine write in fortran in the early

70's that ran on a PDP11. both the compiler and the virtual machine handled recursion. Pat

You're missing the point, I think. The fact that the Fortran standard doesn't preclude a stack-based implementation allowing allow recursion, by no means implies that Fortran "supports recursion". To back up a claim that Fortran (as such, rather than a particular implementation) supported recursion, the language standard would have to *enforce* that it's possible. I'm quite sure it doesn't

--
Hans-Bernhard Broeker (broeker@physik.rwth-aachen.de)
Even if all the snow were burnt, ashes would remain.