Short-circuit Boolean AND and OR operators.

[Dunbaratu]

At the moment, Kerboscript's AND and OR operators don't do short-circuit Booleans. It was never formally defined whether they do or don't - its just that they coincidentally happen not to.

They really should.

(After this is implemented, then we can revisit old issue #18.)

This is my plan of attack:

AND case:

expr1 AND expr2 currently does this:

• Execute expr1, which pushes its result on the stack.
• Execute expr2, which pushes its result on the stack on top of expr1's result.
• Perform an OpcodeAnd - which pops the top two things and and's them, pushing the Boolean result of the and on the stack top

Changing it to short-circuiting means making it do this instead:

• Execute expr1, which pushes its result on the stack.
• br.false to "push false" opcode below.
• Execute expr2, which pushes its result on the stack.
• br.false to "push false" opcode below.
• push true // if it got this far, both expressions were true.
• branch to NOP Opcode below. // skip the false case.
• push false [target branched to from the br.false cases above]
• NOP.

  OR case:

expr1 OR expr2 currently does this:

• Execute expr1, which pushes its result on the stack.
• Execute expr2, which pushes its result on the stack on top of expr1's result.
• Perform an OpcodeOr - which pops the top two things and or's them, pushing the Boolean result of the or on the stack top

Changing it to short-circuiting means making it do this instead:

• Execute expr1, which pushes its result on the stack.
• br.true to "push true" opcode below. // (br.true doesn't exist yet- may make a new opcode or else do a 'not' followed by a br.false.)
• Execute expr2, which pushes its result on the stack.
• br.true to "push true" opcode below. // (br.true doesn't exist yet- may make a new opcode or else do a 'not' followed by a br.false.)
• push false // if it got this far, both expressions were false.
• branch to NOP Opcode below. // skip the true case.
• push true [target branched to from the br.true cases above]
• NOP.

BREAKING: This makes some simple small boolean expressions take more opcodes to execute, but makes more complex ones take less opcodes to execute. Increasing number of opcodes executed means breaking some people's trigger code that was nearing the limit, or increasing some people's program sizes.

This will have the side effect of rendering OpcodeOr and OpcodeAnd rather useless, as short circuiting accomplishes the same effect by jumping past sections of code rather than by comparing two operands. It's unclear whether they should remain in the Opcodes. They probably should for the sake of other future language bindings, or for running KSM direct files, even though I'm nervous about leaving in a feature that doesn't get exercised (and therefore can become incorrect after future changes, without anyone noticing that it broke.)

[Dunbaratu]

I really think we should increase the disk sizes a bit. I feel the constant pressure not to make the KSM files any bigger and that pressure feels really crippling. This is a change that would increase KSM size a bit.

[erendrake]

@Dunbaratu lets do it. I never want diskspace to make things impossible. i just want it to be a design consideration.

[abenkovskii]

@Dunbaratu Your solution adds 5 opcodes to every and and or (not counting nop and not in br.true) I believe I found a more compact solution: expr1 and expr2:

expr1
br.true --> expr2
push false
branch --> nop
expr2
nop

expr1 or expr2:

expr1
br.false --> expr2
push true
branch --> nop
expr2
nop

[abenkovskii]

It adds only 3 opcodes per operator.

[Dunbaratu]

@abenkovskii Your way adds more when there's a chain like expr1 and expr2 and expr3 and expr4 because it repeats thepush true or push false in each term that tries to abort, instead of making all the abortive jumps go to a common place that does the push at the bottom.

I ended up using a way that does this, and gets rid of the nop, and I added a br.true operator just because I didn't like having to NOT the value first, even though it's a bit less RISCy to have both a br.true and a br.false, it makes things less ugly to follow the compiled code.

expr1 and expr2 and expr3 will now do this:

expr1
br.false to ABORT_LABEL
expr2
br.false to ABORT_LABEL
expr3
branch by distance +2 instructions (skips the next single instruction, without using labels)
push false <-- ABORT_LABEL

expr1 or expr2 or expr3 will now do this:

expr1
br.true to ABORT_LABEL
expr2
br.true to ABORT_LABEL
expr3
branch by distance +2 instructions (skips the next single instruction, without using labels)
push true <-- ABORT_LABEL

In both cases the logic is "If aborting, branch to the abort destination, where it will push the abortive default. If you get down to the lastmost expression and haven't aborted yet, then just leave that lastmost expression atop the stack and skip over the abort push."

I got rid of the need for nop by realizing I can just ignore the DestinationLabel system and just jump a raw delta number of instructions - that lets me skip to whatever instruction the compiler happens to add next, without needing to know its label, just that it will be +2 from the location jumped from.

That would only fail if there is no next instruction, but there is guaranteed to be, even if it's just an EOP, or EOF or even a Pop because the expression value is thrown away unused.

[Dunbaratu]

Auto-linking didn't work. This should associate with #1035

[abenkovskii]

In case you don't know: + and * are currently defined in the kOS for booleans: https://github.com/KSP-KOS/KOS/blob/develop/src/kOS.Safe/Compilation/Calculator.cs#L413 but I guess it's impossibel to make a short cirquit logic for this cases too.

[Dunbaratu]

well crud. I guess it's possible to work it out. I have an idea. But the ugly part becomes what it does when there's a wonky mix of boolean and numbers: 1 + false - is that the boolean algebra meaning of + or the integer meaning of +?

Looking at the Calculator code, it looks like when there's a number and a bool being added, the bool logic overrides and the number is treated as a bool, rather than the bool treated as a number.

i.e. 1.0 * true results in Convert.ToBoolean(1.0) && Convert.ToBoolean(true)

And therefore 1.2 * true is an error - trying to convert the 1.2 to bool throws exception.

[abenkovskii]

It looks like true + false behaviour is not documented. It's probably easier to just delete it or leave it as is. BTW kOS is currently supporting < > >= etc for booleans too. Short circuiting all this operators would be a nightmare.

[Dunbaratu]

I think they need to be removed except for and/or/not.

[Dunbaratu]

Yeah it's impossible to do short-circuiting on ANDs that look like *and OR that look like +. Here's why: The compiler is late-binding about types. When you see expr1 * expr2 you won't know what type expr1 is and what type expr2 is until after they've been evaluated. The entire point of short-circuiting is to avoid evaluating the expression. So you can't tell if a *is a boolean-and until after you've already forgone any attempt at short-circuiting, and instead have evaluated the expressions on the left and right sides to discover that they are Booleans.

So I'd rather just remove the ability to interepret * as AND and + as OR.

[abenkovskii]

I agree that there is no reason to have * and + for bools - and and or are more explicit. However comparison of booleans might be useful. For example someone might want to sort a list of structures using boolean field as a key.

[abenkovskii]

Because operators were never documented clear enough disabling * and + for booleans will be a breaking change.

[Dunbaratu]

Didn't auto-associate properly with the PR. The PR is closed, so I'll manually close this issue.