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

161–170 of 241 posts

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

#161

Post by jcgrillo »

naasking wrote: post #153
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…

I think you're overthinking it. Here are probably the people who need to worry about recursion depth: embedded developers working with limited memory, and developers working on data systems that process huge data sets (and even this is debatable as stack growth is log n with these tree data structures). My process for deciding when to use iteration or recursion is simple: if each step needs to keep context then use r…

> I think you're overthinking it

Quite likely :)

> And an oft-ignored factor is the cleanup advantages of allocating on the stack, which offsets any space and time disadvantages you might see with recursion.

This is a very good point.

Alright, you've convinced me to start playing with recursion again. Just not in java or python.

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

#162

Post by bitwize »

howerj wrote: post #15

I wrote a Forth interpreter for a SUBLEQ machine ( https://github.com/howerj/subleq ), and for a bit-serial machine ( https://github.com/howerj/bit-serial ), both of which do not have a function call stack which is a requirement of Forth. SUBLEQ also does not allow indirect loading and stores as well and requires self-modifying code to do anything non-trivial. The approach I took for both machines was to build a virt…

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

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

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

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

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

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

#163

Post by froh »

le-mark wrote: post #72

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.

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.

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

#164

Post by froh »

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

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

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

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

now I feel old

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

#165

Post by sham1 »

CyberDildonics wrote: post #108
samatman wrote: post #74

Earlier quoted context omitted.

The same argument suggests that a recursive stack traversal will never consume more than 64 stack frames, so consuming stack frames is no reason not to use a recursive function. It's just as easy to limit recursion depth, if you need to, just pass along a counter and check it. I haven't found that hand-rolling a second stack, instead of using the program stack, is easier to debug, the opposite if anything, but your m…

so consuming stack frames is no reason not to use a recursive function. Saving stack memory isn't the point (even though a static array definitely does, because instead of multiple pointers and variables on the stack it only would have to store the node index of a tree). The point is that you can see the whole stack and all the data that you're using at one time in a debugger instead of trying switch through call sta…

Well, it's still recursion whether you're using the call stack or are using an explicit stack structure. You're still breaking the problem down into smaller subproblems inductively. I feel that people focus on the wrong things when talking about recursion, focusing on the aspect of having a function calling itself instead of the idea of having the problem solved by way of breaking it down into smaller problems.

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

#166

Post by fuzztester »

dragontamer wrote: post #6

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

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

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

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

#167

Post by pmontra »

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.

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

#168

Post by Aardwolf »

munificent wrote: post #34
autoexecbat wrote: post #24

Earlier quoted context omitted.

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

This opinion is totally wild to me. Do you never work with tree data structures? I can't think of a non-trivial program I've written in the past two decades that didn't have some recursive tree traversal in it.

> Do you never work with tree data structures?

Yes, you can use std::vector or array or similar as a stack, without using recursion (which has some easily reachable depth limit that is much smaller than what your full RAM memory allows, especially in e.g. JS)

Of course ideally programming languages would figure out a way to not have this reachable limit and allow as much recursion as your RAM allows... We're still in the ancient world when it comes to this, it seems

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

#169

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.

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.

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

#170

Post by guenthert »

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

Post reply on HN