1

Is it possible in theory to have a programming language that allows for object lifetimes that exist beyond the current scope but without using heap?

As a little background, in embedded development it can often be advantageous to avoid heap and lean heavily on the stack. On our team we use the stack as a large object graph and essentially inject dependencies all the way down. However, in a perfect world we would also be able to create certain resources on the stack and have them returned to the previous scope. Obviously this can be explicitly via return - and in some cases we do that (e.g. we have a lightweight Task concept that uses a doubly-linked list for task management all managed on the stack and using returns) - but could a compiler theoretically track objects still in play (again, only using stack and static analysis; no GC or reference counting allowed) and return all those objects in the background, rearranging the stack as necessary?

Lastly, even if this is possible in theory, would it be inefficient and inferior to something like Rust, well-written heap-enabled C++, etc.?

EDIT:

Here's an example of what (in this magical language that might not exist) I'd like to do. This is inspired by a C# pattern but written in C++:

Task SetupIsrAsync()
{
    TaskCompletionSource tcs;
    
    c_style_callback_to_isr_registration([&tcs]{ tcs.SetResult(); });
    
    return tcs.Task;
}

If this was a real example, tcs would go out of scope and in doing so, invalidate the returned Task object. However, it seems that in theory a compiler could figure out that tcs is still being referenced indirectly (without actually using a managed object graph) and basically say, well we'll go ahead and preserve tcs on the stack until it isn't being referenced anymore. I realize there may be limitations to this behavior, but that's partly why I'm asking.

I think it probably goes without saying that a language like this wouldn't support pointers and probably a bunch of other concepts (arguable a feature?).

2
  • You want to have the pie and eat it too – not possible. Compilers can use escape analysis to convert some heap allocations to stack allocations, but that won't help here. You can have drastically simpler heaps if you make it impossible to free allocations for later reuse, for example like a stack that only grows. Such bump allocators are actually popular in Rust. The classic solution in the embedded space is to use a bunch of global/static variables instead.
    – amon
    May 24 at 13:39
  • 1
    @amon I'm unclear if you're saying it's impossible or just a bad idea.
    – Jeff
    May 24 at 23:17

4 Answers 4

3

The critical question is how you define a heap, and how object lifetimes can be bounded.

I understand a heap as a store of objects with dynamic lifetimes – once the lifetime of an object ends, its storage can be reused for other objects. For example, in the C standard library the malloc() function creates an object and the free() function ends the lifetime of an object. With garbage collection, the GC algorithm detects unreferenced objects on its own and then ends their lifetime. While heaps are very flexible, managing free and in-use chunks of memory requires extra metadata and extra effort.

Other stores such as stacks constrain the lifetime of objects. With a stack, the lifetimes are strictly LIFO – all younger objects must end their lifetime before the lifetime of older objects can end. This is a perfect fit for call stacks that store temporary variables until a function returns. It is also possible to have an append-only stack that only adds new objects but never frees any memory for reuse – which is extremely time-efficient but means that eventually all available memory will be used up.

You have provided the following C++ snippet of a code with complicated object lifetimes:

Task SetupIsrAsync()
{
    TaskCompletionSource tcs;
    
    c_style_callback_to_isr_registration([tcs]{ tcs.SetResult(); });
    
    return tcs.Task;
}

In C++, the object tcs has automatic storage duration, i.e. the lifetimes continues until the end of the scope. The lambda creates its own copy, which lives for the duration of the lambda. A part of tcs is copied and returned. Due to the use of copies, all lifetime bounds are satisfied.

A way to handle this in C++ without copies is to “leak memory”, i.e. to create an object that lives until the end of the program. For example:

Task& SetupIsrAsync()
{
    auto tcs = new TaskCompletionSource(); // new but no delete
    
    c_style_callback_to_isr_registration([tcs]{ tcs->SetResult(); });
    
    return tcs->Task;
}

But, use of such immortal objects wouldn't involve a heap as per the above definition.

If only one such task completion source can exist globally, then a variable with static lifetime can be used equivalently:

Task& SetupIsrAsync()
{
    static TaskCompletionSource tcs;  // lives until end of program
    
    c_style_callback_to_isr_registration([&tcs]{ tcs.SetResult(); });
    
    return tcs.Task;
}

A heap- or GC-based approach that frees the TCS when it's no longer needed might look like:

shared_ptr<Task> SetupIsrAsync()
{
    auto tcs = make_shared<TaskCompletionSource>();
    
    c_style_callback_to_isr_registration([tcs]{ tcs->SetResult(); });
    
    return shared_ptr<Task>(tcs, &tcs->Task); // aliasing shared poiner
}

After this function returns, there are two shared owners of the tcs object. When the last owner ends its lifetime, the lifetime of the tcs object is ended. However, this shared pointer contains additional metadata to count active owners.

Until now, I'm assuming that c_style_callback_to_isr_registration() takes ownership of a callback and keeps it potentially until the end of the program, in particular if the lifetime of the callback is dynamic so that it might live that long.

