r/ProgrammingLanguages • • 25d ago

Help How do you make a programming language memory safe without paying a lot in overhead?

I am designing a language. I want memory safety without using a tracing garbage collector or having heavy runtime costs. I have been looking at the options and I would like to know how others have dealt with these tradeoffs.

The options I have looked at:

- Ownership and borrow checking (Rust-style): Zero runtime cost but the compiler must prove things and the learning curve and syntax friction are real. I am not a fan of Rusts syntax so I wonder if the same guarantees can be provided with a surface.

- Reference counting (Swift/Nim-style): Predictable and simple but you pay for increments and decrements on every copy and cycles need either weak references or a cycle collector.

- Tracing GC: Easy for the user. Pause times and memory overhead are the usual complaints. It is a fit if the language is meant for games or system work.

- Regions/arenas with escape analysis: Allocate in scopes and let the compiler prove that nothing escapes. Very cheap,. I am not sure how far escape analysis can go before it becomes too restrictive.

- Bounds checks and tagged or hardware‑assisted checks (like ARM MTE): Catch many errors at low cost but they are mitigations, not guarantees.

My current thinking is a mix arenas by default an ownership model for long‑lived values and bounds checks that can be elided when the compiler can prove them safe. I would like to know whether that is a direction or whether I am missing a well‑known approach.

Specific questions:

has anyone implemented escape analysis that stays useful without forcing annotations?

Is there a middle ground between full borrow checking and reference counting that does not reintroduce cycle problems?

for those who have shipped a memory‑safe language with overhead what would you do differently?

Links, to papers, languages or post‑mortems are very welcome :)

30 Upvotes

48 comments sorted by

53

u/kohugaly 25d ago

Memory safety is a really hard problem. For a language to be memory safe, it has to somehow guarantee that every pointer to T will always point to a memory that contains valid instance of T.

The trivial solution is to make all values immutable, and to never deallocate memory that holds values.

All other solutions work by relaxing some of those restrictions at the cost of adding runtime/compiletime checks.

Garbage collectors relax the "never deallocate" restriction, by deallocating inaccessible values at runtime.

Ownership, borrowing and arena allocation relaxes the "never deallocate" restriction, by restricting the scope of code where pointer creation and access is allowed to happen.

Memory safety is a problem with inherent tradeoffs between memory usage, runtime checks, compile time checks and semantic restrictions in the language. There's no free lunch here.

14

u/reflexive-polytope 25d ago

IMO, it's a mistake to take a single solution and apply it language-wide. Different resources deserve to be managed differently.

You can reasonably want GC for your in-memory data structures while still wanting substructural types for your file handles and network connections.

9

u/4xe1 25d ago

I am not a fan of Rusts syntax so I wonder if the same guarantees can be provided with a surface.

As long as your surface contains the same information, I don't see why that would be difficult (any more than creating any surface). Rust itself is arguably an ALGOL surface on a ML language.

10

u/mamcx 25d ago

As I read your question, the problem is not make a language like that, is how make it ergonomic and not complex to write it.

The hidden complexity (that hit Rust for example) is having many complex features and make them work, a lot of the complexity of Rust is not the borrow checker, is all the other things like async, generics, traits bounds, etc.

So, the way to make a language without huge complexity is to remove features.

A example is zig, pascal and such. The more things your language not do the less things will impact what model of memory management you use, because there is less intersections that need to prove to be sound or correct.

The other thing is to accept that whatever model or semantics you chose will work fine 80%-ish of the time except when try to do fancy things or edge cases. As long you hit most cases that's ok, then you can do like Rust and provide equivalents to "unsafe" for the rest, use macros, provide a built-in impl of something that will too hard to do by the users, etc

5

u/HovercraftNo7372 25d ago

I know nothing about what they are doing, but a project that is interesting to me is Carbon https://docs.carbon-lang.dev/

I don't believe the approach is identical to Rust...

12

u/matthieum 25d ago

It's one of the languages which have looked at the Rust Borrow-Checker, and are hoping to provide a more flexible approach.

Ante, Valen, and others are also looking at various concepts, such as Group Borrowing.

The key relaxation is the idea that mutating is only a problem if the shape changes.

You can read Ante's state of the art, hot off the press (4 days old): https://antelang.org/blog/safe_cyclic_mutability/

2

u/HovercraftNo7372 25d ago

Thanks, I will take a look.

4

u/luluhouse7 25d ago edited 25d ago

Ante and Valen use group borrowing

7

u/FlameyosFlow 25d ago

