The semantics of Bob amounts to what we can do with instructions, and how the given model behaves.
After executing an instruction we update the model = (pc,br,dir) as thus
# model update if dir = 0 then if br = 0 then pc := pc + 1 else pc := pc + br else if br = 0 then pc := pc - 1 else pc := pc - brThe model is not reset after updated. For example the br register needs be reset if a jump has been performed. Or else the program counter will jump ahead resulting in undefined behavior. This is often done placing a branch right at the target of a given jump. For example
label0: BRA label1 #some code label1: BRA label0 # more codeBesides the memory that is visible to the programmer, an internal stack is maintained. This stack is not visible to the programmer. Each frame is a list of keys and values. Thus a key can be present several times with different values. In this version of Bob the internal stack is only used for storing arguments when doing CALL or RCALL.
In general all instructions must have an inverse. Some instructions, like multiplication, takes 3 arguments, a destination and two source registers, where the result of evaluating the instruction on the two source registers is XOR'ed into the destination register. Such instructions are self-inverse since they essentially are a XOR instruction. All branch instructions are self-inverse since the way they modify state is automatically inverted in backward execution as of the model described above.
The types of arguments are as thus:
The swap instruction swaps the values of two registers. The inverse of SWAP is itself, that is it is self inverse.
SWAP $reg1 $reg2The add instruction adds the values of two registers and stores the result in the first. The inverse of ADD is SUB.
ADD $dest $sourceThe add1 instruction adds 1 to the destination register. It has SUB1 as inverse.
ADD1 $destSubtracts the values of the two registers. The inverse is ADD.
SUB $dest $sourceSubtracts one from destination register. The inverse is ADD1.
SUB1 $destMultiply the two source registers and XOR the result into the destination register. This instruction is self-inverse.
MUL $dest $s1 $s2Multiplies the destination register with 2. The inverse is DIV2.
MUL2 $destDivides the two source registers and XOR the result into the destination register. This instruction is self-inverse.
DIV $dest $s1 $s2Divides the source with 2. The inverse is MUL2.
DIV2 $destStores 0 minus the value of the destination register in the destination register. This is the same as the additive inverse on integers. This instruction is self-inverse.
NEG $destXOR the result of $s1 modulo $s2 into the destination register. This instruction is self-inverse.
MOD $dest $s1 $s2XOR the value of the source register into the destination register. This instruction is self-inverse.
XOR $dest $sourceAs with XOR, though the source here is an integer. This instruction is self-inverse. It is quite central as it is the only way to move integers into register.
XORI $dest 1234Bit wise ∧s the two source registers and stores the result in the destination register. This instructions is self inverse.
AND $dest $s1 $s2Bit wise ∨s the two source registers and stores the result in the destination register. Self-inverse.
OR $dest $s1 $s2Exchanges the value of the register given as the first argument with what resides at the memory location of the value of register given as second argument. This instruction is self-inverse. It is the only way to directly move values in and out of memory.
EXCH $reg1 $reg2Adds 1 to $spointer. Then exchanges the value of given register into what resides at $spointer in memory. This instruction has POP as inverse. This is essentially a x86 push, though it exchanges values instead of moving them.
PUSH $reg1Exchanges the value of given register into what resides at $spointer in memory. Then subtracts 1 from $spointer. This instruction has PUSH as inverse. This is essentially a x86 pop, though it exchanges values instead of moving them.
POP $reg1First of all the br register is calculated based on the target label. Then one of two things can happen:
This instruction is self-inverse.
CALL label ($reg1,...)Almost the same as CALL. This instruction differs in that the dir register is set to 1, and that the br register is set to 0 - calculated_br. The execution details of this instruction are opposite of the semantics of the model: we want to make a jump and then invert the dir register. But in our model the position tuple is updated after executing a given instruction. To overcome for this we use the additive inverse of the calculated br register. Self-inverse.
RCALL label ($reg1,...)Exchanges the value of the br register with given register. Self-inverse.
SWBR $reg1Exact same as SWBR. This had been included in order to give a more informative name. It is often used when constructing procedures.
SWRET $reg1With this instruction and unconditional jump to the given label is made.
BRA labelThe same as BRA, though after instruction execution the dir register is inverted. This is done in the way described for RCALL.
RBRA labelBranch on equal to 0.
BZ #reg,mem labelBranch on not equal to 0.
BNZ #reg,mem labelBranch on equal.
BEQ #reg,mem #reg,mem labelBranch on not equal.
BNEQ #reg,mem #reg,mem labelBranch on greater than.
BGT #reg,mem #reg,mem labelBranch on greater than or equal to.
BGEQ #reg,mem #reg,mem labelBranch on less than.
BLT #reg,mem #reg,mem labelBranch on less than or equal to.
BLEQ #reg,mem #reg,mem labelStop execution. This instruction results in a success on status.
STOPSimilar to the x86 instruction of the same name. It does nothing, execution just passes on according to the position.
NOPFor compound code we use a set of templates. The CALL, RCALL and the SWRET is made as to accommodate these templates.
These are constructed as thus
# template for procedure proc_top: BRA proc_bot POP $raddr proc: SWRET $raddr NEG $raddr PUSH $raddr # procedure code proc_bot: BRA proc_topAs can be seen: every time we jump to some label, we need to reset the br register. Or else we keep jumping resulting in undefined behavior. The return address resides in $raddr - this is pushed right ahead accommodating for possible recursion.
Reversible statements needs an exit condition so we in case of backwards execution can decide path taken. This condition is called fi. This is illustrated in Figure 1.
The template for a conditional statement is as thus
if_top: BGEZ $if if_else #code for then if_then: BRA if_bot if_else: BRA if_top # code for else if_bot: BGEZ $fi if_thenIn the code the first condition is inverted, that is if the value of $if is less than 0, then do the then branch.
As with conditional statements loops need an exit condition. This is illustrated in Figure 2.
loop_top: BGEZ $entry loop # code for do loop_do: BLZ $exit loop_bot # code for loop loop: BRA loop_top loop_bot: BRA loop_doAgain the top branch checking entry is inverted.
If we need to evaluate a compare operator (⊕ = [ >,<,≥≤,=,≠ ]), we can do so as illustrated in Figure 3. This results in the following code where we need to zero-clear the registers we have used.
c_top_pre: BGT $r1 $r2 c_true_pre c_false_pre: BRA c_bot_pre c_true_pre: BRA c_top_pre XORI $res 1 c_bot_pre: BLE $r1 $r2 c_false_pre # Code that can use $res in condition c_bot_post: BLE $r1 $r2 c_false_pre c_true_post: BRA c_top_pre XORI $res 1 c_false_post: BRA c_bot_pre c_top_post: BGT $r1 $r2 c_true_preHere post-code is in order to zero-clear registers after use.