Comment by jagged-chisel
2 days ago
> The fact that I can have a LRU cache that changes what's at the front by shuffling some pointers, while still keeping stable addresses so the hash map stays stable? That's freaking cool. Atomic operations with pointers for linked lists is really slick for implementing an allocator's free list between threads. Being able to walk a live heap using a breadth first search by just... following pointers, made the elegance of Dijkstra's algorithm come alive.
I feel like these kinds of things should be transformations that the compiler can use to turn Provably Safe code into performant code, i.e. you write the safe code and, once the borrow checker is happy, the compiler does its magic. I have no idea how to codify any of it into a compiler pass, or whether it's actually possible...
There's some interesting work going on with this with Metamath Zero[0], where he's working on verifying everything down to the compiler, to make sure the compiler always emits correct code. His language, Metamath C, also allows for refinement types, which means you can prove certain properties. It's still in its infancy, but I've been watching it from the sidelines for a bit now.
Though in terms of practicality, Graydon Hoare has mentioned in the past that he isn't a big fan of complex systems, and so it's better to have a simple type system that covers 95% of the cases, and an escape hatch when it doesn't. I think that's still a fair assessment, but I've fallen down the proof rabbit hole so I am curious to see how far it could be pushed.
[0] https://github.com/digama0/mm0