chapter8.tex 69.4 KB
Newer Older
1 2 3 4 5 6 7 8
%% 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
paysan's avatar
paysan committed
9
%EIGHT
10 11
%!! horizontal line

paysan's avatar
paysan committed
12 13
\chapter{Minimizing Control~Structures}\Chapmark{8}%
\index{C!Control structure minimization|(}%
14

paysan's avatar
paysan committed
15 16 17 18
\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.
19 20 21 22 23

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

%!! items should be preceded by bullets
paysan's avatar
paysan committed
24 25 26 27 28 29 30
\begin{itemize}
\item computing or calculating
\item hiding conditionals through re-factoring
\item using structured exits
\item vectoring
\item redesigning.
\end{itemize}
31 32 33
In this chapter we'll examine these techniques for simplifying and
eliminating control structures from your code.

paysan's avatar
paysan committed
34
\section{What's So Bad about Control Structures?}%
lesto's avatar
lesto committed
35
\index{C!Control structure minimization!reasons for|(}
36 37 38 39 40 41 42 43 44 45

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
46
\begin{interview}
paysan's avatar
paysan committed
47
\person{Moore}\index{M!Moore, Charles|(} tells this story:
paysan's avatar
paysan committed
48
\begin{tfquot}
49
I recently went back to a company we had done some work for several years
lesto's avatar
lesto committed
50 51 52 53 54 55
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.
56 57 58 59 60 61 62 63 64 65 66 67

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.

lesto's avatar
lesto committed
68 69 70 71 72
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.
73 74 75 76

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
paysan's avatar
paysan committed
77
instead of one. You either say \forth{GO} or you say \forth{PRETEND}.
78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94

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.
lesto's avatar
lesto committed
95
\end{tfquot}\index{M!Moore, Charles|)}
paysan's avatar
paysan committed
96 97
\end{interview}%
\index{C!Control structure minimization!reasons for|)}%
lesto's avatar
lesto committed
98 99 100
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
paysan's avatar
paysan committed
101
a design for an automatic teller machine.\program{teller1}
102

paysan's avatar
paysan committed
103
\begin{figure*}[tttt]
paysan's avatar
paysan committed
104 105
\verbfig{fig8-1}{The structured approach.}
\begin{center}
106
\small\begin{BVerbatim}[commandchars=\&\{\},baselinestretch=0.85]
paysan's avatar
paysan committed
107
&underline{AUTOMATIC-TELLER}
108 109 110 111 112 113

IF card is valid DO
   IF card owner is valid DO
      IF request withdrawal DO
         IF authorization code is valid DO
            query for amount
paysan's avatar
paysan committed
114 115
            IF request &(&le&) current balance DO
               IF withdrawal &(&le&) available cash DO
116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139
                  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
paysan's avatar
paysan committed
140 141 142
\end{BVerbatim}
\end{center}
\end{figure*}
lesto's avatar
lesto committed
143 144 145
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.
146

lesto's avatar
lesto committed
147 148 149
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
lesto's avatar
lesto committed
150
straightedge.
151

paysan's avatar
paysan committed
152
\begin{figure*}[tttt]
paysan's avatar
paysan committed
153
\verbfig{fig8-2}{Nesting conditionals within named procedures.}
154
\small\begin{center}
155
\begin{BVerbatim}[commandchars=\&\{\},baselinestretch=0.85]
paysan's avatar
paysan committed
156
&underline{AUTOMATIC-TELLER}
157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175

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
paysan's avatar
paysan committed
176
     If  request &(&le&) current balance  THEN  DISBURSE  END
177 178

PROCEDURE DISBURSE
paysan's avatar
paysan committed
179
     IF disbursement &(&le&) available cash  THEN
180 181 182 183 184 185 186
           vend currency
           debit account
         ELSE  message  END

PROCEDURE DEPOSIT
     accept envelope
     credit account
paysan's avatar
paysan committed
187 188 189
\end{BVerbatim}
\end{center}
\end{figure*}
lesto's avatar
lesto committed
190 191 192
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.
193

lesto's avatar
lesto committed
194 195
But even with this improvement, the design of each word depends completely
on the \emph{sequence} in which the tests must be performed. The
lesto's avatar
lesto committed
196 197 198
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.
199

paysan's avatar
paysan committed
200
\begin{figure*}[tttt]
paysan's avatar
paysan committed
201 202
\verbfig{fig8-3}{Refactoring and/or eliminating conditionals.}
\begin{center}
203
\small\begin{BVerbatim}[commandchars=\&\{\},baselinestretch=0.85]
paysan's avatar
paysan committed
204
&underline{AUTOMATIC-TELLER}
205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231

: 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
paysan's avatar
paysan committed
232
     request &(&le&) current balance  IF  DISBURSE  THEN ;
233 234

: DISBURSE
paysan's avatar
paysan committed
235
     disbursement &(&le&) available cash  IF
236 237 238 239 240 241 242
            vend currency
            debit account
          ELSE  message  THEN  ;

: DEPOSIT
     accept envelope
     credit account ;
paysan's avatar
paysan committed
243 244 245
\end{BVerbatim}
\end{center}
\end{figure*}
246

lesto's avatar
lesto committed
247 248 249 250 251 252 253 254 255 256 257 258 259
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}.)
lesto's avatar
lesto committed
260

