Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Subroutine calls in the ancient world, before computers had stacks or heaps

devblogs.microsoft.com

Post reply on HN
Print view View original

171–180 of 241 posts

Re: Subroutine calls in the ancient world, before computers had stacks or heaps

#171

Post by mauricioc »

guenthert wrote: post #170

"First, the compiler defined a secret global variable for each inbound function parameter, plus another secret global variable for each function to hold the return address" I believe 'hidden' is the word he's looking for. And one doesn't have to go all that far into history to find architectures w/o hardware support for a return stack, see e.g. Parallax Propeller. And the problem with static variables (hidden or not)…

Raymond Chen has been writing his blog for more than 20 years now, almost 7000 posts. It is a treasure trove of information and first-hand account. I can see an argument for peer-reviewing every post, but I think it would have limited (a lot) the amount of "from the trenches" knowledge we get from him.

Your reference to the Parallax Propeller is domain-specific and a bit anachronic; you're talking about embedded computing, while he is talking about general-purpose computing a few decades prior. The point of the post is that general-purpose computing was different in the past (in a sense, that's the theme for the whole blog! that and compatibility hacks), so going this far back is necessary.

Re: Subroutine calls in the ancient world, before computers had stacks or heaps

#172

Post by blueflow »

082349872349872 wrote: post #80
layer8 wrote: post #73

Earlier quoted context omitted.

In particular input to assemblers, compilers, and interpreters.

I once wrote a 16-bit assembler as a recursive function, which emitted code and fixed data on the way down and patched in relative offsets on the way back up. In principle, one might worry about blowing the stack, but as the sole purpose of this function was to assemble at most a half-k boot sector, in practice they fit.

Im curious about that. At which point did you do the recursion? "Assemble everything after this line and tell me offset of symbol X when you are done" ?

Re: Subroutine calls in the ancient world, before computers had stacks or heaps

#173

Post by 63stack »

derefr wrote: post #150

Funny enough, I was forced to program in exactly this way, when I was first learning to program. But not in the 1970s... in the year 2001! Why? Because my first exposure to programming was the semi-graphical scripting "language" exposed by the game-development tool "RPG Maker 2000." For those who haven't seen RM2K scripting before: picture a cross between Scratch and Emacs Paredit mode. (E.g. https://forums.rpgmakerw…

I started with rpgmaker as well, and your comment made me so nostalgic. I remember downloading a game from rpgmaker.net that had a "custom battle system" implemented in it. They replaced the entire built in battle system with a custom implementation that used techniques like you described. I was absolutely blown away when I opened it in the editor to see how it works. It was hundreds and hundreds of "variables" (which if I remember correctly only allowed i64), and hundreds and hundreds of "switches" (which was booleans). I had no concept of stacks and heaps or function calls at that point.

I can't imagine the amount of energy it took to pull that off and maintain/debug it.

Re: Subroutine calls in the ancient world, before computers had stacks or heaps

#174

Post by Tabular-Iceberg »

mr_toad wrote: post #144
taeric wrote: post #121

If it blows your mind to consider the time before call stacks were somewhat the norm in computers, you should look into the time from before register renaming. I don't think many people realize just how much of a modern processor is made around supporting preemptive multitasking. Folks know that we have a class of security bugs from it, but a lot of what happens in a CPU is around juggling multiple workloads.

In ten years or so all the people who worked on machines without preemptive multitasking will be retired.

Cooperative multitasking is in fashion now, so we might get a whole new generation to take over.

Or they’ll just cargo-cult everything and have no clue what’s happening under the hood.

Re: Subroutine calls in the ancient world, before computers had stacks or heaps

#175

Post by dspillett »

dragontamer wrote: post #6

I really liked the Art of Computer Programming with regards to this subject. While seemingly obsolete, there are a ton of pre-heap / pre-stack algorithms for dynamically changing arrays or other data structures. The book also builds up to garbage collection and how to implements Lisp-lists. The kind of encyclopedic knowledge you'd expect from Knuth. ------- One of my favorites is how to have two Arrays dynamically ta…

> While seemingly obsolete, there are a ton of pre-heap / pre-stack algorithms for dynamically changing arrays or other data structures.

These are not as obsolete as they might seem to many. In some environments you might still be very restricted and want to avoid all dynamic allocation which could force you to use these types of algorithm so you can work in-place in a static memory block.

