Go Forth and Multiply – or Don’t

In which I provide my Forth machine with the ability to make decisions

Now it is time to revisit branching.

Provide builtin branch and branch? words.

http://beza1e1.tuxen.de/articles/forth.html

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.

The 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.

With branch and 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:

https://bitbucket.org/jeremy-pereira/myforth/commits/tag/blog-1008

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.