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

81–90 of 241 posts

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

#81

Post by howerj »

anthk wrote: post #79
howerj wrote: post #67

Earlier quoted context omitted.

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.

How does muxleq work? It looks like a 'concurrent' subleq...

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

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

#82

Post by tanelpoder »

Retr0id wrote: post #16
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…

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

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

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

#83

Post by klyrs »

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.

I think there are a lot of web devs here who never do anything more complicated than process data in a loop, and complexity analysis can be accomplished by counting indentation levels. When this viewpoint is applied with a wide brush to all programmers or the whole practice of programming, it results in some pretty spicy takes.

On the other hand, recursion extremely expensive in some languages and Python has a notorious limit that forces library writers to roll their own stack. So despite the above, I'm actually in the anti-recursion camp.

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

#84

Post by josephg »

mannyv wrote: post #71
munificent wrote: post #34

Earlier quoted context omitted.

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.

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.

If you're using some sort of balanced tree (red-black, AVL or a b-tree of some sort), the depth of the tree is guaranteed to be log(n) where n is the number of items. If you recursively descend down the tree, the number of stack frames involved will never exceed the height of the tree.

If you have a binary tree with 1 billion elements, the depth will be 20. In a b-tree with a reasonable node width (eg 16), assuming 50% occupancy the depth will be about 8.

This is, in practice, totally fine. You won't exhaust your stack traversing a balanced tree.

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

#85

Post by josephg »

Arnavion wrote: post #40
munificent wrote: post #34

Earlier quoted context omitted.

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.

Tree traversal uses stacks / queues unless you're dealing with a small tree such that you're sure recursion won't blow your stack, or your algorithm can work with tail calls and your language guarantees TCO.

Any balanced tree will be shallow enough that this isn't a problem in practice. You'll run out of RAM / hard disk space to store your tree before you run out of stack space.

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

#86

Post by Sponge5 »

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…

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

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

#87

Post by monocasa »

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

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

#88

Post by bsder »

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.

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

#89

Post by yongjik »

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…

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

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

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

#90

Post by tedunangst »

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.

Just fixed size static buffers guaranteed to overflow.
Post reply on HN