Finite State Machines in Forth

J.V. Noble Institute for Nuclear and Particle Physics University of Virginia Charlottesville, VA  22901 Abstract 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. 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. Although generic pattern recognition can be implemented through logical expressions (i.e. by concatenating sufficiently many IFs, ELSEs and THENs) 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 The Programmer's Shop and other developer-oriented software discounters.] 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 discussed previously in this journal [3], [4]. The present approach improves on prior methods. 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-10 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: 0.123, .123, 1.23, -1.23, 123, etc. From these examples we derive the rules: Characters other than 0-9, - and . are illegal. Numerals 0-9 are legal. The first character can be -, 0-9 or a decimal point. After the first character, - is illegal. After the first decimal point, decimal points are illegal. 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 ; The word that does the work is (with apologies to Uderzo and Goscinny, creators of Asterix) : Getafix FALSE PREVIOUS.MINUS? ! FALSE PREVIOUS.DP? ! \ initialize history semaphores BEGIN KEY DUP CR WHILE LEGAL? IF DUP ECHO APPEND THEN REPEAT ; 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. 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 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, 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 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 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; also DDUP is specific to HS/FORTH and should be replaced with 2DUP for ANSI compliance. WITHIN as used here returns TRUE if a <=n <=b, which is different from the ANS specification. These remarks apply here and below, except as noted.] 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 - = ; 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: <Fixed.Pt#> (0) (1) (2) ;CASE : Getafix 0 mystate ! \ initialize state BEGIN KEY DUP 13 \ not CR ? WHILE mystate @ &ltFixed.Pt#> \ execute FSM REPEAT ; A Better FSM While the approach outlined above in P3.1 (essentially the method described recently by Berrian [8]) both works and produces much clearer code than the binary logic tree of P2, it nevertheless can be improved. The words (0), (1) and (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. 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