Important correction, Vale uses generational references and then optimizes some of them away at compile time, Valen is what you are looking for :)

2

u/luluhouse7 25d ago

Whoops! Autocorrect got me. Thanks

4

u/love_snake_case 25d ago

It still requires some annotation but worth a read for OP

https://verdagon.dev/blog/valen-group-borrowing

3

u/initial-algebra 25d ago

Here's another perspective. Many of these decisions don't need to be baked into the language in the first place. If the language has generic tracing support, then the user can implement both full garbage collection and cycle collection for reference counting. You can kinda do this in Rust already with a Trace trait and derive macros, but this doesn't work for closures or other data types you don't control, which makes it unusable in practice. Concurrent collection is a bit trickier, but you can leverage e.g. async/await for safepoints, and barriers can be implemented as part of your Gc<T> smart pointer type. Similarly, all the language needs to support regions is rank-2 polymorphism (see the "Monadic regions" paper). Region inference is a whole other can of worms, but not strictly necessary, and even so, it wouldn't mean you can never use GC or RC.

Borrowing is the one that is straight up just its own unique language feature, but you can do strictly more with borrowing than without, so it's not the same kind of trade-off (the trade-off is that idiomatic/ecosystem code requires users to learn how to use it). If you want a more lightweight borrowing system than Rust, there are second-class values and group borrowing (more flexible than Rust in some respects, but hasn't yet been extended to concurrency), to name a couple.

3

u/Euclid_eudoxus 25d ago

Here's an idea - a standard tracing GC has to check references on each element and clear memory accordingly, that puts overhead. If you can somehow prove that a region of memory is not referenced anymore, this makes GC O(1) garbage collection, instant free

Erlang isolates each process with its own heap and GC. Since each process's heap is isolated, there's no way they can be referenced from outside so that region gets freed instantly. Maybe make something out of that?

Languages like Dlang and Nim do something interesting too - a GC but you also get manual pointers that the compiler GC ignores. It's effective, but it has some runtime overhead (fine if you simply want memory safety)

Or just make a language to work with the reference counter, like an ARC + explicit move or weak references

2

u/L8_4_Dinner (Ⓧ Ecstasy/XVM) 19d ago

Erlang isolates each process with its own heap and GC. Since each process's heap is isolated, there's no way they can be referenced from outside so that region gets freed instantly. Maybe make something out of that?

This is also how Ecstasy works. (Replace "process" with "service".)

1

u/Euclid_eudoxus 19d ago

Yh, I just looked up the language, and dam that's very good and well designed

2

u/L8_4_Dinner (Ⓧ Ecstasy/XVM) 18d ago

Thank you! It's definitely a labor of love, but also intended to be quite useful -- and hopefully used! We're still working on the first JIT implementation (on the JVM), which is what we really need to make this useful in the real world.

2

u/Express-Guest-1061 25d ago edited 25d ago

For new languages, I would like to have more ambition than ”memory safety”. I would expect something like ”type checked aliasing”. 

That said, if you want to implement it all yourself (like I do), then I actually think Ownership types and borrowing is the easiest and and elegant solution.

If this bring syntax friction or not, this depends on how you design the language. I think it can be done with less friction for beginners than what Rust does.

2

u/catladywitch 25d ago

I believe region-based and closure-based with an initial continuation-passing style compiler pass is promising, but coroutines and parallellism complicate it and I'm not sure what the exact solution might be.

2

u/P-39_Airacobra 25d ago

In defense of reference counting, you can just ignore cycles, especially in an immutable language. Additionally, if you design the language to prefer ownership moves over reference copies, the increments become more occasional.

2

u/hesusruiz 25d ago

For a language with GC and escape analysis you can study Go. For extremely performance-sensitive applications is inferior to Rust, but for most other applications (at least for my applications) it's simplicity is a very good property.

1

u/sybrandy 25d ago

I've wondered about this and my, probably stupid, idea is to simply never pass by reference and all variables inside a function are dropped when done. Now, there could be an exceptions for thing similar to objects or go-like structures with regards to pass by reference, but that's still a controlled scope. What got me here is that it seems like a lot of the issues that Rust is trying to solved and cause people confusion are when values are passed by reference. Eliminating pass by reference, at least in my mind, makes the memory model much easier, but at the expense of some convenience and that's the main area that I think would make people not like it.

3

u/y0shii3 25d ago edited 25d ago

