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

https://devblogs.microsoft.com/oldnewthing/20240401-00/?p=109599

by signa11 • 2 years ago

473 233 2 years ago

devblogs.microsoft.com

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"

eschneider• 2 years ago

Those before times are still today, depending on what you're doing. For hard real-time, dynamic memory is (almost) never used, mostly because the time needed to alloc/free memory isn't deterministic. So everything is statically allocated at compile time and yeah, you've got to know how much memory your inputs are going to consume.

But knowing the bounds of memory consumption used to be normal for application programmers, too. I mean, you don't want to run out of memory. Ever. What do people do now, just YOLO memory usage?

shadowgovt5• 2 years ago

What do people do now, just YOLO memory usage?

Yes, literally. Careful allocation has given way to "Use what's there and fail hard if it ain't enough" in the era where machines are cheap and the dominant paradigm is how parallel you can make your algorithm so you can solve your problem with scale.

In the modern era, for most online service software (which is, I'd argue, most software people interface with these days), you write it as fast as you can, prototype it small, start to care about RAM allocation (but build it to just die screaming if it runs out of RAM so you know you need to make a change), and keep scaling up.

You don't care a lot about RAM allocation until you're scaled to a lot of nodes because only at that scale is whether the app takes up a kilobyte less going to start to matter on machines that are swinging gigabytes of storage around.

There are plenty of application spaces where this isn't the status quo (embedded architectures, console gaming), but that tends to be considered specialist engineering in this day and age.

kstrauser2• 2 years ago

Historically, that was also a big goal of GNU. It aimed to get rid of artificial limitations in core utilities. That was a big improvement over (made up example) sed having a finite and short maximum command length.

deckard1• 2 years ago

I can understand why people wanted that, and the benefit of doing that.

With that said, I also see benefit in having limitations. There is a certain comfort in knowing what a tool can do and cannot do. A hammer cannot become a screwdriver. And that's fine because you can then decide to use a screwdriver. You're capable of selection.

Take PostgreSQL. How many devs today know when it's the right solution? When should they use Redis instead? Or a queue solution? Cloud services add even more confusion. What are the limitations and weaknesses of AWS RDS? Or any AWS service? Ask your typical dev this today and they will give you a blank stare. It's really hard to even know what the right tool is today, when everything is abstracted away and put into fee tiers, ingress/egress charges, etc. etc.

tl;dr: limitations and knowledge of those limitations are an important part of being able to select the right tool for the job

lenerdenator• 2 years ago

Really, the mistake was letting humans provide input to computer programs.

layer8• 2 years ago

In particular input to assemblers, compilers, and interpreters.

01HNNWZ0MV43FF• 2 years ago

This was posted yesterday

joeatwork• 2 years ago

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-...

robocat• 2 years ago

Definitely "a tale of intrigue, betrayal, and advanced programming-language semantics"

dang• 2 years ago

How recursion got into programming: intrigue, betrayal, and advanced semantics - https://news.ycombinator.com/item?id=33123916 - Oct 2022 (8 comments)

How Recursion Got into Programming (2014) - https://news.ycombinator.com/item?id=23061881 - May 2020 (47 comments)

How recursion got into Algol 60: a comedy of errors - https://news.ycombinator.com/item?id=10131664 - Aug 2015 (124 comments)

How recursion got into programming: a comedy of errors - https://news.ycombinator.com/item?id=8073361 - July 2014 (108 comments)

dragontamer• 2 years ago

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.

Retr0id• 2 years ago

SQLite's on-disk format uses a similar array technique for storing the contents of table btree leaf node pages. Within a fixed-size page, there's an array of offsets growing forwards, and an array of (variable length) row values growing backwards from the end - the latter of which may end up with holes when rows are deleted (iiuc).

It wouldn't surprise me if it was a direct inspiration, since their docs cite TAOCP for the btree structure itself.

hiAndrewQuinn• 2 years ago

We know from the Corecursive podcast on the hidden story of SQLite that Dr. Hipp did indeed reference and pull at least one alg straight from Knuth's books, which he had behind his desk. What a different world that must have been!

felixge• 2 years ago

This sounds like it was copied from PostreSQL which SQLite cites as a strong source of inspiration.

tanelpoder• 2 years ago

Oracle does this as well and I suspect many other row-major RDBMS storage engines do too.

suncherta• 2 years ago

As others have already mentioned this is used in a lot (most?) of databases. It is called "slotted-page". Searching for it gives good discussions/explanations of it.

shadowgovt5• 2 years ago

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 the top of that physical-RAM slice, and off you went.

I believe around system 8 they added a virtualization layer that started to obviate the need for that approach (and of course by the time of MacOSX they were using paged memory like everyone else was and so such fancy tap-dancing was no longer needed). But it's fun to think about the era where this "one weird trick" from Art of Computer Programming was how we allocated RAM for multiple concurrent applications.

sgerenser• 2 years ago

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.

bewaretheirs• 2 years ago

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

The stack in most ISAs and ABIs grows down from a high address, allowing this trick to be used to divide memory flexibly between heap and stack in single-threaded small-memory systems.

yongjik• 2 years ago

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

Fun fact: Itanium had two stacks, one for manual push/pop and another for cycling through the register file. One stack grew upward, another grew downward. A fascinating architecture, though it never delivered the promised performance.

masfuerte• 2 years ago

Some word processors on 8-bit computers worked like this. Your document took all of the available RAM. Text before the cursor was at the start of RAM and text after the cursor was at the end of RAM. Insertions and pastes didn't need to shuffle data around but navigation did. It worked well.

shadowgovt5• 2 years ago

emacs still does this IIUC. The beating heart of the emacs edit model is a "gap buffer" at the cursor.

There's a neat compare-and-contrast someone did awhile back on the gap buffer approach vs. the other approach often taken for code IDEs ("ropes"). The tl;dr is that gap buffers are actually really performant for a lot of cases except for having to edit at a lot of randomly-chosen cursor points far apart from each other (but how often is that your use case?).

https://coredumped.dev/2023/08/09/text-showdown-gap-buffers-...

fuzztester2• 2 years ago

but at that point you might as well use Malloc and Realloc.

IIRC, the first edition of the classic K&R C book, The C Programming Language, had an example of creating a memory allocator and using it.

tengwar2• 2 years ago

It's not difficult to write a memory allocator, but there are some assumptions there which don't always hold true. For instance SmartCards (e.g. SIMs) use a language alleged to be Java, but without a garbage collector and with only one data type. Applications never terminate, so while you can allocate heap memory, you cannot free it and memory exhaustion is one way to brick the device. Since it is "Java" you don't have the low level control of C. Standard practice is to allocate some global variables once, and use them throughout the life of the device. Since another way to brick the device is by exhausting write cycles on the EEPROM on which these variables are stored, you are also allowed to allocate an array in the small amount of RAM. Ah, you might think - I can use that for an allocator! Nope. The array space is only allocated until the end of an event handler, and after that it holds undefined content.

dspillett2• 2 years ago

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.

gigel82• 2 years ago

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

ivanjermakov• 2 years ago

Me too clicked the link expecting stories of heap and stack uses before computers.

grraaaaahhh• 2 years ago

Yeah, I was all ready to learn about how the ancient Egyptians used stacks to build the pyramids or something.

nerpderp825• 2 years ago

Technically they did.

trealira• 2 years ago

I was expecting some ancient Greek algorithms that used stacks or priority queues, haha.

dfxm12• 2 years ago

I don't find the ambiguity weird, but rather poetic. Perhaps it is intentional. After all, computer technology has come such a long way in just our lifetime. A modern computer would probably be just as alien to someone in the 1920s as the 20s. In the same way, an average person today would be just as baffled by the ENIAC as they would an Antikythera mechanism...

I sincerely doubt that English is the only language that supports such word play.

glhaynes• 2 years ago

I’m no grammarian but I think it should have a comma after “world”.

perihelions• 2 years ago

"Novel analysis of the Antikythera mechanism suggests all of its wheels were statically allocated at construction time"

brudgers• 2 years ago

The ordinarily “The Ancient World” means an era ending with the fall of the Western Roman Empire circa 476 CE.

All that world was well before computers were a thing (even the human type were called “scribes,” “clerks” etc.)

So of course I read it the same way even though “before computers” was redundant once your comment made me think about it.

anthk3• 2 years ago

They had abaci with stacks.

marcellus23• 2 years ago

This has nothing to do with English, it's just syntactic ambiguity. Every language has it.

samatman2• 2 years ago

It's a garden-path sentence: https://en.wikipedia.org/wiki/Garden-path_sentence

One is lead to believe the subject is "the ancient world before computers", as it would be in "the ancient world before computers had gladiators and triremes", but the subject is "computers", and the ancient world is the topic.

Toorkit• 2 years ago

If that had been the way it was intended, I think it would have been phrased "stacks and heaps."

I.e. "the ancient world had stacks and heaps" as opposed to "the ancient world had stacks or heaps," which sounds weird.

mr_toad2• 2 years ago

Well of course they had stacks and queues - computing adopted those terms from the real world. Stacks were even used for calculating in the form of an abacus.

kazinator3• 2 years ago

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 ]

