In which I provide my Forth machine with the ability to make decisions
Now it is time to revisit branching.
We’ll first need to do some refactoring because, in order to jump somewhere, our list of instructions needs to be indexable. In fact, it needs to be bidirectionally indexable.
branch instruction will take the top item on the stack and use it as a relative offset from the
branch instruction to relocate the to a new word. The
branch? instruction is the same, but if the word below the relative address is zero, the branch is not taken.
branch? the Forth machine is now powerful enough to undertake general programming tasks.
I’ve defined some extra words to do comparisons and that means we are ready to write a real program. For example, the following is a program to calculate Fibonacci numbers using the recursion method.
: fibo dup 5 branch? drop 1 15 branch dup 1 = 10 branch? dup 1 - fibo swap 2 - fibo + ;
The first line says “if the top of stack is not zero go to the next line, otherwise discard it, put 1 on the stack and go to the end of the program”.
The second line says “if the top of the stack is 1, go to the end of the program (fibo(1) = 1)”.
The last line says “subtract 1 from the top of the stack and find its fibonacci number, then subtract 2 from the top of the stack and find its fibonacci number, then add them together.
The above program is a very inefficient way to calculate fibonacci numbers having O(2n) time complexity. However, it will be a useful task for measuring optimisations.
The code for this post is here: