+1, this is carbon copy of what Zig compiler does, without attribution. Not good, even if it is useful to popularize the trick.
Incidentally, I’ve been thinking about this recently, and it seems you can get even more compact:
You can encode extra information in the order of nodes. So you can reduce 2x u32 to just a single u32, storing subtree size. You’ll loose random access to nth child, but it’s unclear if that matters. If the child count is larger, you want to iterate them anyway, and if it is small constant, the access is O(1). I am very curious (as in, writing a parser and agonizing over which repr to pick) to learn what wins here. Is that extra u32 matters?
You can go further, and observe that for most nodes children count is known statically, and for dynamic nodes you can inject a synthetic “this was the last child”. You loose the ability to iterate just direct children, jumping over indirect descendants. But if you are doing white tree processing, maybe that’s fine? This I gather is what Carbon does.
zmitchell | 12 hours ago
To be clear, this is mostly copying how Zig's own parser works (at least at the time of this article): https://mitchellh.com/zig/parser
matklad | 9 hours ago
+1, this is carbon copy of what Zig compiler does, without attribution. Not good, even if it is useful to popularize the trick.
Incidentally, I’ve been thinking about this recently, and it seems you can get even more compact:
You can encode extra information in the order of nodes. So you can reduce 2x u32 to just a single u32, storing subtree size. You’ll loose random access to nth child, but it’s unclear if that matters. If the child count is larger, you want to iterate them anyway, and if it is small constant, the access is O(1). I am very curious (as in, writing a parser and agonizing over which repr to pick) to learn what wins here. Is that extra u32 matters?
You can go further, and observe that for most nodes children count is known statically, and for dynamic nodes you can inject a synthetic “this was the last child”. You loose the ability to iterate just direct children, jumping over indirect descendants. But if you are doing white tree processing, maybe that’s fine? This I gather is what Carbon does.
Some recent discussion: https://zsf.zulipchat.com/#narrow/channel/454360-compiler/topic/Denser.20AST/near/609424340
zmitchell | 4 hours ago
You say that like I'm not already trawling the ZSF Zulip daily 😅
WilhelmVonWeiner | 10 hours ago
I believe it's an almost-entirely LLM-generated article probably fed that URL as part of the prompt.
coxley | 5 hours ago
Yeah :/
[OP] sanxiyn | 10 hours ago
Maybe, but the article is about Yuku not Zig, and Arshad is in fact the author of Yuku.