Hacker News Reader

Comment by bryanlarsen | Hacker News Reader

If you learned the difference between reentrant functions and non-reentrant subroutines the way I did you would never equate them again.

Back in the early 80's when I was 14 or so I wanted to replace a slow bubble sort in a BASIC program of mine with something faster. I had a book that had a quicksort implementation in Pascal and I thought it would be straight-forward to translate it into BASIC.

Of course the naive translation didn't work. Luckily the chapter before the quicksort in the book was all about recursion so I did figure out what was wrong. I also had enough experience with assembly language to be familiar with the concept of passing parameters on a stack. I just hadn't really internalized why someone would do that. In the end, I had to use an array to create a parameter stack to work around the lack of reentrant functions, but I did get it working, and it was a lot faster than the old bubble sort.

View on HN

I don't understand what it has to do with reentrancy?

A (non-tail) recursive function actually needs a reentrant mechanism to implement the semantics of calling itself; this mechanism is a stack.

Without recursive functions, we have a bounded call depth and thus don't actually need a growable stack; a fixed-size array suffices.

We take for granted that function calls are always implemented with a stack, because that's how processors work today, but it could have been done differently. We could imagine an alternative timeline with much restricted functions and no implicit call stack.

And indeed, tail recursive functions are usually implemented with tail call elimination, in which the caller reuses the stack frame of the callee; function call becomes a simple goto, which transforms recursion into loop iteration. If we didn't have an implicit stack we could still have tail recursive functions (and a bounded number of non-tail calls), and manage other recursion cases with explicit stacks.

See for example pratt parsing https://matklad.github.io/2020/04/13/simple-but-powerful-pra... which uses the implicit call stack, and contrast with Dijkstra's shunting yard algorithm https://matklad.github.io/2020/04/15/from-pratt-to-dijkstra.... which is the same thing but with an explicit stack. If we didn't have a call stack, we could always program in Dijkstra's style and be none the wiser.

My guess is that:

1) the quicksort algorithm which was used was a recursive version, and relied on local variables to do its job.

2) in the discussed BASIC implementation, local variables are translated to global variables (probably with some form of prefixing based on the function using it to avoid name clashes). This means that functions in that language are never fully reentrant, and that somehow an explicit variable stack has to be implemented to recover the ability to recurse without overwriting variable prematurely.

Note: I initially had a doubt wrt reentrancy, as I had knowledge of this concept in the context of multithreading (I think it actually came up originally in that context), and indeed having concurrent uses of the same function relying on some global variable is problematic, but here there isn't any kind of concurrency. However, global variables can be a problem in the situation outlined above. Another possible issue, although not present here, is when a function F uses a global variable, and accept a function pointer. If that pointer is pointing to a function making a call to F somehow, then lack of reentrancy could also be a problem.

To refresh my memory, I must admit that I had a quick glance at stackoverflow (https://stackoverflow.com/questions/3052393/reentrancy-and-r...).

Reply on news.ycombinator.com