Implement fast operatives

[masak]

They are called fast operatives because like Kernel operatives and unlike regular macros, they run code rather than return an expansion result for the interpreter to evaluate. Accordingly, rather than interpolate the (code) arguments into an expansion result, the operatives run their arguments in a given dynamic environment -- an environment provided as an extra argument to the operative.

This PR implements the following low-hanging fruit fast operatives: do, or, case, aif, pcase, whenlet, awhen, whilet, loop, while, til, repeat, nof, poll, drain.

The fast operatives are pretty nice for implementing sequential and branching control flow, delayed/suspended evaluation, lexical binding, and accumulating into a list. They are not good for setting non-lexical places (like set and its kin), dealing with continuations (like eif or catch), creating actual unique variables (like letu), or dynamically binding variables (like bind or atomic).

Please rebase this PR on a solution to #414 before merging, as the implementations here are known to fail those tests. Done.

[raiph]

Perhaps I'm being so loose/generic in my thinking/question below that you can't get anything particularly useful from it, or feel like you can give anything much, but I'm sure I would get something from your reply, even if your reply is "I've no idea what you're talking about" or "Well, yeah, if you squint like crazy, but it isn't sparking anything especially worth sharing, other than that I'd rather not be crazy, or at least squint like I'm crazy".

---

Why do I feel there's a very strong connection between what you did here and the dispatch work jnthn has done over the last 10 years, culminating in new-disp?

[masak]

@raiph I feel my answer by necessity will have, qualitatively, a wide margin of error. Mostly because I don't grok jnthn's work on new-disp all that well. Which is to say, in the best case, you're onto something, and it's an astonishing connection which would cross-benefit both jnthn and me to understand better — and in the worst case, you're (borrowing your own insistent terminology) squinting like crazy and spotting formless similarities between patterns.

I could end my answer there, but let me try to spell out what it is that jnthn has done, and what I have done. Maybe that will help either or both of us to narrow the margin of error a bit.

Again, I'm not fully versed in what new-disp was about. There was a large gist that I started reading, and what was in there intrigued me, but I am ashamed to say I haven't studied it deeply enough to be confident about what new-disp is trying to do. (Partly this is me being slothful and distracted, partly it's about the difficulty of reading gists in my region of the world.) It was especially funny, because at the time when I was designing a VM instruction set for Bel, I snuck more than one look at how MoarVM handles calling conventions, and that's when jnthn told me he was re-implementing it all, and sent me the gist.

Here's what I think I understand about the effort: it's ultimately a way to make calling conventions (the "handshake" between a caller and a callee) more statically knowable, in order for the JIT to be able to do a better job optimizing and inlining. I don't remember any details, but I remember the feeling of reading it and thinking "hm, this feels like it's written by someone who has had years to observe where their first design falls short in practice, thereby designing the second round to take better advantage of missed opportunities". Like "second system syndrome", but when it ends well. :smile:

The present work, I explained in this comment over at alma/#302, but here's a self-contained short summary: fastfuncs are pure-Perl implementations of built-in Bel functions, eliminating not just interpreter overhead, but also some algorithmic overhead that would have to be eliminated either by a human or by a "sufficiently smart compiler". But built-in Bel macros (of which there are many) had no similar "smartmacro". The conceptual trouble with the smartmacro concept is that they would inevitably render Bel code, which — well, what can you do with it? — would unavoidably be sent to the Bel interpreter, which is the real thing we were trying to avoid. That is, smartmacros are certainly possible, but they are "Amdahl fools" in that they optimize the part that isn't particularly slow — the template-based code generation inside the macro. The slow part is then evaluating that template code.

The compiler-paradigm solution would be to move macros to a separate preprocessing pass, doing a bunch of macro expansion before the program even starts. This may sound like the obvious solution. But note that (a) it actually changes the semantics, in the sense that macros with side effects, or late-bound macros, or macros who otherwise depend on being called at runtime, won't work the same, and (b) more importantly, the Bel language specification says they should run at runtime, so there. Supposedly you're allowed to cheat (optimize surreptitiously in the background), but only if you don't get caught doing so. (Later edit: And the difficulty with that is that you'd need to prove the absence of any code that could change the meaning of any of the names accessed by the macro. That's a tall order in a dynamic language where any code can access anything in the heap, and where both aliasing and eval exist.)

Instead, enter "fastoperatives". They don't generate Bel code that we'll then be forced to send to the interpreter, losing by default. They just contain directly the Perl code corresponding to the Bel code the macro would've generated. In that sense, they really are the true cousins of fastfuncs; they contain the thing as Perl code. But in order to be that, they needed to be operatives (being the code), not macros (creating the code).

@raiph, on a whim I'm going to invite you to a private repository that I have been tinkering with. It's about a hybrid between Bel and Kernel, primarily replacing all the Bel macros with operatives. If it turns out that doesn't tickle your fancy at all, feel free to just ignore the invite, the repo, or both.

[masak]

Adding this in a moment of lucidity...

The problem laid out about fastfuncs in #169 applies equally well to fastoperatives. The fix, pleasantly enough, is also the same: as long as we track (using some kind of weak references) all the dependencies of a fastoperative, so that we can invalidate it when a dependency changes (and maybe lazily recompile it, in the fullness of time), that's enough to make it morally justified to compile Bel macros into fastoperatives in the first place.