chapter8.tex

%% Thinking Forth
%% Copyright (C) 2004 Leo Brodie
%% Initial transcription by Nils M Holm
%% Based on OCR scans by Steve Fisher
%% 
%% Chapter: Eight - Minimizing Control Structures

%!! horizontal line
%EIGHT
%!! horizontal line

\chapter{Minimizing Control~Structures}\Chapmark{8}%
\index{C!Control structure minimization|(}%

\initial Control structures aren't as important in \Forth{} as they
are in other languages. \Forth{} programmers tend to write very
complex applications in terms of short words, without much emphasis on
\forth{IF THEN} constructs.

There are several techniques for minimizing control structures.
They include:

%!! items should be preceded by bullets
\begin{itemize}
\item computing or calculating
\item hiding conditionals through re-factoring
\item using structured exits
\item vectoring
\item redesigning.
\end{itemize}
In this chapter we'll examine these techniques for simplifying and
eliminating control structures from your code.

\section{What's So Bad about Control Structures?}%
\index{C!Control structure minimization!reasons for|(}

Before we begin reeling off our list of tips, let's pause to examine why
conditionals should be avoided in the first place.

The use of conditional structures adds complexity to your code. The
more complex your code is, the harder it will be for you to read and to
maintain. The more parts a machine has, the greater are its chances of
breaking down. And the harder it is for someone to fix.

%!! horizontal line
\begin{interview}
\person{Moore}\index{M!Moore, Charles|(} tells this story:
\begin{tfquot}
I recently went back to a company we had done some work for several years
ago. They called me in because their program is now five years old, and
it's gotten very complicated. They've had programmers going in and
patching things, adding state variables and conditionals. Every statement
that I recall being a simple thing five years ago, now has gotten very
complicated.  ``If this, else if this, else if this'' \dots{} and then the
simple thing.

Reading that statement now, it's impossible for me to figure out what it's
doing and why. I'd have to remember what each variable indicated, why it
was relevant in this case, and then what was happening as a consequence of
it---or not happening.

It started innocently. They had a special case they needed to worry about.
To handle that special case, they put a conditional in one place. Then they
discovered that they also needed one here, and here. And then a few more.
Each incremental step only added a little confusion to the program. Since
they were the programmers, they were right on top of it.

The net result was disastrous. In the end they had half a dozen flags.
Test this one, reset it, set that one, and so on. As a result of this
condition, you knew you had other conditions coming up you had to look out
for. They created the logical equivalent of spaghetti code in spite of the
opportunity for a structured program.

The complexity went far beyond what they had ever intended. But they'd
committed themselves to going down this path, and they missed the simple
solution that would have made it all unnecessary---having two words
instead of one. You either say \forth{GO} or you say \forth{PRETEND}.

In most applications there are remarkably few times when you need to test
the condition. For instance in a video game, you don't really say ``If he
presses Button A, then do this; if he presses Button B, then do something
else.'' You don't go through that kind of logic.

If he presses the button, you do something. What you do is associated with
the button, not with the logic.

Conditionals aren't bad in themselves---they are an essential construct. But
a program with a lot of conditionals is clumsy and unreadable. All you can
do is question each one. Every conditional should cause you to ask, ``What
am I doing wrong?''

What you're trying to do with the conditional can be done in a different
way. The long-term consequences of the different way are preferable to the
long-term consequences of the conditional.
\end{tfquot}\index{M!Moore, Charles|)}
\end{interview}%
\index{C!Control structure minimization!reasons for|)}%
Before we introduce some detailed techniques, let's look at three
approaches to the use of conditionals in a particular example.
\Fig{fig8-1}, \Fig{fig8-2}, and \Fig{fig8-3} illustrate three versions of
a design for an automatic teller machine.\program{teller1}

\begin{figure*}[tttt]
\verbfig{fig8-1}{The structured approach.}
\begin{center}
\small\begin{BVerbatim}[commandchars=\&\{\},baselinestretch=0.85]
&underline{AUTOMATIC-TELLER}

IF card is valid DO
   IF card owner is valid DO
      IF request withdrawal DO
         IF authorization code is valid DO
            query for amount
            IF request &(&le&) current balance DO
               IF withdrawal &(&le&) available cash DO
                  vend currency
                  debit account
               ELSE
                  message
                  terminate session
            ELSE
               message
               terminate session
         ELSE
            message
            terminate session
      ELSE
         IF authorization code is valid DO
            query for amount
            accept envelope through hatch
            credit account
         ELSE
            message
            terminate session
   ELSE
      eat card
ELSE
   message
END
\end{BVerbatim}
\end{center}
\end{figure*}
The first example comes straight out of the School for Structured
Programmers. The logic of the application depends on the correct nesting
of \forth{IF} statements.

Easy to read? Tell me under what condition the user's card gets eaten. To
answer, you have to either count \forth{ELSE}s from the bottom and match
them with the same number of \forth{IF}s from the top, or use a
straightedge.

\begin{figure*}[tttt]
\verbfig{fig8-2}{Nesting conditionals within named procedures.}
\small\begin{center}
\begin{BVerbatim}[commandchars=\&\{\},baselinestretch=0.85]
&underline{AUTOMATIC-TELLER}

PROCEDURE READ-CARD
     IF  card is readable  THEN  CHECK-OWNER
          ELSE  eject card  END

PROCEDURE CHECK-OWNER
     IF  owner is valid  THEN  CHECK-CODE
          ELSE  eat card  END

PROCEDURE CHECK-CODE
     IF  code entered matches owner  THEN  TRANSACT
          ELSE message, terminate session  END

PROCEDURE TRANSACT
     IF requests withdrawal  THEN  WITHDRAW
          ELSE  DEPOSIT END

PROCEDURE WITHDRAW
     Query
     If  request &(&le&) current balance  THEN  DISBURSE  END

PROCEDURE DISBURSE
     IF disbursement &(&le&) available cash  THEN
           vend currency
           debit account
         ELSE  message  END

PROCEDURE DEPOSIT
     accept envelope
     credit account
\end{BVerbatim}
\end{center}
\end{figure*}
The second version, \Fig{fig8-2}, shows the improvement that using many
small, named procedures can have on readability. The user's card is eaten
if the owner is not valid.

But even with this improvement, the design of each word depends completely
on the \emph{sequence} in which the tests must be performed. The
supposedly ``highest'' level procedure is burdened with eliminating the
worst-case, most trivial kind of event. And each test becomes responsible
for invoking the next test.

\begin{figure*}[tttt]
\verbfig{fig8-3}{Refactoring and/or eliminating conditionals.}
\begin{center}
\small\begin{BVerbatim}[commandchars=\&\{\},baselinestretch=0.85]
&underline{AUTOMATIC-TELLER}

: RUN
     READ-CARD  CHECK-OWNER  CHECK-CODE  TRANSACT  ;

: READ-CARD
     valid code sequence NOT readable  IF  eject card  QUIT
        THEN ;

: CHECK-OWNER
     owner is NOT valid  IF  eat card  QUIT  THEN ;

: CHECK-CODE
     code entered MISmatches owner's code  IF  message  QUIT
        THEN ;

: READ-BUTTON ( -- adr-of-button's-function)
     ( device-dependent primitive) ;

: TRANSACT
     READ-BUTTON  EXECUTE ;

1 BUTTON WITHDRAW

2 BUTTON DEPOSIT

: WITHDRAW
     Query
     request &(&le&) current balance  IF  DISBURSE  THEN ;

: DISBURSE
     disbursement &(&le&) available cash  IF
            vend currency
            debit account
          ELSE  message  THEN  ;

: DEPOSIT
     accept envelope
     credit account ;
\end{BVerbatim}
\end{center}
\end{figure*}

The third version comes closest to the promise of \Forth{}. The highest
level word expresses exactly what's happening conceptually, showing only
the main path. Each of the subordinate words has its own error exit, not
cluttering the reading of the main word. One test does not have to invoke
the next test.

Also \code{TRANSACT} is designed around the fact that the user will make
requests by pressing buttons on a keypad. No conditions are necessary. One
button will initiate a withdrawal, another a deposit. This approach
readily accommodates design changes later, such as the addition of a
feature to transfer funds. (And this approach does not thereby become
dependent on hardware. Details of the interface to the keypad may be
hidden within the keypad lexicon, \code{READ-BUTTON} and \code{BUTTON}.)

Of course, \Forth{} will allow you to take any of the three approaches.
Which do you prefer?\program{teller2}

\section{How to Eliminate Control Structures}

In this section we'll study numerous techniques for simplifying or
avoiding conditionals. Most of them will produce code that is more
readable, more maintainable, and more efficient. Some of the techniques
produce code that is more efficient, but not always as readable.
Remember, therefore: Not all of the tips will be applicable in all
situations.

\subsection{Using the Dictionary}%
\index{C!Control structure minimization!dictionary|(}%
\index{D!Dictionary:!control structure minimization with|(}

\begin{tip}
Give each function its own definition.
\end{tip}
By using the \Forth{} dictionary properly, we're not actually eliminating
conditionals; we're merely factoring them out from our application code.
The \Forth{} dictionary is a giant string case statement. The match and
execute functions are hidden within the \Forth{} system.

\begin{interview}
\person{Moore}:\index{M!Moore, Charles|(}
\begin{tfquot}
In my accounting package, if you receive a check from somebody, you type
the amount, the check number, the word \forth{FROM}, and the person's
name:

\begin{Code}
200.00 127 FROM ALLIED
\end{Code}
The word \forth{FROM} takes care of that situation. If you want to bill
someone, you type the amount, the invoice number, the word \forth{BILL}
and the person's name:

\begin{Code}
1000.00 280 BILL TECHNITECH
\end{Code}
\end{tfquot}\index{M!Moore, Charles|)}
\dots{} One word for each situation. The dictionary is making the decision.\medskip
\end{interview}
This notion pervades \Forth{} itself. To add a pair of single-length
numbers we use the command \forth{+}. To add a pair of double-length
numbers we use the command \forth{D+}. A less efficient, more complex
approach would be a single command that somehow ``knows'' which type of
numbers are being added.

\Forth{} is efficient because all these words---\forth{FROM} and
\forth{BILL} and \forth{+} and \forth{D+}---can be implemented without any
need for testing and branching.

\index{D!Dumb words|(}
\begin{tip}
Use dumb words.
\end{tip}
This isn't advice for TV writers. It's another instance of using the
dictionary. A ``dumb'' word is one that is not state-dependent, but
instead, has the same behavior all the time (``referentially
transparent'').

A dumb word is unambiguous, and therefore, more trustworthy.

A few common \Forth{} words have been the source of controversy recently
over this issue. One such word is \forth{."} which prints a string.  In
its simplest form, it's allowed only inside a colon definition:

\begin{Code}
: TEST   ." THIS IS A STRING " ;
\end{Code}
Actually, this version of the word does \emph{not} print a string. It
\emph{compiles} a string, along with the address of another definition
that does the printing at run time.

This is the dumb version of the word. If you use it outside a colon
definition, it will uselessly compile the string, not at all what a
beginner might expect.

To solve this problem, the FIG model added a test inside \forth{."} that
determined whether the system was currently compiling or interpreting.  In
the first case, \forth{."} would compile the string and the address of the
primitives; in the second case it would \forth{TYPE} it.

\forth{."} became two completely different words housed together in one
definition with an \forth{IF ELSE THEN} structure. The flag that indicates
whether \Forth{} is compiling or interpreting is called \forth{STATE}.
Since the \forth{."} depends on \forth{STATE}, it is said to be
``\forth{STATE}-dependent,'' literally.

The command \emph{appeared} to behave the same inside and outside a colon
definition. This duplicity proved useful in afternoon introductions to
\Forth{}, but the serious student soon learned there's more to it than
that.

Suppose a student wants to write a new word called \forthb{B."} (for
``bright-dot-quote'') to display a string in bright characters on her
display, to be used like this:

\begin{Code}
." INSERT DISK IN "  B." LEFT "  ." DRIVE "
\end{Code}
She might expect to define \forth{B."} as

\begin{Code}
: B."   BRIGHT  ."  NORMAL ;
\end{Code}
that is, change the video mode to bright, print the string, then reset the
mode to normal.

She tries it. Immediately the illusion is destroyed; the deception is
revealed; the definition won't work.

To solve her problem, the programmer will have to study the definition of
\forth{(.")} in her own system. I'm not going to get sidetracked here with
explaining how \forth{(.")} works---my point is that smartness isn't all
it appears to be.

Incidentally, there's a different syntactical approach to our student's
problem, one that does not require having two separate words, \forth{."}
and \forth{B."} to print strings. Change the system's \forth{(.")} so that
it always sets the mode to normal after typing, even though it will
already be normal most of the time. With this syntax, the programmer need
merely precede the emphasized string with the simple word \forth{BRIGHT}.

\begin{Code}
." INSERT DISK IN "  BRIGHT ." LEFT "  ." DRIVE "
\end{Code}
The '83 Standard now specifies a dumb \forth{."} and, for those cases
where an interpretive version is wanted, the new word \forth{.(} has been
added. Happily, in this new standard we're using the dictionary to make a
decision by having two separate words.

\index{S!STATE|(}
The word \forth{'} (tick) has a similar history. It was
\forthb{STATE}-dependent in fig-\Forth{}, and is now dumb in the '83
Standard. Tick shares with dot-quote the characteristic that a programmer
might want to reuse either of these words in a higher-level definition and
have them behave in the same way they do normally.%
\index{D!Dumb words|)}

\begin{tip}
Words should not depend on \forthb{STATE} if a programmer might ever want
to invoke them from within a higher-level definition and expect them to
behave as they do interpretively.
\end{tip}
\forthb{ASCII}\index{A!ASCII} works well as a \forth{STATE}-dependent
word, and so does \forthb{MAKE}.\index{M!MAKE} (See \App{C}.)%
\index{S!STATE|)}%
\index{C!Control structure minimization!dictionary|)}%
\index{D!Dictionary:!control structure minimization with|)}

\subsection{Nesting and Combining Conditionals}%
\index{N!Nesting conditionals|(}%
\index{C!Conditionals, nesting and combining|(}%
\index{C!Control structure minimization!nesting and combining conditionals|(}
\begin{tip}
Don't test for something that has already been excluded.
\end{tip}
Take this example, please:

\begin{Code}
: PROCESS-KEY
   key  dup  LEFT-ARROW  =  IF CURSOR-LEFT  THEN
        dup  RIGHT-ARROW =  IF CURSOR-RIGHT THEN
        dup  UP-ARROW    =  IF CURSOR-UP    THEN
             DOWN-ARROW  =  IF CURSOR-DOWN  THEN ;
\end{Code}
This version is inefficient because all four tests must be made regardless
of the outcome of any of them. If the key pressed was the left-arrow key,
there's no need to check if it was some other key.

Instead, you can nest the conditionals, like this:

\begin{Code}
: PROCESS-KEY
   key  dup  LEFT-ARROW  =  IF CURSOR-LEFT  ELSE
        dup  RIGHT-ARROW =  IF CURSOR-RIGHT ELSE
        dup  UP-ARROW    =  IF CURSOR-UP    ELSE
                               CURSOR-DOWN
           THEN THEN THEN  drop ;
\end{Code}
\begin{tip}
Combine booleans of similar weight.
\end{tip}
Many instances of doubly-nested \forthb{IF }\forthb{THEN} structures can
be simplified by combining the flags with logical operators before making
the decision.
Here's a doubly-nested test:
\begin{Code}
: ?PLAY   SATURDAY? IF  WORK FINISHED? IF
     GO PARTY  THEN  THEN ;
\end{Code}
The above code uses nested \forthb{IF}s to make sure that it's both
Saturday and the chores are done before it boogies on down. Instead,
let's combine the conditions logically and make a single decision:

\begin{Code}
: ?PLAY   SATURDAY?  WORK FINISHED? and  IF
   GO PARTY  THEN ;
\end{Code}
It's simpler and more readable.

The logical ``or'' situation, when implemented with
\forthb{IF }\forthb{THEN}s, is even clumsier:

\begin{Code}
: ?RISE    PHONE RINGS? IF  UP GET  THEN
     ALARM-CLOCK RINGS?  IF UP GET THEN ;
\end{Code}
This is much more elegantly written as

\begin{Code}
: ?RISE  PHONE RINGS?  ALARM RINGS? or  IF  UP GET THEN ;
\end{Code}
One exception to this rule arises when the speed penalty for checking
some of the conditions is too great.

We might write

\begin{Code}
: ?CHOW-MEIN   BEAN-SPROUTS?  CHOW-MEIN RECIPE?  and IF
   CHOW-MEIN PREPARE  THEN ;
\end{Code}
But suppose it's going to take us a long time to hunt through our recipe
file to see if there's anything on chow mein. Obviously there's no point in
undertaking the search if we have no bean sprouts in the fridge. It would
be more efficient to write

\begin{Code}
: ?CHOW-MEIN   BEAN-SPROUTS? IF  CHOW-MEIN RECIPE? IF
   CHOW-MEIN PREPARE THEN   THEN ;
\end{Code}
We don't bother looking for the recipe if there are no sprouts.

Another exception arises if any term is probably not true. By
eliminating such a condition first, you avoid having to try the other
conditions.

\begin{tip}
When multiple conditions have dissimilar weights (in likelihood or
calculation time) nest conditionals with the term that is least likely
to be true or easiest to calculate on the outside.
\end{tip}
Trying to improve performance in this way is more difficult with the
\forth{OR} construct. For instance, in the definition

\begin{Code}
: ?RISE  PHONE RINGS?  ALARM RINGS? or  IF  UP GET THEN ;
\end{Code}
we're testing for the phone and the alarm, even though only one of them
needs to ring for us to get up. Now suppose it were much more difficult to
determine that the alarm clock was ringing. We could write

\begin{Code}
: ?RISE   PHONE RINGS? IF  UP GET  ELSE
     ALARM-CLOCK RINGS?  IF UP GET THEN THEN  ;
\end{Code}
If the first condition is true, we don't waste time evaluating the second.
We have to get up to answer the phone anyway.

The repetition of \forth{UP GET} is ugly---not nearly as readable as the
solution using \forth{OR}---but in some cases desirable.%
\index{C!Conditionals, nesting and combining|)}%
\index{C!Control structure minimization!nesting and combining conditionals|)}
\index{N!Nesting conditionals|)}%

\subsection{Choosing Control Structures}%
\index{C!Control structures:!choosing|(}
\begin{tip}
The most elegant code is that which most closely matches the problem.
Choose the control structure that most closely matches the control-flow
problem.
\end{tip}%
\index{C!Control structures:!choosing|)}

\subsubsection{Case Statements}%
\index{C!Case statements|(}%
\index{C!Control structure minimization!case statements|(}

A particular class of problem involves selecting one of several possible
paths of execution according to a numeric argument. For instance, we
want the word \forth{.SUIT} to take a number representing a suit of playing
cards, 0 through 3, and display the name of the suit. We might define this
word using nested \forthb{IF }\forthb{ELSE }\forthb{THEN}s, like this:

\begin{Code}
: .SUIT ( suit -- )
  dup  0=  IF ." HEARTS "   ELSE
  dup  1 = IF ." SPADES "   ELSE
  dup  2 = IF ." DIAMONDS " ELSE
              ." CLUBS "
  THEN THEN THEN  drop ;
\end{Code}
We can solve this problem more elegantly by using a ``case statement.''

Here's the same definition, rewritten using the ``\person{Eaker} case
statement'' format, named after Dr.\@ \person{Charles E. Eaker}, the
gentleman who proposed it \cite{eaker}.

\begin{Code}
: .SUIT ( suit -- )
  CASE
  0 OF   ." HEARTS "    ENDOF
  1 OF   ." SPADES "    ENDOF
  2 OF   ." DIAMONDS "  ENDOF
  3 OF   ." CLUBS "     ENDOF     ENDCASE ;
\end{Code}
The case statement's value lies exclusively in its readability and
writeability. There's no efficiency improvement either in object memory or
in execution speed. In fact, the case statement compiles much the same
code as the nested \forthb{IF }\forthb{THEN} statements. A case statement
is a good example of compile-time factoring.

Should all \Forth{} systems include such a case statement? That's a matter
of controversy. The problem is twofold. First, the instances in which a
case statement is actually needed are rare---rare enough to question its
value. If there are only a few cases, a nested \forthb{IF }\forthb{ELSE
}\forthb{THEN} construct will work as well, though perhaps not as
readably. If there are many cases, a decision table is more flexible.

Second, many case-like problems are not quite appropriate for the case
structure. The \person{Eaker} case statement assumes that you're testing
for equality against a number on the stack. In the instance of
\forth{.SUIT}, we have contiguous integers from zero to three. It's more
efficient to use the integer to calculate an offset and directly jump to
the right code.

In the case of our Tiny Editor, later in this chapter, we have not one, but
two, dimensions of possibilities. The case statement doesn't match that
problem either.

Personally, I consider the case statement an elegant solution to a
misguided problem: attempting an algorithmic expression of what is
more aptly described in a decision table.

A case statement ought to be part of the application when useful,
but not part of the system.%
\index{C!Case statements|)}%
\index{C!Control structure minimization!case statements|)}

\subsubsection{Looping Structures}%
\index{C!Control structure minimization!looping structures|(}%
\index{L!Loops|(}
The right looping structure can eliminate extra conditionals.
\begin{interview}
\person{Moore}:\index{M!Moore, Charles|(}
\begin{tfquot}
Many times conditionals are used to get out of loops. That particular use
can be avoided by having loops with multiple exit points.

This is a live topic, because of the multiple \forthb{WHILE} construct
which is in poly\Forth{} but hasn't percolated up to \Forth{} '83. It's a
simple way of defining multiple \forthb{WHILE}s in the same
\forthb{REPEAT}.

Also \person{Dean Sanderson}\index{S!Sanderson, Dean} [of \Forth{}, Inc.]
has invented a new construct that introduces two exit points to a
\forthb{DO }\forthb{LOOP}.\index{D!DO LOOP} Given that construction you'll
have fewer tests. Very often I leave a truth value on the stack, and if
I'm leaving a loop early, I change the truth value to remind myself that I
left the loop early. Then later I'll have an \forthb{IF} to see whether I
left the loop early, and it's just clumsy.

Once you've made a decision, you shouldn't have to make it again. With the
proper looping constructs you won't need to remember where you came from,
so more conditionals will go away.

This is not completely popular because it's rather unstructured. Or perhaps
it is elaborately structured. The value is that you get simpler programs.
And it costs nothing.
\end{tfquot}\index{M!Moore, Charles|)}
\end{interview}
Indeed, this is a live topic. As of this writing it's too early to make
any specific proposals for new loop constructs. Check your system's
documentation to see what it offers in the way of exotic looping
structures.  Or, depending on the needs of your application, consider
adding your own conditional constructs. It's not that hard in \Forth{}.

I'm not even sure whether this use of multiple exits doesn't violate the
doctrine of structured programming. In a
\forthb{BEGIN }\forthb{WHILE }\forthb{REPEAT}
loop with multiple \forthb{WHILE}s, all the exits bring you to a common
``continue'' point: the \forthb{REPEAT}. But with \person{Sanderson}'s
\index{S!Sanderson, Dean} construct, you
can exit the loop by jumping \emph{past} the end of the loop, continuing
at an \forthb{ELSE}. There are two possible ``continue'' points.

This is ``less structured,'' if we can be permitted to say that. And
yet the definition will always conclude at its semicolon and return to the
word that invoked it. In that sense it is well-structured; the module has
one entry point and one exit point.

When you want to execute special code only if you did \emph{not} leave the
loop prematurely, this approach seems the most natural structure to use.
(We'll see an example of this in a later section, ``Using Structured
Exits.'')
%
\index{C!Counts vs. terminators|(}
\index{T!Terminators vs. counts|(}
\begin{tip}
Favor counts over terminators.
\end{tip}
\Forth{} handles strings by saving the length of the string in the first
byte. This makes it easier to type, move, or do practically anything with
the string. With the address and count on the stack, the definition of
\forthb{TYPE} can be coded:

\begin{Code}
: type  ( a #)  over + swap DO  i c@ emit  LOOP ;
\end{Code}
(Although \forthb{TYPE} really ought to be written in machine code.)

This definition uses no overt conditional. \forthb{LOOP} actually hides the
conditional since each loop checks the index and returns to \forthb{DO} if it
has not yet reached the limit.

If a delimiter were used, let's say ASCII null (zero), the definition
would have to be written:

\begin{Code}
: type  ( a)  BEGIN dup c@  ?dup WHILE  emit  1+
   REPEAT  drop ;
\end{Code}
An extra test is needed on each pass of the loop. (\forthb{WHILE} is a
conditional operator.)

Optimization note: The use of \forthb{?DUP} in this solution is expensive
in terms of time because it contains an extra decision itself. A faster
definition would be:

\begin{Code}
: type  ( a)  BEGIN dup c@  dup WHILE emit 1+
    REPEAT  2drop ;
\end{Code}
The '83 Standard applied this principle to \forthb{INTERPRET}
\index{I!INTERPRET}
which now accepts a count rather than looking for a terminator.

The flip side of this coin is certain data structures in which it's
easiest to \emph{link} the structures together. Each record points to the
next (or previous) record. The last (or first) record in the chain can be
indicated with a zero in its link field.

If you have a link field, you have to fetch it anyway. You might as
well test for zero. You don't need to keep a counter of how many records
there are. If you decrement a counter to decide whether to terminate,
you're making more work for yourself. (This is the technique used to
implement \Forth{}'s dictionary as a linked list.)%
\index{C!Counts vs. terminators|)}%
\index{C!Control structure minimization!looping structures|)}%
\index{L!Loops|)}%
\index{T!Terminators vs. counts|)}%

\subsubsection{Calculating Results}%
\index{C!Control structure minimization!calculating results|(}%
\index{C!Calculations|(}%

\begin{tip}
Don't decide, calculate.
\end{tip}
Many times conditional control structures are applied mistakenly to
situations in which the difference in outcome results from a difference in
numbers. If numbers are involved, we can calculate them. (In Chapter
Four see the section called ``Calculations vs. Data Structures vs. Logic.'')
%
\index{B!Booleans, as hybrid values|(}
\begin{tip}
Use booleans as hybrid values.
\end{tip}
This is a fascinating corollary to the previous tip, ``Don't decide,
calculate.'' The idea is that booleans, which the computer represents as
numbers, can efficiently be used to effect numeric decisions. Here's one
example, found in many \Forth{} systems:

\begin{Code}
: s>d  ( n -- d)  \ sign extend s to d
     dup O<  IF -1  ELSE  0 THEN ;
\end{Code}
(The purpose of this definition is to convert a single-length number to
double-length. A double-length number is represented as two 16-bit
values on the stack, the high-order part on top. Converting a positive
integer to double-length merely means adding a zero onto the stack, to
represent its high-order part. But converting a negative integer to
double-length requires ``sign extension;'' that is, the high-order part
should be all ones.)

The above definition tests whether the single-length number is negative.
If so, it pushes a negative one onto the stack; otherwise a zero.  But
notice that the outcome is merely arithmetic; there's no change in
process. We can take advantage of this fact by using the boolean itself:

\begin{Code}
: s>d  ( n -- d)  \ sign extend s to d
     dup  O< ;
\end{Code}
This version pushes a zero or negative one onto the stack without a
moment's (in)decision.

\medbreak
(In pre-1983 systems, the definition would be:

\begin{Code}
: s>d  ( n -- d)  \ sign extend s to d
     dup  O< negate ;
\end{Code}
See \App{C}.)%
\index{B!Booleans, as hybrid values|)}\medbreak

\index{H!Hybrid values|(}%
We can do even more with ``hybrid values'':
%
\index{A!AND|(}
\begin{tip}
To effect a decision with a numeric outcome, use \forthb{AND}.
\end{tip}
In the case of a decision that produces either zero or a non-zero ``$n$,''
the traditional phrase

\begin{Code}
( ? ) IF  n  ELSE  0  THEN
\end{Code}
is equivalent to the simpler statement

\begin{Code}
( ? )  n and
\end{Code}
Again, the secret is that ``true'' is represented by $-1$ (all ones) in
'83 \Forth{} systems. \forthb{AND}ing ``$n$'' with the flag will either
produce ``$n$'' (all bits intact) or ``$0$'' (all bits cleared).

To restate with an example:

\begin{Code}
( ? )  IF  200  ELSE  0  THEN
\end{Code}
is the same as

\begin{Code}
( ? )  200 and
\end{Code}
Take a look at this example:

\begin{Code}
n  a b <  IF  45 +  THEN
\end{Code}
This phrase either adds 45 to ``$n$'' or doesn't, depending on the
relative sizes of ``$a$'' and ``$b$.'' Since ``adding 45 or not'' is the
same as ``adding 45 or adding 0,'' the difference between the two outcomes
is purely numeric.  We can rid ourselves of a decision, and simply
compute:

\begin{Code}
n  a b <  45 and  +
\end{Code}
\begin{interview}
\person{Moore}:\index{M!Moore, Charles|(}
\begin{tfquot}
The ``\forth{45 AND}'' is faster than the \forth{IF}, and certainly more
graceful. It's simpler. If you form a habit of looking for instances where
you're calculating this value from that value, then usually by doing
arithmetic on the logic you get the same result more cleanly.

I don't know what you call this. It has no terminology; it's merely doing
arithmetic with truth values. But it's perfectly valid, and someday boolean
algebra and arithmetic expressions will accommodate it.

In books you often see a lot of piece-wise linear approximations that fail to
express things clearly. For instance the expression

\begin{Code}[commandchars=\&\{\}]
x = 0 for t < 0
x = 1 for t &(&ge&) 0
\end{Code}
This would be equivalent to
\begin{Code}
t  0<  1 and
\end{Code}
as a single expression, not a piece-wise expression.
\end{tfquot}\index{M!Moore, Charles|)}
\end{interview}%%
\index{A!AND|)}

I call these flags ``hybrid values'' because they are booleans (truth
values) being applied as data (numeric values). Also, I don't know what
else to call them.%
\index{H!Hybrid values|)}

We can eliminate numeric \forth{ELSE} clauses as well (where both results
are non-zero), by factoring out the difference between the two results.
For instance,

\begin{Code}
: STEPPERS  'TESTING? @  IF 150 ELSE 151  THEN  load ;
\end{Code}
can be simplified to

\begin{Code}
: STEPPERS   150  'TESTING? @  1 and +  load ;
\end{Code}
This approach works here because conceptually we want to either load
Screen 150, or if testing, the next screen past it.%
\index{C!Calculations|)}%
\index{C!Control structure minimization!calculating results|)}

\section{A Note on Tricks}%
\index{T!Tricks|(}%
\index{C!Control structure minimization!tricks|(}

This sort of approach is often labeled a ``trick.'' In the computing
industry at large, tricks have a bad reputation.

A trick is simply taking advantage of certain properties of operation.
Tricks are used widely in engineering applications. Chimneys
eliminate smoke by taking advantage of the fact that heat rises.
Automobile tires provide traction by taking advantage of gravity.

Arithmetic Logic Units (ALUs) take advantage of the fact that
subtracting a number is the same as adding its two's complement.

These tricks allow simpler, more efficient designs. What justifies
their use is that the assumptions are certain to remain true.

The use of tricks becomes dangerous when a trick depends on something
likely to change, or when the thing it depends on is not protected by
information hiding.

Also, tricks become difficult to read when the assumptions on which
they're based aren't understood or explained. In the case of replacing
conditionals with \forth{AND}, once this technique becomes part of every
programmer's vocabulary, code can become \emph{more} readable. In the case
of a trick that is specific to a specific application, such as the order
in which data are arranged in a table, the listing must clearly document
the assumption used by the trick.%
\index{C!Control structure minimization!tricks|)}%
\index{T!Tricks|)}%

\begin{tip}
Use \forthb{MIN} and \forthb{MAX} for clipping.
\index{M!MAX}%
\index{M!MIN}%
\end{tip}
Suppose we want to decrement the contents of the variable \forth{VALUE}, but
we don't want the value to go below zero:

\begin{Code}
-1 Value +!  Value @  -1 = IF  0 Value !  THEN
\end{Code}
This is more simply written:

\begin{Code}
Value @  1-  0 max  Value !
\end{Code}
In this case the conditional is factored within the word \forthb{MAX}.

\subsection{Using Decision Tables}%
\index{D!Decision table|(}%
\index{C!Control structure minimization!decision tables|(}

\begin{tip}
Use decision tables.
\end{tip}
We introduced these in \Chap{2}. A decision table is a structure that
contains either data (a ``data table'') or addresses of functions (a
``function table'') arranged according to any number of dimensions. Each
dimension represents all the possible, mutually exclusive states of a
particular aspect of the problem. At the intersection of the ``true''
states of each dimension lies the desired element: the piece of data or
the function to be performed.

A decision table is clearly a better choice than a conditional structure
when the problem has multiple dimensions.

\subsubsection{One-Dimensional Data Table}
\index{O!One-dimensional data table|(}

Here's an example of a simple, one-dimensional data table. Our application
has a flag called \forth{'FREEWAY?} which is true when we're referring to
freeways, false when we're referring to city streets.

Let's construct the word \forth{SPEED-LIMIT}, which returns the speed
limit depending on the current state.
Using \forthb{IF }\forthb{THEN} we would write:

\begin{Code}
: SPEED-LIMIT  ( -- speed-limit)
     'FREEWAY? @  IF  55  ELSE  25  THEN ;
\end{Code}
We might eliminate the \forthb{IF }\forthb{THEN} by using a hybrid value
with \forthb{AND}:

\begin{Code}
: SPEED-LIMIT   25  'FREEWAY? @  30 and + ;
\end{Code}
But this approach doesn't match our conceptual model of the problem
and therefore isn't very readable.

Let's try a data table. This is a one-dimensional table, with only two
elements, so there's not much to it:

\begin{Code}
Create LIMITS   25 ,  55 ,
\end{Code}
The word \forth{SPEED-LIMIT?} now must apply the boolean to offset into
the data table:

\begin{Code}
: SPEED-LIMIT  ( -- speed-limit)
     LIMITS  'FREEWAY? @  2 and  +  @ ;
\end{Code}
Have we gained anything over the \forthb{IF }\forthb{THEN} approach?
Probably not, with so simple a problem.

What we have done, though, is to factor out the decision-making
process from the data itself. This becomes more cost-effective when we
have more than one set of data related to the same decision. Suppose we
also had

\begin{Code}
Create #LANES   4 ,  10 ,
\end{Code}
representing the number of lanes on a city street and on a freeway. We
can use identical code to compute the current number of lanes:

\begin{Code}
: #LANES?  ( -- #lanes)
     #LANES  'FREEWAY? @  2 and  +  @ ;
\end{Code}
Applying techniques of factoring, we simplify this to:

\begin{Code}
: ROAD  ( for-freeway for-city ) Create , ,
     DOES> ( -- data )  'FREEWAY? @  2 and  +  @ ;
55 25 ROAD SPEED-LIMIT?
10  4 ROAD #LANES?
\end{Code}
Another example of the one-dimensional data table is the ``superstring''
(\emph{Starting \Forth{}}, Chapter Ten).
\index{O!One-dimensional data table|)}

\subsubsection{Two-Dimensional Data Table}%
\index{T!Two-dimensional data table|(}%
\program{phone4}
In \Chap{2} we presented a phone-rate problem. \Fig{fig8-4} gives one
solution to the problem, using a two-dimensional data structure.

\begin{figure*}[bbbt]
\verbfig{fig8-4}{A solution to the phone rate problem.}
\begin{Screen}
\ Telephone rates                                       03/30/84
Create FULL     30 , 20 , 12 ,
Create LOWER    22 , 15 , 10 ,
Create LOWEST   12 ,  9 ,  6 ,
Variable RATE   \ points to FULL, LOWER or LOWEST
                \ depending on time of day
FULL RATE !  \ for instance
: CHARGE   ( o -- ) Create ,
   DOES>  ( -- rate )  @  RATE @ +  @ ;
0 CHARGE 1MINUTE   \ rate for first minute
2 CHARGE +MINUTES  \ rate for each additional minute
4 CHARGE /MILES    \ rate per each 100 miles
\end{Screen}

\begin{Screen}
\ Telephone rates                                       03/30/84
Variable OPERATOR?  \ 90 if operator assisted; else 0
Variable #MILES  \ hundreds of miles
: ?ASSISTANCE  ( direct-dial charge -- total charge)
   OPERATOR? @  + ;
: MILEAGE  ( -- charge )  #MILES @  /MILES * ;
: FIRST  ( -- charge )  1MINUTE  ?ASSISTANCE  MILEAGE + ;
: ADDITIONAL  ( -- charge)  +MINUTES  MILEAGE + ;
: TOTAL ( #minutes -- total charge)
   1- ADDITIONAL *  FIRST + ;
\end{Screen}
\end{figure*}

In this problem, each dimension of the data table consists of three
mutually exclusive states. Therefore a simple boolean (true/false) is
inadequate. Each dimension of this problem is implemented in a different
way.

The current rate, which depends on the time of day, is stored as an
address, representing one of the three rate-structure sub-tables. We can
say
\begin{Code}
FULL RATE !
\end{Code}
or
\begin{Code}
LOWER RATE !
\end{Code}
etc.\goodbreak

The current charge, either first minute, additional minute, or per mile,
is expressed as an offset into the table (0, 2, or 4).

An optimization note: we've implemented the two-dimensional table as a set
of three one-dimensional tables, each pointed to by \forth{RATE}. This
approach eliminates the need for a multiplication that would otherwise be
needed to implement a two-dimensional structure. The multiplication can be
prohibitively slow in certain cases.%
\index{T!Two-dimensional data table|)}%
\program{phone5}

\subsubsection{Two-Dimensional Decision Table}%
\index{T!Two-dimensional decision table|(}%
\program{editor4}

We'll hark back to our Tiny Editor example in \Chap{3} to illustrate
a two-dimensional decision table.

In \Fig{fig8-5} we're constructing a table of functions to be performed
when various keys are pressed. The effect is similar to that of a
case statement, but there are two modes, Normal Mode and Insert Mode.
Each key has a different behavior depending on the current mode.

The first screen implements the change of the modes. If we invoke

\begin{Code}
NORMAL MODE# !
\end{Code}
we'll go into Normal Mode.

\begin{Code}
INSERTING MODE# !
\end{Code}
enters Inserting Mode.

The next screen constructs the function table, called \forth{FUNCTIONS}.
The table consists of the ASCII value of a key followed by the address of
the routine to be performed when in Normal Mode, followed by the address
of the routine to be performed when in Insert Mode, when that key
is pressed. Then comes the second key, followed by the next pair of
addresses, and so on.

In the third screen, the word \forth{'FUNCTION} takes a key value,
searches through the \forth{FUNCTIONS} table for a match, then returns the
address of the cell containing the match. (We preset the variable
\forth{MATCHED} to point to the last row of the table---the functions we want
when \emph{any} character is pressed.)

The word \forth{ACTION} invokes \forth{'FUNCTION}, then adds the contents
of the variable \forth{MODE\#}. Since \forth{MODE\#} will contain either a
2 or a 4, by adding this offset we're now pointing into the table at the
address of the routine we want to perform. A simple

\begin{Code}
@ execute
\end{Code}
will perform the routine (or \forthb{@EXECUTE} if you have it).

In fig-\Forth{}, change the definition of \forth{IS} to:

\begin{Code}
: IS   [compile] '  CFA , ;
\end{Code}
\begin{figure*}[tttp]
\verbfig{fig8-5}{Implementation of the Tiny Editor.}
\setcounter{screen}{30}
\begin{Screen}
\ Tiny Editor
2 Constant NORMAL     \ offset in FUNCTIONS
4 Constant INSERTING  \        "
6 Constant /KEY       \ bytes in table for each key
Variable MODE#        \ current offset into table
NORMAL MODE# !
: INSERT-OFF   NORMAL    MODE# ! ;
: INSERT-ON    INSERTING MODE# ! ;

Variable ESCAPE?      \ t=time-to-leave-loop
: ESCAPE  true ESCAPE? ! ;





\end{Screen}
\begin{Screen}
\ Tiny Editor             function table             07/29/83
: IS   ' , ;  \   function   ( -- )    ( for '83 standard)
Create FUNCTIONS
\ keys                  normal mode        insert mode
 4 ,  ( ctrl-D)         IS DELETE          IS INSERT-OFF
 9 ,  ( ctrl-I)         IS INSERT-ON       IS INSERT-OFF
 8 ,  ( backspace)      IS BACKWARD        IS INSERT<
60 ,  ( left arrow)     IS BACKWARD        IS INSERT-OFF
62 ,  ( right arrow)    IS FORWARD         IS INSERT-OFF
27 ,  ( return)         IS ESCAPE          IS INSERT-OFF
 0 ,  ( no match)       IS OVERWRITE       IS insert
here /KEY -  Constant 'NOMATCH  \ adr of no-match key




\end{Screen}
\begin{Screen}
\ Tiny Editor cont'd                                 07/29/83
Variable MATCHED
: 'FUNCTION  ( key -- adr-of-match )  'NOMATCH  MATCHED !
   'NOMATCH FUNCTIONS DO  dup  i @ =  IF
     i MATCHED !  LEAVE  THEN  /KEY +LOOP  drop
    MATCHED @ ;
: ACTION  ( key -- )  'FUNCTION  MODE# @ +  @ execute ;
: GO   false ESCAPE? !  BEGIN  key ACTION  ESCAPE? @ UNTIL ;








\end{Screen}
\end{figure*}
In 79-Standard \Forth{}s, use:
\begin{Code}
: IS   [compile] '  , ;
\end{Code}
We've also used non-redundancy at compile time in the definition just
below the function table:
\begin{Code}
here /KEY -  Constant 'NOMATCH  \  adr of no-match key
\end{Code}
We're making a constant out of the last row in the function table. (At the
moment we invoke \forthb{HERE}, it's pointing to the next free cell after
the last table entry has been filled in. Six bytes back is the last row.)
We now have two words:
\begin{Code}
FUNCTIONS  ( adr of beginning of function table )
'NOMATCH   ( adr of "no-match" row; these are the
             routines for any key not in the table)
\end{Code}
We use these names to supply the addresses passed to \forthb{DO}:
\begin{Code}
'NOMATCH FUNCTION DO
\end{Code}
to set up a loop that runs from the first row of the table to the last. We
don't have to know how many rows lie in the table. We could even delete a
row or add a row to the table, without having to change any other piece of
code, even the code that searches through the table.

Similarly the constant \forth{/KEY} hides information about the number of
columns in the table.

Incidentally, the approach to \forth{'FUNCTION} taken in the listing is a
quick-and-dirty one; it uses a local variable to simplify stack
manipulation. A simpler solution that uses no local variable is:
\begin{Code}
: 'FUNCTION  ( key -- adr of match )
   'NOMATCH swap  'NOMATCH FUNCTIONS DO  dup
      i @ =  IF swap drop i swap  LEAVE  THEN
   /KEY +LOOP  drop ;
\end{Code}
(We'll offer still another solution later in this chapter, under ``Using
Structured Exits.'')%
\index{T!Two-dimensional decision table|)}%
\program{editor5}

\subsection{Decision Tables for Speed}

We've stated that if you can calculate a value instead of looking it up in a
table, you should do so. The exception is where the requirements for
speed justify the extra complexity of a table.

Here is an example that computes powers of two to 8-bit precision:

\begin{Code}
Create TWOS
   1 c,  2 c,  4 c,  8 c,  16 c,  32 c,
: 2**  ( n -- 2-to-the-n)
   TWOS +  c@ ;
\end{Code}
Instead of computing the answer by multiplying two times itself ``$n$''
times, the answers are all pre-computed and placed in a table. We can use
simple addition to offset into the table and get the answer.

In general, addition is much faster than multiplication.

\begin{interview}
\person{Moore}\index{M!Moore, Charles|(} provides another example:
\begin{tfquot}
If you want to compute trig functions, say for a graphics display, you don't
need much resolution. A seven-bit trig function is probably plenty. A table
look-up of 128 numbers is faster than anything else you're going to be able
to do. For low-frequency function calculations, decision tables are great.

But if you have to interpolate, you have to calculate a function anyway.
You're probably better off calculating a slightly more complicated function
and avoiding the table lookup.
\end{tfquot}\index{M!Moore, Charles|)}
\end{interview}%
\index{D!Decision table|)}%
\index{C!Control structure minimization!decision tables|)}

\subsection{Redesigning}%
\index{R!Redesigning to minimize control structures|(}%
\index{C!Control structure minimization!redesigning|(}

\begin{tip}
One change at the bottom can save ten decisions at the top.
\end{tip}
In our interview with \person{Moore}\index{M!Moore, Charles} at the
beginning of the chapter, he mentioned that much conditional testing could
have been eliminated from an application if it had been redesigned so that
there were two words instead of one: ``You either say \forth{GO} or you
say \forth{PRETEND}.''

It's easier to perform a simple, consistent algorithm while changing
the context of your environment than to choose from several algorithms
while keeping a fixed environment.

Recall from \Chap{1} our example of the word \forth{APPLES}. This was
originally defined as a variable; it was referred to many times throughout
the application by words that incremented the number of apples (when
shipments arrive), decremented the number (when apples are sold), and
checked the current number (for inventory control).

When it became necessary to handle a second type of apples, the
\emph{wrong} approach would have been to add that complexity to all
the shipment/\hy sales/\hy inventory words. The \emph{right} approach
was the one we took: to add the complexity ``at the bottom''; that is,
to \forth{APPLES} itself.

This principle can be realized in many ways. In \Chap{7} (under ``The
State Table'') we used state tables to implement the words \forth{WORKING}
and \forth{PRETENDING}, which changed the meaning of a group of variables.
Later in that chapter, we used vectored execution to define
\forth{VISIBLE} and \forth{INVISIBLE}, to change the meanings of
\forth{TYPE'}, \forth{EMIT'}, \forth{SPACES'} and \forth{CR'} and thereby
easily change all the formatting code that uses them.

\begin{tip}
Don't test for something that can't possibly happen.
\end{tip}
Many contemporary programmers are error-checking-happy.

There's no need for a function to check an argument passed by
another component in the system. The calling program should bear the
responsibility for not exceeding the limits of the called component.
%
\index{A!Algorithms|(}
\begin{tip}
Reexamine the algorithm.
\end{tip}
\begin{interview}
\person{Moore}:\index{M!Moore, Charles|(}
\begin{tfquot}
A lot of conditionals arise from fuzzy thinking about the problem. In
servo-control theory, a lot of people think that the algorithm for the
servo ought to be different when the distance is great than when it is
close. Far away, you're in slew mode; closer to the target you're in
decelerate mode; very close you're in hunt mode. You have to test how far
you are to know which algorithm to apply.

I've worked out a non-linear servo-control algorithm that will handle full
range. This approach eliminates the glitches at the transitioning points
between one mode and the other. It eliminates the logic necessary to decide
which algorithm to use. It eliminates your having to empirically determine
the transition points. And of course, you have a much simpler program with
one algorithm instead of three.

Instead of trying to get rid of conditionals, you're best to question the
underlying theory that led to the conditionals.
\end{tfquot}
\end{interview}%%
\index{A!Algorithms|)}
\begin{tip}
Avoid the need for special handling.
\end{tip}
One example we mentioned earlier in the book: if you keep the user out of
trouble you won't have to continually test whether the user has gotten
into trouble.

\begin{interview}
\person{Moore}:
\begin{tfquot}
Another good example is writing assemblers. Very often, even though an
opcode may not have a register associated with it, pretending that it has a
register---say, Register 0---might simplify the code. Doing arithmetic by
introducing bit patterns that needn't exist simplifies the solution. Just
substitute zeros and keep on doing arithmetic that you might have avoided
by testing for zero and not doing it.

It's another instance of the ``don't care.'' If you don't care, then give
it a dummy value and use it anyway.
\end{tfquot}\index{M!Moore, Charles|)}
\end{interview}
Anytime you run into a special case, try to find an algorithm for which
the special case becomes a normal case.

\begin{tip}
Use properties of the component.
\end{tip}
A well-designed component---hardware or software---will let you implement
a corresponding lexicon in a clean, efficient manner. The character
graphics set from the old Epson MX-80 printer (although now obsolete)
illustrates the point well. \Fig{fig8-6} shows the graphics characters
produced by the ASCII codes 160 to 223.

\wepsfiga{fig8-6}{The Epson MX-80 graphics character set.}

%!! include Figure 8-6 here

Each graphics character is a different combination of six tiny boxes,
either filled in or left blank. Suppose in our application we want to use
these characters to create a design. For each character, we know what we
want in each of the six positions---we must produce the appropriate
ASCII character for the printer.

A little bit of looking will tell you there's a very sensible pattern
involved. Assuming we have a six-byte table in which each byte represents
a pixel in the pattern:

%!! include inline graphic here (page 254)
\bigskip
{\sf\begin{tabular}{l|c|c|} \cline{2-3}
PIXELS~~ & ~0~ & ~1~ \\ \cline{2-3}
       & 2 & 3 \\ \cline{2-3}
       & 4 & 5 \\ \cline{2-3}
\end{tabular}}\bigskip

\noindent and assuming that each byte contains hex \code{FF} if the pixel is
``on;'' zero if it is ``off,'' then here's how little code it takes to
compute the character:

\begin{Code}
Create PIXELS  6 allot
: PIXEL  ( i -- a )  PIXELS + ;
: CHARACTER  ( -- graphics character)
   160   6 0 DO  i PIXEL c@  i 2** and  +  LOOP ;
\end{Code}
(We introduced \forth{2**} a few tips back.)

No decisions are necessary in the definition of \forth{CHARACTER}. The
graphics character is simply computed.

Note: to use the same algorithm to translate a set of six adjoining
pixels in a large grid, we can merely redefine \forth{PIXEL}. That's an example
of adding indirection backwards, and of good decomposition.

Unfortunately, external components are not always designed well.
For instance, The IBM Personal Computer uses a similar scheme for
graphics characters on its video display, but without any discernible
correspondence between the ASCII values and the pattern of pixels. The
only way to produce the ASCII value is by matching patterns in a lookup
table.

\begin{interview}
\person{Moore}:\index{M!Moore, Charles|(}
\begin{tfquot}
The 68000 assembler is another example you can break your heart over,
looking for a good way to express those op-codes with the minimal number
of operators. All the evidence suggests there is no good solution. The
people who designed the 68000 didn't have assemblers in mind. And they
could have made things a lot easier, at no cost to themselves.
\end{tfquot}\index{M!Moore, Charles|)}
\end{interview}
By using properties of a component in this way, your code becomes
dependent on those properties and thus on the component itself. This is
excusable, though, because all the dependent code is confined to a single
lexicon, which can easily be changed if necessary.%
\index{C!Control structure minimization!redesigning|)}
\index{R!Redesigning to minimize control structures|)}%

\subsection{Using Structured Exits}%
\index{S!Structured exits|(}%
\index{C!Control structure minimization!structured exits|(}

\begin{tip}
Use the structured exit.
\end{tip}
In the chapter on factoring we demonstrated the possibility of factoring
out a control structure using this technique:

\begin{Code}
: CONDITIONALLY   A B or  C and  IF  NOT r> drop  THEN ;
: ACTIVE   CONDITIONALLY   TUMBLE JUGGLE jump ;
: LAZY   CONDITIONALLY  SIT  EAT  SLEEP ;
\end{Code}
\Forth{} allows us to alter the control flow by directly manipulating the
return stack. (If in doubt, see \emph{Starting \Forth{}}, Chapter Nine.)
Indiscreet application of this trick can lead to unstructured code with nasty
side effects. But the disciplined use of the structured exit can actually
simplify code, and thereby improve readability and maintainability.

\begin{interview}
\person{Moore}:\index{M!Moore, Charles|(}
\begin{tfquot}
More and more I've come to favor \forth{R> DROP} to alter the flow of
control.  It's similar to the effect of an \forthb{ABORT"}, which has an
\forthb{IF }\forthb{THEN} built in it. But that's only one \forthb{IF
}\forthb{THEN} in the system, not at every error.

I either abort or I don't abort. If I don't abort, I continue. If I do
abort, I don't have to thread my way through the path. I short-circuit the
whole thing.

The alternative is burdening the rest of the application with checking
whether an error occurred. That's an inconvenience.
\end{tfquot}\index{M!Moore, Charles|)}
\end{interview}
The ``abort route'' circumvents the normal paths of control flow under
special conditions. \Forth{} provides this capability with the words
\forthb{ABORT"} and \forthb{QUIT}.

The ``structured exit'' extends the concept by allowing the immediate
termination of a single word, without quitting the entire application.

This technique should not be confused with the use of GOTO, which is
unstructured to the extreme. With GOTO you can go anywhere, inside or
outside the current module. With this technique, you effectively jump
directly to the final exit point of the module (the semicolon) and resume
execution of the calling word.
%
\index{E!EXIT|(}
The word \forthb{EXIT} terminates the definition in which the word
appears.  The phrase \forthb{R> DROP} terminates the definition that
called the definition in which the phrase appears; thus it has the same
effect but can be used one level down. Here are some examples of both
approaches.

If you have an \forthb{IF }\forthb{ELSE }\forthb{THEN} phrase in which no
code follows \forthb{THEN}, like this:

\begin{Code}
... HUNGRY?  IF  EAT-IT  ELSE  FREEZE-IT  THEN ;
\end{Code}
you can eliminate \forthb{ELSE} by using \forthb{EXIT}:

\begin{Code}
... HUNGRY?  IF EAT-IT EXIT  THEN  FREEZE-IT ;
\end{Code}
(If the condition is true, we eat and run; \forthb{EXIT} acts like a
semicolon.  If the condition is false, we skip to \forthb{THEN} and
\forth{FREEZE-IT}.)

The use of \forthb{EXIT} here is more efficient, saving two bytes and
extra code to perform, but it is not as readable.%
\index{E!EXIT|)}

\begin{interview}
\person{Moore}\index{M!Moore, Charles|(} comments on the value, and
danger, of this technique:
\begin{tfquot}
Especially if your conditionals are getting elaborate, it's handy to jump
out in the middle without having to match all your \forthb{THEN}s at the
end. In one application I had a word that went like this:

\begin{Code}
: TESTING
   SIMPLE  1CONDITION IF ... EXIT THEN
           2CONDITION IF ... EXIT THEN
           3CONDITION IF ... EXIT THEN ;
\end{Code}
SIMPLE handled the simple cases. SIMPLE ended up with \forthb{R> DROP}.
These other conditions were the more complex ones.

Everyone exited at the same point without having to painfully match all
the \forthb{IF}s, \forthb{ELSE}s, and \forthb{THEN}s. The final result, if
none of the conditions matched, was an error condition.

It was bad code, difficult to debug. But it reflected the nature of the
problem. There wasn't any better scheme to handle it. The \forthb{EXIT}
and \forthb{R> DROP} at least kept things manageable.
\end{tfquot}\index{M!Moore, Charles|)}
\end{interview}
Programmers sometimes also use \forthb{EXIT} to get out of a complicated
\forthb{BEGIN} loop in a graceful way. Or we might use a related technique
in the \forthb{DO }\forthb{LOOP} that we wrote for \forth{'FUNCTION} in
our Tiny Editor, earlier in this chapter. In this word, we are searching
through a series of locations looking for a match. If we find a match, we
want to return the address where we found it; if we don't find a match, we
want the address of the last row of the functions table.

We can introduce the word \forth{LEAP} (see \App{C}), which will work
like \forthb{EXIT} (it will simulate a semicolon). Now we can write:

\begin{Code}
: 'FUNCTION  ( key -- adr-of-match )
   'NOMATCH FUNCTIONS DO  dup  i @ =  IF  drop i LEAP
   THEN  /KEY +LOOP  drop  'NOMATCH ;
\end{Code}
If we find a match we \forth{LEAP}, not to \forthb{+LOOP}, but right out
of the definition, leaving \forth{I} (the address at which we found it) on
the stack. If we don't find a match, we fall through the loop and execute

\begin{Code}
drop  'NOMATCH
\end{Code}
which drops the key\# being searched for, then leaves the address of the
last row!

As we've seen, there may be times when a premature exit is appropriate,
even multiple exit points and multiple ``continue'' points.

Remember though, this use of \forthb{EXIT} and \forthb{R> DROP} is
\emph{not consistent} with structured programming in the strictest sense,
and requires great care.

For instance, you may have a value on the stack at the beginning of a
definition which is consumed at the end. A premature \forthb{EXIT} will
leave the unwanted value on the stack.

Fooling with the return stack is like playing with fire. You can get
burned. But how convenient it is to have fire.%
\index{C!Control structure minimization!structured exits|)}
\index{S!Structured exits|)}%

\subsection{Employing Good Timing}%
\index{C!Control structure minimization!timing|(}

\begin{tip}
Take the action when you know you need to, not later.
\end{tip}
Any time you set a flag, ask yourself why you're setting it. If the answer
is, ``So I'll know to do such-and-such later,'' then ask yourself if you
can do such-and-such \emph{now}. A little restructuring can greatly
simplify your design.

\begin{tip}
Don't put off till run time what you can compile today.
\end{tip}
Any time you can make a decision prior to compiling an application, do.

Suppose you had two versions of an array: one that did bounds
checking for your protection during development and one that ran faster,
though unprotected for the actual application.

Keep the two versions in different screens. When you compile your
application, load only the version you need.

By the way, if you follow this suggestion, you may go crazy editing
parentheses in and out of your load blocks to change which version gets
loaded each time. Instead, write throw-away definitions that make the
decisions for you. For instance (as already previewed in another context):

\begin{Code}
: STEPPERS   150  'TESTING? @  1 and +  load ;
\end{Code}
\begin{tip}
\forthb{DUP} a flag, don't recreate it.
\end{tip}
Sometimes you need a flag to indicate whether or not a previous piece of
code was invoked. The following definition leaves a flag which indicates
that \forth{DO-IT} was done:

\begin{Code}
: DID-I?  ( -- t=I-did)
   SHOULD-I?  IF  DO-IT  true  ELSE  false  THEN ;
\end{Code}
This can be simplified to:

\begin{Code}
: DID-I?  ( -- t=I-did)
        SHOULD-I? dup  IF  DO-IT  THEN ;
\end{Code}
\begin{tip}
Don't set a flag, set the data.
\end{tip}
If the only purpose to setting a flag is so that later some code can decide
between one number and another, you're better off saving the number
itself.

The ``colors'' example in \Chap{6}'s section called ``Factoring
Criteria'' illustrates this point.

The purpose of the word \forth{LIGHT} is to set a flag which indicates
whether we want the intensity bit to be set or not. While we could have
written\program{color4}

\begin{Code}
: LIGHT   true 'LIGHT? ! ;
\end{Code}
to set the flag, and

\begin{Code}
'LIGHT? @ IF  8 or  THEN ...
\end{Code}
to use the flag, this approach is not quite as simple as putting the
intensity bit-mask itself in the variable:

\begin{Code}
: LIGHT   8 'LIGHT? ! ;
\end{Code}
and then simply writing

\begin{Code}
'LIGHT? @  or ...
\end{Code}
to use it.

\begin{tip}
Don't set a flag, set the function. (Vector.)
\end{tip}
This tip is similar to the previous one, and lives under the same
restriction. If the only purpose to setting a flag is so that later some
code can decide between one function and another, you're better off saving
the address of the function itself.

For instance, the code for transmitting a character to a printer is
different than for slapping a character onto a video display. A poor
implementation would define:

\begin{Code}
Variable DEVICE  ( O=video | 1=printer)
: VIDEO   false DEVICE ! ;
: PRINTER   true DEVICE ! ;
: type  ( a # -- ) DEVICE @ IF
   ( ...code for printer...) ELSE
   ( ...code for video...)  THEN ;
\end{Code}
This is bad because you're deciding which function to perform every time
you type a string.

A preferable implementation would use vectored execution. For
instance:

\begin{Code}
DOER type  ( a # -- )
: VIDEO   MAKE type ( ...code for video...) ;
: PRINTER   MAKE type ( ...code for printer...) ;
\end{Code}
This is better because \forth{TYPE} doesn't have to decide which code to
use, it already knows.

(On a multi-tasked system, the printer and monitor tasks would
each have their own copies of an execution vector for \forth{TYPE}
stored in a user variable.)

The above example also illustrates the limitation of this tip. In our
second version, we have no simple way of knowing whether our current
device is the printer or the video screen. We might need to know, for
instance, to decide whether to clear the screen or issue a formfeed. Then
we're making an additional use of the state, and our rule no longer
applies.

A flag would, in fact, allow the simplest implementation of additional
state-dependent operations. In the case of \forth{TYPE}, however, we're
concerned about speed. We type strings so often, we can't afford to waste
time doing it. The best solution here might be to set the function of
\forth{TYPE} and also set a flag:

\begin{Code}
DOER type
: VIDEO   0 DEVICE !  MAKE type
     ( ...code for video...) ;
: PRINTER   1 DEVICE !  MAKE type
     ( ...code for printer...) ;
\end{Code}
Thus \forth{TYPE} already knows which code to execute, but other definitions
will refer to the flag.

Another possibility is to write a word that fetches the parameter of the
\forthb{DOER} word \forth{TYPE} (the pointer to the current code) and
compares it against the address of \forth{PRINTER}. If it's less than the
address of \forth{PRINTER}, we're using the \forth{VIDEO} routine;
otherwise we're using the \forth{PRINTER} routine.

If changing the state involves changing a small number of functions,
you can still use \forth{DOER}/\forth{MAKE}. Here are definitions of three
memory-move operators that can be shut off together.

\begin{Code}
DOER !'  ( vectorable ! )
DOER CMOVE'  ( vectorable CMOVE )
DOER FILL'  ( vectorable FILL )
: STORING   MAKE !' ! ;AND
            MAKE CMOVE'  cmove ;AND
            MAKE FILL'  fill ;
: -STORING  MAKE !'  2drop ;AND
            MAKE CMOVE'  2drop drop ;AND
            MAKE FILL'  2drop drop ;
\end{Code}
But if a large number of functions need to be vectored, a state table
would be preferable.

A corollary to this rule introduces the ``structured exit hook,'' a
\forthb{DOER} word vectored to perform a structured exit.

\begin{Code}
DOER HESITATE  ( the exit hook)
: DISSOLVE   HESITATE  FILE-DIVORCE ;
\end{Code}
(\dots{} Much later in the listing:)
\begin{Code}
: RELENT   MAKE HESITATE   SEND-FLOWERS  r> drop ;
\end{Code}
By default, \forth{HESITATE} does nothing. If we invoke \forth{DISSOLVE},
we'll end up in court. But if we \forth{RELENT} before we
\forth{DISSOLVE}, we'll send flowers, then jump clear to the semicolon,
canceling that court order before our partner ever finds out.

This approach is especially appropriate when the cancellation must be
performed by a function defined much later in the listing (decomposition
by sequential complexity). Increased complexity of the earlier code is
limited solely to defining the hook and invoking it at the right spot.%
\index{C!Control structure minimization!timing|)}

\subsection{Simplifying}%
\index{S!Simplicity|(}%
\index{C!Control structure minimization!simplification|(}

I've saved this tip for last because it exemplifies the rewards of opting
for simplicity. While other tips concern maintainability, performance,
compactness, etc., this tip relates to the sort of satisfaction that
Thoreau sought at Walden Pond.

\begin{tip}
Try to avoid altogether saving flags in memory.
\end{tip}
A flag on the stack is quite different from a flag in memory. Flags on the
stack can simply be determined (by reading the hardware, calculating, or
whatever), pushed onto the stack, then consumed by the control structure.
A short life with no complications.

But save a flag in memory and watch what happens. In addition to
having the flag itself, you now have the complexity of a location for the
flag. The location must be:

%!! items should be preceded by bullets
\begin{itemize}
\item created
\item initialized (even before anything actually changes)
\item reset (otherwise, passing a flag to a command leaves the flag in
that current state).
\end{itemize}
Because flags in memory are variables, they are not reentrant.

An example of a case in which we might reconsider the need for a flag is
one we've seen several times already. In our ``colors'' example we made
the assumption that the best syntax would be:\program{color5}

\begin{Code}
LIGHT BLUE
\end{Code}
that is, the adjective \forth{LIGHT} preceding the color. Fine. But
remember the code to implement that version? Compare it with the
simplicity of this approach:

\begin{Code}
0 Constant BLACK    1 Constant BLUE    2 Constant GREEN
3 Constant CYAN     4 Constant RED     5 Constant MAGENTA
6 Constant BROWN    7 Constant GRAY
: LIGHT   ( color -- color )  8 or ;
\end{Code}
In this version we've reversed the syntax, so that we now say

\begin{Code}
BLUE LIGHT
\end{Code}
We establish the color, then we modify the color.

We've eliminated the need for a variable, for code to fetch from the
variable and more code to reset the variable when we're done. And the
code is so simple it's impossible not to understand.

When I first wrote these commands, I took the English-like approach.
``\forth{BLUE LIGHT}'' sounded backwards, not at all acceptable. That was
before my conversations with
\person{Chuck Moore}\index{M!Moore, Charles|(}.

\begin{interview}
\person{Moore}'s philosophy is persuasive:
\begin{tfquot}
I would distinguish between reading nicely in English and reading nicely.
In other languages such as Spanish, adjectives follow nouns. We should be
independent of details like which language we're thinking in.

It depends on your intention: simplicity, or emulation of English. English
is not such a superb language that we should follow it slavishly.
\end{tfquot}\index{M!Moore, Charles|)}
\end{interview}
If I were selling my ``colors'' words in a package for graphic artists, I
would take the trouble to create the flag. But writing these words for my
own use, if I had to do it over again, I'd favor the \person{Moore}-ish
influence, and use ``\forth{BLUE LIGHT}.''%
\index{C!Control structure minimization|)}%
\index{C!Control structure minimization!simplification|)}%
\index{S!Simplicity|)}%

\section{Summary}

The use of logic and conditionals as a significant structural element in
programming leads to overly-complicated, difficult-to-maintain, and
inefficient code. In this chapter we've discussed several ways to minimize,
optimize or eliminate unnecessary conditional structures.

As a final note, \Forth{}'s downplaying of conditionals is not shared
by most contemporary languages. In fact, the Japanese are basing their
fifth-generation computer project on a language called PROLOG---for
PROgramming in LOGic---in which one programs entirely in logic. It will
be interesting to see the battle-lines forming as we ponder the question:

\begin{tfquot}
To \forthb{IF} or not to \forthb{IF}
\end{tfquot}
In this book we've covered the first six steps of the software development
cycle, exploring both the philosophical questions of designing software
and practical considerations of implementing robust, efficient, readable
software.

We have not discussed optimization, validation, debugging, documenting,
project management, \Forth{} development tools, assembler
definitions, uses and abuses of recursion, developing multiprogrammed
applications, or target compilation.

But that's another story.

\begin{references}{9}
\bibitem{eaker} \person{Charles Eaker}, ``Just in Case,'' \emph{\Forth{}
Dimensions} II/3, p. 37.
\end{references}

\section{For Further Thinking}

\ifeightyfour\begin{enumerate}
\item
You have the word \forth{CHOOSE} which takes an argument ``$n$''
and returns a random number between 0 and $n-1$. The result is always
positive or zero.  You can use \forth{CHOOSE} to produce a flag; the
phrase
\begin{Code}
2 CHOOSE
\end{Code}
produces a random flag of zero or one (false or true).

%%!!! this is not the second question, there is no question above
\item
Write a phrase to choose a number at random between 0 and 19 (inclusive)
\emph{or} between $-20$ and 0.
\end{enumerate}\else
%% replacement problem
Define the word \forth{DIRECTION}, which returns either 1,
$-1$, or 0, depending on whether the input argument is non-zero
positive, negative, or zero, respectively.
\fi