If you have a function, there is a certain equivalence (in terms of compilation) where you can either allocate it as a closure at runtime or emulate the effect of that by just tracking it fully at compile time and inlining it a the site of use. If you do the later, you can avoid having to do a heap allocation that having a runtime closure would require.

I said it is an equivalence in terms of compilation because, whether it is allocated as a closure on the heap, or tracked at compile time has no bearing on the correctness of the program. It only affect its memory allocation and performance profile.

If you are a C programmer, or working at a similar level of abstraction, this concern over heap allocations might seem academic, but to a functional programmer such as myself there is a lot of importance because we use function composition for all of our abstractions and don't want them to heap allocate as closures. The more abstract the code we are writing is, the more inlining matters.

The way I am describing this is confusing because inlining is not an event that happens. Rather inlining is the default. Tracking functions at compile time is the default. Heap allocation of them and their conversion into closures is an event, after which the compiler stops tracking variables of a function on an individual basis and keeps track of them at a lower resolution.

> I would have thought the opposite of heap allocation was "stack allocation"?

      | Stack | Heap
------|-------------
Full  |   x   |
Box   |       |  x

To get a full picture of how Spiral's partial evaluator sees functions and recursive unions, it consider the table above. Spiral is designed so that it is very easy to go between the fully known and boxed. You don't actually control heap and stack allocations explicitly, but instead shift the perspective of the partial evaluator through the dyn patterns and control flow.

It just so happens that a very natural way of generating code for fully known functions is to leave their variables as they are on the stack. If the function needs to be tracked at runtime, then those variables are used to make a closure. The natural way of compiling things that are fully known (functions, unboxed unions) is to put them the stack. While things that are boxed (closures, boxed recursive unions) are on the heap.

This is just on the F# backend. If I were compiling to LLVM for example, I would not use a stack, but the infinite amount of virtual registers instead. And non-recursive union types are compiled as structs, meaning they should be on the stack even in boxed mode.

This view of memory is more complicated than the usual heap vs stack allocation one, because I am playing a game here where I attach a bunch of other concepts to it, but it is very useful and simplifies actual programming.