paysan's avatar
paysan committed
261
Of course, \Forth{} will allow you to take any of the three approaches.
paysan's avatar
paysan committed
262
Which do you prefer?\program{teller2}
lesto's avatar
lesto committed
263 264

\section{How to Eliminate Control Structures}
lesto's avatar
lesto committed
265

lesto's avatar
lesto committed
266 267 268 269 270 271 272
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.

paysan's avatar
paysan committed
273 274
\subsection{Using the Dictionary}%
\index{C!Control structure minimization!dictionary|(}%
lesto's avatar
lesto committed
275 276 277 278 279
\index{D!Dictionary:!control structure minimization with|(}

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

285
\begin{interview}
paysan's avatar
paysan committed
286
\person{Moore}:\index{M!Moore, Charles|(}
paysan's avatar
paysan committed
287
\begin{tfquot}
288
In my accounting package, if you receive a check from somebody, you type
lesto's avatar
lesto committed
289 290
the amount, the check number, the word \forth{FROM}, and the person's
name:
291

292
\begin{Code}
293
200.00 127 FROM ALLIED
294
\end{Code}
lesto's avatar
lesto committed
295 296 297
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:
298

299
\begin{Code}
paysan's avatar
paysan committed
300
1000.00 280 BILL TECHNITECH
301
\end{Code}
lesto's avatar
lesto committed
302
\end{tfquot}\index{M!Moore, Charles|)}
paysan's avatar
paysan committed
303
\dots{} One word for each situation. The dictionary is making the decision.\medskip
304
\end{interview}
305
This notion pervades \Forth{} itself. To add a pair of single-length
lesto's avatar
lesto committed
306 307 308 309 310 311 312 313 314
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.

lesto's avatar
lesto committed
315
\index{D!Dumb words|(}
paysan's avatar
paysan committed
316
\begin{tip}
317
Use dumb words.
paysan's avatar
paysan committed
318
\end{tip}
319 320
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
lesto's avatar
lesto committed
321 322
instead, has the same behavior all the time (``referentially
transparent'').
323 324 325

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

lesto's avatar
lesto committed
326 327 328
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:
329

330
\begin{Code}
331
: TEST   ." THIS IS A STRING " ;
332
\end{Code}
333 334 335 336 337
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
lesto's avatar
lesto committed
338 339
definition, it will uselessly compile the string, not at all what a
beginner might expect.
340

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

lesto's avatar
lesto committed
346 347
\forth{."} became two completely different words housed together in one
definition with an \forth{IF ELSE THEN} structure. The flag that indicates
lesto's avatar
lesto committed
348 349 350
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.
351

lesto's avatar
lesto committed
352 353 354
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
355 356
that.

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

361
\begin{Code}
362
." INSERT DISK IN "  B." LEFT "  ." DRIVE "
363
\end{Code}
lesto's avatar
lesto committed
364
She might expect to define \forth{B."} as
365

366
\begin{Code}
367
: B."   BRIGHT  ."  NORMAL ;
368
\end{Code}
369 370 371 372 373 374
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.

lesto's avatar
lesto committed
375 376 377 378
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.
379

lesto's avatar
lesto committed
380 381 382 383 384 385
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}.
386

387
\begin{Code}
388
." INSERT DISK IN "  BRIGHT ." LEFT "  ." DRIVE "
389
\end{Code}
lesto's avatar
lesto committed
390 391 392 393 394 395 396 397 398 399 400
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.%
lesto's avatar
lesto committed
401
\index{D!Dumb words|)}
402

paysan's avatar
paysan committed
403
\begin{tip}
lesto's avatar
lesto committed
404 405
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
406
behave as they do interpretively.
paysan's avatar
paysan committed
407
\end{tip}
lesto's avatar
lesto committed
408 409 410
\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|)}%
paysan's avatar
paysan committed
411
\index{C!Control structure minimization!dictionary|)}%
lesto's avatar
lesto committed
412
\index{D!Dictionary:!control structure minimization with|)}
413

