Things happen, if however slowly. As promised in my December 2019 article, I am now working on a little stack based language to represent audio functions. It'll be implemented in C rather than Scheme, which I also predicted. That writeup was very exploratory and needlessly complicated. I think I've figured out a one-pass way to compile conditionals, which I'll jot down here. It could also be less than ideal or just plain wrong; I've only worked this out on paper.
The following code
if (x < 100) {
x * 4;
} else {
x * 2;
}
might be represented in theoretical stack lang as
x 100 < ? x 4 * : x 2 * ;
and compile to the following bytecode
x 100 < ? 11 g x 4 * 14 g x 2 *
where g is a GOTO function that pops a number from the stack and jumps to that address (assuming zero indexing). An address beyond the length of the program halts execution.
When ? is evaluated, it skips 2 tokens if the condition is true, and none if the condition is false.
101 100 <. This is false; pop 0 on evaluation stack.? reads 0 from stack, does not skip 2 tokens.11 is pushed on stack, g pops stack and jumps program to index 11: x 2 ….x 2 * is evaluated and program ends with a return value of 200.50 100 <. This is true; pop 1 on evaluation stack.? reads 1 from stack, skips 2 tokens to x 4 ….x 4 * is evaluated, pushing 200 to the stack.14 is pushed on stack, g pops stack and jumps program to index 14: end of program. 200 is returned.A great way to compile stack langs is with stacks themselves. Assume three constructs.
An I→P compilation function would handle tokens of I thus.
? → Write two bytes to P: α and g, where α is a placeholder for an address that will be jumped to. Push the address of α to S.: → Write two bytes to P: β and g, where β is another GOTO placeholder. Pop α from the stack and write the address of β+2 to its address. Push β's address to the stack.; → Pop β from the stack and write the current length of P to its address. Nothing is appended to P.t → Append the token t's bytecode equivalent to P.The most typical use case.
I → x 100 < ? x 4 * : x 2 * ;
P →
S →
The first few tokens are parsed without much manipulation.
I → ? x 4 * : x 2 * ;
P → x 100 <
S →
A GOTO is written when ? is encountered, and its address is pushed to S.
I → x 4 * : x 2 * ;
P → x 100 < ? α g
S → 4
The rest of the happy path is appended to P.
I → : x 2 * ;
P → x 100 < ? α g x 4 *
S → 4
A second GOTO is written for :, and α is overwritten with its address + 2. The new GOTO's address is pushed to the stack.
I → x 2 * ;
P → x 100 < ? 11 g x 4 * β g
S → 9
The second branch is appended to P.
I → ;
P → x 100 < ? 11 g x 4 * β g x 2 *
S → 9
|P| overwrites β at the second GOTO address. This jumps to the end of the program.
I →
P → x 100 < ? 11 g x 4 * 14 g x 2 *
S →
This compilation process kindly degenerates for non ternary operations as well.
I → x 100 < ? x 4 * ;
P →
S →
Same as before.
I → ? x 4 * ;
P → x 100 <
S →
Same first GOTO.
I → x 4 * ;
P → x 100 < ? α g
S → 4
Same first branch.
I → ;
P → x 100 < ? α g x 4 *
S → 4
; is read and α is overwritten to jump to the end of the program. A second branch never enters the picture.
I →
P → x 100 < ? 9 g x 4 *
S →
Stacks reveal their true utility when working with nested conditions. Consider the following.
if (x > 100) {
x + 1;
} else if (x > 50) {
x + 2;
} else {
x + 3;
}
Its I would read as follows.
I → x 100 > ? x 1 + : x 50 > ? x 2 + : x 3 + ; ;
P →
S →
Reading through the first conditional creates the first GOTO, as always.
I → x 1 + : x 50 > ? x 2 + : x 3 + ; ;
P → x 100 > ? α g
S → 4
Reading until the first : still allows α to be overwritten, and pushes β.
I → x 50 > ? x 2 + : x 3 + ; ;
P → x 100 > ? 11 g x 1 + β g
S → 9
The second branch is itself a conditional, which defers the calculation of β's GOTO until the full length of this expression is known. A third GOTO must also be written, with its address pushed to S.
I → x 2 + : x 3 + ; ;
P → x 100 > ? 11 g x 1 + β g x 50 > ? γ g
S → 9 15
The inner condition's : pops γ and writes to its address, then creates a fourth GOTO, whose placeholder address it pushes back onto S.
I → x 3 + ; ;
P → x 100 > ? 11 g x 1 + β g x 50 > ? 22 g x 2 + ω g
S → 9 20
Reading until the first ; ends the inner expression by calculating ω's GOTO as |P|.
I → ;
P → x 100 > ? 11 g x 1 + β g x 50 > ? 22 g x 2 + 25 g x 3 +
S → 9
Reading the last ; finally pops β and uses the same |P| as its GOTO value.
I →
P → x 100 > ? 11 g x 1 + 25 g x 50 > ? 22 g x 2 + 25 g x 3 +
S →
I can only assume this holds true for an arbitrary nesting of conditions, but we'll see.