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

"There was just one catch: You can't do recursion."

You could do tail recursion, because only the return address of the first call would be needed to be stored. `branch_with_link` would be used for the initial call, but the recursive calls would have to be regular branches.

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 take up one space.

Have one array grow normally from location#0, and the second array grow backwards from location#End.

Now both arrays take up the statically allocated space efficiently sharing.

This can be extended to an arbitrary number of arrays, but at that point you might as well use Malloc and Realloc. Or at least, the techniques therein are really close to a malloc-like routine IMO.

Note that before we had arbitrarily extensible heaps, programmers always did at least a little engineering, in that they had to consider the probable distribution of inputs and size* all their intermediate storage appropriately.

* giving rise to "BUGS AND LIMITATIONS"

Am I the only one who read it as the ancient world before computers existed had stacks or heaps? English is so weird sometimes...

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 debugging) and a couple of Z80-SIO serial devices. Notice that there is no SRAM chip :-)

The Z80 has enough registers that I could hold all the data I needed internally so I decided against the extra cost of RAM. This was the early 90's, remember. The one thing I was missing was a stack to make function calls. 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.

I don't remember how I passed and returned values, but I probably dedicated a register to that. I have a couple of old hard drives around here somewhere. I should see if I saved the code anywhere; I was quite proud of it.

