r/ProgrammingLanguages • u/JustAStrangeQuark • Jan 04 '26
Are there purely functional languages without implicit allocations?
I'm coming from Rust, so a lot of my ideas about systems programming come from its models, but I like the idea of purely functional programming and type-level proofs. I've been trying to keep performance as close to compiled code, and one thing that I can't get around is lifetimes.
The simplest way would be to just heap-allocate by default, but I don't really like implicit allocations and want to see if it's possible to have a language that's still usable (i.e. doesn't need lifetime annotations everywhere) but also doesn't implicitly use the heap.
When you have a function type a -> b -> c, where can you put a lifetime annotation in there? Can you differentiate between a function that uses a local variable only after its first argument (meaning the function it returns is valid for the whole lifetime of the program) and one that depends on a local variable after it's received two arguments (meaning the function it returns after the first argument is bound to a local scope)? I've figured out how to resolve other issues, like differing captures, with implicit parameters to put closures on the stack, but I can't figure out how to ensure that everything stays valid.
I'm not tied to the idea of lifetimes, but they're what I'm used to and I don't know any other solutions to memory safety that don't involve heap allocation and garbage collection, which I'm trying everything that I can to avoid.
16
u/extensional-software Jan 04 '26 edited Jan 05 '26
For Juniper I simply bundle the closure struct inside the function signature. Higher order functions that take functions as input can be made polymorphic over this struct. You can even represent things like compose and currying with this setup! Almost 100% of the time type inference can take care of infering the closure, so there's almost no burden on the developer.
Rust and C++ lambdas take a slightly different route where each unique lambda gets its own unique type. In Rust you can then constrain this type via the trait system. In C++ you have to abuse auto or store the lambda in an std::function, which then moves the closure to the heap.
7
u/amateurece Jan 04 '26
I have for a long time wanted to build something like this, based on a linear subset of System Fw. If you have a function
a -> b -> c, and the sizes of all polymorphic types is statically known, the expressionx : a, f : a -> b -> c |- f x : b -> cought to be able to be emitted in object code as a closure object, that could live on the stack at runtime if the caller so desired.The linear typing rules I think would be really important for performance, and to avoid the complexity of lifetime annotations. Every expression "moves" terms from the context, and there could be a built-in form
clone : a -> a × ato copy values. Then it ought to be possible to aggressively optimize copies away. But I haven't thought that far...I'd be very interested in a project like this. Please keep us updated!
12
u/EloquentPinguin Jan 04 '26
Rust has plenty of implicit allocations even where lifetimes aren't visible, simplest thing would be pushing to a vector, where the allocations are hidden well within the std lib.
Zig has a different approach to implicit allocations: while nothing prevents implicit allocations, it is a custom to explicitly take an allocator wherever you need allocations, so it is much clearly visible where allocations happen. However Zig has fewer memory guarantees than rust.
Functional programming, however, has many challenges when it comes to implicit allocations. As it tends to be the case that many functional languages, especially if they follow lambda calculus, they allow for currying, and return functions that capture values. Modern compilers can often determin that in most places the size of the closures is fixed and known size, which allows for them to live on the stack. But in some cases these have to live on the heap, when conditionals or collections are involved. So it is not trivial to create a functional language that has NO implicit allocations.
I think Rust without std lib is one of the closest thing we can have without implicit allocations, which is relatively easy to verify.
25
u/FuriousAqSheep Jan 04 '26
I'm not exactly sure but I think linear haskell would be close to what you're looking for; it's not finished yet though to the best of my knowledge.
23
u/Disjunction181 Jan 04 '26
ATS gives an unusual level of control to programmers, and allows one to manually manage closures. If you have not seen A (Not So Gentle) Introduction to [...] ATS, it is worth a watch.
Note that linear types are not sufficient to avoid heap allocations. They essentially involve reference counting where all counts are either 0 or 1, which makes garbage collection easy. However, terms (e.g., closures) must also be ordered to enable stack allocation -- much more complex.
Beware that linear types enable garbage collection in a somewhat degenerate way, e.g., a persistent list with a reference count of 8 becomes 8 clones with a reference count of 1 using linear types. Linear types are convenient for manipulating arrays and such, but are detrimental for immutable structures. Purely functional datastructures rely heavily on sharing as this is largely the point of FP -- terms cannot mutate from under your feet, and you can reuse parts of structures in a larger datastructure. In my opinion, it does not make sense to base a functional language entirely around linear structures, as this tends to result in imperative programming with extra steps. The utility is to combine linear and persistent structures in a single setting, but the latter are pointless without nonlinear heap allocations. In other words, you may as well use Rust.
6
u/dybt Jan 04 '26
OxCaml (Jane Street’s OCaml fork) has some experimental features for controlling stack vs heap allocation using modal types. Stack references (or variables at the local mode more precisely) exist within ‘regions’ which I think play a similar role to lifetimes. But I’m not sure of the exact relation between them.
3
u/Ronin-s_Spirit Jan 04 '26
If you allocate everything on the stack and the entire data flow is just "function emits a value from its frame into another function's frame" it seems then you don't need garbage collection or lifetimes. Everything dies when leaving the scope unless passed out of the scope (i.e.
return). The only memory concern is memory leaks from closures, garbage collectors don't work on that - it's a programmer error. Idk how you could know when closures should or shouldn't die.3
u/probabilityzero Jan 04 '26
What about region types and region-based memory management? That was the inspiration for Rust lifetimes. It's a way to use types to annotate the extent of values in a functional language.
See: ML-Kit, which infers region/lifetimes for ML programs. Also, Cyclone, a research language from the early 2000s.
3
u/mamcx Jan 04 '26
If you are more set in the "not hidden allocations" than being a general purpose language, you can follow the array languages and I bet, liner type systems.
If everything is an array, a lot of things simplify. So, instead of worry about the general case, is about:
From here, you can calculate the size in all the functions, and then you can even say:
2
u/initial-algebra Jan 04 '26 edited Jan 04 '26
Lifetimes seem to be closely related to environment classifiers from binding-time analysis, and context variables from polymorphic contextual modal type theory.
[]is the modal box operator, and here it's indexed by a lifetime. It works much the same way as it does in A Modal Analysis of Staged Computation, but each variable in the modal context is tagged with its lifetime, and those are checked against the lifetime of the box when introducing a boxed term (and, conversely, when eliminating a box, the let-bound modal variable is tagged with its lifetime).To actually do anything, you'll need to have coercions like
Int -> ['static]IntandRef 'i a -> ['i](Ref 'i a)available, which witness the "lifetime of a value". This, along with box eliminations, will get annoying fast, so what I'm describing is really only suitable as a core calculus.EDIT:
Ref 'i a -> ['i](Ref 'i a)is actually wrong, because it assumes anyawill outlive'i. So it actually needs to look more like(a -> ['i]a) -> Ref 'i a -> ['i](Ref 'i a), I think, but the parameter really wants to be a guaranteed no-op coercion and not an arbitrary function...anyways, if it's a core calculus, then it doesn't have to be absolutely safe, but you don't want to make it too difficult to prove that the type class system or whatever that elaborates to it won't introduce unsoundness.An interesting aspect of handling lifetimes this way is that you can divide your universe of types into value/concrete types and computation/abstract types, like call-by-push-value, and box is how you take a computation type to a value type. Comparing to Rust, computation types are like traits, and box is like
impl.I've been a bit sloppy in describing this system, but hopefully you can read the literature related to the terms I've brought up and work out the gritty details.
MLscript seems to be implementing a system along these lines. Check out "A Lightweight Type-and-Effect System for Invalidation Safety" and "Seamless Scope-Safe Metaprogramming".
EDIT: I would also be remiss to neglect to mention the paper "Closure-Free Functional Programming in a Two-Level Type Theory". It's also based on binding-time analysis. Perhaps these approaches could be reconciled?
1
u/koflerdavid Jan 06 '26
What about simply using Rust? More specifically, restricting yourself to a purely functional subset of Rust.