paysan's avatar
paysan committed
414
\subsection{Nesting and Combining Conditionals}%
lesto's avatar
lesto committed
415
\index{N!Nesting conditionals|(}%
paysan's avatar
paysan committed
416
\index{C!Conditionals, nesting and combining|(}%
lesto's avatar
lesto committed
417
\index{C!Control structure minimization!nesting and combining conditionals|(}
paysan's avatar
paysan committed
418
\begin{tip}
419
Don't test for something that has already been excluded.
paysan's avatar
paysan committed
420
\end{tip}
421 422
Take this example, please:

423
\begin{Code}
424
: PROCESS-KEY
425 426 427
   key  dup  LEFT-ARROW  =  IF CURSOR-LEFT  THEN
        dup  RIGHT-ARROW =  IF CURSOR-RIGHT THEN
        dup  UP-ARROW    =  IF CURSOR-UP    THEN
428
             DOWN-ARROW  =  IF CURSOR-DOWN  THEN ;
429
\end{Code}
430 431
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,
paysan's avatar
paysan committed
432
there's no need to check if it was some other key.
433 434 435

Instead, you can nest the conditionals, like this:

436
\begin{Code}
437
: PROCESS-KEY
438 439 440
   key  dup  LEFT-ARROW  =  IF CURSOR-LEFT  ELSE
        dup  RIGHT-ARROW =  IF CURSOR-RIGHT ELSE
        dup  UP-ARROW    =  IF CURSOR-UP    ELSE
441
                               CURSOR-DOWN
442
           THEN THEN THEN  drop ;
443
\end{Code}
paysan's avatar
paysan committed
444
\begin{tip}
445
Combine booleans of similar weight.
paysan's avatar
paysan committed
446
\end{tip}
lesto's avatar
lesto committed
447 448 449
Many instances of doubly-nested \forthb{IF }\forthb{THEN} structures can
be simplified by combining the flags with logical operators before making
the decision.
450
Here's a doubly-nested test:
451
\begin{Code}
452 453
: ?PLAY   SATURDAY? IF  WORK FINISHED? IF
     GO PARTY  THEN  THEN ;
454
\end{Code}
paysan's avatar
paysan committed
455
The above code uses nested \forthb{IF}s to make sure that it's both
lesto's avatar
lesto committed
456 457
Saturday and the chores are done before it boogies on down. Instead,
let's combine the conditions logically and make a single decision:
458

459
\begin{Code}
460
: ?PLAY   SATURDAY?  WORK FINISHED? and  IF
lesto's avatar
lesto committed
461
   GO PARTY  THEN ;
462
\end{Code}
463 464
It's simpler and more readable.

lesto's avatar
lesto committed
465 466
The logical ``or'' situation, when implemented with
\forthb{IF }\forthb{THEN}s, is even clumsier:
467

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

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

We might write

482
\begin{Code}
483
: ?CHOW-MEIN   BEAN-SPROUTS?  CHOW-MEIN RECIPE?  and IF
484
   CHOW-MEIN PREPARE  THEN ;
485
\end{Code}
486 487 488 489 490
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

491
\begin{Code}
492 493
: ?CHOW-MEIN   BEAN-SPROUTS? IF  CHOW-MEIN RECIPE? IF
   CHOW-MEIN PREPARE THEN   THEN ;
494
\end{Code}
495 496 497 498 499 500
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.

paysan's avatar
paysan committed
501
\begin{tip}
502 503 504
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.
paysan's avatar
paysan committed
505
\end{tip}
lesto's avatar
lesto committed
506 507
Trying to improve performance in this way is more difficult with the
\forth{OR} construct. For instance, in the definition
508

509
\begin{Code}
510
: ?RISE  PHONE RINGS?  ALARM RINGS? or  IF  UP GET THEN ;
511
\end{Code}
512 513 514 515
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

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

paysan's avatar
paysan committed
523
The repetition of \forth{UP GET} is ugly---not nearly as readable as the
paysan's avatar
paysan committed
524 525
solution using \forth{OR}---but in some cases desirable.%
\index{C!Conditionals, nesting and combining|)}%
lesto's avatar
lesto committed
526
\index{C!Control structure minimization!nesting and combining conditionals|)}
lesto's avatar
lesto committed
527
\index{N!Nesting conditionals|)}%
528

