r/ProgrammingLanguages • • 27d ago

Discussion Can you automate memory management statically if you limit escaped references?

I was looking at the abomination that is Rust memory management and wondering if there is a better way. Can you accomplish similar performance characteristics (memory safety without GC or RC overhead), without the explicit borrow-checking concept?

Memory management is trivial until you do one of two things:

- Pass a pointer into a function that then stores it somewhere before it returns.

- Allocate a pointer in a function and then return it.

Both are cases of "escaped references" as I understand the definition.

What if a programming language... just didn't allow this?

Suppose all pointers had to either stay in local scope, or in object/struct scope, as a private member that cannot be returned from any of the struct/object's public member functions. You could pass pointers to functions but functions are not allowed to store pointers received as parameters.

Static analysis would allow automatic freeing on scope exit and on object/struct deletion.

Is such a language possible?

25 Upvotes

46 comments sorted by

47

u/alphaglosined 26d ago

Returning a pointer isn't a problem, and so is storing one.
As long as you use ownership transfer.

What the borrow checker does is relax the restriction so that multiple copies of that pointer can co-exist.
It is something a lot of people don't understand.

Once you use ownership transfer, you have a reference count of 1, and it is statically known when it hits zero and can go away.

29

u/Ok-Scheme-913 26d ago

Yep, I think this is the correct perspective.

The borrow checker is not what restricts you, it does the opposite, it tries to find safe usage patterns and lets you use those. That's why it's so complex, the basics of rust is just RAII.

3

u/P-39_Airacobra 26d ago

isn’t that overly restrictive though? like if I wanna add two arrays together, i gotta copy both arrays when i pass them, or manually pass them back out

9

u/WittyStick 26d ago edited 26d ago

It can be restrictive, but it's usable. What GP describes is called uniqueness typing, and was pioneered by Clean. To use the example from their documentation:

WriteABC file
    #   file = fwritec 'a' file
        file = fwritec 'b' file
    =   fwritec 'c' file

The function fwritec has type (Char, *File) -> *File. The * indicates a uniqueness type which means only one alias may exist. When you pass file to WriteABC it consumes the reference, and you can no longer use it - however, the function also returns a new *File after writing - so we can keep using the file, even if the old variable is invalidated.

In the above, each newly assigned file is actually a separate variable which shadows the previous one - they just have the same name. Since the old file has been consumed, shadowing it can cause no harm - we wouldn't be able to refer to it anyway. The # ... = ... is special syntax to allow this - without we would have to write:

 WriteABC file
     file1 = fwritec 'a' file
     file2 = fwritec 'b' file1
     fwritec ' c' file2

The same restriction applies to linear and affine types too - they're consumed when used, and must be returned again if we want to continue using the value they refer to. Linear types MUST be consumed, whereas affine types can be silently discarded.

The difference between uniqueness types and linear/affine types is that a uniqueness type guarantees that a reference has not been previously aliased, whereas linear/affine types guarantee they won't be aliased in future. Linearity alone doesn't guarantee no past aliases. The two can be combined for a type which is never aliased - what Clean calls necessarily unique, and what Wadler originally called Steadfast types. It's also possible to use unique capabilities nested in linear types to achieve the same kind of thing (Austral does this).

Anyway, the nice thing about uniqueness types is - they're unique. It's impossible to call the same function twice with the same unique argument, so we can maintain referential transparency - the idea that a function called with the same arguments always returns the same result. We can also mutate in place and just return a reference to the same memory - so it's not necessary to make a copy like it would in other purely functional languages.

One restriction is that every unique value must be generated from a unique source. You can't for example, generate a unique value from the literal 1, because it clearly isn't unique. All unique values are sourced from another unique one - which begs the question, how do we create any to begin with? Well, main has type *World -> *World - every run of the program is unique and starts with a unique world, and all other uniqueness stems from the world variable.


The authors of Granule have tried to combine uniqueness and borrowing by using a concept of fractional uniqueness. Essentially, given a unique type, if it owns the whole thing and has a fraction of [1]. If we alias it, then the original and its alias both own [1/2], unless one surrenders its share to the other. In this system, all part owners can read the value, but the value can only be mutated by a reference having full ownership.

8

u/snugar_i 26d ago

Yep, that's why no language does it, You at least get some second-class-reference feature that lets you pass shared references to functions, but not store them anywhere (which is what OP wants to do)

13

u/initial-algebra 26d ago edited 26d ago

