Re:uxn: a portable 8-bit virtual computer
by AnIdiotOnTheNet on Monday May 17, 2021 @04:07PM
(#27187803)
> As one might imagine, a naïve implementation of this spec would be extremely slow (for example, decrementing n requires incrementing another variable m in a loop until m+1==n, which is O(n)).
Yeah, see that seems to go way too far, but then again this stood out as similar to ideas I've had:
> The algorithm for decrementing an atom is to count up to it, an O(n) operation. But if the interpreter knows it's running a decrement formula, it can use the CPU to decrement directly.
I had basically the same idea, only since my ideas still look a lot more like an instruction set it was in the form of explicit annotations to identify functions that could be replaced with a specialized instruction if available.
I'll have to look into this thing. Thanks.
Re:uxn: a portable 8-bit virtual computer
by thewakalix on Monday May 17, 2021 @10:57PM
(#27190809)
Nock does in fact use explicit annotations (called "hints"). I believe it also verifies that the annotated code "looks right" for the hint, but I don't think it scans all code fragments to see if they implement decrement (for example).
You might appreciate appreciate Urbit's Nock, a "functional assembly language" based on combinator calculus which can be specified in ~40 lines of text, and implemented in ~100 lines of code:
https://urbit.org/docs/nock/definition/
As one might imagine, a naïve implementation of this spec would be extremely slow (for example, decrementing n requires incrementing another variable m in a loop until m+1==n, which is O(n)). A regular JIT can make even the braindead implementation decently fast, but in practice, specific implementations are recognized by the interpreter and replaced with faster ones. The benefit of this approach is that the code itself is rigorously specified by the combinator definition, and you can point the finger at the interpreter if the output from the optimized version differs from the naïve implementation.