paysan's avatar
paysan committed
529
\subsection{Choosing Control Structures}%
lesto's avatar
lesto committed
530
\index{C!Control structures:!choosing|(}
paysan's avatar
paysan committed
531
\begin{tip}
532 533 534
The most elegant code is that which most closely matches the problem.
Choose the control structure that most closely matches the control-flow
problem.
paysan's avatar
paysan committed
535
\end{tip}%
lesto's avatar
lesto committed
536 537
\index{C!Control structures:!choosing|)}

paysan's avatar
paysan committed
538 539
\subsubsection{Case Statements}%
\index{C!Case statements|(}%
lesto's avatar
lesto committed
540
\index{C!Control structure minimization!case statements|(}
541 542 543

A particular class of problem involves selecting one of several possible
paths of execution according to a numeric argument. For instance, we
paysan's avatar
paysan committed
544 545
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
546
word using nested \forthb{IF }\forthb{ELSE }\forthb{THEN}s, like this:
547

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

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

562
\begin{Code}
563 564
: .SUIT ( suit -- )
  CASE
565
  0 OF   ." HEARTS "    ENDOF
566 567 568
  1 OF   ." SPADES "    ENDOF
  2 OF   ." DIAMONDS "  ENDOF
  3 OF   ." CLUBS "     ENDOF     ENDCASE ;
569
\end{Code}
570
The case statement's value lies exclusively in its readability and
lesto's avatar
lesto committed
571 572 573 574 575 576 577 578 579 580 581 582 583 584 585 586 587 588
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.
589

590 591
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
592 593 594 595 596 597 598
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,
paysan's avatar
paysan committed
599 600
but not part of the system.%
\index{C!Case statements|)}%
lesto's avatar
lesto committed
601
\index{C!Control structure minimization!case statements|)}
602

paysan's avatar
paysan committed
603 604
\subsubsection{Looping Structures}%
\index{C!Control structure minimization!looping structures|(}%
lesto's avatar
lesto committed
605
\index{L!Loops|(}
606
The right looping structure can eliminate extra conditionals.
607
\begin{interview}
paysan's avatar
paysan committed
608
\person{Moore}:\index{M!Moore, Charles|(}
paysan's avatar
paysan committed
609
\begin{tfquot}
610 611 612
Many times conditionals are used to get out of loops. That particular use
can be avoided by having loops with multiple exit points.

lesto's avatar
lesto committed
613 614 615 616
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}.
617

lesto's avatar
lesto committed
618 619 620 621 622 623 624
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.
625 626

Once you've made a decision, you shouldn't have to make it again. With the
lesto's avatar
lesto committed
627 628
proper looping constructs you won't need to remember where you came from,
so more conditionals will go away.
629 630 631 632

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.
633 634
\end{tfquot}\index{M!Moore, Charles|)}
\end{interview}
lesto's avatar
lesto committed
635 636 637 638 639 640 641 642 643
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}
paysan's avatar
paysan committed
644
loop with multiple \forthb{WHILE}s, all the exits bring you to a common
lesto's avatar
lesto committed
645 646
``continue'' point: the \forthb{REPEAT}. But with \person{Sanderson}'s
\index{S!Sanderson, Dean} construct, you
647
can exit the loop by jumping \emph{past} the end of the loop, continuing
paysan's avatar
paysan committed
648
at an \forthb{ELSE}. There are two possible ``continue'' points.
649 650 651 652 653 654 655 656 657 658

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.'')
paysan's avatar
paysan committed
659
%
lesto's avatar
lesto committed
660
\index{C!Counts vs. terminators|(}
lesto's avatar
lesto committed
661
\index{T!Terminators vs. counts|(}
paysan's avatar
paysan committed
662
\begin{tip}
663
Favor counts over terminators.
paysan's avatar
paysan committed
664
\end{tip}
665
\Forth{} handles strings by saving the length of the string in the first
666 667
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
paysan's avatar
paysan committed
668
\forthb{TYPE} can be coded:
669

670
\begin{Code}
671
: type  ( a #)  over + swap DO  i c@ emit  LOOP ;
672
\end{Code}
paysan's avatar
paysan committed
673
(Although \forthb{TYPE} really ought to be written in machine code.)
674

paysan's avatar
paysan committed
675 676
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
677 678 679 680 681
has not yet reached the limit.

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

682
\begin{Code}
683 684
: type  ( a)  BEGIN dup c@  ?dup WHILE  emit  1+
   REPEAT  drop ;
685
\end{Code}
lesto's avatar
lesto committed
686 687
An extra test is needed on each pass of the loop. (\forthb{WHILE} is a
conditional operator.)
688

lesto's avatar
lesto committed
689 690
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
691 692
definition would be:

693
\begin{Code}
694 695
: type  ( a)  BEGIN dup c@  dup WHILE emit 1+
    REPEAT  2drop ;
696
\end{Code}
lesto's avatar
lesto committed
697 698 699
The '83 Standard applied this principle to \forthb{INTERPRET}
\index{I!INTERPRET}
which now accepts a count rather than looking for a terminator.
700 701

The flip side of this coin is certain data structures in which it's
lesto's avatar
lesto committed
702 703 704
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.
705 706 707 708 709

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
paysan's avatar
paysan committed
710 711 712
implement \Forth{}'s dictionary as a linked list.)%
\index{C!Counts vs. terminators|)}%
\index{C!Control structure minimization!looping structures|)}%
lesto's avatar
lesto committed
713 714
\index{L!Loops|)}%
\index{T!Terminators vs. counts|)}%
715

