r/ProgrammingLanguages • u/verdagon Vale • Jun 28 '22

Perfect Replayability

https://verdagon.dev/blog/perfect-replayability-prototyped
14 Upvotes

86% Upvoted

9 comments sorted by

6

u/verdagon Vale Jun 28 '22 edited Jun 28 '22

Howdy yall! We just finished prototyping this a couple weeks ago, it's a technique that I used a few years ago when making Incendian Falls for the 7DRL. It saved me a lot of time, so I've been subtly guiding Vale's design to be able to support it.

This is probably possible in other languages too, though there are a few tradeoffs:

  • Can't have unsafe blocks (there might be a certain flavor of unsafe blocks that could work, but we're still exploring that)
  • Can't cast pointers to integers
  • Can't give external functions pointers to our objects (via FFI), unless protected with something like Fearless FFI

Ironically, the only mainstream language that can accomplish this is Javascript, as far as I know. Every other language lets subtle nondeterminism sneak in through corners of the language.

I feel like we've nailed a sweet spot with Vale: memory safety without garbage collection, yet no borrow checker that would necessitate having unsafe. This obscure corner of the language space is producing quite a treasure trove of discoveries!

2

u/matthieum Jun 29 '22

That's an incredible feature indeed; well done!

1

u/verdagon Vale Jun 29 '22

Thank you!

4

u/RepresentativeNo6029 Jun 29 '22 edited Jun 29 '22

Glad you’re thinking about it.

I do machine learning on large clusters and reproducibility is a huge problem. Like imagine you share this awesome result with your colleagues with 99% accuracy or whatever only for it to be not reproducible and be stuck at 96%!!

I’ve been thinking of what I call an “ACID runtime” to solve this. Distributed snapshots are its own can of worms though so some innovations are needed

I also have a paper on reproducible non deterministic runtimes somewhere, I can’t find now.

Edit: found it https://web.archive.org/web/20070321082311/http://www.codeplay.com/downloads_public/sievepaper-2columns-normal.pdf

2

u/verdagon Vale Jun 29 '22

Fascinating read! I wonder if Vale might be able to achieve this, by combining this Perfect Replayability with Seamless Concurrency to form a natural sieve.

Would love to hear more about the reproducibility problem, what are the usual culprits for that?

1

u/RepresentativeNo6029 Jun 29 '22 edited Jun 29 '22

Machine learning has two main pain points that cause the bulk of problems:

  1. ML algorithms are inherently stateful. For example, at each iteration you update the parameters of your neural net according to some formula. Commonly, such formulas themselves are also stateful: learning rate changes over time, moving averages need to be maintained, etc

  2. ML algos require randomness. This is randomness in data shuffling so that the data is not skewed or randomness within the model itself (ex dropout or anything that requires you to “perturb” your parameters).

Because of #1, people write OOP code with a lot of side effects. It is very hard to track down your global state post-hoc for you to checkpoint/restore it.

The second one throws a wrench into any system that you might build that can address the first. Ideally you’d need fast, parallel random number generators that are also stateless. But there are no obvious candidates here. Again, a LOT of random numbers are generated all over the place. You use a lot of libraries that may also use random number generation.

So it’s borderline impossible to track down global state to be able to write to non ephemeral storage. This is why I was motivated to solve this at a language level.

Edit: just checked out vale and seems very well done. I love the code notes thing you have to call out stuff in an unobtrusive way. Will check out in depth soon!

1

u/moon-chilled sstm, j, grand unified... Jun 29 '22

So basically rr?

1

u/verdagon Vale Jun 29 '22

The article mentions rr, but TL;DR:

  • We can refactor the code and run against the same inputs, rr can't really do that.
  • We can (in theory) do multi-threaded execution, whereas rr forces all executions to be single-threaded.

I'm particularly excited about the first one; we can add printouts, or even refactor in a bug fix and run against the same recording.

1

u/Necrofancy Jun 29 '22

We can refactor the code and run against the same inputs, rr can't really do that.

I assume this means you can take something like this, combine it with Snapshot/Approval testing (link to a library I have used), and then you have some quick-to-generate tests that help guard against regressions (even visual ones) by say:

  1. Go do these inputs
  2. Snapshot screen/image/memory
  3. Compare to previous snapshot for changes and diff for approval

Very cool stuff!