Finite State Machines in Forth - Noble

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<br>nondeterministic finite state automata in Forth. The "best" method<br>produces a one-to-one relation between the definition and the state table of<br>the automaton. An important feature of the technique is the absence of (slow)<br>nested IF clauses.

Introduction

Certain programming problems are difficult to solve procedurally even using<br>structured code, but simple to solve using abstract finite state machines<br>(FSMs) [1]. For example, a compiler must distinguish a text string<br>representing--say--a floating point number, from an algebraic expression that<br>might well contain similar characters in similar order. Or a machine controller<br>must select responses to pre-determined inputs that occur in random order.

Such problems are interesting because a program that responds to indefinite<br>input is closer to a "thinking machine" than a mere sequential<br>program. Thus, a string that represents a floating point number is defined by a<br>set of rules; it has neither a definite length nor do the symbols appear in a<br>definite order. Worse, more than one form for the same number may be<br>permissible-user-friendliness demands a certain flexibility of format.

Although generic pattern recognition can be implemented through logical<br>expressions (i.e. by concatenating sufficiently many IFs,<br>ELSEs and THENs) the resulting code is generally hard to<br>read, debug, or modify. Worse, this approach is anything but structured, no<br>matter how "prettily" the code is laid out: indentation can only do<br>so much. And programs consisting mainly of logical expressions can be slow<br>because many processors dump their pipelines upon branching [2]. These defects<br>of the nested-IF approach are attested by the profusion of commercial<br>tools to overcome them: Stirling Castle's Logic Gem (that translates and<br>simplifies logical expressions), Matrix Software's Matrix Layout (that<br>translates a tabular representation of a FSM into one of several languages such<br>as BASIC, Modula-2, Pascal or C), or AYECO, Inc.'s COMPEDITOR (that performs a<br>similar translation). [These CASE tools were available at least as recently as<br>1993 from The Programmer's Shop and other developer-oriented software<br>discounters.]

Forth is a particularly well-structured language that encourages natural,<br>readable ways to generate FSMs. This note describes several high-level Forth<br>implementations. Finite state machines have been discussed previously in this<br>journal [3], [4]. The present approach improves on prior methods.

A Simple Example

Consider the task of accepting numerical input from the keyboard. An<br>unfriendly program lets the user enter the entire number before informing him<br>that he typed two decimal points after the first digit. A friendly program, by<br>contrast, refuses to recognize or display illegal characters. It waits instead<br>for a legal character or carriage return (signifying the end of input). It<br>permits backtracking, allowing erasure of incorrect input.

To keep the example small, our number input routine allows signed decimal<br>numbers without power-of-10 exponents (fixed-point, in FORTRAN parlance).<br>Decimal points, numerals and leading minus signs are legal, but no other ASCII<br>characters (including spaces) will be recognized. Here are some examples of<br>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<br>VARIABLE PREVIOUS.DP?

: DIGIT? ( c -- f) ASCII 0 ASCII 9 WITHIN ; \ tests<br>: DP? ( c -- f) ASCII . = ;<br>: MINUS? ( c -- f) ASCII - = ;<br>: FIRST.MINUS? MINUS? PREVIOUS.MINUS? @ NOT AND ;<br>: FIRST.DP? DP? PREVIOUS.DP? @ NOT AND ;

: LEGAL? ( c -- f) \ horrible example<br>DUP DIGIT?<br>IF DROP TRUE DUP PREVIOUS.MINUS? !<br>ELSE DUP FIRST.MINUS?<br>IF DROP TRUE DUP PREVIOUS.MINUS? !<br>ELSE FIRST.DP?<br>IF TRUE DUP PREVIOUS.DP? !<br>ELSE FALSE<br>THEN<br>THEN<br>THEN ;

The word that does the work is (with apologies to Uderzo and Goscinny,<br>creators of Asterix)

: Getafix<br>FALSE PREVIOUS.MINUS? ! FALSE PREVIOUS.DP? !<br>\ initialize history semaphores<br>BEGIN KEY DUP CR WHILE<br>LEGAL? IF DUP ECHO APPEND THEN<br>REPEAT ;

What makes this example--whose analogs appear frequently in published code<br>in virtually every language--horrible? Each character whose legality is<br>time-dependent requires a history semaphore. It is therefore difficult to tell<br>by inspection that the word LEGAL?'s logic is actually incorrect,<br>despite the simplification obtained by partial factoring and logical<br>arithmetic.

FORTH Finite State Machines

The...