https://www.kylheku.com/cgit/egawk/about/

1letterunixname• 2 years ago

That website doesn't work from my ISP. Can't even ping it or nc -z 104.37.63.7 443.

Edit update: Your security infrastructure is broken because I don't know what that is and don't use Twitter. If you check the AS, it's Google Fiber. And I'd appreciate it if you wouldn't dox me.

kazinator3• 2 years ago

Not sure why. Out of the 26 IP addresses that accessed the egawk repository in the last day or so, only one was banned. The client identified as Twitterbot, coming from 136.49.X.X.

wizzwizz4• 2 years ago

That isn't your dox: if you can't even ping it, you wouldn't have been able to request a specific repository, and won't appear in that access log.

kazinator3• 2 years ago

I made it clear it's something reporting itself as "Twitterbot". Unlikely to be your web browser, unless you went out of your way to impersonate Twitterbot. Still, I only quoted two octets out of the IPv4 Class B address, even though I feel that it would be fine to reveal the full address of a bot.

weinzierl2• 2 years ago

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.

comex• 2 years ago

It does allow nested calls, because each function has its own storage for the return address and local variables.

dbcurtis• 2 years ago

Nor reentrant. In machines where the JSR that stores the return address at the jump target, usually interrupts are locked for 1 following instruction so that you have a chance to load the return address into the accumulator. Back in the day I worked with a RTOS on one of those beasties.

