I’m writing a functional language without a GC, so maybe I can offer some insight.
The basic reasons you want a GC are closures, as you mention, and reference cycles.
In a pure, eagerly evaluated language, cycles aren’t possible, so naïve reference-counting is enough to reclaim all garbage. If the language has mutable reference types, you can still use RC, but you need a cycle detector.
Closures are more interesting.
A neat thing about purely functional languages is that you can’t observe whether something is a value or a reference, so there’s no difference (apart from performance) between copying and sharing. Purely functional data structures take advantage of this to share common parts of modified structures. For instance, when replacing a node in a tree, you produce a new tree, but all nodes are shared except the O(log n) nodes in the path from the root to the new node.
What I do in my language project, then, is to always copy (or move) values into a closure. If they’re unboxed, they’re probably small, and if they’re boxed, they’re in a reference-counted or copy-on-write structure, so sharing is safe.
The next thing you can do is to unbox closures (like C++ lambdas). You only need to box them (like C++ std::function) if you want them to have uniform size, for example if you’re storing them in a homogeneous list.
Finally, you tie value lifetimes to scopes. When a value goes out of scope, you drop it and reclaim its memory immediately (or place it on a queue, for deferred RC). That’s where stack-based languages become really handy, part of the reason I’m writing one. That’s also where substructural types become interesting, because they let you encode the answer to the question “When am I allowed to copy or drop this value?”
Rust augments this with “lifetimes”, which are essentially a static approximation of stack depth. For instance, you can talk about references to objects on the stack, but you can’t store a reference to a younger value into an older value, because the younger one will be reclaimed first—its lifetime is not a supertype of the destination’s. This prevents the problem of dangling references.
I don’t feel like substructural types are really geared toward functional languages, however; where they really shine is safe imperative programming like Rust—for a particular definition of “safe”, anyway.
Agree with most of this, and even upvoted it, but...
> I don’t feel like substructural types are really geared toward functional languages, however; where they really shine is safe imperative programming like Rust—for a particular definition of “safe”, anyway.
I disagree with this. Even vanilla Standard ML and Haskell can benefit from substructural types. The structural rules (weakening, contraction) don't have to be an all-or-nothing proposition. Why should I be forced to pick one between garbage collection for in-memory data structures (which Rust won't give me, at least not out of the box), and deterministic reclamation guarantees for file handles and network connections (which ML and Haskell won't give me)? I want both!
Thanks for your insight. This is all very interesting. I'm reading about lifetimes and static analysis now. I hope you let HN know about your language when its time. I will be very interested hear more considering what you mentioned the inspiration was.
You can check my profile for the GitHub repo; it’s a long work-in-progress research project, so I don’t like to advertise too much, but you can play around with the old compiler and check out the work on the new one if you’re interested.
The basic reasons you want a GC are closures, as you mention, and reference cycles.
In a pure, eagerly evaluated language, cycles aren’t possible, so naïve reference-counting is enough to reclaim all garbage. If the language has mutable reference types, you can still use RC, but you need a cycle detector.
Closures are more interesting.
A neat thing about purely functional languages is that you can’t observe whether something is a value or a reference, so there’s no difference (apart from performance) between copying and sharing. Purely functional data structures take advantage of this to share common parts of modified structures. For instance, when replacing a node in a tree, you produce a new tree, but all nodes are shared except the O(log n) nodes in the path from the root to the new node.
What I do in my language project, then, is to always copy (or move) values into a closure. If they’re unboxed, they’re probably small, and if they’re boxed, they’re in a reference-counted or copy-on-write structure, so sharing is safe.
The next thing you can do is to unbox closures (like C++ lambdas). You only need to box them (like C++ std::function) if you want them to have uniform size, for example if you’re storing them in a homogeneous list.
Finally, you tie value lifetimes to scopes. When a value goes out of scope, you drop it and reclaim its memory immediately (or place it on a queue, for deferred RC). That’s where stack-based languages become really handy, part of the reason I’m writing one. That’s also where substructural types become interesting, because they let you encode the answer to the question “When am I allowed to copy or drop this value?”
Rust augments this with “lifetimes”, which are essentially a static approximation of stack depth. For instance, you can talk about references to objects on the stack, but you can’t store a reference to a younger value into an older value, because the younger one will be reclaimed first—its lifetime is not a supertype of the destination’s. This prevents the problem of dangling references.
I don’t feel like substructural types are really geared toward functional languages, however; where they really shine is safe imperative programming like Rust—for a particular definition of “safe”, anyway.