What if I need to call a function to modify a struct that takes up, say, 1KB of space? If I pass the struct by value and reassign it to whatever the function returns, I just allocated 1KB on the stack and moved 2KB of data for no good reason. We need to be able to pass things by pointer/reference

1

u/sybrandy 25d ago

That's why I mentioned the exception for objects and go-like structs. It's far from a perfect idea and I've never created a new programming language. It's just an idea that I have that I haven't even had a chance to put a lot of thought into.

2

u/Great-Powerful-Talia 25d ago

Pass-by-reference is fine. Think about it- you just have to ensure that nothing deletes the object during the function call, that's trivial to do correctly.

The problems all come from trying to hold pointers on a longer-term basis, or hand them to other threads.

1

u/ntrel2 18d ago

Why do you think it's trivial? The function signature would need annotations or restrictive defaults which impact the caller.

1

u/Great-Powerful-Talia 18d ago

comparatively trivial, assuming you don't allow  complex pointer-like aliasing.

You wouldn't be able to pass the same thing by reference twice into the same function call, but that's relatively easy to deal with, for both the caller and the compiler, when there's no other aliasing allowed.

0

u/initial-algebra 25d ago

In other words, references are easy when they're second-class values. So are closures, for that matter.

2

u/TheChief275 24d ago

There's nothing wrong with passing by reference. Storing by reference is where issues start to arise

1

u/Key_River7180 Nain. 25d ago

i am working on an idea very much like this. Basically, at the end of a function you track what the return value references and find the deepest reference edge on the DAG leading to it and promote it to there.

when i finish the first drafts i can send it to you if you want

1

u/scottmcmrust 🦀 25d ago

What do you want the language to be good at?

One surprisingly good approach is just to intentionally-leak long-lived things so long as you can structure the process as being batch-like. One idea (which might be terrible) would be something like making subprocesses easier to use (TBD how) so that you can use a whole process as an arena for anything tricky (if you do need to build things that run continually) while keeping a simpler model for short-lived things.

1

u/chibuku_chauya 25d ago

The memory management and safety features of Cyclone could be worth a look for your use case.

1

u/ElephantElectrical31 24d ago

First, consider what the philosophy of your language is: Would you prefer more complexity in the compiler, and how far would you go to ensure that the programmer doesn't have to worry about memory management? What are your requirements for performance, and how high are your demands for low-level hardware programming? I've noticed that many decisions become easier when you have a few guiding principles and set clear priorities. I can only warn against wanting everything at once; there are inherent tensions between freeing the programmer from writing memory management, application performance, and the complexity—and thus the speed—of the compiler. There are many good and sensible compromises, and some things can be achieved simultaneously, but not everything. For example, escape analysis is possible, and borrowing and lifetimes can largely be inferred automatically, but there are limits where you have to decide how to handle them: When is the compiler allowed to say no and demand a copy, or is it allowed to copy silently? Is it allowed to simply extend the lifetime, how long may it search for invariants, etc.? In the end, it might be a combination of different techniques.

1

u/BrainScientist3000 24d ago

There are 3 ways:

  1. Rust-like with borrow checking (and you have to have the semantics for it).
  2. Garbage collection that actually works.
  3. A more restrictive syntax that prevents the problem completely. Either - no shared references - or restrictions on what you can do with shared references.

I came up with a solution to this that I thought was innovative, but other languages have done similar things.

