13 ms·

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

473 points by signa11 3y ago

082349872349872 3y ago
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 3y 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?
  - shadowgovt 3y 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.
- kstrauser 3y 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 3y 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
    - Joker_vD 3y ago
      > A hammer cannot become a screwdriver. Don't tell me you've never hammered a screw into a wooden plank? Vice versa, a screwdriver also can be used as a hammer although a quite pathetic one.
    - kstrauser 3y ago
      I see zero benefit in having artificial functionality limitations. In my hypothetical example, imagine that `sed 's/foo/bar/'` works but `sed 's/foo/bark/'` does not because it's 1 character too long. There's not a plausible scenario where that helps me. You wouldn't want to expand sed to add a fullscreen text editor because that's outside its scope. Within its scope, limitations only prevent you from using it where you need it. It would be more like a hammer that cannot be made to hammer 3 inch nails because it has a hard limit of 2.5 inches. Those are the kinds of limits GNU wanted to remove. Why use a fixed-length buffer when you can alloc() at runtime? It doesn't mean that `ls` should send email.
- lenerdenator 3y ago
  Really, the mistake was letting humans provide input to computer programs.
  - layer8 3y ago
    In particular input to assemblers, compilers, and interpreters.
    - 082349872349872 3y ago
      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.
      - blueflow 3y ago
        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" ?
        082349872349872 3y ago
        Yes. (well: tell me the entire symtab when you are done, but you probably could've guessed that)
      - kragen 3y ago
        i seem to recall you wrote a sort of 16-bit assembler in machine code consisting entirely of printable ascii, except for a couple of places where it had to use printable ascii instructions to modify itself to add instructions like int 21 that couldn't be done that way. but that was a different one, wasn't it?
        082349872349872 3y ago
01HNNWZ0MV43FF 3y ago
This was posted yesterday
joeatwork 3y 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-into-programming-a-comedy-of-errors-3/ https://vanemden.wordpress.com/2014/06/18/how-recursion-got-...
- robocat 3y ago
  Definitely "a tale of intrigue, betrayal, and advanced programming-language semantics"
- dang 3y ago
  Related: How recursion got into programming: intrigue, betrayal, and advanced semantics - https://news.ycombinator.com/item?id=33123916 https://news.ycombinator.com/item?id=33123916 - Oct 2022 (8 comments) How Recursion Got into Programming (2014) - https://news.ycombinator.com/item?id=23061881 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 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 https://news.ycombinator.com/item?id=8073361 - July 2014 (108 comments)
dragontamer 3y 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 3y 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 3y 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!
    - andrewshadura 3y ago
      FYI, he's D. R. Hipp, not Dr. Hipp.
      - jcgrillo 3y ago
        More like Dr. D. R. Hipp, actually.
gigel82 3y 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...
- glhaynes 3y ago
  I’m no grammarian but I think it should have a comma after “world”.
  - tinier_subsets 3y ago
    [dead]
- ivanjermakov 3y ago
  Me too clicked the link expecting stories of heap and stack uses before computers.
- deleted 3y ago
  [deleted]
- grraaaaahhh 3y ago
  Yeah, I was all ready to learn about how the ancient Egyptians used stacks to build the pyramids or something.
  - nerpderp82 3y ago
    Technically they did.
- trealira 3y ago
  I was expecting some ancient Greek algorithms that used stacks or priority queues, haha.
- dfxm12 3y 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.
kazinator 3y 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/ https://www.kylheku.com/cgit/egawk/about/
- 1letterunixname 3y 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.
  - kazinator 3y 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 3y 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.
  - kazinator 3y 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.
weinzierl 3y 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 3y ago
  It does allow nested calls, because each function has its own storage for the return address and local variables.
- dbcurtis 3y 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 3y 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
howerj 3y ago
I wrote a Forth interpreter for a SUBLEQ machine (https://github.com/howerj/subleq https://github.com/howerj/subleq), and for a bit-serial machine (https://github.com/howerj/bit-serial 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.
- anthk 3y ago
  I was about to talk about subleq, but it's damn difficult even to write a "Hello world".
  - howerj 3y 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.
    - anthk 3y ago
      How does muxleq work? It looks like a 'concurrent' subleq...
      - howerj 3y ago
        I am not sure what you mean by concurrent in this case, muxleq is just subleq with one extra instruction. The extra instruction is based off of multiplexing (see https://en.wikipedia.org/wiki/Multiplexer https://en.wikipedia.org/wiki/Multiplexer). Subleq as you know is incredibly inefficient, muxleq is an experiment to add a single instruction to Subleq in order to greatly improve its efficiency. The `mux` instruction added computes: m[operand2] = (m[operand1] & ~selector) | (m[operand2] & selector) As multiplexing is a universal gate (so long as you have access to true and false as constants) you can use this to calculate AND/OR/XOR, which are very expensive to do in a pure Subleq machine. It also means you can do a MOV in a single instruction instead of four (set the `selector` to zero in this case). This in turns speeds up indirect loads and stores.
weinzierl 3y 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_Mckay 3y 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 3y ago
    Outside of a university course, if I see recursion in a non-FP language I consider it a code-smell
    - mikepurvis 3y ago
      The only time I ever do it is for tree walking, and then it's always a private internal function, so like: def process_that_tree(my_tree): def _handle(node): # do the things for child in node.children: _handle(child) _handle(my_tree.root) The processing can even be brought outside sometimes, or the walker can just become a generator, yielding nodes out to a regular loop doing the actual work. Either way, the recursive part is kept very minimal and easy to reason about. Obviously for the filesystem these kinds of abstractions exist already in shutil/pathlib/glob, but it still can have a place for dealing with other kinds of hierarchies, like a package dependency tree or the like.
    - II2II 3y ago
      While I am not a fan of recursion, the call stack that enables it sounds infinitely better than statically allocating space for parameters and return values. Besides, it makes some algorithms clearer. That is certainly useful in learning environments, including early academic research.
ginko 3y ago
If you write a GPU shader in most graphics APIs today you will also not have a stack or heap.
deleted 3y ago
[deleted]
elvis70 3y 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.
PaulHoule 3y 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 3y 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 3y 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.
  - PaulHoule 3y 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.
dhosek 3y 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.
- dhosek 3y 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 3y 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 3y ago
the headline reminded me of "ancient computers" in sci fi games, which was essentially a tower of Hanoi problem inmplemented in-game
Ericson2314 3y ago
Whenever Raymond Chen retires, I am going to be really sad.
- abhinavk 3y ago
  Why? I feel he will able to write more.
  - Ericson2314 3y ago
    I mean when he stops writing. Fair enough if he does it for fun afterwards.
JoeAltmaier 3y 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.
- wglb 3y 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?
  - JoeAltmaier 3y 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 3y ago
  Jump and Link also carried over to POWER and PowerPC
benreesman 3y 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 3y 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 3y ago
  Just fixed size static buffers guaranteed to overflow.
- froh 3y 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.
TheRealNGenius 3y ago
[dead]
HeyLaughingBoy 3y 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 3y 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 3y 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 3y 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).
greesil 3y ago
It's not ancient if you still do embedded development
- dnedic 3y 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 3y 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.
- wglb 3y 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 3y 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 3y 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 3y 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 3y 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
taneq 3y 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 )
tombert 3y 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.
- wglb 3y 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.
- deleted 3y ago
  [deleted]
taeric 3y 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_toad 3y ago
  In ten years or so all the people who worked on machines without preemptive multitasking will be retired.
  - froh 3y ago
    wait what? you're right! 386 came 1985, 45 years later is 2030 now I feel old
    - Narishma 3y ago
      Why the 386? You could do preemptive multitasking on a 286 or even an 8088.
      - froh 3y ago
        without MMU you have to trust your tasks, but yes technically all you need is timed interrupts. so if you go the no mmu route, you could even list 6502 and z80, as in "I rarely do multithreading, but if I do I do it without MMU" ;-) or at least have an MPU, which is what some microcontrollers have to protect multitasking.
  - Tabular-Iceberg 3y 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 3y 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.
