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.