Sunday, June 14, 2009

Fall through factoring

The idea is that you can have multiple entry points to the same word. Here's an example. Say if you needed code for shifting right twice (4 *) and shifting right3 times (8 *). You could code that without factoring as:

4* 2* 2* ;
8* 2* 2* 2* ;

You could also code it using traditional factoring as:

4* 2* 2* ;
8* 2* 4* ;

Using fall through factoring that becomes:

8* 2*
4* 2* 2* ;

With fall through factoring 8* doesn't have the overhead of having to call 4*, but you still get the code density benefit of having 4* factored out. Fall through factoring can also be used to increase code readability without added overhead. Consider the example from Starting Forth chapter 2.

: YARDS 36 * ;
: FEET 12 * ;
: INCHES ;

: YARD YARDS ;
: FOOT FEET ;
: INCH INCHES ;

The only reason for yard, foot and inch is readability. Here is the same result using fall through factoring.

yard
yards 36 * ;
foot
feet 12 * ;
inch
inches ;

Note that there is now no overhead for yard, foot, or inch being their own separate words. Each word is a separate label for the same code address. In traditional Forth the words yard, foot and inch all have the overhead of making a call to their plural versions. Some traditional Forths have a word alias that can give a similar result as this last example, but that's not standard.

4 comments:

David J. Göhrig said...

In your second example of fall through factoring you should have combined each concept and produced:

yards

yard 3 *

feet

foot 12 * ;



This produces the same result, and factors out the 12 common to both 12 and 36. Aka classic factoring :)

johnmdrake said...

Yes you could do that. But you would take 1 multiplication for yards and make it 2. Depending on what you're doing that could significantly slow down your code. Fall through factoring shouldn't do that IMO.

From my first example I'd rather do:

4* 2 shl ;
8* 3 shl ;

but ColorForth doesn't directly support shifting more than one bit at a time. (It's easy enough to add.)

David J. Göhrig said...

In most applications, this sort of unit conversion would be done as a compile time application, and not done at run time. These words would better be run as macros (aka immediate words).

johnmdrake said...

Hello David,

First I should point out that the "yards - feet" example came from Starting Forth at the "8*" example came from Jeff Fox. So I'm simply using them as opposed to showing code from an actual application.

That said, it all depends on your application. If I had an interactive calculator that I needed to make quick conversions I would need those conversions to happen at run time rather than compile time.

Also I think it's important to distinguish between immediate code (yellow words) and inline code (words defined in the macro vocabulary with cyan instead of green compile words). Inline words run at runtime, but without the call overhead. Immediate words run at compile time. If you needed the ability to do conversions at run time you couldn't do it with immediate words and its difficult (though not impossible) to handle literals with cyan words.