If this registration function guarantees that it only needs the object for some statically checkable duration, then other solutions become possible as well. For this example, let's switch to Rust notation. Let's assume the registration function only needs to hold the callback for at most the lifetime 'a. Then we might have:

// the callback is a function that is valid for at least 'a
fn c_style_callback_to_isr_registration(callback: impl Fn() + 'a) { ... }

fn setup_isr_async(alloc: SomeAllocator<'a>) -> &'a Task {
  // this lifetime-bounded allocator creates an object that is valid for at least 'a
  let tcs: &'a TaskCompletionSource = alloc.allocate(TaskCompletionSource::new());
  
  c_style_callback_to_isr_registration(|| tcs.set_result());

  return &tcs.task;
}

Then, the caller can provide some allocator that guarantees a suitable minimum lifetime of objects. If the lifetime 'a happens to be the lifetime of the caller's local variables, then the allocator might be able to use storage on the call stack.

(But in reality, Rust's concept of lifetimes is probably not sufficiently expressive to do this.)

How could such storage semantics be implemented in practice?

Given a non-recursive function context() that bounds the lifetime of the registered callback and therefore the lifetime of the task completion source, we might have a call stack

...
#2 context()
#1 some_other_function()
#0 setup_isr_async()

Then, a downwards-growing stack might contain the following data:

...
| context frame
| context frame
| context frame
| some_other_function frame
| some_other_function frame
| setup_isr_async frame
| setup_isr_async frame
V

We could now store the task completion source at the end of this stack:

...
| context frame
| context frame
| context frame
| some_other_function frame
| some_other_function frame
| setup_isr_async frame
| setup_isr_async frame
| TaskCompletionSource tcs
V

When the setup function returns, there will be a hole in the stack:

...
| context frame
| context frame
| context frame
| (empty)
| (empty)
| (empty)
| (empty)
| TaskCompletionSource tcs
V

The easiest way to handle this would be to note the maximum stack offset in the allocator (a tiny bit of dynamic data), and then in the context frame skip back to that maximum extent (so basically using the C alloca() function). For example, if context() calls another_function(), then we might get the following stack layout that just wastes the empty space:

...
| context frame
| context frame
| context frame
| (empty)
| (empty)
| (empty)
| (empty)
| TaskCompletionSource tcs
| another_function frame
| another_function frame
V

But this is extremely restrictive. To do that, we need the following constraints:

  • the maximum stack usage of all functions that perform this kind of allocation must be statically known
  • this prohibits recursion
  • this prohibits dynamic linking, function pointers, OOP, or other indirect calls

This scheme allows a dynamic amount of objects to be created. If the number of allocations is statically known, then space could be reserved by the caller and we might get a stack layout (just before the tcs is allocated) like this:

...
| context frame
| context frame
| context frame
| (reserved space for allocation)
| some_other_function frame
| some_other_function frame
| setup_isr_async frame
| setup_isr_async frame
V

But that is an extremely tight requirement.

Back to the case that the lifetime of allocated objects is bounded but the number of objects to be allocated is not statically known. We don't have to leave holes in the stack, and don't need to prohibit recursion. For essentially the same amount of metadata + overhead but with less stringent requirements, it would be possible to support those allocations via a second stack just for data. Here would be an example of a data stack in the same memory space that grows towards the call stack:

...
| context frame
| context frame
| context frame
| some_other_function frame
| some_other_function frame
| setup_isr_async frame
| setup_isr_async frame
V

...

^
| TaskCompletionSource tcs
...

Since we defined that the TCS cannot outlive the lifetime of the context() invocation, the code for context() could contain code to clean up all allocations performed by its child functions:

static char* data_stack = ...;

void context() {
  char* old_data_stack = data_stack;

  // call that eventually allocates on the data stack
  some_other_function();

  // call that executes while the allocated objects remain alive
  another_function(); 

  // end lifetime of all those allocations
  data_stack = old_data_stack
}

So yes, your idea kind of works for very specific constellations, if you can somehow bound the lifetime of objects, and if we define this kind data storage to not be a true heap.

In practice, you'll find that few interesting problems have such clear bounds.

Good examples where allocations are clearly bounded include graph problems where the entire graph can be deallocated once a query has been answered, and request handlers in a web server where no object outlives the response (all data that outlives the request/response must be externalized, e.g. into a database). But for exactly those problems, generational GC will also perform very well (if enough memory overhead can be allowed).

Examples were it's extremely difficult to find lifetime bounds include any software with a long-term mutable in-memory data model, for example GUI applications.

6
  • Thanks for your extremely thorough analysis! I'll need to think about some of what you said, but the reason my intuition makes me think this could be more useful than those extremely limited cases, is that we are currently going through great machinations to accomplish the same thing using return clauses. If a language did this all automatically, it would be of tremendous utility (and of course, the language could actually support heap and other features as well, if desirable).
    – Jeff
    May 26 at 3:05
  • I think maybe a useful distinction between a classic definition of a heap and this approach would be similar to storing values in a database vs passing them as context to a method, web service, etc. While both work, one creates contention and the other creates some inefficiencies as a result of requiring the additional context to be passed along, but it is arguably a more stateless approach. In the analogy, passing "allocated" objects via the stack may be similar to the latter approach.
    – Jeff
    May 26 at 3:14
  • Lastly, I will say that in my mind I was imagining in your "holy stack" example, the remaining data would simply be relocated to the bottom (at some cost, of course). I don't know if that is a reasonable approach.
    – Jeff
    May 26 at 3:16
  • Oh, also tcs was meant to be captured by reference. Sorry! Fixed.
    – Jeff
    May 26 at 11:11
  • @Jeff It is not possible to move/relocate an object during its lifetime without invalidating all pointers/references. GC like in Java can move objects only because it knows the entire object graph and can fix up outdated pointers. Specifically in C++ the lifetime of a return value is typically extended without moving it (NRVO), but it would be difficult to guarantee that the caller keeps that object alive for some specific lifetime. Could you perhaps expand on your “great machinations … using return clauses”?
    – amon
    May 26 at 14:56
1

You probably could do this with continuation passing, where rather than returns on the stack, the equivalent to a stack is the program state passed as a parameter to the continuation. An allocated object is put on the stack for the continuation. You would then have the issue of unreachable objects on the stack, but that is not unsurmountable, compaction becomes equivalent to garbage collection.

I don't know of any non-toy languages which implement this though - I played about with something about twelve years ago, as it meant for many actors all garbage collection could occur during blocked states and be local to one actor. I didn't know whether it could really still be called a stack or not https://stackoverflow.com/questions/521057/continuation-passing-style-vs-aggressively-trimmed-call-stack

3
  • 1
    Then the "stack" is so complicated that it has to be allocated dynamically, right? Or, objects have to move around a lot (making pointers useless although that wasn't specified in the question)
    – user253751
    May 24 at 13:46
  • 1
    Each actor has a stack, much like each thread having a stack, allocated from system memory. Compacting it is much like garbage collection, you update all references to any objects which are moved. May 24 at 13:59
  • I have considered the continuation approach. I think it's interesting, although maybe I'm hoping this same behavior can be accomplished more fluidly somehow and with less manual labor.
    – Jeff
    May 26 at 3:19
1

Could a language allow for persistent allocations without heap?

Sure. Just allocate them in static memory. But, unless you really need those allocations to stay allocated until termination, you now have a memory leak. Oh sure, you can invent some way to dynamically de-allocate to avoid the leak. But now you've reinvented the heap.

Maybe figure out why you need to avoid using the heap.

1
  • Good point! I added an example, which hopefully clarifies things a little.
    – Jeff
    May 24 at 23:17
-5

Could a language allow for persistent allocations without heap?

Is it possible in theory to have a programming language that allows for object lifetimes that exist beyond the current scope but without using heap?

Yes, this is possible. In fact, programming languages like this exist. You may even have heard of some of them:

  • C#
  • Java (Note that the Java Language Specification does talk about a concept called "Heap Pollution" but that actually has nothing to do with a heap, it is simply a name for a particular kind of type-unsoundness caused by an unfortunate interaction between Java's Generics and Type Erasure.)
  • ECMAScript
  • Python
  • Ruby

are just some of the examples. None of these programming languages has a heap. This is just a small list off the top of my head, I am almost certain, there are more, possibly dozens or hundreds, even thousands more.

In fact, I have the suspicion that the vast majority of programming languages do not have a heap, simply because specifying how memory allocation is supposed to work is tedious and mostly unnecessary. Programming language designers very much prefer to leave the tedious details to the implementors than deal with them themselves.

The only exceptions are programming languages like BitC, which are (were) specifically designed for low-level systems programming. But even then, it is not strictly necessary. E.g. both Python, Smalltalk, and Lisp all have been used to write operating systems and none of them have a heap.

6
  • 7
    Insisting that there is no heap because it's called "the dynamic object store" or whatever instead of "the heap" is pointless pedantry.
    – user253751
    May 24 at 8:31
  • 2
    The C# documentation calls it a heap: docs.microsoft.com/en-us/dotnet/standard/garbage-collection/…
    – pjc50
    May 24 at 9:14
  • 2
    Garbage collected object memory is a heap. It's managed by the runtime, and the application programmer doesn't need to deal with explicit alloc/free, but it has the same characteristics of statically unpredictable memory behavior. For highly dynamic applications that's often ok, but embedded software needs to run reliable in constrained environments. Compilers may use lifetime analysis to handle passing structures up in scope, I think Rust does this, and likely some other modern statically compiled languages. May 24 at 9:14
  • 1
    Basically two possible answers: Either 1. You don't need a heap (because you call it whatever you want) or 2. Wherever you store your data is by definition a heap. Implementations can be different, but we can always call it "the heap".
    – gnasher729
    May 24 at 10:15
  • 1
    Jörg, you are famous for regularly pointing out that a programming language is just an abstract spec and different from its implementation (and the heap usually belongs to the implemention). But this answer could be heavily improved if you would replace the sentence "None of these programming languages has a heap" by something along the lines of "In theory, the implementation of all of these programming languages does not require a heap (though most standard implementations of those languages use one)."
    – Doc Brown
    May 25 at 15:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.