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
[2] http://www.jsoftware.com/help/dictionary/d332.htm
[3] http://www.jsoftware.com/help/dictionary/d020.htm
[4] http://www.jsoftware.com/help/dictionary/dx009.htm
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
