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.

Advertisements

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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s