paysan's avatar
paysan committed
716 717
\subsubsection{Calculating Results}%
\index{C!Control structure minimization!calculating results|(}%
lesto's avatar
lesto committed
718
\index{C!Calculations|(}%
719

paysan's avatar
paysan committed
720
\begin{tip}
721
Don't decide, calculate.
paysan's avatar
paysan committed
722
\end{tip}
723 724 725 726
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.'')
paysan's avatar
paysan committed
727
%
lesto's avatar
lesto committed
728
\index{B!Booleans, as hybrid values|(}
paysan's avatar
paysan committed
729
\begin{tip}
730
Use booleans as hybrid values.
paysan's avatar
paysan committed
731
\end{tip}
732 733 734
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
735
example, found in many \Forth{} systems:
736

737
\begin{Code}
738 739
: s>d  ( n -- d)  \ sign extend s to d
     dup O<  IF -1  ELSE  0 THEN ;
740
\end{Code}
741 742 743 744 745
(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
paysan's avatar
paysan committed
746
double-length requires ``sign extension;'' that is, the high-order part
747 748
should be all ones.)

lesto's avatar
lesto committed
749 750 751 752
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:
753

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

paysan's avatar
paysan committed
761
\medbreak
762 763
(In pre-1983 systems, the definition would be:

764
\begin{Code}
765 766
: s>d  ( n -- d)  \ sign extend s to d
     dup  O< negate ;
767
\end{Code}
paysan's avatar
paysan committed
768
See \App{C}.)%
769
\index{B!Booleans, as hybrid values|)}\medbreak
770

paysan's avatar
paysan committed
771
\index{H!Hybrid values|(}%
772
We can do even more with ``hybrid values'':
paysan's avatar
paysan committed
773
%
lesto's avatar
lesto committed
774
\index{A!AND|(}
paysan's avatar
paysan committed
775
\begin{tip}
paysan's avatar
paysan committed
776
To effect a decision with a numeric outcome, use \forthb{AND}.
paysan's avatar
paysan committed
777
\end{tip}
lesto's avatar
lesto committed
778 779
In the case of a decision that produces either zero or a non-zero ``$n$,''
the traditional phrase
780

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

786
\begin{Code}
787
( ? )  n and
788
\end{Code}
789
Again, the secret is that ``true'' is represented by $-1$ (all ones) in
lesto's avatar
lesto committed
790 791
'83 \Forth{} systems. \forthb{AND}ing ``$n$'' with the flag will either
produce ``$n$'' (all bits intact) or ``$0$'' (all bits cleared).
792 793 794

To restate with an example:

795
\begin{Code}
796
( ? )  IF  200  ELSE  0  THEN
797
\end{Code}
798 799
is the same as

800
\begin{Code}
801
( ? )  200 and
802
\end{Code}
803 804
Take a look at this example:

805
\begin{Code}
806
n  a b <  IF  45 +  THEN
807
\end{Code}
lesto's avatar
lesto committed
808 809 810 811 812
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:
813

814
\begin{Code}
815
n  a b <  45 and  +
816
\end{Code}
817
\begin{interview}
paysan's avatar
paysan committed
818
\person{Moore}:\index{M!Moore, Charles|(}
paysan's avatar
paysan committed
819
\begin{tfquot}
lesto's avatar
lesto committed
820 821 822 823
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.
824 825 826 827 828 829 830 831

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

832
\begin{Code}[commandchars=\&\{\}]
833 834
x = 0 for t < 0
x = 1 for t &(&ge&) 0
835
\end{Code}
836
This would be equivalent to
837
\begin{Code}
838
t  0<  1 and
839
\end{Code}
840
as a single expression, not a piece-wise expression.
841
\end{tfquot}\index{M!Moore, Charles|)}
paysan's avatar
paysan committed
842
\end{interview}%%
lesto's avatar
lesto committed
843
\index{A!AND|)}
lesto's avatar
lesto committed
844

845 846
I call these flags ``hybrid values'' because they are booleans (truth
values) being applied as data (numeric values). Also, I don't know what
paysan's avatar
paysan committed
847
else to call them.%
lesto's avatar
lesto committed
848
\index{H!Hybrid values|)}
849

lesto's avatar
lesto committed
850
We can eliminate numeric \forth{ELSE} clauses as well (where both results
lesto's avatar
lesto committed
851 852
are non-zero), by factoring out the difference between the two results.
For instance,
853

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

859
\begin{Code}
860
: STEPPERS   150  'TESTING? @  1 and +  load ;
861
\end{Code}
862
This approach works here because conceptually we want to either load
paysan's avatar
paysan committed
863 864
Screen 150, or if testing, the next screen past it.%
\index{C!Calculations|)}%
lesto's avatar
lesto committed
865
\index{C!Control structure minimization!calculating results|)}
866