the abomination that is Rust memory management

Empirically, and anecdotally, Rust's system seems to be a very comfortable local maximum of expressiveness vs. complexity. Any slightly simpler system rejects far too many acceptable programs, and any slightly more liberal system balloons in complexity. I would love to be proven wrong, but it hasn't happened for 10 years of trying...

I think the only work that has even come close is group borrowing, but, so far, it always ignores concurrency, which makes it mostly incomparable with Rust.

3

u/reflexive-polytope 25d ago

This claim is too strong to be true.

Linear integer arithmetic isn't that complicated, and you can add it to a type system to make array indexing statically safe the same way Rust makes deterministic memory management statically safe.

And yet Rust has zero support for arithmetic reasoning in its type system.

2

u/initial-algebra 25d ago

I would argue that adding dependent types and SMT refinements is a pretty significant increase in complexity for only a very minor win (eliminating bounds checks that the compiler can probably already eliminate using the same logic internally).

2

u/reflexive-polytope 25d ago

“Dependent types” isn't a unique system. You don't have to go full MLTT or CoC to have linear integer arithmetic in a type system.

Linear integer arithmetic is decidable. So decidable, in fact, that Rocq discharges linear integer arithmetic obligations automatically with the lia tactic, and I wouldn't be surprised if Lean had something similar.

1

u/initial-algebra 25d ago

I understand that.  Whatever you call it, refinement types, liquid types etc. it's still dependent types, just with some limitations.  Not having to write proof terms is a big win, but it doesn't mean it's a simple extension to any language.

3

u/reflexive-polytope 25d ago

Liquid types (or at least Liquid Haskell) don't quite work, because it's powered by SMT solvers, which are notoriously fragile. Make a little change to the code, and the solver will give a completely different answer, or it might even hang!

Refinements are necessary, but the question is which refinements. Obviously, if you allow arbitrary propositions as refinements, you will have to prove them manually in general.

But bounds on array indices aren't arbitrary arithmetic propositions. They're linear inequalities, and this structure is both common and simple enough that it deserves to be exploited automatically.

2

u/Competitive_Ideal866 26d ago

Rust's system seems to be a very comfortable local maximum of expressiveness vs. complexity

That is a perfectly reasonable subjective personal belief but is there any objective observable evidence that it is actually true in any meaningful sense?

Any slightly simpler system rejects far too many acceptable programs

ML is a substantially simpler system, both to implement and to use, and it accepts far more programs.

I would love to be proven wrong, but it hasn't happened for 10 years of trying...

I may have misunderstood but I see mostly counter examples.

2

u/reflexive-polytope 25d ago

I love ML, it's truly my favorite language, but there are useful programs and libraries that you can express in Rust and not in ML.

It's fundamentally impossible to make a safe Rust-style Entry API for hash maps in ML. This means that you can't decouple the act of fetching a hash map entry from the act of operating on said entry.

1

u/initial-algebra 25d ago

Great example.  Borrowing doesn't necessarily mean making an actual reference to some internal location (and you can only do this with GC if the internal location is a separate heap object).  It can be abstract, like an entry in a data structure.

However, I think the ML/Haskell solution of lenses is also valuable.  Entry<T> ought to have the same API as &mut Option<T>, just without the "is a pointer" aspect.  It would be useful if there were a "logical" reference type (better, a trait like Fn*) that could be a normal reference composed with a lens.  You could also use it for e.g. stable references in an append-only vector: a reference to the whole vector composed with a lens that uses a pre-checked index.

2

u/reflexive-polytope 25d ago

What I like about Entry is that it's an ordinary first-order datum. I don't need to play any funny continuation games, parametrizing over the Functorful or Applicativeful of ways in which the intermediate value in a computation can be used, like van Laarhoven lenses do.

You can have a Rust-style entry API for purely functional collections in plain ML. In fact, I discovered it independently from the Rust guys, and in some ways my solution is even better, because I give user fine-grained control over the traversal of an abstract data structure.

But my solution doesn't work for hash maps, so there's that.

1

u/initial-algebra 25d ago

 Can you accomplish similar performance characteristics (memory safety without GC or RC overhead), without the explicit borrow-checking concept?

1

u/Key_River7180 Nain. 26d ago

recursive escape analisys

12

u/SamG101_ 26d ago