Re: Subroutine calls in the ancient world, before computers had stacks or heaps

#176

Post by sgerenser »

shadowgovt wrote: post #28
dragontamer wrote: post #6

I really liked the Art of Computer Programming with regards to this subject. While seemingly obsolete, there are a ton of pre-heap / pre-stack algorithms for dynamically changing arrays or other data structures. The book also builds up to garbage collection and how to implements Lisp-lists. The kind of encyclopedic knowledge you'd expect from Knuth. ------- One of my favorites is how to have two Arrays dynamically ta…

This succinctly describes how old MacOS allocated per-application resources. Each app had a minimum and preferred RAM requirement tagged to it. When launched, it would take up the whole preferred slot, unless that amount wasn't available in which case it'd take up less than preferred (and fail to launch if it couldn't get minimum). The system allocated the heap (and libraries, I think) at the bottom and the stack at…

Pretty sure even with virtual memory (which was actually added sometime in the System 7 days), you still could manually set the minimum and desired memory sizes for each app. Maybe it made less of a difference than it used to, but I still remember tweaking those values for certain apps (like trying to open a large file in Photoshop) even after MacOS 8 and 9 were out. MacOS X was a breath of fresh air by comparison.

Re: Subroutine calls in the ancient world, before computers had stacks or heaps

#177

Post by dspillett »

pmontra wrote: post #167

If my memory is correct "no stack" was the way I was writing BASIC programs on my ZX81. 1 GOTO 30 10 LET C = A + B 20 RETURN 30 LET A = 1 40 LET B = 2 50 GOSUB 10 60 LET A = C 70 LET B = 3 80 GOSUB 10 90 PRINT C RUN 6 I was doing the job of the compiler in the article. Line numbers are memory addresses and the hidden variables are not hidden to me, because I'm the compiler. The only thing the interpreter made for me…

That is using a stack, at least a call stack: GOSUB will store a line number (or other reference) for RETURN to refer to, and if you nest GOSUB calls you have to remember multiple return points which requires some form of stack.

Though some BASICs didn't have a generic stack, instead a fixed array of return pointers and an index to the current one, so there was a fixed depth limit of, say, 7 calls, but from your PoV as the programmer this behaves as a call stack. Obviously this isn't a “proper” stack with local variables/parameters & such which you might expect when someone refers to a stack.

An interesting demo of what happens with nested (including recursive) calls that you could do with BBC BASIC in its native environment was that you could set the location of the stack to the top of display memory, and make sure you didn't do anything that would cause things to be drawn there of course, then you can watch the stack grow as work happens. The display was low-res enough that the pair of bytes for a return address could be seen as (in screen mode 1 or 5) eight chunky pixels (four in mode 2, but they would include flashing colours which is less ideal, sixteen in mode 0, 3, 4, or 6, but seeing individual bits doesn't work as well because a sequence of eight colours repeating amongst others is slightly easier to pick out then a sequence of 16 black/white ones).

Re: Subroutine calls in the ancient world, before computers had stacks or heaps

#178

Post by [deleted] »

tombert wrote: post #113

I've been doing functional programming so long that I genuinely have a hard time thinking about how I would write things without recursion. Like, I technically know how to convert a recursive algorithm to an iterative one, I've done it before on more resource-constrained stuff, but I don't like it. I think the recursive stuff is generally prettier and for 99% of things it's fast enough (and 100% if your compiler supp…

[deleted]

Re: Subroutine calls in the ancient world, before computers had stacks or heaps

#180

Post by HeyLaughingBoy »

RiverCrochet wrote: post #119
HeyLaughingBoy wrote: post #77

A long time ago (1991 maybe?) one of my first freelance projects during my first job out of college was to design an RS232 serial multiplexer -- take an incoming serial datastream, parse it, and redirect it to one of n outputs based on its header. I remember doing something similar to what he describes. My hardware design was basically a Z80, a 2716 EPROM (I may have also had a Parallax EPROM emulator to speed debugg…

> This was done (memory is fuzzy here) by preloading the return address onto a register pair and then calling the function. When the function was done, it would do an indirect jump to the location held in that register pair, which would return to the next instruction after the call. This is pretty much what the MIPS `jal` and ARM `BL` do. TMS9900 also did something similar (edit: it had a `BL` instruction too.) I was…

MC68xx series also had a 16-bit indexed jump. It's a very useful instruction.
Post reply on HN