Vocabulary/SequentialMachineNotes
Notes on the usage of Sequential Machine (dyadic ;:)
See Vocabulary/WordsNotes for notes on usage of monadic (;:)
Case study
Here I exhibit a working machine to process Boolean lists.
I learned to use the sequential machine through a series of errors. If you don't understand it at first reading, persevere to see the mistakes and substeps I took to make it work. My experience might help your understanding.
Project: define STATE to validate these assertions:
assert 0 1 0 -: (1 ; STATE) ;: 0 0 0 1 1 0 assert 1 0 1 -: (1 ; STATE) ;: -. 0 0 0 1 1 0 assert 0 1 0 1 -: (1 ; STATE) ;: 0 0 1 1 1 0 0 0 0 1 1
A solution is
STATE=: (1 1 ,: 2 1) , (1 1 ,: 2 2) ,: (1 2 ,: 2 1)
How did I find it? The remaining examples trace my learning curve. First I tried a two state machine. The machine starts in state 0. This incorrect logic seemed reasonable for my first try.
In state 0, if an item is of class 0 remain in state 0 and advance i . Otherwise, transition to state 1 , emit word, and advance i . State 1 would work in opposition.
STATE=: (0 1 ,: 1 2) ,: (0 2 ,: 1 1) ((>;:'Next state and action') ; ;:'Class0 Class1'),(;: 'State0 State1'),.<"1 STATE ┌──────┬──────┬──────┐ │Next │Class0│Class1│ │state │ │ │ │and │ │ │ │action│ │ │ ├──────┼──────┼──────┤ │State0│0 1 │1 2 │ ├──────┼──────┼──────┤ │State1│0 2 │1 1 │ └──────┴──────┴──────┘ assert 0 1 0 -: (1 ; STATE) ;: 0 0 0 1 1 0 assert 1 0 1 -: (1 ; STATE) ;: 1 1 1 0 0 1 |index error | assert 1 0 1-:(1;STATE) ;: 1 1 1 0 0 1
The first item, class 1 in state 0 causes transition to state 1 AND emit word. Variable j started as _1 , emit word signaled index error. The ijrd parameter won't help because i must be greater than j.
I decided the project was too difficult. Let's start with a machine that stops.
(0 ; (,: ,: 0 6) ) ;: 0 NB. by default, an integer is its class
(0 ; (1 2 2 $ 0 6) ; <<0 ) ;: 5 32 4 NB. stop on any integer
stop=: ;:~ 0 ; (1 2 2$0 6) ; [: < [: < {. NB. stop as above, take data type from y
stop 'abc'
SUCCESS! Next baby step: define a machine that returns text up to 'b' then stops. State table proposal:
In state 0
if the first character is retainable, set j=.i and go to state 1. otherwise it is 'b'. Quit without output.
In state 1
while not 'b' remain in state 1 without output. otherwise transition to state 2 and emit word. Action 3 sets j to _1 to prevent emit word if 'b' is at the end of the character vector.
In state 2 stop.
FUNCTION=: 1 STATE=: (1 1 ,: 0 6) , (1 0 ,: 2 3) ,: (0 6 ,: 0 6) MAP=: a. = 'b' (FUNCTION ; STATE ; MAP)&;:&.>;:'Xa Xab Xabc b ba cba' ┌──┬──┬──┬┬┬─┐ │Xa│Xa│Xa│││c│ └──┴──┴──┴┴┴─┘ (FUNCTION;STATE;MAP);:'my-cat-bart' my-cat- (FUNCTION;STATE;MAP);:'buy-my-cat-bart'
SUCCESS! Changing the map would change the stop character set.
Next baby step: duplicate the transliteration deletion action of the unix command tr -d [characterSet] .
- Class 0: characters to keep.
- Class 1: characters to delete.
- State 0: start of sequence to analyze.
- State 1: retention.
- State 2: elision.
In state 0, the beginning of the items to analyze
- 1 1 Transition to state 1, mark the start of word
- 0 0 Found a deletable item. Remain in state 0
In state 1, retention
- 1 0 Stay in state 1, no output. The machine increments i .
- 2 3 Found unwanted item. Enter state 2, emit word.
In state 2, elision
- 1 1 Desirable. Enter state 1, j=.i to mark start of next word.
- 2 0 Unwanted. Stay put.
FUNCTION=: 1 STATE=: 3 2 2 $ 1 1 0 0 1 0 2 3 1 1 2 0 MAP=: a. = 'b' (FUNCTION;STATE;MAP)&;:&.>'buy my cat bart';'bb0123bb45bbb';'666' ┌─────────────┬──────┬───┐ │uy my cat art│012345│666│ └─────────────┴──────┴───┘ NB. same STATE table removes 'a' and 'b' . ELISIONS=: 'ab' (FUNCTION ; STATE ; <<a.-.ELISIONS) ;: 'buy my cat bart' uy my ct rt NB. Challenge: NB. Rewrite the state table to eliminate unnecessary state 2.
SUCCESS! Let's finish the original project. Item classes are the integers 0 and 1 . Plan: report previous item when it differs from the current item. Solution: use 3 states, advance the start of word at every item. Emit word at each state change.
STATE=: (1 1 ,: 2 1) , (1 1 ,: 2 2) ,: (1 2 ,: 2 1) [A=: (,: -.) 0 0 0 1 1 0 0 0 0 1 1 0 1 1 1 0 0 1 (1 ; STATE) ;:"_ 1 A 0 1 0 1 0 1 NB. insert the explicit item map (1 ; STATE ; < < 0 ) ;:"_ 1 A 0 1 0 1 0 1 NB. group 'a' with 'b' (1 ; STATE ; <<'ab' ) ;: 'abbacdeab' aeb
SUCCESS!
Suppose you think, as I thought, to specify both items in the map. Index error arises because there are now 3 item classes, the 0 and 1 specified, and the implicit set of all else. Use smcheck defined in the Sequential Machine lab.
(1 ; STATE ; < 0 ; 1 ) ;:"_ 1 A |index error | (1;STATE;<0;1) ;:"_ 1 A [X=: 1 ; STATE ; < 0 ; 1 +-+---+-----+ |1|1 1|+-+-+| | |2 1||0|1|| | | |+-+-+| | |1 1| | | |2 2| | | | | | | |1 2| | | |2 1| | +-+---+-----+ X smcheck 1 1 1 0 0 0 0 1 |assertion failure | q>#m
Quick reference for common problems
Use smcheck , defined in the Sequential Machine lab.
Index error causes
- Emit with j equal to _1.
- Data type mismatch of y items and the item map boxes.
- Incorrectly specified boxed map. Remember to use an extra box < to put a box of boxes as the y argument of link . The item classes are correctly boxed in the next examples.
- q doesn't bound the item classes. I still commit the error of "specifying all the classes" when actually the additional implicit class of all else extends the character classes and it is my state table that falls short.
STATE=: (1 1 ,: 2 1) , (1 1 ,: 2 2) ,: (1 2 ,: 2 1) (1 ; STATE ; <0;1) ;: 0 0 0 1 1 0 NB. WRONG, 3 item classes in map, 2 = q in STATE |index error | (1;STATE;<0;1) ;:0 0 0 1 1 0 (1 ; STATE ; <<0) ;: 0 0 0 1 1 0 NB. RIGHT 0 1 0
- State table contains possible transition to undefined state.
(1 ; ,:^:2 ] 0 6);:0 NB. OK, state 0 exists (1 ; ,:^:2 ] 99 6);:0 NB. NO! state 99 undefined |index error | (1;,:^:2]99 6) ;:0
Rank error causes
- State table must be rank 3.
Length error causes
- Character map must tally 256
NB. curtailed map is too short (1 ; STATE ; }: 'b' = a.) ;: 'abcdebf' |length error | (1;STATE;}:'b'=a.) ;:'abcdebf'
(Contributed by DavidLambert)