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

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

devblogs.microsoft.com

Post reply on HN
Print view View original

141–150 of 241 posts

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

#141

Post by wglb »

JoeAltmaier wrote: post #61

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…

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

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

#142

Post by kazinator »

1letterunixname wrote: post #131
kazinator wrote: post #11

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 BIN…

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.

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.

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

#143

Post by furyofantares »

jcgrillo wrote: post #134
naasking wrote: post #120

Earlier quoted context omitted.

> Recursion in production code is bad news, because you can't control the depth of your call tree. Of course you can, if you wanted to , just like you can control the iteration count of a loop. It's not even hard. This is simply a non-issue. Some algorithms are much more naturally expressed recursively and writing the imperative equivalent with manual stack handling is just annoying. Stack growth is just something yo…

> This is simply a non-issue. Well, it's about the tradeoffs right? If I have a recursive algorithm that's growing the stack (assuming no TCO, because few languages people actually use in production support it) I'm trading execution time, space, and reliability for economy of expression. In reverse order: - reliability: if, as you suggest, I implement some hard depth limit (which is necessary because all the processe…

They were referring to algorithms that need to use that much space either way and where the alternative is maintaining your own stack.

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

#144

Post by mr_toad »

taeric wrote: post #121

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

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

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

#145

Post by mr_toad »

gigel82 wrote: post #7

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

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

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

#146

Post by jcgrillo »

furyofantares wrote: post #143
jcgrillo wrote: post #134

Earlier quoted context omitted.

> This is simply a non-issue. Well, it's about the tradeoffs right? If I have a recursive algorithm that's growing the stack (assuming no TCO, because few languages people actually use in production support it) I'm trading execution time, space, and reliability for economy of expression. In reverse order: - reliability: if, as you suggest, I implement some hard depth limit (which is necessary because all the processe…

They were referring to algorithms that need to use that much space either way and where the alternative is maintaining your own stack.

Even in that case there's a tradeoff, if that stack needs to be large you can maintain it on the heap. Now you can do that to some extent with either a recursive implementation or not of course, but it's still a matter of deciding which is the better approach. It's not simply the case that "you can always just use recursion and it'll be totally fine mostly".

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

#147

Post by EnigmaFlare »

naasking wrote: post #120
mannyv wrote: post #71

Earlier quoted context omitted.

Recursion in production code is bad news, because you can't control the depth of your call tree. At some point you will crash because the runtime won't be able to allocate any more stack. And you can't preflight it because if you could preflight it you wouldn't be doing recursion. Recursion is a nice toy, but in real life it's a ticking time bomb.

> Recursion in production code is bad news, because you can't control the depth of your call tree. Of course you can, if you wanted to , just like you can control the iteration count of a loop. It's not even hard. This is simply a non-issue. Some algorithms are much more naturally expressed recursively and writing the imperative equivalent with manual stack handling is just annoying. Stack growth is just something yo…

That sounds awfully complicated modifying a recursive algorithm to control the recursion depth. By that, I mean, if sometimes the data happens to be a very deep unbalanced tree that would cause a stack overflow with a naive recursive algorithm, you detect that situation and make it work. Isn't that much harder than just using your own stack (from a library/framework)?

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

#148

Post by ChrisMarshallNY »

billforsternz wrote: post #103
HeyLaughingBoy wrote: post #77

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

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 complex…

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

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

#149

Post by derefr »

shadowgovt wrote: post #98
masfuerte wrote: post #94

Earlier quoted context omitted.

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

emacs still does this IIUC. The beating heart of the emacs edit model is a "gap buffer" at the cursor. There's a neat compare-and-contrast someone did awhile back on the gap buffer approach vs. the other approach often taken for code IDEs ("ropes"). The tl;dr is that gap buffers are actually really performant for a lot of cases except for having to edit at a lot of randomly-chosen cursor points far apart from each ot…

> except for having to edit at a lot of randomly-chosen cursor points far apart from each other (but how often is that your use case?)

I use Sublime, and pretty often I do a "Find All" for some term; then Multiselect (Cmd+L); then select from cursor (Shift+RightArrow); and then type something. Which is essentially "editing at a lot of randomly [or at least arbitrarily]-chosen cursor points."

That, and IIRC Sublime actually does its "Find and Replace All" operation, as essentially this same multicursor-select-and-type operation internally. (If you have a large-enough buffer open, you can see it gradually doing it!)

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

#150

Post by derefr »

Funny enough, I was forced to program in exactly this way, when I was first learning to program. But not in the 1970s... in the year 2001!

Why? Because my first exposure to programming was the semi-graphical scripting "language" exposed by the game-development tool "RPG Maker 2000."

For those who haven't seen RM2K scripting before: picture a cross between Scratch and Emacs Paredit mode. (E.g. https://forums.rpgmakerweb.com/data/attachments/21/21958-f89...) It's presented as textual, but you can't edit it like text — only as blocks with associated properties dialogs.

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

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

---

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

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

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

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

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

Post reply on HN