Language constructs

Any language intended to do real work, should of course provide a way of iterating, and a way of branching. Both are provided in this language by means of the loop and the branch opcodes.

The loop opcode takes one argument. If the argument evaluates to something non-zero, the loop opcode will set the instruction pointer of the virtual machine to point to the actual loop code (the code that is inside the loop). If the argument evaluates to zero, the instruction pointer is instead moved to the instruction immediately following the loop construct.

A program approximating the machine precision could look like:

;;
;; Calculate machine precision
;;
entry "prec"
        decl floating,   ; r0 is floating point
             floating,   ; r1 is floating point
             integer,    ; r2 is a condition variable (integer)
             floating    ; the previous older value is floating too
        move r0, 1.      ; move a floating-point 1 into r0
        move r2, 1       ; move an integer 1 into r2
        loop r2          ; loop while r2 is nonzero
         move r3, r1        ; older <- old
         move r1, r0        ; old <- current
         div r0, 2.         ; current <- current / 2
         add r0, 1.
         add r0, -1.
         cmpgt r2, r1, r0   ; is old > current ?
        end                 ; if not, then older = precision
        return r3
end

The comments in the code should make it pretty clear what is going on. The algorithm is close to Malcolm's algorithm (see [3]), but not equivalent. Especially Malcolm took into account whether the machine rounded or truncated (``chopped'') values. His algorithm would add a few extra lines to the example above.

Note, we add and subtract to/from the value after we have divided it by two. This is needed for the value not to evaluate to something around $10^{-308}$, the smallest possible value in 64-bit IEEE floating-point. The code isn't that important, but it demonstrates a simple use of the loop construct.

The second construct is the branch. This is similar to the if/then/else constructs of other languages. The branch opcode takes one argument, just like the loop, and chooses one branch if the argument evaluates to something non-zero, and the other branch if the argument evaluates to zero. After executing any of the two branches, the instruction pointer of the virtual machine is set to point at the instruction immediately following the branch construct.

An example of a program using the branch construct, is the following recursive factorial calculator. Yes, the following code may not be a stunning example of expressive beauty, but it demonstrates the use of the branch construct rather well.

;;
;; This snippet calculates the factorial
;; of the argument given.
;; 
entry "fact"
        decl integer,   
             integer
        move r0, a0
        decr r0                    ; r0 = n-1
        cmpgt r1, a0, 1            ; r1 = a0 > 1
        branch r1
         call r0, "fact", r0       ; if a0 > 1 then r0 = f(r0)
        else
         return 1                  ; if a0 <= 1 then return 1
        end
        mult r0,a0                 ; r0 = a0 * f(r0)
        return r0
end

The code is given an argument in the a$_0$ register, this is the number $n$ of which want to calculate the factorial. If the number is greater than 1, the routine makes a recursive call to calculate the factorial of $n-1$, to multiply that result with $n$, and then return. If the number is not greater than 1, we just return 1. So we do not handle negative arguments, but both $0!$ and $1!$ should be covered.

One thing that should be noted about these constructs is, that we know exactly which variables they depend upon, and which they have the potential of changing. If a loop uses $s$ as loop variable, the instructions in the loop uses $T = \{ t_1, t_2,\ldots\}$, the entire loop construct uses $T \cup \{s\}$. The loop construct will touch (or have the potential to touch) the union of the variables each of the instructions inside the loop touches.

Branches can be looked at similarly. It is at all times extremely easy to find out what variables may be used or touched by any loop or branch, just as it is with single opcodes.

In fact, since we use balanced trees to actually represent the uses and touches sets of instructions and constructs, we can calculate the entire set of dependencies of a loop in almost linear time wrt. the number of instructions in the loop. This will be more thoroughly treated in chapter 4.