- wglb 3y 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.
derefr 3y 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-f8978e9d268a8359ef8547ff5736de90.jpg 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/ 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 3y 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 3y 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 3y 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_lodsb 3y 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 https://en.wikipedia.org/wiki/Return-oriented_programming
mark-r 3y 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 3y 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.
- dspillett 3y 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 3y 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 3y 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 3y 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 3y ago
> This would be transformed by the compiler into something like this: Even modern C compilers for "modern" 8051-derived MCUs work like this :)
Wowfunhappy 3y 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_lodsb 3y 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.
  - Wowfunhappy 3y ago
    Thank you!
yencabulator 3y 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.

473 points by signa11 3y ago

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 3y 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?
- shadowgovt 3y 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.
kstrauser 3y 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 3y 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
  - Joker_vD 3y ago
    > A hammer cannot become a screwdriver. Don't tell me you've never hammered a screw into a wooden plank? Vice versa, a screwdriver also can be used as a hammer although a quite pathetic one.
  - kstrauser 3y ago
    I see zero benefit in having artificial functionality limitations. In my hypothetical example, imagine that `sed 's/foo/bar/'` works but `sed 's/foo/bark/'` does not because it's 1 character too long. There's not a plausible scenario where that helps me. You wouldn't want to expand sed to add a fullscreen text editor because that's outside its scope. Within its scope, limitations only prevent you from using it where you need it. It would be more like a hammer that cannot be made to hammer 3 inch nails because it has a hard limit of 2.5 inches. Those are the kinds of limits GNU wanted to remove. Why use a fixed-length buffer when you can alloc() at runtime? It doesn't mean that `ls` should send email.