paysan's avatar
paysan committed
867
\section{A Note on Tricks}%
lesto's avatar
lesto committed
868
\index{T!Tricks|(}%
lesto's avatar
lesto committed
869
\index{C!Control structure minimization!tricks|(}
870

paysan's avatar
paysan committed
871
This sort of approach is often labeled a ``trick.'' In the computing
paysan's avatar
paysan committed
872
industry at large, tricks have a bad reputation.
873 874 875 876 877 878 879 880 881 882 883 884 885 886 887 888 889 890

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
paysan's avatar
paysan committed
891
conditionals with \forth{AND}, once this technique becomes part of every
lesto's avatar
lesto committed
892 893 894 895 896 897
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|)}%
898

paysan's avatar
paysan committed
899
\begin{tip}
paysan's avatar
paysan committed
900
Use \forthb{MIN} and \forthb{MAX} for clipping.
lesto's avatar
lesto committed
901 902
\index{M!MAX}%
\index{M!MIN}%
paysan's avatar
paysan committed
903
\end{tip}
paysan's avatar
paysan committed
904
Suppose we want to decrement the contents of the variable \forth{VALUE}, but
905 906
we don't want the value to go below zero:

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

912
\begin{Code}
913
Value @  1-  0 max  Value !
914
\end{Code}
paysan's avatar
paysan committed
915
In this case the conditional is factored within the word \forthb{MAX}.
916