kps• 2 years ago

On some systems, arguments were stored at the call site, typically immediately after the call instruction, where the callee could use the return address to find and skip over them. This made calls using constant arguments easy.

   CALL MUL
   2
   3
   BNE 6, FAIL

howerj4• 2 years ago

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.

anthk3• 2 years ago

I was about to talk about subleq, but it's damn difficult even to write a "Hello world".

howerj4• 2 years ago

Yeah, it really is a pain to do anything in it. I got around that by writing in another language instead as soon as possible. You can paper over many issues with a VM, although it will slow things down on such limited computers.

parlortricks2• 2 years ago

I came across your works learning and consuming all things Forth and Subleq. It was great to read over how you approach things. I wanted to purchase your book but Amazon says no...will there be another run?

howerj4• 2 years ago

Thanks! You should still be able buy it, you might have to either click on "Paperback" or "Hardcover", if you want to get the kindle edition you have to go to the Amazon webpage that serves you country (e.g. if you are in the UK and you are on amazon.com you get "This title is not currently available for purchase", but if you go to amazon.co.uk, you get buy it). That's an odd user interface issue...

bitwize• 2 years ago

EDIT: There were some BASIC interpreters which did this as well, implementing a VM and then targetting that instead.

The TI-99/4A had 256 bytes (128 words) of main, CPU-accessible RAM. Most of the base system's memory was video RAM, accessible by a relatively cumbersome process of poking and peeking registers on the system's video chip. The video chip maintained an autoincrementing current memory pointer, so successive reads (or writes) would bump the pointer by one allowing straightforward transfers of data, but the very fact that most of the system's memory was only accessible in this way made significant programs difficult to write. So, TI's solution was to create an abstract machine called GPL in which memory accesses to this video RAM were more natural. It was interpreted on the TMS9900 and therefore slower than native code, though -- especially given that the CPU can only access the video chip's RAM while the chip itself is not doing scanout to the display, so during horizontal and vertical retrace.

And since all the BASIC code and variables lived in this video memory, guess what the TI-99/4A's BASIC interpreter was written in! Yeah, it wasn't very fast, like at all.

The neat part, apropos of the article's topic, is that there were no actual general-purpose registers on the TMS9900: workspace registers WR0 through WR15 were instead located somewhere in memory, pointed to by the WP (workspace pointer) register. The CPU only had three physical registers: PC (program counter), WP, and a status register. What this amounted to was you could do a very primitive form of register windowing: by using the BLWP (Branch and Load WP) instruction, you can branch to a subroutine in which a new set of "registers" will be active elsewhere in memory -- and the return address will be saved in the new workspace.