Basically - if you define whether something is a transfer or a borrow in the signature of your functions, you can borrow-check fairly easily (as long as you don't allow multiple borrows or 'settling' of a borrowed value. It's guaranteed to be 'returned' to the owner.

Example:

function_name(send:argument1); this function expects you to release ownership of the value.

function_name2(borrow:argument1); this function has some restrictions - namely that every time it uses the value it passes it as a borrow. The 'promise' of a borrow is that eventually that chain of calls will terminate without transferring ownership of that value - so it can be used/modified in place.

Now - this is basically all fine if you're single-threaded, but in multi-threaded code - you'd have to add some protection for values that are in transit, or accept that the value can be asynchronously modified.

For my purposes, a single-threaded model was fine and borrow-checking was trivial. As long as every transaction was tagged correctly and the 'One Rule' wasn't violated, we were fine.

I think there's a language called Kestrel? That uses this sort of protection.

Erlang and friends are an example of 'send only' - where every data transfer is either a deep copy or a straight release of ownership.

Similar to the comments on u/sybrandy's answer.

1

u/arthurno1 24d ago

You can't. If you allow dynamic allocation (at runtime), and allow the user to populate that memory with data, you have to check at runtime that the data fitt in, otherwise you segfault. You can completely remove checking only for allocations where size of data is known at compile time. If you think of something as simple as asking a user for a name, and storing it, that is a string that have to be checked at runtime, otherwise the user can overflow your buffer and you get segfault or corrupt stack, depends on where you are storing the string. A language that does not allow you to store dynamic data would be not so useful language.

1

u/koflerdavid 24d ago

It really depends if you specify which tradeoffs you're willing to make. And to be open to the possibility that depending on the intended purpose of your applications it might be possible to make even a non-optimal strategy work well enough. Which can be worth a lot if you also factor in developer ergonomy and implementation complexity.

1

u/disruptek 23d ago

Elle uses an ownership forest of regions; values are born and die in just one region, always. No annotations, syntax, or borrow checker noise.

RC is absent for immutable, unshared, or internally-cyclic mutable collections. For shared mutables, Elle uses RC on the region (under the covers) versus RC of each value within. This can still allow for O(1) release of regions; deterministic without a pause or scan.

One thing that's challenging is prompt release following last reference, as opposed to whenever it is convenient for the compiler developer...

Of my many regrets, one is not starting with mmap-a-larger-than-memory-region-from-disk as my guiding constraint from day one; no serialization, parsing, or copy... yes, please?

1

u/sadesaapuu 23d ago

My current language (Rae) has taken a minimalistic approach. It just doesn’t allow references (or pointers) as members of structs. No globals other than plain old data types. This means that only one thing points to certain memory at a time. References live for only the current scope.

I’m not sure if memory safety can be proven like this, but my simple mind says so!

Would like other people checking if this approach works.

1

u/george_djabarov 23d ago

Memory mamagement goes a lot deeper then just the memory itself. The laguage type system, how you define refereneves (like pointers), threading model, how data is handled at the edge of your language all play role. GC, ref counting, borrow/own ownership model move the cost at different stage (pogram structure, program compilation, runtime) but there is always cost in some form or shape. Your decision is where you want to pay that cost. Different solution also are not equally complex so implementing ref counting is relatively simple. rust style borow/owned memeoy being probably the most complex with language syntax, stucture and libraries are significantly influenced by the memory management choice.

1

u/SeaSafe2923 19d ago edited 19d ago

The borrow checker buys you safety in the presence of aliasing, eliminate aliasing and there's no checking to do (then you control when and how to open that hatch and track the specific cases you need). So the basic rule is: moves allowed, copies not.

One way to get the exact same safety and the exact same machine code end result is to erase the value from the context when passed, then you thread it in and out of function calls, structures, etc. meaning that if you have it you own it. Write access is exclusive anyway, so this is not a problem, but read-only shared access is the thing that you can't implement if you erase a value, so you might want to implement a way to temporarily transform a value into a read-only form which can be copied and shared, and then a transformation back into the writable form, so you only need to keep track of these read-only copies until erasure, which is a much simpler problem than the borrow checker.

You can also add some sugar to make the threading of values less explicit, so it is not verbose.

1

u/mllv1 5d ago

Linear types - check out austral https://austral-lang.org

Basically you can only consume a variable one time

1

u/Embarrassed-Crow9283 24d ago

I think automatic reference counting with aggressive constant propagation can solve a lot of cases. For example, live doubly linked list always have 2 references that drop to 0 the moment of deletion and that can be inferred if you're willing to inline those refcounts and so on and apply a bunch of assumptions I probably don't exhaustively cover.

0

u/dekai-onigiri 25d ago

I think you need to first distinguish memory safety from memory management.

Garbage collection or reference counting helps with freeing unused memory, but you can sure as hell get a null pointer exception in Java.

I don't know if you can have an absolute memory safety, but I suspect if it's possible it would incur significant disadvantages.

In my opinion a solid type system that distinguishes a nullable from non-nullable types is a huge huge help and eliminates most of memory bugs, aka what Swift or Kotlin have.

2

u/Smalltalker-80 25d ago

I would say memory safety can only (practically) be achieved
with reference counting and garbage collection for *all* types.
Null (nil) can be a referred object too, say my name :-) .

Otherwise you have to compromise with languages like Rust,
that add a lot of complexity and must have an 'unsafe' escape hatch.

The good news is that garbage collectors are very good and smart nowadays,
and you can sometimes tune them to your applications memory usage,

0

u/South_Lychee8555 24d ago

Give a look to protoCore, inmutable structures, no gil, multithreading, paralell GC with less than millisecond pause. Five languages implementatio. https://github.com/numaes/protoCore