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

11–20 of 241 posts

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

#11

Post by kazinator »

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/

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

#12

Post by trealira »

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

I was expecting some ancient Greek algorithms that used stacks or priority queues, haha.

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

#13

Post by weinzierl »

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.

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

#14

Post by comex »

weinzierl wrote: post #13

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

It does allow nested calls, because each function has its own storage for the return address and local variables.

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

#15

Post by howerj »

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

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

#16

Post by Retr0id »

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 for the btree structure itself.

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

#17

Post by robocat »

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

Definitely "a tale of intrigue, betrayal, and advanced programming-language semantics"

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

#18

Post by dfxm12 »

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

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.

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

#19

Post by weinzierl »

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

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

#20

Post by kstrauser »

082349872349872 wrote: post #2

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 "

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.
Post reply on HN