If I'm going on about the TI-99/4A a lot recently, it's because I'm writing an assembler for it as a personal project.

snowAbstraction• 2 years ago

Interesting. For other readers, this is about an early 80s Texas Instruments computer and not a graphing calculator as I first thought.

weinzierl2• 2 years ago

"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.

Joel_Mckay15• 2 years ago

Most recursion is about as bad as goto coding methodologies.

Personally, I think it should be avoided in modern compiled languages too.

Haskell is fun to play around on, but it is horrific to consider using in a stable production environment. =)

autoexecbat• 2 years ago

Outside of a university course, if I see recursion in a non-FP language I consider it a code-smell

EdwardCoffin• 2 years ago

I'd recommend you read Guy Steele's blog post Why Object-Oriented Languages Need Tail Calls [1] and perhaps the essay by William Cook [2] and the discussion over on Lambda the Ultimate [3]

[1] https://web.archive.org/web/20091206042608/http://projectfor...

[2] https://www.cs.utexas.edu/~wcook/Drafts/2009/essay.pdf

[3] http://lambda-the-ultimate.org/node/3702

tome• 2 years ago

It's interesting because I love using Haskell in a stable production environment. In fact I'd hate to use anything else!

On the other hand, I almost never use naked recursion in Haskell. It typically do recursion indirectly through more familiar combinators such as for loops.

CyberDildonics13• 2 years ago

I agree. People love making things clever instead of making things done.

Recursion for iteration is just more complicated iteration. I've never seen a good argument for it in modern programming, it just ends up being the classic backwards rationalization of something people want to believe.

Recursion for traversing a tree is just using the call stack as a stack data structure.

Any balanced tree is never going to exceed 64 levels deep (really 48 on a 48 bit memory addressing cpu) and that could easily be put in a static array that gets used as a stack without recursing. This is easier to limit and debug.

twoodfin• 2 years ago

This limitation doesn’t just proscribe traditional recursive algorithms: Any reentrancy is impossible.

Your threads, co-routines, interrupt handlers, error handlers, all have to be careful not to stomp on someone else’s use of the same function, even if they’re not directly using a function recursively.

wglb5• 2 years ago

Yes, but you do need to handle local storage.

ginko• 2 years ago

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

elvis70• 2 years ago

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.

PaulHoule2• 2 years ago

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.

thadt• 2 years ago

Yes, C's stack usage can be unintuitive when working in a constrained environment, especially when accustomed to the affordances of desktop operating system. I once joined a project where several developers had spent a couple weeks trying to track really hard to pin down bugs in several subsystems they were developing in a microcontroller codebase. They would move things around and the bugs would move. After tracing things a bit and setting a trap, I found the places in the codebase where the call stack got too deep and was scribbling over other data structures.

JonChesterfield• 2 years ago

Putting a `out-of-stack? branch` check in every function prolog made an embedded chip programmed in C much nicer to work with. Cost a few instructions which was contentious but definitely a development aid.

PaulHoule2• 2 years ago

Recursion is a bad thing in embedded systems and generally overrated in CS pedagogy.

It can be useful in analyzing algorithms but often in cases like search it is a "second best" answer compared to say, using nondeterminism.

dhosek2• 2 years ago

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.

dhosek2• 2 years ago