paysan's avatar
paysan committed
917 918
\subsection{Using Decision Tables}%
\index{D!Decision table|(}%
lesto's avatar
lesto committed
919
\index{C!Control structure minimization!decision tables|(}
920

paysan's avatar
paysan committed
921
\begin{tip}
922
Use decision tables.
paysan's avatar
paysan committed
923
\end{tip}
924
We introduced these in \Chap{2}. A decision table is a structure that
925 926 927
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
lesto's avatar
lesto committed
928 929 930
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.
931 932 933 934 935

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

\subsubsection{One-Dimensional Data Table}
lesto's avatar
lesto committed
936
\index{O!One-dimensional data table|(}
937 938

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

paysan's avatar
paysan committed
942
Let's construct the word \forth{SPEED-LIMIT}, which returns the speed
lesto's avatar
lesto committed
943 944
limit depending on the current state.
Using \forthb{IF }\forthb{THEN} we would write:
945

946
\begin{Code}
947 948
: SPEED-LIMIT  ( -- speed-limit)
     'FREEWAY? @  IF  55  ELSE  25  THEN ;
949
\end{Code}
lesto's avatar
lesto committed
950 951
We might eliminate the \forthb{IF }\forthb{THEN} by using a hybrid value
with \forthb{AND}:
952

953
\begin{Code}
954
: SPEED-LIMIT   25  'FREEWAY? @  30 and + ;
955
\end{Code}
956 957 958 959 960 961
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:

962
\begin{Code}
963
Create LIMITS   25 ,  55 ,
964
\end{Code}
paysan's avatar
paysan committed
965
The word \forth{SPEED-LIMIT?} now must apply the boolean to offset into
966 967
the data table:

968
\begin{Code}
969
: SPEED-LIMIT  ( -- speed-limit)
970
     LIMITS  'FREEWAY? @  2 and  +  @ ;
971
\end{Code}
lesto's avatar
lesto committed
972 973
Have we gained anything over the \forthb{IF }\forthb{THEN} approach?
Probably not, with so simple a problem.
974 975 976 977 978 979

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

980
\begin{Code}
981
Create #LANES   4 ,  10 ,
982
\end{Code}
983 984 985
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:

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

992
\begin{Code}
993 994
: ROAD  ( for-freeway for-city ) Create , ,
     DOES> ( -- data )  'FREEWAY? @  2 and  +  @ ;
995 996
55 25 ROAD SPEED-LIMIT?
10  4 ROAD #LANES?
997
\end{Code}
998
Another example of the one-dimensional data table is the ``superstring''
paysan's avatar
paysan committed
999
(\emph{Starting \Forth{}}, Chapter Ten).
lesto's avatar
lesto committed
1000
\index{O!One-dimensional data table|)}
1001

1002 1003
\subsubsection{Two-Dimensional Data Table}%
\index{T!Two-dimensional data table|(}%
paysan's avatar
paysan committed
1004
\program{phone4}
1005
In \Chap{2} we presented a phone-rate problem. \Fig{fig8-4} gives one
1006 1007
solution to the problem, using a two-dimensional data structure.

paysan's avatar
paysan committed
1008
\begin{figure*}[bbbt]
paysan's avatar
paysan committed
1009
\verbfig{fig8-4}{A solution to the phone rate problem.}
paysan's avatar
paysan committed
1010
\begin{Screen}
paysan's avatar
paysan committed
1011
\ Telephone rates                                       03/30/84
1012 1013 1014 1015
Create FULL     30 , 20 , 12 ,
Create LOWER    22 , 15 , 10 ,
Create LOWEST   12 ,  9 ,  6 ,
Variable RATE   \ points to FULL, LOWER or LOWEST
1016 1017
                \ depending on time of day
FULL RATE !  \ for instance
1018
: CHARGE   ( o -- ) Create ,
1019
   DOES>  ( -- rate )  @  RATE @ +  @ ;
1020
0 CHARGE 1MINUTE   \ rate for first minute
1021 1022
2 CHARGE +MINUTES  \ rate for each additional minute
4 CHARGE /MILES    \ rate per each 100 miles
paysan's avatar
paysan committed
1023
\end{Screen}
1024

paysan's avatar
paysan committed
1025
\begin{Screen}
paysan's avatar
paysan committed
1026
\ Telephone rates                                       03/30/84
1027 1028
Variable OPERATOR?  \ 90 if operator assisted; else 0
Variable #MILES  \ hundreds of miles
1029 1030 1031 1032 1033 1034 1035
: ?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 + ;
paysan's avatar
paysan committed
1036
\end{Screen}
paysan's avatar
paysan committed
1037
\end{figure*}
paysan's avatar
paysan committed
1038 1039 1040 1041 1042 1043 1044 1045 1046 1047 1048 1049 1050 1051 1052 1053 1054 1055

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

paysan's avatar
paysan committed
1056
The current charge, either first minute, additional minute, or per mile,
1057 1058
is expressed as an offset into the table (0, 2, or 4).

lesto's avatar
lesto committed
1059 1060
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
1061
approach eliminates the need for a multiplication that would otherwise be
lesto's avatar
lesto committed
1062
needed to implement a two-dimensional structure. The multiplication can be
1063 1064
prohibitively slow in certain cases.%
\index{T!Two-dimensional data table|)}%
paysan's avatar
paysan committed
1065
\program{phone5}
1066

1067 1068
\subsubsection{Two-Dimensional Decision Table}%
\index{T!Two-dimensional decision table|(}%
paysan's avatar
paysan committed
1069
\program{editor4}
1070

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

paysan's avatar
paysan committed
1074
In \Fig{fig8-5} we're constructing a table of functions to be performed
1075 1076 1077 1078 1079 1080
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

1081
\begin{Code}
1082
NORMAL MODE# !
1083
\end{Code}
1084 1085
we'll go into Normal Mode.

1086
\begin{Code}
1087
INSERTING MODE# !
1088
\end{Code}
1089 1090
enters Inserting Mode.

paysan's avatar
paysan committed
1091
The next screen constructs the function table, called \forth{FUNCTIONS}.
1092 1093 1094 1095 1096 1097
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.

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

lesto's avatar
lesto committed
1104 1105 1106 1107
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
1108

1109
\begin{Code}
1110
@ execute
1111
\end{Code}
paysan's avatar
paysan committed
1112
will perform the routine (or \forthb{@EXECUTE} if you have it).
1113

lesto's avatar
lesto committed
1114
In fig-\Forth{}, change the definition of \forth{IS} to:
1115

1116
\begin{Code}
1117
: IS   [compile] '  CFA , ;
1118
\end{Code}
paysan's avatar
paysan committed
1119
\begin{figure*}[tttp]
paysan's avatar
paysan committed
1120 1121 1122 1123
\verbfig{fig8-5}{Implementation of the Tiny Editor.}
\setcounter{screen}{30}
\begin{Screen}
\ Tiny Editor
1124 1125 1126 1127
2 Constant NORMAL     \ offset in FUNCTIONS
4 Constant INSERTING  \        "
6 Constant /KEY       \ bytes in table for each key
Variable MODE#        \ current offset into table
paysan's avatar
paysan committed
1128 1129 1130 1131
NORMAL MODE# !
: INSERT-OFF   NORMAL    MODE# ! ;
: INSERT-ON    INSERTING MODE# ! ;

1132 1133
Variable ESCAPE?      \ t=time-to-leave-loop
: ESCAPE  true ESCAPE? ! ;
paysan's avatar
paysan committed
1134 1135 1136 1137 1138





paysan's avatar
paysan committed
1139 1140 1141 1142
\end{Screen}
\begin{Screen}
\ Tiny Editor             function table             07/29/83
: IS   ' , ;  \   function   ( -- )    ( for '83 standard)
1143
Create FUNCTIONS
paysan's avatar
paysan committed
1144 1145
\ keys                  normal mode        insert mode
 4 ,  ( ctrl-D)         IS DELETE          IS INSERT-OFF
paysan's avatar
paysan committed
1146
 9 ,  ( ctrl-I)         IS INSERT-ON       IS INSERT-OFF
paysan's avatar
paysan committed
1147 1148 1149 1150
 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
1151 1152
 0 ,  ( no match)       IS OVERWRITE       IS insert
here /KEY -  Constant 'NOMATCH  \ adr of no-match key
paysan's avatar
paysan committed
1153 1154 1155 1156




paysan's avatar
paysan committed
1157 1158 1159
\end{Screen}
\begin{Screen}
\ Tiny Editor cont'd                                 07/29/83
1160
Variable MATCHED
paysan's avatar
paysan committed
1161
: 'FUNCTION  ( key -- adr-of-match )  'NOMATCH  MATCHED !
1162 1163
   'NOMATCH FUNCTIONS DO  dup  i @ =  IF
     i MATCHED !  LEAVE  THEN  /KEY +LOOP  drop
paysan's avatar
paysan committed
1164
    MATCHED @ ;
1165 1166
: ACTION  ( key -- )  'FUNCTION  MODE# @ +  @ execute ;
: GO   false ESCAPE? !  BEGIN  key ACTION  ESCAPE? @ UNTIL ;
paysan's avatar
paysan committed
1167 1168 1169 1170 1171 1172 1173 1174








paysan's avatar
paysan committed
1175 1176
\end{Screen}
\end{figure*}
1177
In 79-Standard \Forth{}s, use:
1178
\begin{Code}
1179
: IS   [compile] '  , ;
1180
\end{Code}
1181 1182
We've also used non-redundancy at compile time in the definition just
below the function table:
1183
\begin{Code}
1184
here /KEY -  Constant 'NOMATCH  \  adr of no-match key
1185
\end{Code}
1186
We're making a constant out of the last row in the function table. (At the
lesto's avatar
lesto committed
1187 1188 1189
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:
1190
\begin{Code}
1191 1192 1193
FUNCTIONS  ( adr of beginning of function table )
'NOMATCH   ( adr of "no-match" row; these are the
             routines for any key not in the table)
1194
\end{Code}
paysan's avatar
paysan committed
1195
We use these names to supply the addresses passed to \forthb{DO}:
1196
\begin{Code}
1197
'NOMATCH FUNCTION DO
1198
\end{Code}
1199 1200 1201 1202 1203
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.

paysan's avatar
paysan committed
1204
Similarly the constant \forth{/KEY} hides information about the number of
1205 1206
columns in the table.

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

1221
\subsection{Decision Tables for Speed}
1222 1223 1224 1225 1226 1227 1228

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:

1229
\begin{Code}
1230 1231
Create TWOS
   1 c,  2 c,  4 c,  8 c,  16 c,  32 c,
1232
: 2**  ( n -- 2-to-the-n)
1233
   TWOS +  c@ ;
1234
\end{Code}
paysan's avatar
paysan committed
1235
Instead of computing the answer by multiplying two times itself ``$n$''
1236 1237 1238 1239 1240
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.

1241
\begin{interview}
paysan's avatar
paysan committed
1242
\person{Moore}\index{M!Moore, Charles|(} provides another example:
paysan's avatar
paysan committed
1243
\begin{tfquot}
1244 1245 1246 1247 1248 1249 1250 1251
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.