Subroutine calls in the ancient world, before computers had stacks or heaps • Hacker News Board

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

#111

Post by suncherta » Wed, Apr 03, 2024, 9:37 PM UTC

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…

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

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

#112

Post by dang » Wed, Apr 03, 2024, 9:41 PM UTC

joeatwork wrote: post #5

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

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

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

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

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

#113

Post by tombert » Wed, Apr 03, 2024, 9:42 PM UTC

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.

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

#114

Post by CyberDildonics » Wed, Apr 03, 2024, 10:03 PM UTC

agumonkey wrote: post #93

CyberDildonics wrote: post #68

Earlier quoted context omitted.

I agree. People love making things clever instead of making things done. Recursion for iteration is just more complicated iteration. I've never seen a good argument for it in modern programming, it just ends up being the classic backwards rationalization of something people want to believe. Recursion for traversing a tree is just using the call stack as a stack data structure. Any balanced tree is never going to exce…

To my poor eyes it's creating self sustaining computing blocks. You could recurse using an explicit stack or use tiny function that will thread themselves as see fit. In a way it's more encapsulating than languages preaching encapsulation.

Are you saying recursion creates "self sustaining computing blocks" ? What does that mean and how does it do it?

that will thread themselves as see fit.*

What does this mean?

In a way it's more encapsulating than languages preaching encapsulation.

Recursion does this? Are you talking about not depending on a stack structure in this specific instance or something else?

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

#115

Post by munificent » Wed, Apr 03, 2024, 10:15 PM UTC

Joel_Mckay wrote: post #107

munificent wrote: post #96

Earlier quoted context omitted.

This is just bananas. I work in programming languages. I currently have open in my editor a code formatter that I maintain that uses at least half a dozen recursive algorithms to traverse syntax trees and other data structures. This program is used by almost every user of our language, invoked on every save, and probably executed billions of times a day. Recursion is fine .

"Recursion is fine [for your use-case]." In general it is naive, often dangerous, and an inefficient space/time trade-off. I have been writing software for several decades... does that make one less insightful or more biased? https://youtu.be/pmu5sRIizdw?feature=shared&t=31 =)

If you're going to make a generalization, I think recursion is fine, efficient, and rarely dangerous.

There may be use cases where it's insecure or has performance concerns, but those are the exception. Most of the time, it's fine.

We don't generally tell programmers that loops are naive, often dangerous, and risk locking up the program. They certainly can, but most just... don't.

Just like loops, recursion can make code much simpler to write, read, and maintain. Every modern language under the sun supports it for very good reasons. Use it.

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

#116

Post by cerved » Wed, Apr 03, 2024, 10:18 PM UTC

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…

seems like Vim does too

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

#117

Post by swatcoder » Wed, Apr 03, 2024, 10:19 PM UTC

mywittyname wrote: post #105

deckard1 wrote: post #38

Earlier quoted context omitted.

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

Imagine using a program that can only allocate 4GB of ram because it has 32-bit address space. There's no benefit to that limitation, it's an arbitrary limit imposed by the trades-offs made in the 80s. It just means that someone will need to build another layer to their program to chunk their input data then recombine the output. It's a needless waste of resources. The benefit of not having a limitation is that the r…

> Imagine using a program that can only allocate 4GB of ram because it has 32-bit address space. There's no benefit to that limitation

You're looking at isolated parts of a system. In a system, an artificial "limit" in one component becomes a known constraint that other components can leverage as part of their own engineering.

In the example of memory addresses, it might be "artificial" to say that a normal application can only use 32-bit or 48-bit addresses when the hardware running the application operates in 64-bits, but this explicit constraint might enable (say) a runtime or operating system to do clever things with those extra bits -- security, validation, auditing, optimization, etc.

And in many cases, the benefits of being able to engineer a system of constrained components are far more common and far more constructive than the odd occasion that a use case is entirely inhibited by a constraint.

That's not to say that we should blindly accept and perpetuate every constraint ever introduced, or introduce new ones without thoughtful consideration, but it's wrong to believe they have "no benefit" just because they seem "artificial" or "arbitrary".

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

#118

Post by andrewshadura » Wed, Apr 03, 2024, 10:26 PM UTC

hiAndrewQuinn wrote: post #22

Retr0id wrote: post #16

Earlier quoted context omitted.

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…

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!

FYI, he's D. R. Hipp, not Dr. Hipp.

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

#119

Post by RiverCrochet » Wed, Apr 03, 2024, 10:26 PM UTC

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…

> This was done (memory is fuzzy here) by preloading the return address onto a register pair and then calling the function. When the function was done, it would do an indirect jump to the location held in that register pair, which would return to the next instruction after the call.

This is pretty much what the MIPS `jal` and ARM `BL` do. TMS9900 also did something similar (edit: it had a `BL` instruction too.)

I was fascinated by the fact the Signetics 2650 that had an 8-byte internal stack.

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

#120

Post by naasking » Wed, Apr 03, 2024, 10:27 PM UTC

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.

> 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 you don't have to worry about for almost all scenarios you're likely to encounter.