I built a garbage collector for a language that doesn’t need one

Makes more sense to me that a language/framework/etc. would 'oxidise' to Rust, and someone learning/getting hooked on Rust would 'carcinise'.

But this is all silly and doesn't matter anyway, ha!

I know there's a nontrivial overhead to using index-based references, especially since CPUs can't easily predict load operations. This gives me an idea: create a CPU architecture where pointers are actually (object, offset) tuples, enabling better on-metal performance with index-based references. I've neither the time, money, expertise, nor energy to implement such a thing, but it would be really cool if it existed - maybe CHERI is a close approximation, though I haven't looked very closely at it.

I dunno, isn't a usize index into a collection essentially just the same as a pointer? Ok it's a bit safer because you at least know the type of the object you're accessing is correct, but you can still get e.g. use after free bugs.

I think Jonathan Blow is right and wrong - it is a hack to get around the borrow checker, but also that's totally fine. The borrow checker still works for the other 95% of code you are writing. Nobody ever claimed it was the perfect solution to every problem.

Heap integrity / reachability is a dynamic property of a running program, and so all the static solutions basically end up as half-measures. (I imagine this would include using macros, though I don't know exactly what you mean),

FWIW this is my experience - https://www.oilshell.org/blog/2023/01/garbage-collector.html

Take it with however many grains of salt, but I heard many static solutions proposed, and they're all "wrong" for the simple reasons in theory of computation.

Also, Rust's static memory management inherently clashes a bit with dynamic memory management. That's also a fundamental thing, and you can have a bazillion mechanisms to ameloriate it for some cases (which may be valuable), but the problem will still be there no matter what.

Rust already has precise heap allocations with Box and Rc/Arc without the need for GC. GC implies uncomputed heap allocation liveness deferring work until later.

> requisite time trudging through the lifetime swamp

Rust really isn't like that. It gets a bad rap.

> I couldn't couldn't imagine running my whole life on the stack

Most of the things you touch in Rust are heap allocated.

> this would be a really nice language if it were garbage collected

It is a nice language, and all of your complaints go away once you start using the language idiomatically.

Oh you can absolutely say that.

It's just a dumb take. Because there are already languages which have a solid type system, a functional bent, and a GC. And you can probably bang out one yourself if you want.

If that was what Rust was, it probably wouldn't have existed in the first place, Mozilla would not have been interested in it in the second place, and no community would have gelled around it in the third place. Hell, it was specifically dragged further downstack by the people who coalesced around its potential in that space.

Edit: Well, I didn't think it through. You're correct. A "perfect GC" is indeed undecidable, and all the real world, practical GC have "false positive" (a piece of memory is no longer used by the code, but there is no way to know it). A perfect GC without false positive is equal to halting problem.

Example:

  var obj = new Object();

  // === real code begin 
  ... 50 lines of real code that never uses obj
  if (something == true) return;
  ... another 50 lines of real code that never uses obj
  // === real code end

  obj.doThings();

The conservative approximation that GC's make is that they keep all objects that could be accessed in the future by the program (reach-able) instead of only keeping the objects that will be used in the future.

A trivial example is:

    void main() {
      var obj = new Object();

      while (true) {
        // Do other work...

        if (dayOfWeek == 9) {
          print(obj);
        }
      }
    }

1. The GC frees objects that could be reachable (program gets corrupted in spectacular ways).

2. The GC never frees anything (as it can't decide).

The GC may not dispose of objects immediately, but when it determines they're not reachable, they're not reachable, period. There's nothing undecidable about it.

The issue is not necessarily unreachability being undecidable. The issue is that reachability depends on control flow. And that implies being conservative which translates into having to deal with false positives.

That static analysis in a nutshell: how to get precision and soundness.

Probably a mere question of terminology.

Rust is facing a similar problem in terms of sync vs async, which seems to limit options primarily for folks who want to avoid async, but it doesn't seem like a major blocker for adoption comparatively.

Overwhelming majority of mainstream programmers want important choices to be made for them.

- People want language designers to decide: Has GC or no GC. Choose one and be consistent with it. Then all the libraries will be written on top of it.

- People want language designers to decide: Has async green thread or not. Choose one and be consistent with it. Then all the libraries will be written on top of it.

- People want language designers to decide an auto format syntax style. Choose one and be consistent with it. Then all the libraries will be written on top of it.

etc. etc.

Rust takes its fundamentals from more advanced and well thought out functional languages. As a result it outclasses D and its ilk.

I actually haven't read that paper! Thanks for sharing it. What I'm doing is slightly different - it looks like they're building a conservative GC with an unsafe API, much like one might for C. My intent was closer toward building a GC which can be used with any safe Rust code more or less unconditionally.