May I suggest you make this into an essay in the Wiki?
On Fri, Aug 10, 2012 at 2:49 PM, Peter B. Kessler < [email protected]> wrote: > In response to my request for a solution to the alternating binary array > problem that uses J's Sequential Machine (;:) verb, Raul Miller posted > this[1] > > Here's an implementation which uses ;: >> >> smalt=: 12 > (3;1,~&>0 1 2 3,1 3 2 3,2 1 3 3,:3)&;:@:#.@|: >> > > I thought it would be worth writing Raul's solution up, for my own benefit > and for any other people trying to learn how to use Sequential Machine in > J. I will try to remain faithful to the spirit of Raul's original, except > in a one place where I thought something could be clarified, and I tend to > put spaces and parentheses around things to break up the phrases because > I'm still learning J and find the line noise hard to read. > > The key idea is to represent a finite state machine that tracks whether > the last seen pair of inputs is 0 1 or 1 0. There are 4 states: if we > haven't seen either a 0 1 or a 1 0; if the last alternating pair was a 0 1; > if the last alternating pair was a 1 0; and if we've seen a pair that > violates the "alternating" rule. > > In Karnough maps, if we call the elements of the inputs A and B, and the > states, respectively, Before, Bwas1, Awas1, and Error, the state > transitions are > > | B > Before: | 0 1 > ----+-------------- > 0 | Before Bwas1 > A | > 1 | Awas1 Error > > | B > Bwas1: | 0 1 > ----+-------------- > 0 | Bwas1 Error > A | > 1 | Awas1 Error > > | B > Awas1: | 0 1 > ----+-------------- > 0 | Awas1 Bwas1 > A | > 1 | Error Error > > | B > Error: | 0 1 > ----+-------------- > 0 | Error Error > A | > 1 | Error Error > > For example: if we are in state Before and see an A of 0 and a B of 1, > then we transition to state Bwas1; if we see an A of 1 and a B of 0, then > we transition to state Awas1; an A of 0 and B of 0 leaves us in state > Before; an A of 1 and a B of 1 takes us to state Error. The other states > are similar. The state transition diagram is the program for our machine. > Now we have to deal with the data for the machine. > > Since the J Sequential Machine doesn't read pairs of 0's and 1's as input, > but instead reads successive elements of the input, we encode the inputs by > treating the pairs as numbers in base 2. If we Laminate the A and B input > vectors (A ,: B) we can convert each pair to a number with a (BaseTwo Atop > Transpose) conjunction, the (#. @ |:) from Raul's implementation, as in > > A =: 1 0 0 1 0 1 NB. A first vector of binary digits. > B =: 0 1 0 0 1 0 NB. A second vector of binary digits. > A ,: B NB. Laminate those together into a 2xN matrix. > 1 0 0 1 0 1 > 0 1 0 0 1 0 > |: (A ,: B) NB. Transpose to an Nx2 matrix. > 1 0 > 0 1 > 0 0 > 1 0 > 0 1 > 1 0 > (#. @ |:) (A ,: B) NB. Convert each row of the transpose from base > 2. > 2 1 0 2 1 2 > > (Note that none of the parentheses in the last expression above is needed. > I put them in to emphasize that (A ,: B) is computed first, then the > resulting noun is supplied as the single argument to the monadic > conjunction (#. @ |:), which applies Transpose (|:) to the argument and > then applies Base 2 (#.) to the result of the transpose.) > > Similarly, we encode the state names as numbers: Before as 0, Bwas1 as 1, > Awas1 as 2, and Error as 3, and index the state transitions with the > numbers formed by the input pairs. That is, the state transitions are > represented by the 4x4 matrix from Raul's implementation > > 0 1 2 3,1 3 2 3,2 1 3 3,:3 > 0 1 2 3 > 1 3 2 3 > 2 1 3 3 > 3 3 3 3 > > with the rows indexed by states and the columns indexed by inputs, > yielding the next state. (It's worth noting that Raul uses Laminate (,:) > to build a 2x4 matrix using the automatic reshaping of Laminate to > replicate the 3 in the right argument to the shape of the left argument. > He could have replicated the 3's himself, which might have been clearer > than depending on the implicit replication. On the other hand, one could > read that single 3 as reinforcing the idea that once the finite state > machine enters the Error state, it stays in that state. Once he has formed > the 2x4 matrix with the Laminate, the successive Append (,) verbs add their > left argument vectors as additional rows to the top of the matrix to form > the resulting 4x4 matrix.) > > The J Sequential Machine (;:) verb needs more information than just the > state transition table. See the Dictionary for details[2], but the verb > needs: a function code, an input mapping function, an initial iteration > counter, an initial index into the input, the initial state, and an > end-of-input action. These are all combined into the left argument to > Sequential Machine. In particular, we want a function code of 3, and an > output table of 1's. In Raul's implementation that's done with > > 3;1,~&>0 1 2 3,1 3 2 3,2 1 3 3,:3 > +-+---+ > |3|0 1| > | |1 1| > | |2 1| > | |3 1| > | | | > | |1 1| > | |3 1| > | |2 1| > | |3 1| > | | | > | |2 1| > | |1 1| > | |3 1| > | |3 1| > | | | > | |3 1| > | |3 1| > | |3 1| > | |3 1| > +-+---+ > > (I have to say that it took me a long time to figure out what the Open (>) > verb was doing in there. What's needed is to Append (,) a 1 to the > individual elements of the 4x4 state transition matrix, to produce a 4x4x2 > matrix. Using Passive Append (,~) seems somewhat backwards to me, as the 1 > wants to be Appended to the right of elements of the state transition > table, so it seemed like the 1 should be the right argument to the Append. > Furthermore, the Passive Append is used in a Compose (&) conjunction, with > Open (>) as the right verb. The Dictionary entry for Open[3] says it has > no effect when applied to an array with no boxed elements. The state > transition table has no boxed elements. So why the Open, and why does that > have to be performed before the Passive Append? The answer is that Open is > used here not for its verb, but for its rank, which is 0 0 0. The Compose > (&) with a right verb of Open (>) says that the state transition matrix is > accessed by individual elemen > t, and then the result of that is Passive Appended to a 1. To me it would > be more natural to use Append rather than Passive Append, and to say that > it should be applied to individual elements explicitly, with a Rank > conjunction, as in > > (0 1 2 3 , 1 3 2 3 , 2 1 3 3 ,: 3) (,"0) 1 > 0 1 > 1 1 > 2 1 > 3 1 > > 1 1 > 3 1 > 2 1 > 3 1 > > 2 1 > 1 1 > 3 1 > 3 1 > > 3 1 > 3 1 > 3 1 > 3 1 > > The verb with the rank conjunction has to be separated from the right > argument to keep the parser from including the rank in the right argument. > I use parentheses to do that, but I've seen other idioms, e.g., Same (]) > used for that effect. I've seen the Append Rank 0 verb (,"0) in the > Dictionary (e.g., on the page for Append), so it's not heresy to use it.) > > When we Bond (&) our machine description to the Sequential Machine verb > (;:) we get a complete, specific, sequential machine verb > > ( 3 ; ( 0 1 2 3 , 1 3 2 3 , 2 1 3 3 ,: 3 ) (,"0) 1 ) & ;: > +------------------+-+--+ > |+-+---++---------+|&|;:| > ||3|0 1||0 _1 0 _1|| | | > || |1 1|| || | | > || |2 1|| || | | > || |3 1|| || | | > || | || || | | > || |1 1|| || | | > || |3 1|| || | | > || |2 1|| || | | > || |3 1|| || | | > || | || || | | > || |2 1|| || | | > || |1 1|| || | | > || |3 1|| || | | > || |3 1|| || | | > || | || || | | > || |3 1|| || | | > || |3 1|| || | | > || |3 1|| || | | > || |3 1|| || | | > |+-+---++---------+| | | > +------------------+-+--+ > > with the default value for m (the column of empty (cf. 0$0) to the right > of the state transition table) and the default value for ijrd (0 _1 0 _1) > as shown by the boxed display of non-nouns, with the ((9!:3) 2) display > function[4]. > > When we compose that particular sequential machine verb with the verb that > encodes the inputs, the current state (initially 0) is used to index a > plane of the state transition table, and the encoded input is used to index > a row of the state. The output is the next state for the sequential > machine. For our sample input > > ( ( (3 ; (0 1 2 3 , 1 3 2 3 , 2 1 3 3 ,: 3) (,"0) 1) & ;: ) @: (#. @ > |:) ) (A ,: B) > 10 > > (That is perhaps too many parentheses even for me, but I want to emphasize > that we are composing the verb for our sequential machine with the verb > that encodes the input, and applying that new verb to the laminated input > vectors. Raul's implementation has the minimum parentheses, but as a newb > I find it hard to read long verb trains.) > > We get as output the state 10 (which encodes that the last state was > Awas1, and that the last input was a 1 0. We can track the individual > state changes by tediously applying the verb to successively longer > sequences of the input > > ( ( (3 ; (0 1 2 3 , 1 3 2 3 , 2 1 3 3 ,: 3) (,"0) 1) & ;: ) @: (#. @ > |:) ) (1 ,: 0) > 10 > ( ( (3 ; (0 1 2 3 , 1 3 2 3 , 2 1 3 3 ,: 3) (,"0) 1) & ;: ) @: (#. @ > |:) ) (1 0 ,: 0 1) > 5 > ( ( (3 ; (0 1 2 3 , 1 3 2 3 , 2 1 3 3 ,: 3) (,"0) 1) & ;: ) @: (#. @ > |:) ) (1 0 0 ,: 0 1 0) > 4 > ( ( (3 ; (0 1 2 3 , 1 3 2 3 , 2 1 3 3 ,: 3) (,"0) 1) & ;: ) @: (#. @ > |:) ) (1 0 0 1 ,: 0 1 0 0) > 10 > ( ( (3 ; (0 1 2 3 , 1 3 2 3 , 2 1 3 3 ,: 3) (,"0) 1) & ;: ) @: (#. @ > |:) ) (1 0 0 1 0 ,: 0 1 0 0 1) > 5 > ( ( (3 ; (0 1 2 3 , 1 3 2 3 , 2 1 3 3 ,: 3) (,"0) 1) & ;: ) @: (#. @ > |:) ) (1 0 0 1 0 1 ,: 0 1 0 0 1 0) > 10 > > or by changing the function code from 3 to 5 to get tracing of the state > of the sequential machine > > ( ( (5 ; (0 1 2 3 , 1 3 2 3 , 2 1 3 3 ,: 3) (,"0) 1) & ;: ) @: (#. @ > |:) ) (A ,: B) > 0 _1 0 2 2 1 > 1 0 2 1 1 1 > 2 1 1 0 1 1 > 3 2 1 2 2 1 > 4 3 2 1 1 1 > 5 4 1 2 2 1 > > where the columns are (quoting the Dictionary, but adding a pair of > pedagogical parentheses) > > i , j , r , c , (s {~ < r,c) > > For example, on the line where i is 5: j is 4, r is 1, c is 2, and the > state transition table at ( < 1 2 ) is ( 2 1 ). Reading down the r column > of that output shows us the successive states of the machine (0 2 1 1 2 1), > reading down the c column shows us the successive encoded inputs (2 1 0 2 1 > 2), and reading down the first of the s columns shows us the next state of > the machine (2 1 1 2 1 2). > > If at the end of the input the state is not in the Error state, then the > machine has seen alternating binary inputs. That condition is tested by > whether the output of our machine is less than 12 (the beginning of the > Error state), e.g., from Raul Miller's implementation > > 12 > (3;1,~&>0 1 2 3,1 3 2 3,2 1 3 3,:3)&;:@:#.@|: > > (I would write that as > > 12 > ( ( (3 ; (0 1 2 3 , 1 3 2 3 , 2 1 3 3 ,: 3) (,"0) 1) & ;: ) @: (#. > @ |:) ) > > but I expect to learn, eventually, to read J without all those extra > parentheses.) > > Thank you for reading this far. > > ... peter > > P.S. All that said, I think I now prefer Marshall Lochbaum's solution > > (-: (0 1,:1 0)$~#)@:(0 0 -.~ |:)@:/:~ > > so I'll write that up next. > > -------- > [1] > http://jsoftware.com/**pipermail/programming/2012-**July/028838.html<http://jsoftware.com/pipermail/programming/2012-July/028838.html> > [2] > http://www.jsoftware.com/help/**dictionary/d332.htm<http://www.jsoftware.com/help/dictionary/d332.htm> > [3] > http://www.jsoftware.com/help/**dictionary/d020.htm<http://www.jsoftware.com/help/dictionary/d020.htm> > [4] > http://www.jsoftware.com/help/**dictionary/dx009.htm<http://www.jsoftware.com/help/dictionary/dx009.htm> > > ------------------------------**------------------------------**---------- > For information about J forums see > http://www.jsoftware.com/**forums.htm<http://www.jsoftware.com/forums.htm> > ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
