The Way of Forth

Lots of people have difficulty grasping what Forth is all about - and what sets its followers apart. This weekend I had a real Forth experience that might illustrate in a small way what makes it tick.

It all started with a stupid TV show. Two people have to answer twelve questions and form a word with the first letters of the answers. One of these questions is always a "knight jump" puzzle. A "knight jump" puzzle is played on a 3x3 grid, centre unused. The remaining cells are filled with letters. Moving like a knight in a chess game, you have to find the 8-letter word.

Now I'm pretty good at this game, but the "knight jump" always baffles me. So, what do you do? You turn to the computer to solve the problem once and for all. First, I laid out the grid and explored the possibilities.

0 1 2
3   4
5 6 7

Every cell offers two possible jumps, e.g. cell "0" can jump to cell "4" or cell "6"; cell "1" can jump to cell "5" or cell "7". That means - no matter which cell you occupy, you always got two choices. Since we always know on which cell we are, we got 7 choices to make to get the complete word. That's 2^7 or 128. Multiply that by a choice of 8 cells to start from and we got over 1000 options. That's not too bad - at least not for a computer..

I decided to test each cell - and every possible path from that cell. Now is "left" or "right" pretty binary, so every integer between 0 and 127 was a good representation of the paths it had to follow. Quite "brute force", agreed, but one has to start somewhere. This is the program I came up with:

offset jumps                           \ possible jumps per cell
  4 c, 6 c, 5 c, 7 c, 6 c, 3 c, 2 c, 7 c,
  0 c, 5 c, 1 c, 4 c, 0 c, 2 c, 1 c, 3 c,

: try                                  ( path used current -- path)
  /knight 1- 0 do                      ( p u c)
    rot over 2* over i bit if 1+ then jumps
    >r rot dup r@ bit                  ( c p u f r:n)
    if                                 \ if we've been there
      r> drop drop nip unloop exit     \ this is not a valid path, exit
    else                               \ this is a valid path, it's untouched
      rot drop r>                      ( p u c)
      puzzle over chars + c@ knight i 1+ chars + c!
      tuck set swap                    \ mark the letter and add to solution 
    then                               \ show the solution
  loop drop drop knight /knight type cr 
;
                                       \ knight jump solver
: solve                                ( --)
  /knight 0 do                         \ try all eight letters
    puzzle i chars + c@ knight c!      \ set the first letter
    0 begin dup 128 < while 0 i set i try 1+ repeat drop
  loop                                 \ now try all possible paths
;

Of course, not all paths are viable. When the algorithm revisits a cell you can be sure you're on the wrong track. So I added another integer, which was a bitmask of the visited cells. Whenever the LOOP of TRY was exhausted, we had a fully qualified path - not before. The byte-array JUMPS holds the jump options of all the cells, two per cell, eights cells, so 16 values in total.

What can I say? It worked. It spit out sixteen possible answers and the right one was always among them. Problem solved. Or not. Remember, I started out with over a thousand possible paths and now only sixteen of them prove to be viable. There must be more to this..

So I figured out what these 16 paths were:

0: 26, 79; 1: 67, 122; 2: 83, 104; 3: 80, 105;
4: 13, 30; 5:  6,  61; 6: 39,  52; 7: 33, 116.

Then I wrote a tiny program that took a starting cell and a path and listed the sequence of cells it had visited. It came up with this:

1 7 3 2 6 0 4 5 
7 3 2 6 0 4 5 1
3 2 6 0 4 5 1 7
2 6 0 4 5 1 7 3
6 0 4 5 1 7 3 2
0 4 5 1 7 3 2 6 
4 5 1 7 3 2 6 0
5 1 7 3 2 6 0 4

5 4 0 6 2 3 7 1
4 0 6 2 3 7 1 5
0 6 2 3 7 1 5 4 
6 2 3 7 1 5 4 0
2 3 7 1 5 4 0 6 
3 7 1 5 4 0 6 2
7 1 5 4 0 6 2 3 
1 5 4 0 6 2 3 7

Note it didn't present itself so nicely as this. Of course I could have encoded these 16 sequences in 128 bytes flat and get it over with. But no, I still felt there was more to optimize. If you look carefully you'll see that the first eight sequences are the same - they're just shifted left and rotated. The first sequences of both blocks are identical as well - just mirrored. By MOD-wrapping a sequence, I could reproduce an entire block. Inverting it - and I got the other block.

I decided to make one routine which solved one block of sequences and simply call it twice with both sequences. I thought that was better than to spend code to manipulate the sequence. In short, the whole shebang could be encoded in 16 bytes:

offset sequences 
  0 c, 4 c, 5 c, 1 c, 7 c, 3 c, 2 c, 6 c,
  0 c, 6 c, 2 c, 3 c, 7 c, 1 c, 5 c, 4 c,
                                       \ solve a sequence
: solve                                ( offset --)
  /puzzle 0 do                         \ different starting points
    /puzzle 0 do
      puzzle over j i + /puzzle mod + sequences chars + c@ emit
    loop cr
  loop drop                            \ drop offset
;

Of course, with this scheme, it is quite trivial to make a "knight jump" generator using the same sequences:

: makepuzzle                           ( --)
  cr 2 choose /sequence * /knight choose
                                       \ choose a sequence
  /knight 0 do
    over over i + /knight mod + sequences chars puzzle + 
    knight i chars + c@ swap c!        \ fill the matrix
  loop drop drop                       \ drop sequence and offset
                                       \ make room for centre space
  puzzle /grid 1+ + dup dup 1+ /grid 1+ cmove bl swap c! 
  /grid 0 do /grid 0 do puzzle i j /grid * + chars + c@ emit loop cr loop
;                                      \ show puzzle

But it also has benefits if you have to solve a puzzle by hand: all you need is the number 17326045. This will place the letters in the correct order. You only have to shift-rotate them to explore the first eight possibilities. Reverse the sequence and repeat for the second eight possiblities.

Ok, back to the original question: what sets a Forth programmer apart? Where your average Java programmer would have been happy to solve the problem in a short time without any performance issues, goes the Forth programmer quite a bit further. He wants to understand the problem fully before he decides which algorithm to use. This makes Forth programs not only faster and smaller, but also much more maintainable.

And that is worth more than anything.