He's back! very excited to dig into this. For anyone new, read the commit log. it's a very entertaining insight into the thought process of creative programming.
What does inlining have to do with heap allocation? I would have thought the opposite of heap allocation was "stack allocation"? In particular, I would expect that inlining would produce no effect on the number or size of heap allocations?
Not sure if this is what the OP is referring to, but escape analysis determines whether a variable can be on the stack of a single function, or if it must be the heap (because it "escapes" the function's lifetime).
So if you can inline more functions, then you can allocate more objects on the stack rather than the heap.
Inlining pattern matches allows you to eliminate the value being matched on, preventing an allocation. It transforms an allocation into a function call.
What do you mean “return type state”? If you mean the return value, that depends on the semantics/ABI of the language, but if it would result in an allocation, that can be eliminated by another round of inlining. Functional compilers typically have to deal with the tradeoff between code size and compile time (from lots of inlining) and runtime allocation.
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.
It sounds like you're using "inlining" to mean "stack-allocating the closure", but when I think of "inlining" I think of "expanding a function body into its call sites to elide function-call overhead". Maybe there's an implicit relationship between the two that I'm not understanding? I guess in order to stack allocate a closure you have to generate new function instances for each "type" of closure, and since these types rarely change between call sites we just inline them? Apologies if I'm just dense.
Regular function (not heap allocated closures) do not have a runtime footprint. Their body just gets tracked by the partial evaluator, but never manifests unless they are applied. Their variables (usually stack-alloc'd) get tracked on an individual basis.
So it is not the case that functions are stack allocated. They are fully known.
A closure is something that is opaque to the partial evaluator. Closures do need to be heap allocated because they could be recursive data types.
> "expanding a function body into its call sites to elide function-call overhead"
If you do this, not only do you not need the function call overhead, but you also do not need the overhead from heap allocating a function a runtime (converting it into a closure.)
I am not sure how good I am at explaining this. I would appreciate somebody going over the docs and giving me some feedback on it. When the last Spiral was posted on HN, there was some initial excitement for a few days and then it was crickets.
If you are willing to give it a try, I'd be happy to answer all your questions in the Spiral issues.
Sorry, that Spiral is an entirely different language that has nothing to do with mine! The only reason I linked to it is because somebody in the Reddit PL sub thread brought my attention to it.