(D’oh, not page 3, page one. Page 3 on the Apple ][ was reserved for & handlers and, IIRC page 2 was the input buffer.

not2b• 2 years ago

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.

caycep• 2 years ago

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

Ericson23142• 2 years ago

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

abhinavk• 2 years ago

Why? I feel he will able to write more.

Ericson23142• 2 years ago

I mean when he stops writing. Fair enough if he does it for fun afterwards.

JoeAltmaier2• 2 years ago

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.

wglb5• 2 years ago

In fact call was really jump-and-link(?)

Yes, technically "BALR" for Branch and Link Register. (I knew a guy who had been a 360 assembly language programmer who called his consulting firm BALR consulting, referring to that instruction.)

Interestingly, Gene Amdahl was asked why the 360 architecture didn't have a stack. "Too expensive" he said. I found this amusing at the time you could buy an 8085 for $5 retail quantity one. Perhaps he meant culturally expensive?

JoeAltmaier2• 2 years ago

The ol 360 used core memory if I recall. A stack would likely have meant, another whole cabinet on your computer room floor!

microtherion• 2 years ago

Jump and Link also carried over to POWER and PowerPC

benreesman• 2 years ago

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.

le-mark• 2 years ago

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.

tedunangst• 2 years ago

Just fixed size static buffers guaranteed to overflow.

froh3• 2 years ago

I remember having to preallocate an array and do manual stack management there. the old hands told me to 'simply' use a disk if I needed the stack (or heap) to be larger. with the mainframe VM these could then be virtual in the 1980s/1990s, 'for performance'

stackless Cobol really did fun things to brains on long term exposure.

HeyLaughingBoy3• 2 years ago

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.

Sponge5• 2 years ago

You should be proud of it, I can't even begin to think about programming with these constraints, and I work in embedded.

billforsternz• 2 years ago

That is very cool and I say that as someone whose first project in my first job (1982) was to write the code for a serial multiplexer with a Z80, a 2716 EPROM, Zilog SIOs (or maybe DUARTs actually).... and 2K of static RAM. I basically learned my craft on the job and there's no way I could have done it without the RAM. A few years later I would have relished the challenge. Although you are really limiting the complexity of the protocol you can deal with ... (perhaps not such a terrible thing:).

ChrisMarshallNY• 2 years ago

Writing code for the old Mac serial chip was an adventure.

I wrote a MIDI driver once, and that required dividing a 1MHz external clock, to get the 62.5KHz (I think) serial clock (you couldn’t divide the internal clock).

Their chip had 8 control lines, with each line controlling some aspect of the chip operation. They set it up as the lower 8 bits of the 16-bit address bus, with the upper 8 bits fixed (so you were working with 256 addresses, to control the chip).

So just referencing an address would change the state of the chip.

A lot of hardware limitations influenced software structure, and I’ll bet that a lot of software proclivities have their genesis in weird hardware compromises (like bytes).

smcin2• 2 years ago

'2716 EPROM' was a 16K (2kb x 8) EPROM.

Which customer/sector was your project intended for?

mytailorisrich• 2 years ago

Yes, the xx(x) number in the 27xx(x) EPROM series indicates the kilo (1024) bits. So indeed this is 2 KiB. This sounds OK for the application described, especially as it was no doubt written in assembly and obviously bare metal. When it does not fit but not far off it's when the fun of code optimisation kicks in ;)

Edit: Very interesting how easily available they still seem to be according to Google.

HeyLaughingBoy3• 2 years ago

Don't remember. I do remember that I didn't get paid.

I was so excited to have a freelance job (don't remember how I got the customer either) that I jumped right into it and worked heads down for a couple weeks. Then when I went to tell the customer that I was done and ready to ship, I couldn't reach him. Finally heard back from him about 6-12 months later and he was surprised that I had been working on it without hearing back from him and that he no longer needed the product.

And that, kids, is how I learned to get at least partial payment upfront.

RiverCrochet• 2 years ago

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 fascinated by the fact the Signetics 2650 that had an 8-byte internal stack.

HeyLaughingBoy3• 2 years ago

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

greesil• 2 years ago

It's not ancient if you still do embedded development

dnedic• 2 years ago

It really depends on what you classify under embedded. Everything more expensive than a Padauk or newer than PIC will have hardware support for the stack, and also most likely have the heap provided by newlib.

monocasa• 2 years ago

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.

wglb5• 2 years ago

As did the IBM 1800 and IBM 1130 and many machines of that era. Machines such as the Xerox Sigma series had enough registers to avoid this practice.

drfuchs• 2 years ago

Way back in 1956, Librascope's LGP-30 had an "R" instruction ("store Return address") that stored (already-incremented)PC+1 into the address portion of the instruction at the destination, which was by convention an unconditional branch just in front of the beginning of a subroutine. You'd follow the "R" instruction with a "U" (unconditional branch) to that subroutine. The subroutine would return by branching to the address just in front of it, which conveniently was an unconditional branch back to just after the call location. So, recursion was out of the question unless you used some more advanced calling convention. (And all opcodes in assembly language were a single letter.)

bsder• 2 years ago

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.

deanCommie• 2 years ago

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?

hollowturtle• 2 years ago

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

tombert• 2 years ago

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.

wglb5• 2 years ago

Yes, instruction sets these days are significantly more useful.

To do recursion in those old machines, one would need to build your own stack mechanism, but there would still be issues to take care of, as there was no native way to use anything but global storage.

Having lived through those times, I don't wish them on anyone.

taeric2• 2 years ago

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.

mr_toad2• 2 years ago

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

froh3• 2 years ago

wait what? you're right! 386 came 1985, 45 years later is 2030

now I feel old

Tabular-Iceberg2• 2 years ago

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.

gumby• 2 years ago

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.

wglb5• 2 years ago

While those are of the same era, the goto issue was its own whole issue, generally referring to goto statements in a give block of code, and not talking about subroutines.

While this, as you note, often led to mass refusal to use a goto, the effect of the paper led to much discussion and presaged the practice of much better control flow constructs in languages.

derefr2• 2 years ago

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.

63stack• 2 years ago

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.

justinlloyd• 2 years ago

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.

mikewarot• 2 years ago

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.

rep_lodsb2• 2 years ago

Similar with PC BIOSes from before x86 CPUs got internal cache. The DRAM wasn't usable until it was properly set up (refresh, and possibly timing parameters on later chipsets).

One trick I've seen in BIOS code is basically return-oriented programming[1]: before a "call", the stack pointer is set to some location in ROM containing one or more return addresses. The advantage over putting the return address itself in some register is that this way, it can use subroutines ending in a normal RET instruction, that might also be called later when there is an actual stack.

[1] https://en.wikipedia.org/wiki/Return-oriented_programming

mark-r2• 2 years ago

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.

pmontra• 2 years ago

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 is storing the return address of GOSUB.

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.

dspillett2• 2 years ago

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).

pugworthy• 2 years ago

GOSUB definitely popped into my mind too. Nice to see the other reply that goes into a bit more detail and the part about showing the "stack" in screen-memory.

guenthert• 2 years ago

"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.

mauricioc• 2 years ago

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.

matja• 2 years ago

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

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

Wowfunhappy2• 2 years ago

How did you call a function if you didn’t have a stack for the return address or local variables? Here’s how it worked. 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. It also defined a secret global variable for each of the function’s local variables.

I always assumed that functions did something like this behind the scenes. At the lowest level, all of memory is just a very large, globally-accessible array of numbers. Functions are just JMPs with fancy syntax sugar.

...is that completely wrong? Do modern computers actually have some type of hardware support for functions?

rep_lodsb2• 2 years ago

Yes they do. Depending on the architecture, there's either a stack pointer register and CALL/PUSH/POP instructions, or a general purpose auto-increment/decrement addressing mode.

Local variables are placed on the stack as well, this is necessary if you want recursion, and it also typically results in faster/shorter code, because the instruction set and microarchitecture are optimized for this type of memory access.

Wowfunhappy2• 2 years ago

Thank you!

yencabulator• 2 years ago

And if you were really fancy, you wrote a custom allocator that operated on that fixed-size buffer so people could “allocate” and “free” memory from the buffer.

That's still what current day allocators are.

Think of RAM as just a byte array in your favorite systems programming language. It's size is that fixed-size buffer (or, when RAM size is unknown due to hardware modularity, its size is the maximum possible and you pinky-promise not to look beyond the end).

The kernel sees all of the RAM as a fixed-size buffer, and an allocator manages what's free etc. These days, userspace processes see virtual addresses and you can think of them as all getting 2*64 bytes as their "fixed-size buffer". brk and mmap are really more hints to the kernel as to what part of the buffer you won't be needing.

taneq• 2 years ago

I don't feel like this is quite the right way to look at it. Computers don't have stacks and heaps, software has stacks and heaps. Of course, in recent times there are built-in CPU instructions that do memory management and whatnot, but that's not the point. Give a programmer a Turing-complete machine and enough time to play with it and, while elegance and efficiency will vary with the underlying architecture, they (on that machine) will have stacks, heaps, and any other computable thing they wanted.

I first learned to program on a calculator in a kneecapped version of BASIC which didn't support recursion, function calls, user defined variables (you got 'A' to 'Z' and that was all) or dynamic memory management (other than resizing 'matrices' and 'lists' iirc). I wanted to write Minesweeper on it and to do so I independently invented what I later found out were well know as depth first search and breadth first search, using just some loops and a list as a stack. (I was a kid and we didn't really have the internet yet. :P )

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

Related Stories