I wrote a Forth interpreter for a SUBLEQ machine (https://github.com/howerj/subleq), and for a bit-serial machine (https://github.com/howerj/bit-serial), both of which do not have a function call stack which is a requirement of Forth. SUBLEQ also does not allow indirect loading and stores as well and requires self-modifying code to do anything non-trivial. The approach I took for both machines was to build a virtual machine that could do those things, along with cooperative multithreading. The heap, if required, is written in Forth, along with a floating point word-set (various MCUs not having instructions for floating point numbers is still fairly common, and can be implemented as calls to software functions that implement them instead).

I would imagine that other compilers took a similar approach which wasn't mentioned.

EDIT: There were some BASIC interpreters which did this as well, implementing a VM and then targetting that instead. P-Code is a similar thing.

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 the @let feature in Enhanced GNU Awk, for those @let blocks that are outside of a function, like in BEGIN or END blocks, I have the compiler allocate secret global variables. They are reused as much as possible between blocks.

  $ ./gawk --dump-variables 'BEGIN { @let (a, b, c = 1) { } }'
  $ cat awkvars.out
  $let0001: untyped variable
  $let0002: untyped variable
  $let0003: 1
  ARGC: 1
  ARGIND: 0
  ARGV: array, 1 elements
  BINMODE: 0
  [ .. snip many ]

The article does not distinguish between recursive and nested subroutine calls.

I understand, why the provided example does not allow for recursion, but doesn't it also prevent a nested call to another subroutine?

If I remember correctly before FORTRAN90 we already had nested subroutine calls. How did that work?

EDIT: I think I get it. The hidden global variables are prefixed with the sub's name. This is pretty wasteful, but as long as a function does not call itself (even indirectly) we are good.

For the kind of programs I write for AVR-8 it seems insane to use the calling conventions of C, so if I write assembly I can sometimes keep the inner loop variables in registers (big register file) and otherwise use the methods he describes. I like “coloring” functions in an app like that, if I know a red and a green function will never be active at once I can reuse locals/parameters for them.

As I recall, some processors stored the return address at the word before the first instruction of the subroutine.

Yep, that's what the PDP-8 did. The evolution of the PDP-8 is arguably a journey in hardware support for recursion.

Initially the JMS instruction stuck the return address in the first word of the function (as an aside, a lot of time caller would put it's arguments after the JMS instruction, and the callee would read arguments offset of the return instruction, incrementing it with each read argument until the return address pointed to code again).

Then it became relatively common to use one of the autoincrement locations (the PDP-8 had 8 memory locations that would increment any time you used them as a pointer) to create a simple stack, and function prologues/epilogues manually managed this stack to allow full recursion.

Then later on hardware stacks were added in the microprocessor implementations like the Harris 6120 to make this more performant.

Cobol upto and including the 85 Standard was stackless and heapless which is quite a cognitive divide. For those going to and coming from that language.

I didn’t read Raymond say anything about security in the present article, but the advantages a clear. No stack or buffer overflow vulnerability for example.

Getting recursive functions into ALGOL turns out to have been a controversial move that made for a fun story: https://vanemden.wordpress.com/2014/06/18/how-recursion-got-...

The old IMB 360 use a 'display' where you just chose a register by convention, pointed it at some memory then did your own linked list on call and return.

In fact call was really jump-and-link(?) where you got the return address in a register. Anticipating that if your subroutine took more than a little code you'd just store it temporarily in your allocated 'display'.

No push/pop at all! Unless you wanted to write it that way. You were just on your own.

Whenever Raymond Chen retires, I am going to be really sad.

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 supports tail recursion, though you'd still be stuck maintaining a stack for most of the more interesting stuff).

Occasionally I'll do things to force myself to learn how things were done before I was born. I've been on/off hacking on a Commodore 64 game, but man I feel pretty grateful to be as spoiled as I am with fast, cheap, easy-to-use hardware.

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

Disclaimer 1: the code could be syntactically wrong and hallucinated (40 years are a long time) but it gives the general idea.

Disclaimer 2: The Z80 processor inside the machine had stack management, the BASIC interpreter was really very basic but it could be excused: it had 1 kB RAM and a 8 kB ROM with the OS, the interpreter and everything.

This post happens to describe the world of the famous “Goto considered harmful” paper.

Most people just know the title and simply fetishistically refuse to use a goto (most of the time they are terrible, but not always). But really the paper argues for giving subroutines a single entry point.

Sometimes I write assembly code that falls through into another subroutine, but I don’t want all my assembly to be spaghetti like that.

"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) is not only that they prevent recursion, but also reentrancy.

I think that article could have benefited from a peer review from one of his colleagues at Microsoft.

It's not ancient if you still do embedded development

My first assembly was 6502 which kept a call stack in page 3 (128 levels deep being the maximum call depth as a consequence). When I learned 370 assembly, I remember being shocked to discover that an application was responsible for maintaining its own call stack.

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.rpgmakerweb.com/data/attachments/21/21958-f89...) It's presented as textual, but you can't edit it like text — only as blocks with associated properties dialogs.

And, of course, that scripting language in RPG Maker doesn't have anything so fancy as a stack.

Want some reusable subroutines? Well, you better believe you're allocating secret global variables for their parameters — no re-entrancy for you!

---

Mind you, thinking back on it, it's probably possible to implement both registers and a runtime stack in RPG Maker 2000, given sufficient stubbornness.

Both features seem easy enough at first: you can do pseudo-"registers" like the zero page on a 6502; and you can do a stack through indirect variable access (https://rpgmaker.net/tutorials/523/).

The problem with both of these, though, is that RM2K actually has concurrency in the form of "parallel process" scripts — so any use of either of these abstractions by these parallel processes, will have different "threads" stomping all over one-another's state.

So you'd actually need multiple "zero pages" and "stacks" — one for each "virtual core" — and then you'd need to somehow assign/bind/schedule the "virtual cores" to parallel scripts (i.e. somehow get each script its own privately-known "stack pointer.") Which, to be stable in the face of race conditions, would normally require something like mutexes...

Knowing the bloody-mindedness of RPG Maker gamedevs, I'm sure someone did come up with a way to trick some runtime feature into acting like a mutex. But I'm genuinely scared to know what it was they did.

When I was first starting out a very long time ago, I wrote a lot of Fortran (mainly for digital signal processing applications), and a couple of times I had to work around the lack of recursion by building my own stacks for intermediate results, with arrays and a position to keep track of where I was. It was ugly.

Very unfortunate that the mobile layout of the devblog has so many fixed elements on the side, they are distracting and can’t navigate the page without feeling some discomfort

I was looking through the ROM listing on a really old diskette controller for an S-100 computer, and I saw all those jumps... and didn't understand what was going on. Then a friend told me there wasn't any guarantee of RAM in any given address, so they used the BX register (if I recall correctly) for the return address.

This would be transformed by the compiler into something like this:

Even modern C compilers for "modern" 8051-derived MCUs work like this :)

My first exposure to assembly language was one of those computers that used self-modifying code for subroutine calls, the Control Data Cyber 6400. It had a special instruction (I think it was called RJ) that replaced the first word of the subroutine with a jump instruction back to the caller. Every function had to start with a special no-op so that it could be replaced, and you returned from a function by jumping back to the beginning.

A couple of personal experiences from the ancient world:

I wrote code for a microprocessor that did not have a stack as an actual concept. There are still embedded processors out there today like this. To work around this you stored a value at a zero page location, and when you wanted to jump to a subroutine, you would first load up this value from zero-page, advance it, put the program counter into the memory address now pointing to a new memory location, then execute a simple go to, and at the end of your function, to return, you would load up that value in zero page, then load up your return address, decrement your pointer, store it back to zero page, then go to back to the calling function. Every value you wanted to pass to the subroutine would be either in one of your three registers, or you would pass those values by storing them in memory pointed to by your zero page value. The 6502 offers nice instructions to do these very operations, by turning the assembly/machine code into microcode that does the exact same thing, but more succinctly.

Another trick I used was bank weaving. You only had a limited amount of addressable memory, but you could bank switch ROMs, so you'd write your code to have it reside at a fixed memory location, and another chunk of code at another fixed memory location in a different ROM bank, then your first code would execute down to a point where it would switch banks based on a condition, and when the other ROM bank switched in, your alternative code path would be waiting for you, you'd execute that, then switch the ROM bank again back to the first one, and the PC (program counter) will have advanced several hundred bytes possibly, so you'd return to a point in your code, back in the first ROM bank, that was a completely different point in memory, but still the same calling function.

A few years later I used a similar technique on a large text adventure game, a compiler and a word processor, where the core of the program was always resident, but chunks of code could be loaded in at fixed memory locations from disk. So if you ran a spell check, the spell check functions would load in at a known memory location, various bits were set in RAM to indicate which functions were resident, and the application could perform the spell check, or run the logic for a part of the text adventure game. And functions would automatically unload to make room for new functions based on the last time they were invoked.

I wrote code for a Timex processor that had a "execute the instruction at the following address" opcode, so effectively your instruction here, would execute that instruction over there, but only for one instruction. It made writing the equivalent of switch/case in assembly interesting, and also good for self-modifying code.

Zero-page on some old CPUs was a faster RAM, a few dozen bytes, or even 256 bytes, so if you had a tight loop, you'd copy the code into zero page, perhaps having to move other stuff out of the way first, and execute it there.

I wrote a word processor that stored only a tiny fraction of its data in under 3KB of RAM, the rest was stored on big floppy disks. As you scrolled through the text, it would page through the pages (memory pages, not pages of text) on the floppy disc, but the memory pages were not stored continuously, either in RAM or on disk. The RAM acted more like a cache, and a couple of memory pages were reserved for edit operations and even copy & paste. To copy and paste entire pages was fast, you only had to adjust a few pointers in RAM and on disk, plus a few hundred bytes for head and tail page operations so moving large blocks of text around was very fast, and inserting large blocks of text, or even just typing, was very fast, because the buffers were quite small. It was the only word processor I know of that came with a disk defrag operation built in, but the company called it "housekeeping" in the manual with no explanation to the end user of what it was doing. I learned a lot about "don't mark that as deleted until you are damn sure the operation is completed and you've verified it worked."

I did a 6507 and Z80 emulator on the MIPS R3000 that ran the code in a very pedestrian way, but as the 6507 or Z80 ran through the code, each memory address was added to a list, and the 6507/Z80 opcode found there was translated into an intermediate assembly language, and then I post-processed that intermediate assembly into R3000, which gave me a huge performance boost; post-process dynamic recompilation effectively. I had to do other sneaky things with it too because the original hardware raced the electron beam whereas the target platform just had a big VRAM buffer. Used the same trick to port 6507 code to an early ARM processor for an old handheld too.

There's a lot of other tricks we used to in the before-times, such as LFSR and LCG to permute game objects in seemingly random patterns, cheating on distance checks by counting the clock cycles between two objects drawn on screen, low-rez bitmaps of the screen to speed up collision detection, compiled graphics/sprites, even sprite blitting routines that were hard-coded to specific pixel offsets.

If you write a GPU shader in most graphics APIs today you will also not have a stack or heap.

And to think that's where we come from. The Intel 8008, the ancestor of the x86 processor family, just has a 7-level call hardware stack only used by the unconditional and conditional call and return instructions. So, there is no push and pop instructions. As the only way to access a byte in memory was to store the address in the HL register pair (no absolute addressing mode) before the load or store instruction and as there was no way to disable hardware interrupts, it was almost impossible to write useful interrupt routines without some external hardware trick.

Another commenter said: "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."

I wonder what programming techniques exist today that will be obsolete in 30 years? I imagine Transformers made a bunch of early ML algorithms completely obsolete?

What else?

the headline reminded me of "ancient computers" in sci fi games, which was essentially a tower of Hanoi problem inmplemented in-game

One of the things that people miss is that a "stack" was not just for recursion.

A "stack" was also a small memory, single thread optimization because it allows you to multiplex memory for function calls. If two functions do not call each other, they can share the memory used for their activation records.

Keeping track of this memory multiplexing in the compilers of the day would have been very hard and highly memory intensive--a stack solves that problem.

Without a stack, your memory usage (static) goes as O(n) with the number of functions. With a stack, your memory usage (dynamic) goes as O(n) with the depth of function calls. The memory usage of these two scenarios is wildly different.

Raymond Chen has to be one of the few OG legends where the title of the post alone is just like: “Today is Old New Thing day, and that’s just going to be the coolest thing I learn today.” I started salivating before my eyes scanned so far as the domain name.

And as usual, worth reading at least one or two more times.

Fucking. Legend.

This was posted yesterday