Hacker News Reader

Comment by kibwen | Hacker News Reader

I'm interested in examining the idea of a programming language that eschews the notion of a callstack and returns to having a single fixed activation record per function. This obviously places a lot of limits on language design, but in return you get a statically-guaranteed upper bound on memory usage, plus weirdo stuff like the ability to hand out references to local data in functions that have already returned (which remains valid as long as you don't call the function again, which I think should be possible to enforce via a borrow checker).

View on HN

There's prior art in this, very very old prior art. If you check out the first volume of The Art of Computer Programming, it uses a fictitious architecture called MIX. I understand that while it was fictitious, it was made to be similar enough to contemporary architectures. In it there are no special stack manipulation instructions, because there is no first-class notion of a stack! Functions used global variables for their scratch space. To call a function you would just jump to that address. Of course that function needed to know where to jump back to when complete. To do that, before jumping, the caller would WRITE THE RETURN ADDRESS TO THE JUMP INSTRUCTION AT THE END OF THE FUNCTION. This seems kind of insane in the modern day (function calls requiring self-modifying code!) but it meant you could implement functions without needing even a single extra word of storage space, and all you really gave up was recursion. I believe the original Fortran and some other older languages were originally implemented this way.

There's definitely an advantage with this idea, but also some downsides. While you have a guaranteed upper bound on memory usage, it's completely static and actually going to be worse than doing the equivalent on the stack. Suppose you have 100 functions that each need 100 bytes of scratch space. Statically allocating everything like you describe means you need 10KB of memory reserved. But suppose there is one main function, and the rest are helper functions, and the main function calls each helper function one at time and the helper functions don't call anything. With the static approach, you still need 10KB. With the stack-based approach, you only need 200 bytes (the stack space for the main function, and the stack space for the helper function it is currently calling). Another advantage to the stack-based approach is due to caching. In the static approach, whether or not a function's scratch space is in the cache or not depends on how often that function is called. But in the stack-based approach, the top of the stack is almost always in the L1 cache, giving a speed boost to functions, even when they are not called frequently.

That said, I do think it is an interesting idea that is worth exploring.

> Suppose you have 100 functions that each need 100 bytes of scratch space. Statically allocating everything like you describe means you need 10KB of memory reserved. But suppose there is one main function, and the rest are helper functions, and the main function calls each helper function one at time and the helper functions don't call anything. With the static approach, you still need 10KB. With the stack-based approach, you only need 200 bytes (the stack space for the main function, and the stack space for the helper function it is currently calling).

This is not necessarily the case: if you statically analyze the call graph, you may be able to prove that two functions will never be live at the same time, and thus reuse memory regions for their local variables: https://github.com/llvm-mos/llvm-mos/blob/main/llvm/lib/Targ...

Of course, recursion, function pointers, and dynamic linking will defeat (or at least complicate) this scheme.

That's a good point, you can definitely optimize. I'd be curious how far you could go using static analysis. Assuming no recursion, function pointers, dynamic linking, etc; can you optimize to the point that you use as little memory as a stack approach would? I think you ALMOST can! The only blocker would be specific call patterns that would require a lot of memory, but are unreachable. That's where the halting problem hits.

You just make a call graph where the nodes are functions and directed edges indicate which function calls which. Without recursion function pointers and the like you can compute this exactly and this forms a DAG. Each node is given a weight, which is the amount of local memory that function needs. Start at the entry point function, and compute the longest distance path (using the node weight).

Original Fortran did not modified the code. Rather each function had a global variable storing the address to return that the caller had to set.

The CDC 6600 of blessed memory had "return jump" instruction that wrote an unconditional jump back to the return address into the word prior to the first instruction of the called procedure. So one would implement a subroutine return by jumping to the word before the entry point.

