¶Can you compile quotations in parallel?
2023-10-13
@max22- asked on Mastodon:
is it possible to compile quotations to assembly the same way as simple functions on this slide (at 35 minutes) ?
“Compiling stack programs” slide from
my Strange Loop talk on concatenative programming
The short answer is “yes, but not as easily”. There are a few wrinkles you have to consider:
First off, in the talk, I mention that you can choose to break your program into pieces “anywhere you want”, but that's a bit of a white lie. When you have quotations, you have to choose whether program concatenation needs to be aware of syntax. That is, are you allowed to choose a cut-point in the middle of a quotation? Or does each quotation need to be “atomic” — something that you can't break into pieces? The easier choice is that you can't break apart quotations when choosing your cut-points.
The next wrinkle is that you're going to have to compile the body of each quotation into a separate buffer, and what you'd push onto the stack is the location in memory of the resulting assembled code. So you'd generate a unique label to put at the start of the quotation's assembly buffer, and back in the “main” code, you'd add some assembly to push that label onto the stack:
mov %ax, LABEL push %ax
Then you have to figure out what assembly to generate for apply. In my talk, when I was stepping through executing a stack program “by hand”, we applied a quotation by moving its contents “back to the right”. But that won't work with the assembly programs that we've generated — there is no (easy, safe, worth the hassle) way to dynamically move the assembled machine code into place where our current instruction pointer is. Instead, you'd lean on the analogy that applying quotations is just like invoking functions, and do the same thing that you'd do in a compiled/assembled program for function invocation. You'd assume top-of-stack is a quotation — that is, the location in memory of the quotation's compiled code. And the assembly for apply would be
pop %ax jmp %ax
But now you have to figure out how to return to the main instruction stream when the quotation's code is done! That sounds an awful lot like a return stack — i.e., we should use CALL instead of JMP, so that we can use RET to return back. Unfortunately, it's not quite as simple as just doing that, because it means you need two stacks: the value stack we've been discussing all along, and a new “call stack” to track the stack of quotation applications that we're in the middle of. We started with the idea of using the x86 stack to model the value stack, and we can't easily use it to model both the value and call stacks. It's a more natural fit for the call stack, so we'd have to put the value stack somewhere else in memory, track it with a different register than ‘%sp’, and update the assembly snippets for all of the instructions to use this new location/snippet for the value stack.
And at that point, yes, you'll have found a way to compile quotations too, in parallel.