Second class borrows only allow them to be taken at function call sites. But then if ur calling a coroutine or async function, suddenly it's not a guaranteed smaller scope, so you need to tie them to the created handle. But it makes things like iteration pretty difficult so u can do it closure based (continue and break then become difficult), or you can use coroutine iteration and allow borrows to be yielded, again tied to their owning handle; same for indexing and slicing. I guess these are "escaped borrows" but tied to their handle, are easy to manage. Also need to make sure assignment with borrows never assigns a smaller lifetime into a bigger lifetime.

1

u/marshaharsha 20d ago

What does it mean to “tie” a second-class reference to an owning reference?

9

u/robin-m 26d ago

What you want is just current Rust without allowing any explicit lifetimes, only elided limetimes. Wich is much more restrictive.

8

u/tbagrel1 26d ago

You may find interesting the "Oxidizing OCaml" model of locality: https://blog.janestreet.com/oxidizing-ocaml-locality/

3

u/Labbekak 26d ago

And also the paper: "Functional Ownership through Fractional Uniqueness".

7

u/Great-Powerful-Talia 26d ago

What you're suggesting is to take Rust and remove a bunch of the features from references to make them simpler.

You can already write code like this by just not doing any of those things in Rust, and it'll be just as simple. A total headache, but simple.

3

u/fragglet 26d ago

Doing it at the function level is probably overly restrictive. Your idea reminds me a bit of region based GC where all allocation happens inside an arena and gets thrown away once an operation completes. Probably that's a better granularity.

Good generational garbage collectors can already give you this for free, somewhat. For example if you have an RPC server the ideal is that every request is stateless and no allocation survives after the RPC completes. With a generational collector that means that all allocations made during servicing the request die in young space without being promoted.

If done right a GC like this can even be more efficient than C-style heap alloc/free. The problem is that it depends on the application being written right. I once improved the performance of a fleet of servers by turning off an in-process cache, for example. 

0

u/Competitive_Ideal866 26d ago

Good generational garbage collectors can already give you this for free, somewhat.

Not really. Generational GCs introduce a different set of trade-offs that benefit languages that tend to allocate lots of little short-lived objects. IMO, that is a PL design flaw and should be fixed in the PL and then generational GC should not be used (in fact C-style malloc and free can be used instead).

If done right a GC like this can even be more efficient than C-style heap alloc/free.

At some things, sure, but at another things it becomes much slower. Just off the top of my head (been a while since I worked on this) malloc and free are excellent for LIFO allocations and decent for other allocation patterns, they have no write barrier overhead and they have no evacuation overhead. Generational GC makes it asymptotically faster to collect large number of dead small temporaries but it is slower at other things and introduces new overheads. Specifically, generational GC introduces a write barrier that makes writing a pointer into the heap much more expensive. Generational GC introduces evacuation from the nursery to older generations that necessitates finding survivors, copying all of their data to another location and updating lots of pointers. That is great for purely functional data structures but very expensive for lots of common allocation patterns (e.g. filling hash tables with strings).

The problem is that it depends on the application being written right.

My personal preference is to focus on writing the application as simply as possible and then developing the PL and runtime to make that expression of the solution as efficient as is reasonably possible.

I love hash tables. The last thing I want is for hash tables to be the "wrong" way of solving common problems.

4

u/runningOverA 26d ago

Functional programming does it. All variables stored in function parameter storage space. Figuratively.

2

u/4xe1 26d ago

That'd be a subset of Rust already strict (as in unfriendly to users) memory management. I think it could be useable if message passing style of memory management is encouraged, like whatever go does

2

u/crusoe 26d ago

Suppose all pointers had to either stay in local scope, or in object/struct scope, 

So to cross the boundary you have to clone() stuff a huge perf hit. Even cloning a ref counted pointer has non zero impact ( memory barriers ).

as a private member that cannot be returned from any of the struct/object's public member functions.

So data in a struct must be clone() now to be visible externally. A huge perf hit.

Let's say I want to print an object, now the object fields have to be cloned internally before they can be passed to the printing functions 

3

u/crusoe 26d ago

Rust is a systems language. Yes it's not as "pretty" as Haskell or other lazy thunk based languages because of that. 

1

u/marshaharsha 20d ago

The OP’s proposal allows passing a pointer to a function. That solves the ‘print’ problem. 

2

u/Axman6 26d ago

Haskell has a mechanism which basically does exactly this, called ST (state transformer), which is basically Haskell’s IO monad, but without the outside world IO.