(Fortran programmers are probably wondering how alternate ENTRY statements worked; yes, they had to allocate a word before the ENTRY, and copy whatever jump instruction was placed there by the hardware into the main subroutine's jump word, so that RETURN or END would work for all entry points. Recursive languages like Pascal had to copy that word to and from the stack. Reentrant code had to avoid using the return jump instruction entirely.)

As others have pointed out, that's pretty much how things originally started. A more recent example I remember is the Action! programming language for Atari 8-bit computers[1], an Algol descendent for 6502 with static activation frames.

But I don't understand the appeal. Many algorithms and data structures are most naturally expressed with recursion. Not allowing it forces the programmer to create and maintain their own manual stack data structures which brings us to square one in terms of statically-guaranteed upper bound on memory usage since they can grow indefinitely. At best, stack overflow errors will be replaced by array out of bounds errors which is the exact same thing anyway. In fact, it will be even worse: Manual stack implementation will come with its own complexity and source of bugs.

[1] https://en.wikipedia.org/wiki/Action!_(programming_language)

> I'm interested in examining the idea of a programming language that eschews the notion of a callstack

Chicken Scheme fits the bill. While it doesn't eschew the notation of a call stack, it turns it on its ear.

In Chicken Scheme

1. All objects are allocated on the stack. Strings, conses, symbols, lexical environments, ...

2. Functions do not return. Everything is compiled to C which uses continuation passing style. What looks like returning in the Scheme source code is a continuation call: the parent function passes a continuation, and so the function return invokes that and runs that lambda.

3. Because functions do not return and everything is allocated from the stack, the stack grows voraciously. When it hits a certain limit, a kind of ephemeral garbage collection takes place: all objects that have been allocated on the stack which are still live are transferred to the heap. Then ... the stack pointer is rewound.

Essentially, the C stack has become a bump allocator in a kind of generational GC.

That programming language exists.

The old FORTRAN and COBOL language versions were like this.

In ancient FORTRAN programs, the programmer typically computed a maximum possible size for the data and allocated statically in the main program one or more work arrays corresponding to that maximum size, which were either placed in a COMMON block of global variables or they were passed as arguments to the invoked functions and subroutines.

In the functions or subroutines, the work arrays were typically partitioned by allocating in them various local variables.

Overall, this approach was more reliable, because there were no risks of exceeding the memory limits, but it was much more tedious for the programmer, because the worst cases for memory usage had to be accurately predicted.

> Overall, this approach was more reliable, because there were no risks of exceeding the memory limits, but it was much more tedious for the programmer, because the worst cases for memory usage had to be accurately predicted.

Well, most importantly, it fixated the program's limits. Got a bigger machine and wanted to tackle greater data-sets? You're out of luck, if you didn't have the source code. Old Unix programs were often like that. It were the GNU counterparts which often did away with such arbitrary limits allowing systems to grow and the software to stay relevant.

>plus weirdo stuff like the ability to hand out references to local data in functions that have already returned (which remains valid as long as you don't call the function again, which I think should be possible to enforce via a borrow checker).

The C programming language supports this with the static keyword. Further calls may overwrite the pointed data. I have played with allocating fixed-size data in static locals, but I always found that allocating in the caller does the same job better. For example, compare strerror() with strerror_s(). (A sensible strerror implementation should return a pointer to static immutable data, but the Standard doesn't specify it.)

A procedural language can achieve a statically bounded call stack by restricting self recursion, mutual recursion, and function pointers. I struggle to imagine how a language without a call stack could perform differently or better.

> I'm interested in examining the idea of a programming language that eschews the notion of a callstack

Technically, I don’t know any language whose spec mentions the notion of a call stack. For example, it’s perfectly OK for a conforming C compiler to use a linked list of dynamically allocated activation records (from a standards view point; users of such an implementation may have different opinions)

A conforming C compiler also could choose to only use a call stack for functions that take part in recursive calls or that may get called by multiple threads.

> plus weirdo stuff like the ability to hand out references to local data in functions that have already returned (which remains valid as long as you don't call the function again, which I think should be possible to enforce via a borrow checker).

If you add multi-threading (something that is almost a must have for languages on powerful CPUs nowadays), I don’t think that’s easy to do.

I don’t think that “call stack” implies “contiguous memory”, or “what the operating system might think of a process call stack”, so a linked list would still qualify as a call stack. While the C standard doesn’t use the word “stack”, it explicitly requires support for recursive function calls, and the related semantics it specifies with regard to automatic storage duration effectively describe a stack.

If you want to ignore such implementation details, you’re basically saying you want to see a language that doesn’t allow recursion, or maybe even one that allows recursion, but only in such a way that the compiler can compute the maximum amount of memory needed for activation records.

In a language that doesn’t allow recursion, using a call stack still can make sense for the implementation because it allows reuse of memory for local variables between functions that do not call each other, directly or indirectly.

But then, you’re giving up “plus weirdo stuff like the ability to hand out references to local data in functions that have already returned”, although, thinking of it, static analysis could make those locals survive by manipulating the stack pointer (if you have the caller allocate and, reallocate the locals of the called function, the caller can postpone that reallocation if it wants to access the locals of the called function). I’m not sure that weirdo stuff is worth the effort, though. It’s just a weird way to return multiple values from a function.

> single fixed activation record per function

What about statically determining a fixed number of activation records at compile time? Similar in spirit to security focused languages that require loops to have a statically determined finite bound in order to successfully compile.

As to lifetime after returning, do you really hate continuations that much?

> What about statically determining a fixed number of activation records at compile time?

Sure, it may be useful to represent a function's local storage as a first-class concept, and then allow users to instantiate copies of the function at will, if they're willing to allocate more storage themselves, thereby allowing users to either precisely limit the number of instances of a function or otherwise use dynamic allocation to manually reimplement a callstack if they so choose.

> As to lifetime after returning, do you really hate continuations that much?

This is a language that forbids recursion, the functional programmers have already run screaming for the exits. :P

Does it require a new language, or could it be enforced by simple discipline or linting?

I'd suspect it makes sense in an embedded bare-metal environment where you know all the data structures you might ever have in circulation at once. This sometimes ties into things like explicitly unchanging data as "this can be allocated to ROM" to tightly manage the limited RAM.

related thoughts perhaps? http://lambda-the-ultimate.org/node/5555

(be warned that the old site links are slow, one has to wait for the unarchiving to run, or something.)

> I'm interested in examining the idea of a programming language that eschews the notion of a callstack and returns to having a single fixed activation record per function.

Welcome to the old 8-bit C compilers.

Everything was statically allocated so no recursion. The downside is that you can only have a single thread of execution.

It would be interesting to see what that would look like if extended to multiple threads (they would have to be defined/allocated at compile time).

Reply on news.ycombinator.com