Notes on the short circuit AND for the PVM

The solutions submitted for how to achieve short circuit AND and OR on the PVM were interestingly varied and prompt me to issue these notes on ways of doing the AND. You could amuse yourself by trying to do the analogous variations for the short-circuit OR operation

Without the short-circuit requirement, the expression x && y can be evaluated, if x and y are simple variables, with code like

           LDA  X
           LDV
           LDA  Y
           LDV
           AND
   OUT     ....

a total of 7 words of "code". Of course, if X and Y are complex Boolean expressions then we would have something more complicated

  evaluate X and leave it on the stack
  evaluate Y and leave it on the stack
  AND

Sticking with the simple case for the moment - the idea of the short-circuit AND is not to use an AND at all, but to use what my friend and compiler writer John Gough calls "jumping code".

This can developed by starting from the idea that

     Z = X and Y

amounts to assigning to Z, after leaving a value on the top of stack computed as

          "if not x then false else y"

     or   "if x then y, else false"

On the PVM we only have a BZE operation, so we have to work within that constraint. Something like this, which totals 12 words of code:

           LDA  X
           LDV          ; leave x on top of stack
           BZE  FALSE   ; if !x goto push false
           LDA  Y       ; else
           LDV          ;   leave y on top of stack
           BRN  OUT     ; bypass pushing false
   FALSE   LDC  0       ; push false (0)
   OUT     ....

This code has the advantage that it (a) evaluates X only once (b) evaluates Y at most once (c) can be developed easily as one reads the expression from left to right. This would be true even if X and Y were complicated Boolean sub-expressions. So it is the "preferred" solution, for the moment (but see later).

Assembler programmers love to use tricks. Unfortunately these may obscure what is going on. How does this variation work (also 12 words)?

           LDA  X
           LDV          ; leave x on top of stack
           BZE  FALSE   ; if !x push false
           LDA  Y       ; else
           LDV          ;   leave y on top of stack
           BRN  OUT     ; bypass false
   FALSE   DSP  1       ; ??
   OUT

Most students who tried this problem came up with something like this

           LDA  X
           LDV          ; leave x on top of stack
           LDA  X
           LDV          ; leave another copy of x on top of stack
           BZE  OUT     ; if !x goto push false
           LDA  Y       ; else
           LDV          ;   leave y on top of stack
           AND
   OUT     ....

This has the disadvantage that X has to be evaluated twice, which would amount to a lot of extra code if X were actually a complicated expression, and still uses an AND operation. There are still 12 words of code in the simple case, of course.

There is always a better way. Convince yourself that this achieves the same result, but without reevaluating X (11 words)

           LDC  0       ; push false onto the stack
           LDA  X
           LDV          ; evaluate X once and leave on the stack
           BZE  OUT     ; if !x goto leave false on the stack
           LDA  Y       ; else
           LDV          ;   leave y on top of stack
           AND          ; that pesky AND - but we may need it, why?
   OUT     ....

So how else can we get rid of the AND? How about

           LDC  0       ; push false onto the stack
           LDA  X
           LDV          ; evaluate X once and leave on the stack
           BZE  OUT     ; if !x goto leave false on the stack
           LDA  Y       ; else
           LDV          ;   leave y on top of stack
           ADD          ; what the hell does adding have to do with it?
   OUT     ....

or, mysteriously

           LDC  0       ; push false onto the stack
           LDA  X
           LDV          ; evaluate X once and leave on the stack
           BZE  OUT     ; if !x goto leave false on the stack
           DSP  -1      ; ??
           LDA  Y       ; else
           LDV          ;   leave y on top of stack
   OUT     ....

And here is a version that may look more bizarre still. How does this work?

           LDC  0
           LDA  X
           LDV          ; leave another copy of x on top of stack
           BZE  OUT     ; if !x goto leave false on stack
           BZE  NEXT    ; good grief!  Didn't we just check?  Why twice?
   NEXT    LDA  Y       ; else
           LDV          ;   leave y on top of stack
   OUT     ....

Of course, the best way to do this would be to extend the opcode set and the PVM machine to allow us to write code like the following (8 words):

           LDA  X
           LDV
           BRF  OUT
           LDA  Y
           LDV
    OUT    ....

where BRF is an opcode which .... well, work it out for yourself what it would have to do.