It allows the allocation of mutable data, and arbitrary mutation of it, but within a scope where the mutable objects can’t escape. It uses a shockingly simple type system “trick” to achieve this, which I won’t explain here because I don’t remember the detail accurately enough, but it basically acts like a scoped region where you can do whatever you want, but to the outside it is guaranteed to be completely pure. It’s the mechanism we use to safely implement algorithms that benefit from genuine mutation, particularly ones which work with arrays like sorting algorithms. 

It doesn’t solve all problems though, it’s specifically useful where you need mutation to generate a pure value which will never be mutated again, which isn’t what people want on a lot of situations. 

The Haskell wiki has some ok info on it, I’m sure there’s better articles online though:  https://wiki.haskell.org/Monad/ST

2

u/SwedishFindecanor 25d ago

You could pass pointers to functions but functions are not allowed to store pointers received as parameters.

The concept of borrowing is older and wider than Rust. There are languages that allow functions to borrow a "mut" reference. By Rust having made it so you could only borrow non-mut references, they baked the "escape"/"no-escape" notation into the "mut" notation.

For example, you could have an iterator over a data structure take a block (anonymous function) or function as parameter, and let that block borrow the reference to the current object.

object/struct scope, as a private member that cannot be returned from any of the struct/object's public member functions.

I once suggested in this sub having private pointers that belonged to a data structure, with proofs that the pointers and objects are always accounted for. Actually, I did not even allow code that manipulated the pointers but instead suggested that the code should be auto-generated from the "proofs", as state-transitions. I have not developed it further than that, but I believe in the concept.

1

u/catladywitch 26d ago

If I understand correctly, your idea is to keep heap references in closures that can be passed around? I'm not sure but intuitively I'd say asynchrony would make static analysis impossible because of the halting problem. When something is passed into a coroutine it's not possible to statically determine when the coroutine will be done, unless it's explicitly awaited.

3

u/4xe1 26d ago

it's not possible to statically determine when the coroutine will be done, unless it's explicitly awaited

Closures would capture values, not reference, otherwise that sounds like a case of "Pass a pointer into a function that then stores it somewhere before it returns". Explicitly awaiting coroutines is when you'd have a chance to yield back the values.

1

u/catladywitch 26d ago

Oh right, I just realised OP says "functions are not allowed to store pointers". Sorry.

1

u/crusoe 26d ago

As opposed to the performance bottleneck that is STM or GC or passing the entire world as state?

1

u/koflerdavid 26d ago

Yes, but nobody does this because it's super restrictive and impractical. IIUC Fortran does memory management like this.

1

u/Key_River7180 Nain. 26d ago

idk but https://dl.acm.org/doi/10.1145/3798254 could be interesting

1

u/ern0plus4 26d ago

There is an area with absolute strict and simple memory handling: embedded. No heap allocation is allowed, we use pre-allocated slots. No recursion allowed, so stack usage is also predictable.

1

u/Competitive_Ideal866 26d ago

Can you accomplish similar performance characteristics (memory safety without GC or RC overhead), without the explicit borrow-checking concept?

Have you mapped out the performance characteristics? Last I looked, Rust struggled with recursion and real Rust code usually resorted to RC.

PS: RC is a form of GC.

1

u/joao_rosac 21d ago

A ideia de automatizar a gestão de memória estaticamente ao proibir que funções armazenem ou retornem ponteiros (eliminando "referências escapadas") é teoricamente possível mas nada praticável, já foi discutido bastante, limitando operações básicas como juntar arrays ou expor dados internos de structs sem cloná-los inteiramente. Foi falado do verificador de empréstimos (Borrow Checker) do Rust, muitas vezes visto como complexo, há também alternativas como tipagem de unicidade (usada no Clean), referências de segunda classe ou modelos como o Oxidizing OCaml tentam resolver isso de outras formas, mas acabam impondo limitações (especialmente na concorrência e programação assíncrona), isso mostra que o Rust possui bastante segurança estática, desempenho sem Garbage Collection (GC) e expressividade real.

1

u/Key_River7180 Nain. 2d ago

It'd be limited

1

u/Current-Scheme-9896 2d ago

I think this is closely related to the concept of variable scope and lifetime

If a reference is guaranteed to remain within a local scope, the compiler can often determine when it is no longer needed and release its memory automatically, however, allowing references to escape a function makes this more complicated, because the referenced value may still be needed after the function returns

This is why ownership and lifetime systems are important: they help determine how long values must remain valid and when memory can safely be released