Don’t underestimate the power of the Forth

Let’s look at an example program in Forth – the ubiquitous Greatest Common Divisor, solved using the Euclidean algorithm. To find the GCD of two numbers, a and b (a > b),  a loop repeatedly replaces a by b and b by a mod b while b is not zero. Here is the Forth code:

: gcd ( a b -- gcd )
begin ?dup while tuck mod repeat ;

This does not look like any regular sort of program does it? It’s called in this fashion:

cr 6 10 gcd .

What does this code actually do?

The first line, : gcd ( a b — gcd ) sets up a function of sorts.

The phrase begin ?dup while … repeat executes the loop while the top of the stack is non-zero. ?dup does not duplicate the top item if it is zero.

tuck ( a b — b a b ) copies the top item underneath the second item on the stack. It is equivalent to swap over.

mod ( a b — a%b ) takes the modulus of the top two items on the stack.

Together, tuck mod does ( a b — b a%b ).

Having fun yet?

If you want to play with Forth, gforth is a nice little compiler.


Leave a Reply

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

You are commenting using your 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.