Essays/MultipleOr

In Donald Knuth: The Art of Computer Programming Volume 1 Fascicle 1, MMIX: A RISC Computer for the New Millenium (2005), page 11, Knuth takes the idea of a generalized matrix product (denoted by the u/ .v dyad in J) from Ken Iverson. He considers especially the cases ~:/ .* and +./ .* for boolean matrices. The MMIX machine he defines has instructions MXOR (multiple xor) and MOR (multiple or) that perform these on 8x8 boolean matrices.

Multiple xor is of course just the usual matrix multiplication on GF(2), so it probably has applications in code theory or something like that. However, I've long since wondered on the usefulness of multiple or. Even the fascicle has failed to convince me that it's useful, as it doesn't really show a useful application of multiple or that can't be done with multiple xor instead.

Yesterday, however, I wrote a perl obfu http://www.perlmonks.com/?node_id=657861. A more readable version of it is here:

use 5.010_000; use warnings; use strict;
my @l = map { [unpack "(A)*", $_] } qw"
@ |*'!~ |%+:( >|(+: }~|:*( |!:( ;(!:^| ;='*( @
";
my @r = map { {unpack "(A.)*"} } qw"
^ = = = | [ ] ( ~ ~ ~ (-: [ ] !( ~ ~ ~ + [ ]
%>* * * * ! [ ] ; ; [ ] %= |= = [ ]
: ' ' ' : [ ] '( } } } *(
";
foreach my $l (@l) { foreach (@r) { when ($l) { print "@" } print " " } say "";
}

The trick in this is the smart match operator, which in this case checks if a literal list from @l like '}~|:*(' has a common element with a literal list from @r like '%='.

Let's try to translate this to J. Here are the input lists of lists.

   r =: <;._2 '@ |*''!~ |%+:( >|(+: }~|:*( |!:( ;(!:^| ;=''*( @ '
   c =: <;._2 '^ = = = | [ ] ( ~ ~ ~ (-: [ ] !( ~ ~ ~ + [ ] %>* * * * ! [ ] ; ; [ ] %= |= = [ ] : '' '' '' : [ ] ''( } } } *( '

The most straightforward translation would be to use the e. verb to find the intersection of each list from r with each from r. This is what we get.

  ' @'{~ r +./@:e.&>"0/ c

However, we can get a more interesting translation using multiple or.

   b =: (~.;r)&e.@>
   ' @'{~ (b r) +./ .* |: b c

Here, we convert r and c to a matrix which has one column for each of the 15 literals used, and each element tells whether that literal is an element of that particular list in r. Then, +./ .* calculates whether each list has an intersection with each other. Multiple xor wouldn't work here.

-- B Jonas <<DateTime(2007-12-21T10:38:08Z)>>