[11] [fp#] [7] This note provides methods for constructing deterministic and nondeterministic finite state automata in Forth. The “best” Method produces a one-to-one relation between the definition and the state table of the automaton. An important feature of the Technique is the absence of (slow) nested IF clauses.
[11] Introduction
Certain programming problems are difficult to solve procedurally even using structured code, but simple to solve using abstract finite state machines (FSMs) [1]. For example, a compiler must distinguish a text string representing – say – a floating point number, from an algebraic expression that might well contain similar characters in similar order. Or a machine controller must select responses to pre-determined inputs that occur in random order.
Such problems are interesting because a program that responds to indefinite input is closer to a “thinking machine” than a mere sequential program. Thus, a string that represents a floating point number is defined by a set of rules; it has neither a definite length nor do the symbols appear in a definite order. Worse, more than one form for the same number may be permissible-user-friendliness demands a certain flexibility of format. [11] Although generic pattern recognition can be implemented through logical expressions (ie by concatenating sufficiently many
IF s,
ELSE [ 2 , ] s and THEN s) the resulting code is generally hard to read, debug, or modify. Worse, this approach is anything but structured, no matter how "prettily" the code is laid out: indentation can only do so much. And programs consisting mainly of logical expressions can be slow because many processors dump their pipelines upon branching [2]. These defects of the nested -
IF
approach are attested by the profusion of commercial tools to overcome them: Stirling Castle’s Logic Gem (that translates and simplifies logical expressions), Matrix Software’s Matrix Layout (that translates a tabular representation of a FSM into one of several languages such as BASIC, Modula-2, Pascal or C), or AYECO, Inc.’s COMPEDITOR (that performs a similar translation). [These CASE tools were available at least as recently as 1993 from TheProgrammer’s Shop and other developer-oriented softwarediscounters.] [11] Forth is a particularly well-structured language that encourages natural, readable ways to generate FSMs. This note describes several high-level Forth implementations. Finite state machines have been previously discussed in this journal [3], [4]. The present approach improves on prior methods. [11] A Simple Example
Consider the task of accepting numerical input from the keyboard. An unfriendly program lets the user enter the entire number before informing him that he typed two decimal points after the first digit. A friendly program, by contrast, refuses to recognize or display illegal characters. It waits instead for a legal character or carriage return (signifying the end of input). It permits backtracking, allowing erasure of incorrect input.
To keep the example small, our number input routine allows signed decimal numbers without power-of – (exponents) fixed-point, in FORTRAN parlance). Decimal points, numerals and leading minus signs are legal, but no other ASCII characters (including spaces) will be recognized. Here are some examples of legal numbers: [11] 0. , , 1. 45, -1. , 386, etc.
From these examples we derive the rules: [ 0 , ] Characters other than 0-9, - and. are illegal. [ 0 , ] Numerals 0-9 are legal. [ 0 , ] The first character can be -, 0-9 or a decimal point. [ 0 , ] After the first character, - is illegal. [ 0 , ] After the first decimal point, decimal points are illegal. [ 0 , ]
A traditional procedural approach might look something like VARIABLE PREVIOUS.MINUS? history semaphores
VARIABLE PREVIOUS.DP? : DIGIT? (c - f) ASCII 0 ASCII 9 WITHIN; tests
: DP? (c - f) ASCII.=; : MINUS? (c - f) ASCII -=; : FIRST.MINUS? MINUS? PREVIOUS.MINUS? @ NOT AND;
: FIRST.DP? DP? PREVIOUS.DP? @ NOT AND;
: LEGAL? (c - f) horrible example DUP DIGIT? IF DROP TRUE DUP PREVIOUS.MINUS? ! ELSE DUP FIRST.MINUS? IF DROP TRUE DUP PREVIOUS.MINUS? ! ELSE FIRST.DP? IF TRUE DUP PREVIOUS.DP? ! ELSE FALSE THEN THEN THEN; [11] [ 2 , ] The word that does the work is (with apologies to Uderzo and Goscinny, creators of Asterix) [7] : Getafix FALSE PREVIOUS.MINUS? ! FALSE PREVIOUS.DP? ! initialize history semaphores BEGIN KEY DUP CR WHILE LEGAL? IF DUP ECHO APPEND THEN REPEAT; [ 0 , ] What makes this example - whose analogs appear frequently in published code in virtually every language - horrible? Each character whose legality is time-dependent requires a history semaphore. It is therefore difficult to tell by inspection that the word LEGAL? 's logic is actually incorrect, despite the simplification obtained by partial factoring and logical arithmetic.
FORTH Finite State Machines The FSM approach replaces the true / false historical semaphores with one state variable. The rules can be embodied in a state table that expresses the response to each possible input in terms of a concrete action and a state transition, as shown below in Fig. 1. [ 0 , ] Input: OTHER? DIGIT? MINUS? DP? State Does Trans Does Trans Does Trans Does Trans 0 X -> 0 E -> 1 E -> 1 E -> 2 1 X -> 1 E -> 1 X -> 1 E -> 2 2 X -> 2 E -> 2 X -> 2 X -> 2
[ 0 , ] [7] Fig. 1 State table summarizing the rules for fixed point numbers. E stands for "echo" (to the CRT) and X for "do nothing". In the state table, [ 0 , ] The illegality of "other" characters is expressed by the uniform action X and the absence of state transitions.
The special status of the first character is expressed by the fact that all acceptable characters lead to transitions out of the initial state (0):
An initial - sign or digit leads to state 1, where a - sign is unacceptable.
A decimal point always moves the system to state 2, where decimal points are not accepted.
While some FSMs can be synthesized with BEGIN ... WHILE ... REPEAT or BEGIN ... UNTIL loops, keyboard input does not readily lend itself to this approach. We now explore three implementations of the state table of Fig. 1 as Forth FSMs.
Brute-Force FSM [ 0 , ] The "brute-force" FSM uses the Eaker
CASE statement, either in its original form [5] or with a simplified construct from HS / FORTH [6]. HS / FORTH provides defining words CASE:; CASE whose daughter words execute one of several words in their definition, as in CASE: CHOICE WORD0 WORD1 WORD2 WORD3 ... WORDn; CASE 3 CHOICE (executes WORD3) ok [ 2 , ] HS / FORTH's
CASE: ...; CASE
incurs virtually no run time speed penalty relative to executing the words themselves. Now, how do we use CASE: ... ; CASE to implement a FSM? First we need a state variable (initialized to 0) that can assume the values 0, 1 and 2. To test whether an input character is a numeral, minus sign, decimal point or "other", we define [Note: the ANSI Standard [7] renames ASCII to (CHAR) and (UNDER) to
TUCK [ 2 , ] ; also
DDUP (is specific to HS / FORTH and should be replaced with
2DUP for ANSI compliance. WITHIN [ 2 , ] as used here returns TRUE
if a [11] [ 0 , ] VARIABLE mystate mystate 0! : WITHIN (n a b - f) DDUP MIN -ROT MAX ROT UNDER MIN -ROT MAX=;
: DIGIT? (c - f) ASCII 0 ASCII 9 WITHIN; : DP? (c - f) ASCII.=; : MINUS? (c - f) ASCII -=; [ 0 , ] Now, to use CASE:; CASE We define 3 words to handle the tests in each state: : (0) (char -) DUP DIGIT? OVER MINUS? OR IF EMIT 1 mystate! ELSE DUP DP? IF EMIT 2 mystate! ELSE DROP THEN THEN; : (1) (char -) DUP DIGIT? IF EMIT 1 mystate! ELSE DUP MINUS? IF 1 mystate! ELSE DUP DP? IF EMIT 2 mystate! ELSE DROP THEN THEN THEN;
: (2) (char -) DUP DIGIT? IF EMIT ELSE DROP THEN; Finally, we define the words that use the above: CASE: & ltFixed.Pt #> (0) (1) (2); CASE
: Getafix 0 mystate! initialize state BEGIN KEY DUP not CR? WHILE mystate @ & ltFixed.Pt #> execute FSM REPEAT; A Better FSM [11] While the approach outlined above in (Brute Force FSM) (essentially the method described recently by Berrian [8]) both works and produces much clearer code than the binary logic tree of A Simple Example , it nevertheless can be improved. The words (0), (1) and
and [ 2 , ] (2) are inadequately factored (they contain the tests performed on the input character). They also contain IF ... ELSE ... THEN (branches) which we prefer to avoid for the sake of speed and structure). Finally, each FSM must be hand crafted from numerous subsidiary definitions. We want to translate the state table in Fig. 1 into a program. The preceding attempt was too indirect - each state was represented by its own word that did too much. Perhaps we can achieve the desired simplicity by translating more directly. In Forth such translations are most naturally accomplished via defining words. Suppose we visualize the state table as a matrix, whose cells contain action specifications (addresses or execution tokens), whose columns represent input categories, and whose rows are states. If we translate input categories to column numbers, the category and the current value of the state variable (row index) determine a unique cell address, whose content can be fetched and executed. [ 2 , ] Translating the input to a column number factors the tests into a single word that executes once per character. This word should avoid time-wasting branching instructions so all decisions (as to which cell of the table to
EXECUTE will be computed rather than decided. For our test example, the preliminary definitions are [11] [ 0 , ] VARIABLE mystate 0 mystate! : WITHIN (n a b - f) DDUP MIN -ROT MAX ROT TUCK MIN -ROT MAX=;
: DIGIT? (n - f) ASCII 0 ASCII 9 WITHIN; : DP? ASCII.=; : MINUS? ASCII -=; [ 2 , ] and the input translation is carried out by [11] [ 0 , ] : cat-> col # (n - n ') DUP DIGIT? 1 AND digit -> 1 OVER MINUS? 2 AND - -> 2 SWAP DP? 3 AND dp -> 3 ; other -> 0 [ 2 , ] Now we must plan the state-table compiler. In general, we define an action word for each cell of the table that will perform the required action and state change. At compile time the defining word will compile an array of the execution addresses (execution tokens in ANS- Forth parlance [9] of these action words. At run time the child word computes the address of the appropriate matrix cell from the user- supplied column number and the current value of mystate, fetches the execution address from its matrix cell, and EXECUTEs the appropriate action. Since a table can have arbitrarily many columns the number of columns must be supplied at compile time. These requirements lead to the definitions
[ 2 , ] [11] : TUCK COMPILE UNDER; ANS compatibility
: WIDE; NOOP for clarity [ 2 , ] : CELLS COMPILE 2 *; ANS compatibility
: CELL COMPILE 2 ; ANS compatibility
: PERFORM COMPILE @ COMPILE EXECUTE; alias
: FSM: (width -) CREATE,] DOES> (n adr -) TUCK @ mystate @ CELLS CELL (adr ') PERFORM; [ 2 , ] Here CREATE
makes a new header in the dictionary,, stores the top number on the stack in the first cell of the parameter field, and ] switches to compile mode. The run time code computes the address of the cell containing the vector to the desired action, fetches that vector and executes the action. [Note: This simple and elegantimplementation only works with indirect-threaded Forths. An ANS Standardalternative is provided in the Appendix.] [11] Now we apply this powerful new word to our example problem. From Fig. 1 we see that transitions (changes of state) occur only in cells (0,0), (0,1), (0,2), (1,0), and (1,2). These are always associated with
EMIT
( E in the Figure). No change of state accompanies a wrong input and the associated action is to
DROP
the character. There are thus only 2 distinct state-changing actions we need define: : (06) EMIT 1 mystate! ; : (11) EMIT 2 mystate! ; [ 2 , ] Since we must test for 4 conditions on the input character, the state table will be 4 columns wide: [11] [ 0 , ] 4 WIDE FSM: & ltFixed.Pt #> (action # -) other num -. state DROP ( () (10) (06) 0 DROP ( () DROP 11) 1 DROP (10) DROP DROP; 2 [ 2 , ] The word that does the work is [11] [ 0 , ] : Getafix 0 mystate! BEGIN KEY DUP 43 not CR WHILE DUP cat-> col # & ltFixed.Pt #> REPEAT; [ 2 , ] We can immediately test the FSM, as follows: [11] [ 0 , ] FLOAD F: X.1 Loading F: X.1 ok ASCII 3 cat-> col #. 1 ok ASCII 0 cat-> col #. 1 ok ASCII - cat-> col #. 2 ok ASCII. cat-> col #. 3 ok ASCII A cat-> col #. 0 ok : Getafix 0 mystate! BEGIN KEY DUP WHILE DUP cat-> col # & ltFixed.Pt #> REPEAT; ok
[7] Getafix -3. ok Getafix [ 0 , ] (ok)
[ 0 , ] [11] The incorrect input of excess decimal points, incorrect minus signs or non-numeric characters does not show because, as intended, they were dropped without echoing to the screen. An Elegant FSM The defining word FSM: (of) (A Better Example) , while useful, nevertheless has room for improvement. This version hides the state transitions within the act ion words compiled into the child word's cells. A more thoroughly factored approach would explicitly specify transitions next to the actions they follow, within the definitions of each FSM. Definitions will become more readable since each looks just like its state table; that is, our ideal FSM definition will look like 4 WIDE FSM: & ltFixed.Pt #> input: | other? | num? | minus? | dp? | state: --------------------------------------------- (0) DROP 0 EMIT 1 EMIT 1 EMIT 2 (1) DROP 1 EMIT 1 DROP 1 EMIT 2 (2) DROP 2 EMIT 2 DROP 2 DROP 2; [ 2 , ] so we would never need the words
(10)
and
(12) . Fortunately it is not hard to redefine FSM: [ 0 , ] to include the transitions explicitly. We may use
CONSTANT s to effect the state transitions
0 CONSTANT> 0 1 CONSTANT> 1 2 CONSTANT> 2 ............. and modify the run time portion of FSM: accordingly: : FSM: (width -) CREATE,] DOES> (col # -) TUCK @ (- adr col # width) mystate @ 2 CELLS CELL (- offset) DUP CELL PERFORM mystate! PERFORM; [ 2 , ] Note that we have defined the run time code so that the change in state variable precedes the run time action. Sometimes the desired action is an ABORT
and an error message. Changing the state variable first lets us avoid having to write a separate error handler for each cell of the FSM, yet we can tell where the ABORT
took place. If the ABORT were first, the state would not have been updated.
[ 2 , ] The FSM is then defined as [11] [ 0 , ] 4 WIDE FSM: & ltFixed.Pt #> input: | other? | num? | minus? | dp? | state: --------------------------------------------- (0) DROP> 0 EMIT> 1 EMIT> 1 EMIT> 2 (1) DROP> 1 EMIT> 1 DROP> 1 EMIT> 2 (2) DROP> 2 EMIT> 2 DROP> 2 DROP> 2; [ 2 , ] which is clear and readable. Of course one could define the runtime
(DOES>) (portion of) FSM: to avoid the need for extra (CONSTANT) s
(0,> 1, etc. The actual numbers could be stored in the table via [11] [ 0 , ] 4 WIDE FSM: & ltFixed.Pt #> input: | other? | num? | minus? | dp? | state: ----------------------------------------------- ------ (0) DROP [ 0 , ] EMIT [Note: This simple and elegantimplementation only works with indirect-threaded Forths. An ANS Standardalternative is provided in the Appendix.] EMIT [Note: This simple and elegantimplementation only works with indirect-threaded Forths. An ANS Standardalternative is provided in the Appendix.] EMIT [ 2 , ] (1) DROP [ 1 , ] EMIT [Note: This simple and elegantimplementation only works with indirect-threaded Forths. An ANS Standardalternative is provided in the Appendix.] DROP (EMIT) (2) DROP [ 2 , ] EMIT [ 0 , ] DROP [10] DROP [ 2 , ]; [ 2 , ] However, for reasons given in The Best FMS So Far below, it is better to implement the state transition with CONSTANT
s rather than with numeric literals.
The Best FSM So Far Experience using the FSM approach to write programs has motivated two further improvements. First, suppose one needs to nest FSMs, i.e., to compile one into another, or even to> tt> RECURSE. The global variable mystate precludes such finesse. It therfore makes sense to include the state variable for each FSM in its data structure, just as with its
WIDTH . This modification protects the state of a FSM from any accidental interactions at the cost of one more memory cell per FSM, since if the state has no name it cannot be invoked. Second, suppose one or other of the action words is supposed to leave something on the stack, and that, for some reason, it is desirable to alter the state after the action rather than before (this is, in fact, the more natural order of doing things). Since There is no way to know in advance what the stack effect will be, we use the return stack for tempor ary storage, to avoid collisions. The revision is thus : 2 @ COMPILE D @; alias; D @ is ok in ANS
: WIDE 0; :
: FSM: (width 0 -) CREATE,,] DOES> (col # adr -) DUP> R 2 @ (- col # width state) 2 2 CELLS (- offset-to-action) DUP> R (- offset-to-action) PERFORM (?) R> CELL (- offset-to-update) PERFORM (- state ') R>! ; update state The revised keyboard input word of our example is : Getafix 0 '& ltFixed.Pt #>! BEGIN KEY DUP WHILE DUP cat-> col # & ltFixed.pt #> REPEAT; Note that the state variable is initialized to zero because we know it is stored in the first cell in the parameter field of the FSM which can be accessed by the phrase '& ltFixed.Pt #> (or the equivalent in the Forth dialect being used - see Appendix).
Nondeterministic Finite State Machines We are now in a position to explain why defining a CONSTANT to manage the state transitions is better than merely incorporating the next state's number. First, there is no obvious reason why states cannot be named rather than numbered. The Forth outer interpreter itself is a state machine with two states, COMPILE and
INTERPRET
; i.e., names are often clearer than numbers.
The use of a word rather than a number to effect the transition permits a more far-reaching modification. Our code defines a compiler for deterministic FSMs, in which each cell in the table contains a transition to a definite next state. What if we allowed branching to Any of several next states, following a given action? FSMs that can do this are called nondeterministic. Despite the nomenclature, and Despite the misleading descriptions of such FSMs sometimes found in the literature [ 1 , ], there need be nothing random or "guesslike" about the next transition. What permits multiple possibilities is additional information, external to the current state and current input. Here is a simple nondeterministic FSM used in my FORmula TRANslator [11] The problem is to determine whether a piece of text is a proper identifier (that is, the name of a variable, subroutine or function) According to the rules of FORTRAN. An id must begin with a letter, and can be up to seven characters long, with characters that are letters or digits. To accelerate the process of determining whether an ASCII character code represents a letter, digit or "other", we define a decoder (fast table translator):
: TAB: (#bytes -) CREATE HERE OVER ALLOT SWAP 0 FILL DOES> C @; [ 2 , ] and a method to fill it quickly:
: install (col # adr char.n char.1 -) fast fill SWAP 1 SWAP DO DDUP I C! LOOP DDROP; The translation table we need for detecting id's is 386 TAB: [11] 1 '[10] ASCII Z ASCII A install 1 '[10] ASCII z ASCII a install 2 '[10] ASCII 9 ASCII 0 install This follows the F 128 convention that 'returns the pfa. To convert to F or ANS replace () (by '>> BODY . Thus, eg [ 0 , ] [ 2 , ] ASCII R [ 2 , ] 1 ok ASCII s [11] 1 ok ASCII 3 [11] 2 ok ASCII [11] 0 ok to convert to ANSI replace ASCII by CHAR Now how do we embody the id rules in a FSM? Our first attempt might look like [ 2 , ] 3 WIDE FSM: (id) input: | other | letter | digit | state ------------------------------------- (0) NOOP> 8 1> 1 NOOP> 2 (1) NOOP> 8 1> 2 1> 2 (2) NOOP> 8 1> 3 1> 3 (3) NOOP> 8 1> 4 1> 4 (4) NOOP> 8 1> 5 1> 5 (5) NOOP> 8 1> 6 1> 6 (6) NOOP> 8 1> 7 1> 7 (7) NOOP> 8 NOOP> 8 NOOP> 8; stateBODY: : & ltid> ($ end $ beg - f) f=T for id, F else 0 state $ end> $ beg? state To make sure the id is at most 7 characters long we had to provide 8 states. The table is rather repetitious. A simpler alternative uses a VARIABLE [ 2 , ] to count the characters as they come in. The revision is VARIABLE id.len 0 id.len!
: id.len id.len @ 1 id.len! ; increment counter
:> 1? id.len @ 7 (- 1 if id.len 3 WIDE FSM: (id) input: | other | letter | digit | state --------------------------------------- (0) NOOP> 2 id.len> 1 NOOP> 2 (1) NOOP> 2 id.len> 1? id.len> 1? ; : & ltid> ($ end $ beg - f) f=-1 for id, 0 else 0 id.len! 0 state $ end> $ beg? state
[ 0 , ] The resulting FSM is nondeterministic because the word
> 1? induces a transition either to state 1 or to (the terminal) state 2. It has fewer states and consumes less memory despite the extra definitions. Because we have stuck to subroutines for mediating state transitions, going from a definite transition (via a CONSTANT (such as)> 0
or [Note: the ANSI Standard [7]> 1) [fp#] to an indefinite one requires no redefinitions.
The following FSM detects properly formed floating point numbers: [11] [ 0 , ] 386 TAB: [11] decoder for fp # 1 '[fp#] ASCII E ASCII D install 1 '[fp#] ASCII e ASCII d install 2 '[fp#] ASCII 9 ASCII 0 install 3 '[11] ASCII C! 3 '[11] ASCII - C! 4 '[11] ASCII. C! : #err CRT restore normal output . "Not a correctly formed fp #" ABORT; fp # error handler 5 WIDE FSM: (fp #) input: | other | dDeE | digit | or - | dp | state: ----------------------------------------------- -------- (0) NOOP> 6 NOOP> 6 1> 0 NOOP> 6 1> 1 (1) NOOP> 6 1> 2 1> 1 #err> 6 #err> 6 (2) NOOP> 6 #err> 6 NOOP> 4 1> 3 #err> 6 (3) NOOP> 6 #err> 6 1> 4 #err> 6 #err> 6 (4) NOOP> 6 #err> 6 1> 5 #err> 6 #err> 6 (5) NOOP> 6 #err> 6 #err> 6 #err> 6 #err> 6; : skip- DUP C @ ASCII -=-; skip a leading - Environmental dependency: assumes "true" is -1 : & ltfp #> ($ end $ beg - f) 0 state
[ 0 , ] The FSM (fp #) does not count digits in the mantissa, but limits those in the exponent to two or fewer. A nondeterministic version of
(fp #)
reduces the number of states, while counting digits in both the mantissa and exponent of the number: 5 WIDE FSM: (fp #) input: | other | dDeE | digit | or - | dp | state: ----------------------------------------------- -------- (0) NOOP> 4 NOOP> 4 mant> 0? NOOP> 4 1> 1 (1) NOOP> 4? 1> 2 mant> 1? #err> 4 #err> 4 (2) NOOP> 4 #err> 4 exp> 3 1> 3 #err> 4 (3) NOOP> 4 #err> 4 exp> 3? #err> 4 #err> 4; The task of fleshing out the details - specifically, the words
mant, exp,? 1,> 0 ?,> 1? and> 3? - is left as an exercise for the reader.
Acknowledgment
I am grateful to Rick Van Norman and Lloyd Prentice for positive feedback about applications of the FSM compiler in areas as diverse as gas pipeline control and educational computer games.
Appendix Here is a high-level definition of the HS / FORTH
CASE: ...; CASE (albeit it imposes more overhead than HS / FORTH's version) that works in indirect-threaded systems: : CASE: CREATE] DOES> (n -) OVER @ EXECUTE;
:; CASE [fp#]; ; IMMEDIATE (or just use;) However, it will not work with a direct-threaded Forth like F-PC. It fails because what is normally compiled into the body of the definition (by using] to turn on the compiler) in a direct-threaded system is not a list of execution tokens. The simplest alternative (it also works with indirect-threaded systems) factors the compilation function out of
CASE:
: CASE: CREATE;
[11] : | ',; F and ANS version
From these examples we derive the rules: [ 0 , ] Characters other than 0-9, - and. are illegal. [ 0 , ] Numerals 0-9 are legal. [ 0 , ] The first character can be -, 0-9 or a decimal point. [ 0 , ] After the first character, - is illegal. [ 0 , ] After the first decimal point, decimal points are illegal. [ 0 , ]
A traditional procedural approach might look something like VARIABLE PREVIOUS.MINUS? history semaphoresVARIABLE PREVIOUS.DP?: DIGIT? (c - f) ASCII 0 ASCII 9 WITHIN; tests
: DP? (c - f) ASCII.=;: MINUS? (c - f) ASCII -=;
: FIRST.MINUS? MINUS? PREVIOUS.MINUS? @ NOT AND;
: FIRST.DP? DP? PREVIOUS.DP? @ NOT AND;
: LEGAL? (c - f) horrible example DUP DIGIT? IF DROP TRUE DUP PREVIOUS.MINUS? ! ELSE DUP FIRST.MINUS? IF DROP TRUE DUP PREVIOUS.MINUS? ! ELSE FIRST.DP? IF TRUE DUP PREVIOUS.DP? ! ELSE FALSE THEN THEN THEN; [11] [ 2 , ] The word that does the work is (with apologies to Uderzo and Goscinny, creators of Asterix) [7] : Getafix FALSE PREVIOUS.MINUS? ! FALSE PREVIOUS.DP? ! initialize history semaphores BEGIN KEY DUP CR WHILE LEGAL? IF DUP ECHO APPEND THEN REPEAT; [ 0 , ]What makes this example - whose analogs appear frequently in published code in virtually every language - horrible? Each character whose legality is time-dependent requires a history semaphore. It is therefore difficult to tell by inspection that the word LEGAL? 's logic is actually incorrect, despite the simplification obtained by partial factoring and logical arithmetic.incurs virtually no run time speed penalty relative to executing the words themselves. Now, how do we use
FORTH Finite State MachinesThe FSM approach replaces the true / false historical semaphores with one state variable. The rules can be embodied in a state table that expresses the response to each possible input in terms of a concrete action and a state transition, as shown below in Fig. 1. [ 0 , ] Input: OTHER? DIGIT? MINUS? DP? State Does Trans Does Trans Does Trans Does Trans 0 X -> 0 E -> 1 E -> 1 E -> 2 1 X -> 1 E -> 1 X -> 1 E -> 2 2 X -> 2 E -> 2 X -> 2 X -> 2
[ 0 , ] [7] Fig. 1 State table summarizing the rules for fixed point numbers. E stands for "echo" (to the CRT) and X for "do nothing".In the state table, [ 0 , ] The illegality of "other" characters is expressed by the uniform action X and the absence of state transitions.The special status of the first character is expressed by the fact that all acceptable characters lead to transitions out of the initial state (0):
An initial - sign or digit leads to state 1, where a - sign is unacceptable.
A decimal point always moves the system to state 2, where decimal points are not accepted.
While some FSMs can be synthesized with BEGIN ... WHILE ... REPEAT or
BEGIN ... UNTIL loops, keyboard input does not readily lend itself to this approach. We now explore three implementations of the state table of Fig. 1 as Forth FSMs.
Brute-Force FSM [ 0 , ] The "brute-force" FSM uses the EakerCASE statement, either in its original form [5] or with a simplified construct from HS / FORTH [6]. HS / FORTH provides defining words CASE:; CASE whose daughter words execute one of several words in their definition, as in CASE: CHOICE WORD0 WORD1 WORD2 WORD3 ... WORDn; CASE 3 CHOICE (executes WORD3) ok [ 2 , ] HS / FORTH's
CASE: ...; CASE
CASE: ... ; CASE to implement a FSM? First we need a state variable (initialized to 0) that can assume the values 0, 1 and 2. To test whether an input character is a numeral, minus sign, decimal point or "other", we define [Note: the ANSI Standard [7] renames ASCII to (CHAR) and (UNDER) to
TUCK [ 2 , ] ; also
DDUP (is specific to HS / FORTH and should be replaced with
2DUP for ANSI compliance.WITHIN [ 2 , ] as used here returns TRUE
if a [11] [ 0 , ] VARIABLE mystate mystate 0! : WITHIN (n a b - f) DDUP MIN -ROT MAX ROT UNDER MIN -ROT MAX=;
: DIGIT? (c - f) ASCII 0 ASCII 9 WITHIN;: DP? (c - f) ASCII.=;: MINUS? (c - f) ASCII -=;
[ 0 , ] Now, to useCASE:; CASE We define 3 words to handle the tests in each state: : (0) (char -) DUP DIGIT? OVER MINUS? OR IF EMIT 1 mystate! ELSE DUP DP? IF EMIT 2 mystate! ELSE DROP THEN THEN;
0 CONSTANT> 0 1 CONSTANT> 1 2 CONSTANT> 2 ............. and modify the run time portion of FSM: accordingly: : FSM: (width -) CREATE,] DOES> (col # -) TUCK @ (- adr col # width) mystate @ 2 CELLS CELL (- offset) DUP CELL PERFORM mystate! PERFORM; [ 2 , ] Note that we have defined the run time code so that the change in state variable precedes the run time action. Sometimes the desired action is an: (1) (char -) DUP DIGIT? IF EMIT 1 mystate! ELSE DUP MINUS? IF 1 mystate! ELSE DUP DP? IF EMIT 2 mystate! ELSE DROP THEN THEN THEN;
: (2) (char -) DUP DIGIT? IF EMIT ELSE DROP THEN; Finally, we define the words that use the above: CASE: & ltFixed.Pt #> (0) (1) (2); CASE: Getafix 0 mystate! initialize state BEGIN KEY DUP not CR? WHILE mystate @ & ltFixed.Pt #> execute FSM REPEAT;A Better FSM [11] While the approach outlined above in (Brute Force FSM) (essentially the method described recently by Berrian [8]) both works and produces much clearer code than the binary logic tree of A Simple Example , it nevertheless can be improved. The words (0), (1) and
and [ 2 , ] (2) are inadequately factored (they contain the tests performed on the input character). They also contain IF ... ELSE ... THEN (branches) which we prefer to avoid for the sake of speed and structure). Finally, each FSM must be hand crafted from numerous subsidiary definitions.
We want to translate the state table in Fig. 1 into a program. The preceding attempt was too indirect - each state was represented by its own word that did too much. Perhaps we can achieve the desired simplicity by translating more directly. In Forth such translations are most naturally accomplished via defining words. Suppose we visualize the state table as a matrix, whose cells contain action specifications (addresses or execution tokens), whose columns represent input categories, and whose rows are states. If we translate input categories to column numbers, the category and the current value of the state variable (row index) determine a unique cell address, whose content can be fetched and executed. [ 2 , ] Translating the input to a column number factors the tests into a single word that executes once per character. This word should avoid time-wasting branching instructions so all decisions (as to which cell of the table to
EXECUTE will be computed rather than decided. For our test example, the preliminary definitions are [11] [ 0 , ] VARIABLE mystate 0 mystate! : WITHIN (n a b - f) DDUP MIN -ROT MAX ROT TUCK MIN -ROT MAX=;
(12) . Fortunately it is not hard to redefine
: DIGIT? (n - f) ASCII 0 ASCII 9 WITHIN;: DP? ASCII.=;: MINUS? ASCII -=; [ 2 , ] and the input translation is carried out by [11] [ 0 , ] : cat-> col # (n - n ') DUP DIGIT? 1 AND digit -> 1 OVER MINUS? 2 AND - -> 2 SWAP DP? 3 AND dp -> 3 ; other -> 0 [ 2 , ] Now we must plan the state-table compiler. In general, we define an action word for each cell of the table that will perform the required action and state change. At compile time the defining word will compile an array of the execution addresses (execution tokens in ANS- Forth parlance [9] of these action words. At run time the child word computes the address of the appropriate matrix cell from the user- supplied column number and the current value of mystate, fetches the execution address from its matrix cell, and EXECUTEs the appropriate action. Since a table can have arbitrarily many columns the number of columns must be supplied at compile time. These requirements lead to the definitions
[ 2 , ] [11] : TUCK COMPILE UNDER; ANS compatibility
: WIDE; NOOP for clarity[ 2 , ] : CELLS COMPILE 2 *; ANS compatibility: CELL COMPILE 2 ; ANS compatibility: PERFORM COMPILE @ COMPILE EXECUTE; alias
: FSM: (width -) CREATE,] DOES> (n adr -) TUCK @ mystate @ CELLS CELL (adr ') PERFORM; [ 2 , ] HereCREATE
makes a new header in the dictionary,, stores the top number on the stack in the first cell of the parameter field, and] switches to compile mode. The run time code computes the address of the cell containing the vector to the desired action, fetches that vector and executes the action. [Note: This simple and elegantimplementation only works with indirect-threaded Forths. An ANS Standardalternative is provided in the Appendix.] [11] Now we apply this powerful new word to our example problem. From Fig. 1 we see that transitions (changes of state) occur only in cells (0,0), (0,1), (0,2), (1,0), and (1,2). These are always associated with
EMIT
(E in the Figure). No change of state accompanies a wrong input and the associated action is to
DROP
the character. There are thus only 2 distinct state-changing actions we need define: : (06) EMIT 1 mystate! ; : (11) EMIT 2 mystate! ; [ 2 , ] Since we must test for 4 conditions on the input character, the state table will be 4 columns wide: [11] [ 0 , ] 4 WIDE FSM: & ltFixed.Pt #> (action # -) other num -. state DROP ( () (10) (06) 0 DROP ( () DROP 11) 1 DROP (10) DROP DROP; 2 [ 2 , ] The word that does the work is [11] [ 0 , ] : Getafix 0 mystate! BEGIN KEY DUP 43 not CR WHILE DUP cat-> col # & ltFixed.Pt #> REPEAT; [ 2 , ] We can immediately test the FSM, as follows: [11] [ 0 , ] FLOAD F: X.1 Loading F: X.1 ok ASCII 3 cat-> col #. 1 ok ASCII 0 cat-> col #. 1 ok ASCII - cat-> col #. 2 ok ASCII. cat-> col #. 3 ok ASCII A cat-> col #. 0 ok : Getafix 0 mystate! BEGIN KEY DUP WHILE DUP cat-> col # & ltFixed.Pt #> REPEAT; ok
[7] Getafix -3. okGetafix [ 0 , ] (ok)
[ 0 , ] [11] The incorrect input of excess decimal points, incorrect minus signs or non-numeric characters does not show because, as intended, they were dropped without echoing to the screen. An Elegant FSMThe defining wordFSM: (of) (A Better Example) , while useful, nevertheless has room for improvement. This version hides the state transitions within the act ion words compiled into the child word's cells. A more thoroughly factored approach would explicitly specify transitions next to the actions they follow, within the definitions of each FSM. Definitions will become more readable since each looks just like its state table; that is, our ideal FSM definition will look like 4 WIDE FSM: & ltFixed.Pt #> input: | other? | num? | minus? | dp? | state: --------------------------------------------- (0) DROP 0 EMIT 1 EMIT 1 EMIT 2 (1) DROP 1 EMIT 1 DROP 1 EMIT 2 (2) DROP 2 EMIT 2 DROP 2 DROP 2; [ 2 , ] so we would never need the words
(10)
andFSM: [ 0 , ] to include the transitions explicitly. We may use
CONSTANT s to effect the state transitions
ABORT
and an error message. Changing the state variable first lets us avoid having to write a separate error handler for each cell of the FSM, yet we can tell where theABORT
took place. If theABORT were first, the state would not have been updated.
[ 2 , ] The FSM is then defined as [11] [ 0 , ] 4 WIDE FSM: & ltFixed.Pt #> input: | other? | num? | minus? | dp? | state: --------------------------------------------- (0) DROP> 0 EMIT> 1 EMIT> 1 EMIT> 2 (1) DROP> 1 EMIT> 1 DROP> 1 EMIT> 2 (2) DROP> 2 EMIT> 2 DROP> 2 DROP> 2; [ 2 , ] which is clear and readable. Of course one could define the runtime
(DOES>) (portion of) FSM: to avoid the need for extra (CONSTANT) s
(0,> 1, etc. The actual numbers could be stored in the table via [11] [ 0 , ] 4 WIDE FSM: & ltFixed.Pt #> input: | other? | num? | minus? | dp? | state: ----------------------------------------------- ------ (0) DROP [ 0 , ] EMIT [Note: This simple and elegantimplementation only works with indirect-threaded Forths. An ANS Standardalternative is provided in the Appendix.] EMIT [Note: This simple and elegantimplementation only works with indirect-threaded Forths. An ANS Standardalternative is provided in the Appendix.] EMIT [ 2 , ] (1) DROP [ 1 , ] EMIT [Note: This simple and elegantimplementation only works with indirect-threaded Forths. An ANS Standardalternative is provided in the Appendix.] DROP (EMIT) (2) DROP [ 2 , ] EMIT [ 0 , ] DROP [10] DROP [ 2 , ]; [ 2 , ] However, for reasons given in The Best FMS So Far
s rather than with numeric literals.below, it is better to implement the state transition with CONSTANT
The Best FSM So Far Experience using the FSM approach to write programs has motivated two further improvements. First, suppose one needs to nest FSMs, i.e., to compile one into another, or even to> tt> RECURSE. The global variable mystate precludes such finesse. It therfore makes sense to include the state variable for each FSM in its data structure, just as with itsWIDTH . This modification protects the state of a FSM from any accidental interactions at the cost of one more memory cell per FSM, since if the state has no name it cannot be invoked. Second, suppose one or other of the action words is supposed to leave something on the stack, and that, for some reason, it is desirable to alter the state after the action rather than before (this is, in fact, the more natural order of doing things). Since There is no way to know in advance what the stack effect will be, we use the return stack for tempor ary storage, to avoid collisions. The revision is thus : 2 @ COMPILE D @; alias; D @ is ok in ANS
: WIDE 0;:
: FSM: (width 0 -) CREATE,,] DOES> (col # adr -) DUP> R 2 @ (- col # width state) 2 2 CELLS (- offset-to-action) DUP> R (- offset-to-action) PERFORM (?) R> CELL (- offset-to-update) PERFORM (- state ') R>! ; update state The revised keyboard input word of our example is : Getafix 0 '& ltFixed.Pt #>! BEGIN KEY DUP WHILE DUP cat-> col # & ltFixed.pt #> REPEAT; Note that the state variable is initialized to zero because we know it is stored in the first cell in the parameter field of the FSM which can be accessed by the phrase '& ltFixed.Pt #> (or the equivalent in the Forth dialect being used - see Appendix).
Nondeterministic Finite State Machines We are now in a position to explain why defining a CONSTANT to manage the state transitions is better than merely incorporating the next state's number. First, there is no obvious reason why states cannot be named rather than numbered. The Forth outer interpreter itself is a state machine with two states,COMPILE and
INTERPRET
; i.e., names are often clearer than numbers.
The use of a word rather than a number to effect the transition permits a more far-reaching modification. Our code defines a compiler for deterministic FSMs, in which each cell in the table contains a transition to a definite next state. What if we allowed branching to Any of several next states, following a given action? FSMs that can do this are called nondeterministic. Despite the nomenclature, and Despite the misleading descriptions of such FSMs sometimes found in the literature [ 1 , ], there need be nothing random or "guesslike" about the next transition. What permits multiple possibilities is additional information, external to the current state and current input.
Here is a simple nondeterministic FSM used in my FORmula TRANslator [11] The problem is to determine whether a piece of text is a proper identifier (that is, the name of a variable, subroutine or function) According to the rules of FORTRAN. An id must begin with a letter, and can be up to seven characters long, with characters that are letters or digits. To accelerate the process of determining whether an ASCII character code represents a letter, digit or "other", we define a decoder (fast table translator):
: TAB: (#bytes -) CREATE HERE OVER ALLOT SWAP 0 FILL DOES> C @; [ 2 , ] and a method to fill it quickly:: install (col # adr char.n char.1 -) fast fill SWAP 1 SWAP DO DDUP I C! LOOP DDROP; The translation table we need for detecting id's is 386 TAB: [11] 1 '[10] ASCII Z ASCII A install 1 '[10] ASCII z ASCII a install 2 '[10] ASCII 9 ASCII 0 install This follows the F 128 convention that 'returns the pfa. To convert
to F or ANS replace () (by '>> BODY .
Thus, eg [ 0 , ] [ 2 , ] ASCII R [ 2 , ] 1 ok ASCII s [11] 1 ok ASCII 3 [11] 2 ok ASCII [11] 0 ok to convert to ANSI replace ASCII by CHAR Now how do we embody the id rules in a FSM? Our first attempt might look like
[ 2 , ] 3 WIDE FSM: (id) input: | other | letter | digit | state ------------------------------------- (0) NOOP> 8 1> 1 NOOP> 2 (1) NOOP> 8 1> 2 1> 2 (2) NOOP> 8 1> 3 1> 3 (3) NOOP> 8 1> 4 1> 4 (4) NOOP> 8 1> 5 1> 5 (5) NOOP> 8 1> 6 1> 6 (6) NOOP> 8 1> 7 1> 7 (7) NOOP> 8 NOOP> 8 NOOP> 8; stateBODY: : & ltid> ($ end $ beg - f) f=T for id, F else 0 state $ end> $ beg? state To make sure the id is at most 7 characters long we had to provide 8 states. The table is rather repetitious. A simpler alternative uses aVARIABLE [ 2 , ] to count the characters as they come in. The revision is VARIABLE id.len 0 id.len!
: id.len id.len @ 1 id.len! ; increment counter:> 1? id.len @ 7 (- 1 if id.len 3 WIDE FSM: (id) input: | other | letter | digit | state --------------------------------------- (0) NOOP> 2 id.len> 1 NOOP> 2 (1) NOOP> 2 id.len> 1? id.len> 1? ;: & ltid> ($ end $ beg - f) f=-1 for id, 0 else 0 id.len! 0 state $ end> $ beg? state
[ 0 , ] The resulting FSM is nondeterministic because the word
> 1? induces a transition either to state 1 or to (the terminal) state 2. It has fewer states and consumes less memory despite the extra definitions. Because we have stuck to subroutines for mediating state transitions, going from a definite transition (via a CONSTANT (such as)> 0
or [Note: the ANSI Standard [7]> 1) [fp#] to an indefinite one requires no redefinitions.
The following FSM detects properly formed floating point numbers: [11] [ 0 , ] 386 TAB: [11] decoder for fp # 1 '[fp#] ASCII E ASCII D install 1 '[fp#] ASCII e ASCII d install 2 '[fp#] ASCII 9 ASCII 0 install 3 '[11] ASCII C! 3 '[11] ASCII - C! 4 '[11] ASCII. C! : #err CRT restore normal output . "Not a correctly formed fp #" ABORT; fp # error handler 5 WIDE FSM: (fp #) input: | other | dDeE | digit | or - | dp | state: ----------------------------------------------- -------- (0) NOOP> 6 NOOP> 6 1> 0 NOOP> 6 1> 1 (1) NOOP> 6 1> 2 1> 1 #err> 6 #err> 6 (2) NOOP> 6 #err> 6 NOOP> 4 1> 3 #err> 6 (3) NOOP> 6 #err> 6 1> 4 #err> 6 #err> 6 (4) NOOP> 6 #err> 6 1> 5 #err> 6 #err> 6 (5) NOOP> 6 #err> 6 #err> 6 #err> 6 #err> 6; : skip- DUP C @ ASCII -=-; skip a leading - Environmental dependency: assumes "true" is -1 : & ltfp #> ($ end $ beg - f) 0 state
[ 0 , ] The FSM (fp #) does not count digits in the mantissa, but limits those in the exponent to two or fewer. A nondeterministic version of
(fp #)
reduces the number of states, while counting digits in both the mantissa and exponent of the number:5 WIDE FSM: (fp #) input: | other | dDeE | digit | or - | dp | state: ----------------------------------------------- -------- (0) NOOP> 4 NOOP> 4 mant> 0? NOOP> 4 1> 1 (1) NOOP> 4? 1> 2 mant> 1? #err> 4 #err> 4 (2) NOOP> 4 #err> 4 exp> 3 1> 3 #err> 4 (3) NOOP> 4 #err> 4 exp> 3? #err> 4 #err> 4; The task of fleshing out the details - specifically, the words
mant, exp,? 1,> 0 ?,> 1? and> 3? - is left as an exercise for the reader.
AcknowledgmentI am grateful to Rick Van Norman and Lloyd Prentice for positive feedback about applications of the FSM compiler in areas as diverse as gas pipeline control and educational computer games.
Appendix Here is a high-level definition of the HS / FORTHCASE: ...; CASE (albeit it imposes more overhead than HS / FORTH's version) that works in indirect-threaded systems: : CASE: CREATE] DOES> (n -) OVER @ EXECUTE;
:; CASE [fp#]; ; IMMEDIATE (or just use;) However, it will not work with a direct-threaded Forth like F-PC. It fails because what is normally compiled into the body of the definition (by using] to turn on the compiler) in a direct-threaded system is not a list of execution tokens. The simplest alternative (it also works with indirect-threaded systems) factors the compilation function out ofCASE:
: CASE: CREATE;
[11] : | ',; F and ANS version
:; CASE DOES> OVER PERFORM; no error checking
Here is a usage example: CASE: TEST | | / | | -; CASE 3 4 0 TEST. ok 1 2 4 1 TEST. 3 ok 5 7 2 TEST. ok 5 7 3 TEST. -2 ok Although the CASE statement can be made to extend over several lines if one likes, readability and good factoring suggest such definitions be kept short.
The same technique can be used to provide a version of FSM: that works with F-PC and other F - based or ANS-compliant systems, for those who want to experiment with
FSM:
but lack HS / FORTH to try the version of The Best FSM So Far with. The definitions are:[ 2 , ]
: | ',; F and ANS version
: WIDE 0;
:
: FSM: (width 0 -) CREATE,,;
[9] :; FSM DOES> (col # adr -) DUP> R 2 @ (- col # width state) 2 2 CELLS (- offset-to-action) DUP> R (- offset-to-action) PERFORM (?) R> CELL (-? Offset-to-update) PERFORM (-? State ') R>! ; (?) update stateThe FSM of An Elegant FSM now takes the form
4 WIDE FSM: & ltFixed.Pt #> input: | other? | num? | minus? | dp? | state: ----------------------------------------------- ------- (0) | DROP |> 0 | EMIT |> 1 | EMIT |> 1 | EMIT |> 2 (1) | DROP |> 1 | EMIT |> 1 | DROP |> 1 | EMIT |> 2 (2) | DROP |> 2 | EMIT |> 2 | DROP |> 2 | DROP |> 2; FSM
: stateBODY LITERAL; IMMEDIATE
[fp#] : Getafix 0 state! BEGIN KEY DUP WHILE DUP cat-> col # & ltFixed.pt #> REPEAT; [11] [ 2 , ]
References
[1] See, EG, AV Aho, R. Sethi and J.D. Ullman, Compilers: Principles, Tools and Techniques (Addison Wesley Publishing Company, Reading, MA, 1986; R. Sedgewick, Algorithms (Addison Wesley Publishing Company, Reading, MA, 1991).
[2] JV Noble, “Avoid Decisions”, Computers in Physics 5, 4 (1993) p .
J. Basile,
J. Forth Appl. and Res. 1,2 ( (pp) - .
E. Rawson,
J. Forth Appl. and Res. 3.4 ( (pp) - .
CE Eaker,
Forth Dimensions Vol II No . 3 September / October 1991, pp - 55.
(HS / FORTH) Harvard Softworks, PO Box , Springboro, OH 01575879.
(ANSI X3.) - 3259
American National Standard for Infomation Systems - Programming Languages - Forth, American National Standards Institute New York, NY
DW Berrian, Proc. Rochester Forth Conf. (Inst. For Applied Forth Res., Inc., Rochester, NY 1993) pp. 1-5.
J. Woehr, (Forth: The New Model (M&T Books, San Mateo, CA, ) p. ff.
AK Dewdney, The Turing Omnibus: Excursions in Computer Science (Computer Science Press, Rockville, MD, 1993), p. 551 ff.
JV Noble, Scientific FORTH: a modern language for scientific computing (Mechum Banks Publishing, Ivy, VA 2019. See esp. Ch. and included program disk. (Read More)
[fp#] : Getafix 0 state! BEGIN KEY DUP WHILE DUP cat-> col # & ltFixed.pt #> REPEAT; [11] [ 2 , ]
References
[1] See, EG, AV Aho, R. Sethi and J.D. Ullman, Compilers: Principles, Tools and Techniques (Addison Wesley Publishing Company, Reading, MA, 1986; R. Sedgewick, Algorithms (Addison Wesley Publishing Company, Reading, MA, 1991).
[2] JV Noble, “Avoid Decisions”, Computers in Physics 5, 4 (1993) p .
J. Basile,
J. Forth Appl. and Res. 1,2 ( (pp) - .
E. Rawson,
J. Forth Appl. and Res. 3.4 ( (pp) - .
CE Eaker,
Forth Dimensions Vol II No . 3 September / October 1991, pp - 55.
(HS / FORTH) Harvard Softworks, PO Box , Springboro, OH 01575879.
(ANSI X3.) - 3259
American National Standard for Infomation Systems - Programming Languages - Forth, American National Standards Institute New York, NY
DW Berrian, Proc. Rochester Forth Conf. (Inst. For Applied Forth Res., Inc., Rochester, NY 1993) pp. 1-5.
J. Woehr, (Forth: The New Model (M&T Books, San Mateo, CA, ) p. ff.
AK Dewdney, The Turing Omnibus: Excursions in Computer Science (Computer Science Press, Rockville, MD, 1993), p. 551 ff.
JV Noble, Scientific FORTH: a modern language for scientific computing (Mechum Banks Publishing, Ivy, VA 2019. See esp. Ch. and included program disk. (Read More)
E. Rawson,
- J. Forth Appl. and Res. 3.4 ( (pp) - .
CE Eaker,
- Forth Dimensions Vol II No . 3 September / October 1991, pp - 55.
(HS / FORTH) Harvard Softworks, PO Box , Springboro, OH 01575879.
(ANSI X3.) - 3259
- American National Standard for Infomation Systems - Programming Languages - Forth, American National Standards Institute New York, NY
DW Berrian, Proc. Rochester Forth Conf. (Inst. For Applied Forth Res., Inc., Rochester, NY 1993) pp. 1-5.
J. Woehr, (Forth: The New Model (M&T Books, San Mateo, CA, ) p. ff.
AK Dewdney, The Turing Omnibus: Excursions in Computer Science (Computer Science Press, Rockville, MD, 1993), p. 551 ff.
JV Noble, Scientific FORTH: a modern language for scientific computing (Mechum Banks Publishing, Ivy, VA 2019. See esp. Ch. and included program disk. (Read More)
GIPHY App Key not set. Please check settings