lenerdenator 3y ago
Really, the mistake was letting humans provide input to computer programs.
- layer8 3y ago
  In particular input to assemblers, compilers, and interpreters.
  - 082349872349872 3y ago
    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.
    - blueflow 3y ago
      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" ?
      - 082349872349872 3y ago
        Yes. (well: tell me the entire symtab when you are done, but you probably could've guessed that)
    - kragen 3y ago
      i seem to recall you wrote a sort of 16-bit assembler in machine code consisting entirely of printable ascii, except for a couple of places where it had to use printable ascii instructions to modify itself to add instructions like int 21 that couldn't be done that way. but that was a different one, wasn't it?
      - 082349872349872 3y ago

01HNNWZ0MV43FF 3y ago

This was posted yesterday

joeatwork 3y 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-into-programming-a-comedy-of-errors-3/ https://vanemden.wordpress.com/2014/06/18/how-recursion-got-...

robocat 3y ago
Definitely "a tale of intrigue, betrayal, and advanced programming-language semantics"
dang 3y ago
Related: How recursion got into programming: intrigue, betrayal, and advanced semantics - https://news.ycombinator.com/item?id=33123916 https://news.ycombinator.com/item?id=33123916 - Oct 2022 (8 comments) How Recursion Got into Programming (2014) - https://news.ycombinator.com/item?id=23061881 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 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 https://news.ycombinator.com/item?id=8073361 - July 2014 (108 comments)

dragontamer 3y 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 3y 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 3y 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!
  - andrewshadura 3y ago
    FYI, he's D. R. Hipp, not Dr. Hipp.
    - jcgrillo 3y ago
      More like Dr. D. R. Hipp, actually.

gigel82 3y 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...

glhaynes 3y ago
I’m no grammarian but I think it should have a comma after “world”.
- tinier_subsets 3y ago
  [dead]
ivanjermakov 3y ago
Me too clicked the link expecting stories of heap and stack uses before computers.
deleted 3y ago
[deleted]
grraaaaahhh 3y ago
Yeah, I was all ready to learn about how the ancient Egyptians used stacks to build the pyramids or something.
- nerpderp82 3y ago
  Technically they did.
trealira 3y ago
I was expecting some ancient Greek algorithms that used stacks or priority queues, haha.
dfxm12 3y 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.

kazinator 3y 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/ https://www.kylheku.com/cgit/egawk/about/

1letterunixname 3y 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.
- kazinator 3y 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 3y 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.
- kazinator 3y 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.

weinzierl 3y 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 3y ago
It does allow nested calls, because each function has its own storage for the return address and local variables.
dbcurtis 3y 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 3y 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

howerj 3y ago

I wrote a Forth interpreter for a SUBLEQ machine (https://github.com/howerj/subleq https://github.com/howerj/subleq), and for a bit-serial machine (https://github.com/howerj/bit-serial 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.

anthk 3y ago
I was about to talk about subleq, but it's damn difficult even to write a "Hello world".
- howerj 3y 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.
  - anthk 3y ago
    How does muxleq work? It looks like a 'concurrent' subleq...
    - howerj 3y ago
      I am not sure what you mean by concurrent in this case, muxleq is just subleq with one extra instruction. The extra instruction is based off of multiplexing (see https://en.wikipedia.org/wiki/Multiplexer https://en.wikipedia.org/wiki/Multiplexer). Subleq as you know is incredibly inefficient, muxleq is an experiment to add a single instruction to Subleq in order to greatly improve its efficiency. The `mux` instruction added computes: m[operand2] = (m[operand1] & ~selector) | (m[operand2] & selector) As multiplexing is a universal gate (so long as you have access to true and false as constants) you can use this to calculate AND/OR/XOR, which are very expensive to do in a pure Subleq machine. It also means you can do a MOV in a single instruction instead of four (set the `selector` to zero in this case). This in turns speeds up indirect loads and stores.

weinzierl 3y 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_Mckay 3y 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 3y ago
  Outside of a university course, if I see recursion in a non-FP language I consider it a code-smell
  - mikepurvis 3y ago
    The only time I ever do it is for tree walking, and then it's always a private internal function, so like: def process_that_tree(my_tree): def _handle(node): # do the things for child in node.children: _handle(child) _handle(my_tree.root) The processing can even be brought outside sometimes, or the walker can just become a generator, yielding nodes out to a regular loop doing the actual work. Either way, the recursive part is kept very minimal and easy to reason about. Obviously for the filesystem these kinds of abstractions exist already in shutil/pathlib/glob, but it still can have a place for dealing with other kinds of hierarchies, like a package dependency tree or the like.
  - II2II 3y ago
    While I am not a fan of recursion, the call stack that enables it sounds infinitely better than statically allocating space for parameters and return values. Besides, it makes some algorithms clearer. That is certainly useful in learning environments, including early academic research.

ginko 3y ago

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

deleted 3y ago

[deleted]

elvis70 3y 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.

PaulHoule 3y 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 3y 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 3y 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.
- PaulHoule 3y 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.

dhosek 3y 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.

dhosek 3y 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 3y 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 3y ago

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

Ericson2314 3y ago

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

abhinavk 3y ago
Why? I feel he will able to write more.
- Ericson2314 3y ago
  I mean when he stops writing. Fair enough if he does it for fun afterwards.

JoeAltmaier 3y 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.

wglb 3y 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?
- JoeAltmaier 3y 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 3y ago
Jump and Link also carried over to POWER and PowerPC

benreesman 3y 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 3y 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 3y ago
Just fixed size static buffers guaranteed to overflow.
froh 3y 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.

TheRealNGenius 3y ago

[dead]

HeyLaughingBoy 3y 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 3y 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 3y 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 3y 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).

greesil 3y ago

It's not ancient if you still do embedded development

dnedic 3y 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 3y 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.

wglb 3y 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 3y 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 3y 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 3y 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 3y 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

taneq 3y 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 )

tombert 3y 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.

wglb 3y 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.
deleted 3y ago
[deleted]

taeric 3y 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_toad 3y ago
In ten years or so all the people who worked on machines without preemptive multitasking will be retired.
- froh 3y ago
  wait what? you're right! 386 came 1985, 45 years later is 2030 now I feel old
  - Narishma 3y ago
    Why the 386? You could do preemptive multitasking on a 286 or even an 8088.
    - froh 3y ago
      without MMU you have to trust your tasks, but yes technically all you need is timed interrupts. so if you go the no mmu route, you could even list 6502 and z80, as in "I rarely do multithreading, but if I do I do it without MMU" ;-) or at least have an MPU, which is what some microcontrollers have to protect multitasking.
- Tabular-Iceberg 3y 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 3y 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.

wglb 3y 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.

derefr 3y 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-f8978e9d268a8359ef8547ff5736de90.jpg 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/ 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 3y 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 3y 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 3y 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_lodsb 3y 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 https://en.wikipedia.org/wiki/Return-oriented_programming

mark-r 3y 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 3y 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.

dspillett 3y 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 3y 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 3y 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 3y 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 3y ago

> This would be transformed by the compiler into something like this: Even modern C compilers for "modern" 8051-derived MCUs work like this :)

Wowfunhappy 3y 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_lodsb 3y 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.
- Wowfunhappy 3y ago
  Thank you!

yencabulator 3y 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.