Eindige Toestandsmachines in Forth
Samenvatting
Dit artikel beschrijft methoden voor het construeren van deterministische en nondeterministische eindige toestandsautomaten (Finite State Automata) in Forth. De "beste" methode creëert een één-op-één relatie tussen de definitie en de toestandstabel van de automaat. Een belangrijk kenmerk van deze techniek is het ontbreken van (trage) geneste IF-instructies.
Inleiding
Sommige programmeerproblemen zijn moeilijk procedureel op te lossen, zelfs met gestructureerde code, maar eenvoudig op te lossen met behulp van abstracte eindige toestandsmachines (FSM's) [1]. Een compiler moet bijvoorbeeld een tekstreeks die een floating-point getal representeert onderscheiden van een algebraïsche expressie die vergelijkbare tekens in een vergelijkbare volgorde kan bevatten. Of een machinecontroller moet reacties selecteren op vooraf bepaalde inputs die in willekeurige volgorde voorkomen.
Dergelijke problemen zijn interessant omdat een programma dat reageert op onbepaalde input dichter bij een "denkende machine" staat dan een louter sequentieel programma. Een reeks tekens die een floating-point getal representeert wordt bijvoorbeeld gedefinieerd door een set regels; het heeft geen vaste lengte en de symbolen verschijnen niet in een vaste volgorde. Bovendien kunnen meerdere vormen voor hetzelfde getal zijn toegestaan om de gebruiksvriendelijkheid te vergroten.
Hoewel algemene patroonherkenning kan worden geïmplementeerd via logische expressies (door voldoende IF's, ELSE's en THEN's aan elkaar te rijgen), is de resulterende code over het algemeen moeilijk te lezen, te debuggen of te wijzigen. Bovendien is deze benadering allesbehalve gestructureerd, ongeacht hoe "netjes" de code is ingesprongen. Programma's die hoofdzakelijk uit logische expressies bestaan, kunnen traag zijn omdat veel processors hun pipelines legen bij vertakkingen (branching) [2].
De tekortkomingen van de geneste-IF benadering worden bevestigd door de overvloed aan commerciële tools om deze te overwinnen: Stirling Castle's Logic Gem (die logische expressies vertaalt en vereenvoudigt), Matrix Software's Matrix Layout (die een tabelvormige representatie van een FSM vertaalt naar talen zoals BASIC, Modula-2, Pascal of C), of AYECO, Inc.'s COMPEDITOR.
Forth is een bijzonder goed gestructureerde taal die natuurlijke, leesbare manieren aanmoedigt om FSM's te genereren. Dit artikel beschrijft verschillende high-level Forth-implementaties. Eindige toestandsmachines zijn eerder besproken in dit tijdschrift [3], [4]; de huidige benadering verbetert eerdere methoden.
Een eenvoudig voorbeeld
Beschouw de taak om numerieke input via het toetsenbord te accepteren. Een onvriendelijk programma laat de gebruiker het volledige getal invoeren voordat het meldt dat er twee decimale punten na het eerste cijfer zijn getypt. Een vriendelijk programma weigert daarentegen illegale tekens te herkennen of weer te geven. Het wacht in plaats daarvan op een legaal teken of een carriage return (wat het einde van de invoer betekent). Het staat backtracking toe, waardoor onjuiste invoer kan worden gewist.
Om het voorbeeld klein te houden, staat onze routine voor numerieke invoer ondertekende decimale getallen toe zonder macht-van-10 exponenten (fixed-point). Decimale punten, cijfers en een leidend minteken zijn legaal, maar geen andere ASCII-tekens (inclusief spaties) worden herkend.
Voorbeelden van legale getallen:
- 0.123
- .123
- 1.23
- -1.23
- 123
Uit deze voorbeelden leiden we de volgende regels af:
- Tekens anders dan 0-9,
-en.zijn illegaal. - Cijfers 0-9 zijn legaal.
- Het eerste teken kan
-, 0-9 of een decimaal punt zijn. - Na het eerste teken is
-illegaal. - Na het eerste decimale punt zijn verdere decimale punten illegaal.
Een traditionele procedurele benadering zou er als volgt uit kunnen zien:
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 ;
: Getafix
FALSE PREVIOUS.MINUS? ! FALSE PREVIOUS.DP? !
\ initialize history semaphores
BEGIN KEY DUP CR WHILE
LEGAL? IF DUP ECHO APPEND THEN
REPEAT ;Wat maakt dit voorbeeld "verschrikkelijk"? Elk teken waarvan de legaliteit afhankelijk is van de tijd, vereist een geschiedenis-semafoor. Het is daardoor moeilijk om door inspectie te zien dat de logica van het woord LEGAL? eigenlijk onjuist is, ondanks de vereenvoudiging verkregen door partiële factoring en logische rekenkunde.
Finite State Machines in Forth
De FSM-benadering vervangt de true/false historische semaforen door één toestandsvariabele (state variable). De regels kunnen worden belichaamd in een toestandstabel die de respons op elke mogelijke input uitdrukt in termen van een concrete actie en een toestandsovergang, zoals getoond in Tabel 1.
Tabel 1: Toestandstabel voor fixed-point getallen
| Toestand | Input: OTHER? | Input: DIGIT? | Input: MINUS? | Input: DP? |
|---|---|---|---|---|
| 0 | Actie: X → Trans: 0 | Actie: E → Trans: 1 | Actie: E → Trans: 1 | Actie: E → Trans: 2 |
| 1 | Actie: X → Trans: 1 | Actie: E → Trans: 1 | Actie: X → Trans: 1 | Actie: E → Trans: 2 |
| 2 | Actie: X → Trans: 2 | Actie: E → Trans: 2 | Actie: X → Trans: 2 | Actie: X → Trans: 2 |
E staat voor "echo" (naar het scherm) en X voor "niets doen".
In de toestandstabel geldt:
- De illegaliteit van "overige" tekens wordt uitgedrukt door de uniforme actie X en de afwezigheid van toestandsovergangen.
- De speciale status van het eerste teken wordt uitgedrukt door het feit dat alle acceptabele tekens leiden tot overgangen vanuit de initiële toestand (0):
- Een initieel
-teken of cijfer leidt naar toestand 1, waar een-teken onacceptabel is. - Een decimaal punt verplaatst het systeem altijd naar toestand 2, waar decimale punten niet worden geaccepteerd.
Hoewel sommige FSM's gesynthetiseerd kunnen worden met BEGIN...WHILE...REPEAT of BEGIN...UNTIL loops, leent toetsenbordinput zich hier niet gemakkelijk voor. We verkennen nu drie implementaties van de toestandstabel uit Tabel 1 als Forth FSM's.
3.1 Brute-force FSM
De "brute-force" FSM gebruikt de Eaker CASE-statement, ofwel in zijn originele vorm [5] of met een vereenvoudigd construct uit HS/FORTH [6]. HS/FORTH biedt definiërende woorden CASE: ;CASE waarvan de dochterwoorden één van verschillende woorden in hun definitie uitvoeren.
Om een FSM te implementeren, hebben we eerst een toestandsvariabele nodig (geïnitialiseerd op 0) die de waarden 0, 1 en 2 kan aannemen. Om te testen of een input-teken een cijfer, minteken, decimaal punt of "overig" is, definiëren we:
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 - = ;Vervolgens definiëren we drie woorden om de tests in elke toestand af te handelen:
: (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 ;
CASE: <Fixed.Pt#> (0) (1) (2) ;CASE
: Getafix 0 mystate ! \ initialize state
BEGIN
KEY DUP 13 \ not CR ?
WHILE mystate @ <Fixed.Pt#> \ execute FSM
REPEAT ;3.2 Een betere FSM
Hoewel de bovenstaande methode werkt en duidelijkere code produceert dan de binaire logische boom, kan deze nog worden verbeterd. De woorden (0), (1) en (2) zijn onvoldoende gefactoreerd; ze bevatten zowel de tests op het input-teken als IF...ELSE...THEN vertakkingen (die we liever vermijden voor snelheid en structuur).
We willen de toestandstabel in Tabel 1 directer vertalen naar een programma. Als we de tabel visualiseren als een matrix waarbij kolommen inputcategorieën representeren en rijen toestanden, kunnen we de categorie en de huidige waarde van de toestandsvariabele gebruiken om een unieke celadres te bepalen.
De vertaling van input naar een kolomnummer wordt uitgevoerd door één woord:
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 - = ;
: cat->col# ( n -- n')
DUP DIGIT? 1 AND \ digit -> 1
OVER MINUS? 2 AND + \ - -> 2
SWAP DP? 3 AND + \ dp -> 3
; \ other -> 0Vervolgens implementeren we de state-table compiler:
: TUCK COMPILE UNDER ; \ ANS compatibility
: WIDE ; \ NOOP for clarity
: 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 ;Nu passen we dit toe op ons voorbeeld. Er zijn slechts twee verschillende toestandsveranderende acties nodig:
: (00) EMIT 1 mystate ! ;
: (02) EMIT 2 mystate ! ;
4 WIDE FSM: <Fixed.Pt#> ( action# -- )
\ other num - . \ state
DROP (00) (00) (02) \ 0
DROP (00) DROP (02) \ 1
DROP (02) DROP DROP ; \ 2
: Getafix 0 mystate ! BEGIN KEY DUP 13 <> \ not CR
WHILE DUP cat->col# <Fixed.Pt#> REPEAT ;3.3 Een elegante FSM
De versie in sectie 3.2 verbergt de toestandsovergangen binnen de actie-woorden. Een betere benadering is om overgangen expliciet naast de acties te specificeren, zodat de definitie lijkt op de toestandstabel zelf.
We gebruiken CONSTANT voor de toestandsovergangen:
0 CONSTANT >0
1 CONSTANT >1
2 CONSTANT >2En we passen de runtime-sectie van FSM: aan:
: FSM: ( width -- ) CREATE , ] DOES> ( col# -- )
TUCK @ ( -- adr col# width )
mystate @ * + 2* CELLS CELL+ + ( -- offset )
DUP CELL+ PERFORM mystate ! PERFORM ;De FSM wordt nu gedefinieerd als:
4 WIDE FSM:
\ 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 ;3.4 De beste FSM tot nu toe
Er zijn nog twee verbeteringen mogelijk. Ten eerste: om geneste FSM's of recursie mogelijk te maken, moet de toestandsvariabele onderdeel zijn van de datastructuur van de FSM zelf in plaats van een globale variabele. Ten tweede, om botsingen op de stack te voorkomen wanneer actie-woorden iets achterlaten op de stack, gebruiken we de return stack voor tijdelijke opslag.
De herziene versie:
: 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 stateDe bijbehorende invoerroutine:
: Getafix 0 ' <Fixed.Pt#> !
BEGIN KEY DUP 13 <> WHILE
DUP cat->col# <fixed.pt#> REPEAT ;4. Nondeterministische Eindige Toestandsmachines
Door overgangen via woorden (zoals CONSTANTs) in plaats van getallen te beheren, kunnen we nondeterministische FSM's bouwen. Een nondeterministische FSM kan na een actie naar meerdere volgende toestanden vertakken, afhankelijk van aanvullende informatie buiten de huidige toestand en input.
Voorbeeld: FORTRAN Identifiers
Het doel is om te bepalen of een tekstreeks een correcte identifier is volgens de regels van FORTRAN (begint met een letter, maximaal 7 tekens lang). We gebruiken een decoder-tabel (TAB:) voor snelle karakterherkenning.
: TAB: ( #bytes -- )
CREATE HERE OVER ALLOT SWAP 0 FILL DOES> + C@ ;
: install ( col# adr char.n char.1 -- ) \ fast fill
SWAP 1+ SWAP DO DDUP I + C! LOOP DDROP ;
128 TAB: [id]
1 ' [id] ASCII Z ASCII A install
1 ' [id] ASCII z ASCII a install
2 ' [id] ASCII 9 ASCII 0 installOm de lengtebeperking van 7 tekens te implementeren zonder een enorme tabel, gebruiken we een VARIABLE om de tekens te tellen:
VARIABLE id.len 0 id.len !
: +id.len id.len @ 1+ id.len ! ; \ increment counter
: >1? id.len @ 7 < DUP 1 AND SWAP NOT 2 AND + ;
( -- 1 if id.len < 7, 2 otherwise)
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? ;Deze FSM is nondeterministisch omdat het woord >1? een overgang induceert naar óf toestand 1 óf de terminale toestand 2.
Voorbeeld: Floating Point getallen
Een soortgelijke aanpak kan worden gebruikt voor het detecteren van correct gevormde floating point getallen (fp#). De FSM hanteert regels voor de mantisse en de exponent (beperkt tot twee of minder cijfers).
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 ;Dankwoord
Ik ben dankbaar aan Rick Van Norman en Lloyd Prentice voor hun positieve feedback over de toepassingen van de FSM-compiler in diverse gebieden, zoals gasleidingcontrole en educatieve computerspellen.
Appendix
Hier volgt een high-level definitie van CASE: ... ;CASE die werkt in indirect-threaded systemen:
: CASE: CREATE ] DOES> ( n -- ) OVER + + @ EXECUTE ;
: ;CASE [COMPILE] ; ; IMMEDIATEVoor direct-threaded systemen zoals F-PC is een andere aanpak nodig waarbij de compilatiefunctie wordt gescheiden van CASE::
: CASE: CREATE ;
: | ' , ; \ F83 and ANS version
: ;CASE DOES> OVER + + PERFORM ; \ no error checkingVoor gebruikers die willen experimenteren met FSM: maar geen HS/FORTH hebben, is hier een versie die compatibel is met F83 of ANS-standaarden:
: | ' , ; \ F83 and ANS version
: WIDE 0 ;
: FSM: ( width 0 -- ) CREATE , , ;
: ;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> ! ; ( ? )Referenties
- A.V. Aho, R. Sethi en J.D. Ullman, Compilers: Principles, Tools and Techniques (Addison Wesley Publishing Company, 1986); R. Sedgewick, Algorithms (Addison Wesley Publishing Company, 1983).
- J.V. Noble, "Avoid Decisions", Computers in Physics 5, 4 (1991) p 386.
- J. Basile, J. Forth Appl. and Res. 1,2 (1982) pp 76-78.
- E. Rawson, J. Forth Appl. and Res. 3,4 (1986) pp 45-64.
- C. E. Eaker, Forth Dimensions Vol II No. 3 September/October 1980, pp 37-40.
- HS/FORTH Harvard Softworks, Springboro, OH 45066.
- ANSI X3.215-1994 American National Standard for Information Systems -- Programming Languages -- Forth.
- D.W. Berrian, Proc. 1989 Rochester Forth Conf. (Inst. for Applied Forth Res., Inc., 1989) pp. 1-5.
- J. Woehr, Forth: The New Model (M&T Books, 1992) p. 43 ff.
- A.K. Dewdney, The Turing Omnibus: 61 Excursions in Computer Science (Computer Science Press, 1989), p. 154ff.
- J.V. Noble, Scientific FORTH: a modern language for scientific computing (Mechum Banks Publishing, 1992).
Groetjes,