Evolution of a Computer Application - Groups16 -- 1990 version

Groups16 is an early version of the groups system.  The system originated with a posting to Usenet in 1989 by Kenneth Almquist. He had generated tables for groups of orders 1-16, apparently as an exercise in combinatorics programming. In his original posting some of the tables represented isomorphic groups.  Groups16 started in an effort to find out how much (or how little) one must know about groups to distinguish which tables were isomorphic.

The Almquist tables looked like this:

1 group of order 1:
   ___
   A|A

1 group of order 2:
   _____
   A|A B
   B|B A

1 group of order 3:
   _______
   A|A B C
   B|B C A
   C|C A B

2 groups of order 4:
   _________        _________
   A|A B C D        A|A B C D
   B|B A D C        B|B C D A
   C|C D A B        C|C D A B
   D|D C B A        D|D A B C

1 group of order 5:
   ___________
   A|A B C D E
   B|B C D E A
   C|C D E A B
   D|D E A B C
   E|E A B C D

An interesting thing happened: Some readers pointed out that Almquist had posted more groups of certain orders than the literature claimed.  He traced the problem to the fact that his algorithm had not detected that some of the original tables were isomorphic. A subsequent posting corrected the error.  However, this raised an interesting question: How much do you need to know about a group of order 1-16 to be able to easily detect isomorphism?  It is obvious that, even for groups of order 16, one does not try all possible bijective mappings to see if two groups are isomorphic.  Instead, one hopes to look at properties of the groups that must be preserved under isomorphism. The original steps in the system were to represent the data in a suitable way, and to implement words that computed various information about the groups.

1. Data Representation
2. Input and Output
3. Some First Procedures
4. Evolution of ORDERS
5. Finding Isomorphisms

a. Data Representation

The original version was implemented on a computer that had only 64K of memory. The version of Forth used 16-bit integers and so could address only this much memory. The Forth system and DOS used 26K of memory -- and a nicer editor had been added to bring this to 44K.  This left just 20K for the group theory system and data.

Fortunately the Forth systems commonly available at that time provided a rather clever way to use the hard disk for virtual memory.  The disk was organized into 1024 byte blocks, and the system provided a word BLOCK with stack diagram ( n - addr ). Using 5 BLOCK, for example, the system would check if block 5 on the disk had already been loaded into memory. If not, it would be read from disk into a buffer. In either case, the base address of the buffer would be returned. With this scheme, one could create the illusion that a large amount of data was in memory.

For purposes of this article, I have moved the earlier code to a modern (32-bit) version of Forth on a computer that has 128 megabytes of memory.  I therefore put the tables into a section of the dictionary.  To make the earlier code run without rewriting, I redefined the word BLOCK to refer to parts of this section of memory.

The original tables were converted to an internal format by stripping everything except the interior squares of the tables. These were arranged sequentially by row:

   AABBAABCBCACABABCDBADCCDABDCBAABCDBCDACDABDABCABCDEBCDEACDEABDEA
   BCEABCDABCDEFBCAEFDCABFDEDFEACBEDFBACFEDCBAABCDEFBCDEFACDEFABDEF
   ABCEFABCDFABCDEABCDEFGBCDEFGACDEFGABDEFGABCEFGABCDFGABCDEGABCDEF
   ABCDEFGHBADCFEHGCDABGHEFDCBAHGFEEFGHABCDFEHGBADCGHEFCDABHGFEDCBA
   etc.

This amalgamation of the group tables was put in Blocks 1-10.  They were spaced so that tables did not straddle disk blocks. In order to locate a particular group, it is necessary to know the order of the group, the block in which the data are contained, and the number of bytes from the beginning of the block where the data are located.  With this information we can calculate the address in memory for a particular table.

Block 0 was used to store the triples Gnum, Gblk, Goffs for each group.

0  CONSTANT  IDXBLK   65  CONSTANT  ID
0  VALUE  GNUM   0  VALUE  GORD   
0  VALUE  GBLK   0  VALUE  GOFFS

At this point I made an important decision. Most of my computations would be for a certain group, fixed for the moment.  Rather than write procedures to which I would have to pass the group number as a parameter, I designated the group of interest at the moment (given by number) as "the current group", and I wrote all procedures to refer to that current group.

My word to assign the current group is  >GROUP  -- it stores the group number as the value Gnum, as well as the triple mentioned above.  It is therefore not necessary to go back to block 0 each time we do a group computation, nor is it necessary to re-read the table from disk for each computation. Once the current group is specified, vital information about it is read into memory. 

In the current version of Groups32, all the tables are stored in memory and the word >GROUP is replaced by an appropriate version.  The virtual memory scheme is not used, and it is not essential for the reader to understand how it is used.  It is, however, interesting that

1. there was such a mechanism for dealing with the limited memory of early computers and
2. code written to use this scheme can be updated fairly easily. 

Click for more information about virtual memory and the code for >GROUP.

: >GROUP ( n -- ) \ set GORD GBLK and GOFFS 
         DUP TO GNUM
         6 * IDXBLK BLOCK + DUP @ TO GORD
         2+ DUP @ TO GBLK 
         2+ @ TO GOFFS ;

[To run this on a 32-bit system using the original data file, the @ needs to be replaced by W@, which fetches a 16-bit value.]

We now have the group data stored, together with information needed to locate the start of a particular table.  Next we want to implement multiplication - which means to locate an element in a particular row and column of the table. If we number the rows and columns from 0 to Gord-1, the entry in the i-th row and j-th column will be located  i*Gord + j bytes from the start of the table.

Remember that we are storing group elements as letters A, B, C, …  that a computer is representing by ASCII codes  65, 66, 67, … . If we want to multiply B and C in the current group, we must first subtract 65 (the ASCII code for "A") to get the row and column, and then compute the location of the product in the table.

: 'ELE ( ele1 ele2 – addr )     \ compute address of product 
      ID - SWAP ID - GORD * +   \ offset from base address
      GBLK BLOCK GOFFS +        \ address of start of table
      + ;                       \ address of element

Now we can define a word to print the table of a group. We first define a word that takes two elements and returns their product:

: G*  ( ele1 ele2 - ele1*ele2 )   
      'ELE C@  ;

Notice we have named this word G* suggesting it computes the product of two elements in a group.

: .ELE  ( ele -- ) 
\ print element with a trailing space.
EMIT SPACE ;

The following word produces the limits for loops over all elements in the current group.

: GLIMITS ( -- u l )
\ loop limits to run through group
                 GORD  ID +  ID  ;

: TABLE   ( N -- )   >GROUP  CR
     2 SPACES GLIMITS
     DO  ." __"  LOOP CR
     GLIMTS DO   I .ELE  ." |"
            GLIMITS DO  J I G* .ELE LOOP CR
                          LOOP CR ; 

You can't usually tell much about a group by looking at its table. I have found that the ability to generate tables in various formats is a useful way to transport information to other computer programs.

b. Input and Output

At this point we have a way of representing and storing the main pieces of data for the program -- the group tables. We can "install" a group as the current group. We have defined the main "group theory" word, G*, which determines multiplication in the current group. We have the output word TABLE to display the table of a given group. In some sense, the word >GROUP is an input word: It allows us to specify the number of the group currently of interest. 

The next step is to develop words that compute group information by chasing around the table.  We need a way to input an element of the current group. We cannot, at this moment, type "B C G*"  to get the product of B and C in the current group.  We could, however, type  66 67 G*. WHY? First note that G* takes two parameters that are expected to be ASCII codes of upper case letters within the range of the current group.  The parameters for G* must be on the stack in advance.  If we type B C G*, the system will start reading from the left and will try to find B and C as words in the dictionary. If it cannot find them, it will try to interpret them as numbers in the current base (10).  So 66 67 G* will work -- and the letters won’t.

Here is what happens on the current Forth system (Win32Forth) running the original code:

8 >group  ok
B C G*
    Error: C is undefined

In this case, B is actually a word in the dictionary (having something to do with the editor) -- but its action is not to put 66 in the stack!  On the other hand, C is neither a word in the dictionary nor a recognized number. (Note 4)

Keep in mind that G* is expecting ASCII codes for group letters. An input format that requires the user to remember and put in these codes is not friendly. There are several ways to handle the input of group letters.

Input of Elements - method 1 (using a handler)

Forth is perfectly happy to work with strings that are not names for words in the dictionary (and not numbers):  We just precede them by a "handler," a word that reads a string from the following input and does something specific with it.

The Forth word ASCII (which is replaced by CHAR in the current Forth Standard) takes a following string and returns the ASCII code of its first character.  In the following example we use the word . (dot) to print the number on top of the stack (and remove it).

ASCII A . 65 
ASCII B . 66 
ASCII b . 98 
ASCII C . 67 
66 EMIT B
98 EMIT b

So, for example, we could say   ASCII B  ASCII C  G*  to multiply elements B and C.

In the 1990 version, I introduced a new handler, GETE:

: GETE BL WORD 1+ C@ ;

The Forth word WORD does not take parameters from the stack -- it reads the input stream. WORD, preceded by a delimiter, takes the next string from the input stream up to the delimiter and returns the address as a counted string.

So GETE gets the next word (up to blank) and returns its first character.  It is used just like ASCII but has a name that suggests that we are getting a group element.

Input of Elements - method 2 (making group elements dictionary words)

If we wish to use the simple syntax  B C G*  we could just make A, B, C, etc., words in the dictionary whose action is to put their ASCII codes on the stack.  The easiest way to do this is to make them constants:

65 CONSTANT A      66 CONSTANT B
67 CONSTANT C      68 CONSTANT D
69 CONSTANT E      70 CONSTANT F
71 CONSTANT G      72 CONSTANT H   etc.

There is a major disadvantage to this: The words I and J are the names used in Forth for loop indices. If they are redefined, they cannot be used with their original meanings. Any particular Forth implementation may already have some useful meaning attached to other letters. (Note 5)

A better approach is to use slightly different names, /A, /B, etc., for the group elements:

 65 CONSTANT /A      66 CONSTANT /B
 67 CONSTANT /C      68 CONSTANT /D
 69 CONSTANT /E      70 CONSTANT /F
 71 CONSTANT /G      72 CONSTANT /H   etc.

This allows the syntax  /B /C G* when typing from the keyboard.

c. Some First Procedures

: EORDER  ( ele -- ord )   ID  GLIMITS
      DO  OVER G*  DUP ID =
          IF 2DROP I ID - 1+ LEAVE THEN  
      LOOP ;

This computes the order of an element by taking powers until the identity is found.

   /A EORDER . 1 
      /B EORDER . 6 
      /C EORDER . 3 
      /D EORDER . 2 
      /F EORDER . 6 

  8 table
      ____________
      A |A B C D E F
      B |B C D E F A
      C |C D E F A B
      D |D E F A B C
      E |E F A B C D
      F |F A B C D E

: EORDER ID  
    GLIMITS DO
         ( x  x^n  )
    OVER 
    G*  
    DUP ID =
    IF 
      2DROP 
      I  ID  -  1+
      LEAVE 
    THEN  
  LOOP ;

: POWERS  GETE  ID  GLIMITS
      DO  DUP .ELE  OVER G*  DUP ID =
          IF 2DROP LEAVE THEN  LOOP ;

POWERS A A          
POWERS B A B C D E F 
POWERS C A C E 
POWERS D A D 
POWERS E A E C 
POWERS F A F E D C B 

4 >GROUP            
 /A EORDER . 1 
 /B EORDER . 2 
 /C EORDER . 2 
 /D EORDER . 2

5 >GROUP            
 /A EORDER . 1 
 /B EORDER . 4 
 /C EORDER . 2 
 /D EORDER . 4

:  ORDERS ( grp# -- )   >GROUP
          GLIMITS DO I EORDER . LOOP ;
       
  4 ORDERS 1 2 2 2 
  5 ORDERS 1 4 2 4
 

d. The Evolution of ORDERS

In this section I discuss several attempts to improve the functionality of ORDERS. The process illustrated here, where several versions of a word are produced, each improving upon the previous in some respect, is common. We always have the older version available for comparison – the system is never "broken" at any point. We try to write so that individual words can be improved without affecting other parts of the system.

The ORDERS command provides important information, but group letters may be rearranged in an isomorphism, so the orders of elements may be in a different order for two isomorphic tables. It may not be easy to see at a glance if two groups have the same number of elements of each order. It would also be much easier to compare two groups if the outputs were in a matching form. One approach would be to sort the list of orders of elements. A simpler approach, since we just want the number of elements of each order, is to define a new version of ORDERS that does book-keeping. We need an array to save the number of times each order occurs. Here we look at a way to build special types of array structures by allocating memory and producing words to access it.

I wrote the original version of Groups16 using F83, a 16-bit version of Forth (integers occupied 16 bits or 2 bytes) so a sequence of integers in memory had addresses 2 units apart. To allocate a block of memory for storage of up to 20 integers I used

CREATE OCNT 40 ALLOT

: 'OCNT  ( k – addr )  2* OCNT +  ;

: +OCNT  ( k --  )   'OCNT  1 SWAP +!  ;

: OCLEAR  OCNT 40 ERASE ;

CREATE OCNT 20 CELLS ALLOT
: 'OCNT  ( k – addr )  CELLS OCNT +  ;
: +OCNT  ( k --  )   'OCNT  1 SWAP +!  ;
: OCLEAR  OCNT 20 CELLS ERASE ;

:  ORDERS ( grp# -- )  >GROUP 
    OCLEAR  
    GLIMITS DO I EORDER +OCNT LOOP
           
    GNUM 3 .R  GORD 3 .R 2 SPACES
    20 1 DO
         GORD I MOD 0=
         IF I 'OCNT @ . THEN
       LOOP ; 

8 orders   8  6  1 1 2 2 
21 orders  21 12  1 3 8 0 0 0

: COMMA   ASCII , EMIT ; 
: QUOTES  ASCII " EMIT ;

4 orders 
Group number 4 of Order 4 
  1 elements of order  1:  A 
  3 elements of order  2:  B C D 
  0 elements of order  4:

5 orders
Group number 5 of Order 4
  1 elements of order  1:  A
  1 elements of order  2:  C
  2 elements of order  4:  B D

Producing this output requires saving not only the count but also the order of each element. The original code, as mentioned, had built-in assumptions that integers were 16-bit. We show both the original and modified version of the code for this final version of ORDERS.

CREATE OTABLE   40 ALLOT 
CREATE OCNT     40 ALLOT

:   'ORD   ( ele -- addr )
        ID - 2* OTABLE +  ;
:   'OCNT  ( i -- addr )
        2* OCNT +  ;
:   +OCNT  ( ord -- )
       'OCNT 1 SWAP +!  ;
:   ORD!  ( ord ele -- )
       'ORD !  ;
:   OCLEAR
       OTABLE 40 ERASE
       OCNT   40 ERASE ;

CREATE OTABLE  20 CELLS ALLOT
CREATE OCNT    20 CELLS ALLOT

:   'ORD   ( ele -- addr )
        ID - CELLS OTABLE +  ;
:   'OCNT  ( i -- addr )
        CELLS OCNT +  ;
:   +OCNT  ( ord -- )
        'OCNT 1 SWAP +!  ;
:   ORD!  ( ord ele -- )
        'ORD !  ;
:   OCLEAR
        OTABLE 20 CELLS ERASE
        OCNT   20 CELLS ERASE ;

Using these auxiliary words, the new definition of ORDERS is

: ORDERS  ( grp# --  )  CR >GROUP
    ." Group number " GNUM .
    ." of Order " GORD .  CR  OCLEAR
  GLIMITS  DO  
      I EORDER DUP +OCNT I ORD!  LOOP
      GORD 1+ 1 DO  GORD I MOD 0=
      IF 3 SPACES I 'OCNT @ 2 .R
         ."  elements of order "

           I 2 .R ." :   "
         GLIMITS DO I 'ORD @ J =
             IF  I .ELE THEN
         LOOP  CR
      THEN  LOOP ;

: Orders  ( grp# --  )   CR >Group
   ." Group number " Gnum .
   ." of Order "     Gord .  CR
       Calc-Orders  Prt-Orders  ;

Gnum

Gord

#elements of each order

25

12

" 1  1  2  2  2  4"

24

12

" 1  1  2  6  2  0"

22

12

" 1  3  2  0  6  0"

20

12

" 1  3  8  0  0  0"

21

12

" 1  3  8  0  0  0"

Groups #20 and #21 are, therefore, the first groups in the original set that could be isomorphic. To show that they are isomorphic, we need to display an isomorphism between them. A first attempt at displaying an isomorphism is to create a mechanism for showing what happens to a table under a mapping of elements.  We imagine a mapping X that sends the letters A, B, C, … to the same letters in a permuted order.

CREATE 'XG  20 ALLOT   \ This will contain the images of A,B,C,…


: XG   ( ele - xele )  \  given ele this displays the image xele 
      ID - 'XG + C@ ;


: XG'  ( xele - ele )     \  this finds the inverse image of a letter
      GLIMITS DO I XG OVER =
         IF DROP I LEAVE THEN LOOP ;


: XG*  ( x1 x2 - x3 )  \ Multiply in image group
      XG' SWAP XG' SWAP G* XG  ;


: >XG   ( follow by string in letters )
       \  this allows input of the mapping
      BL WORD COUNT 'XG SWAP CMOVE ;


: RTABLE  ( n -- )  \  This prints the table of the image group
      >GROUP   CR
      2 SPACES  GLIMITS DO  ." __"  LOOP  CR
      GLIMITS DO   I .ELE ." |"
         GLIMITS DO  J I XG* .ELE LOOP CR
             LOOP CR ;

>XG ACBD

5 TABLE
  ________
A |A B C D
B |B C D A
C |C D A B
D |D A B C

 _A_C_B_D
A|A C B D
C|C B D A
B|B D A C
D|D A C B

5 RTABLE
  ________
A |A B C D
B |B A D C
C |C D B A
D |D C A B

We have applied the isomorphism X and obtained the resulting table.  Can we apply an isomorphism like this to Group #20 and transform its table to that of Group #21?

There are 12! = 479,001,600 candidates for X. However, if X is an isomorphism from group 20 to group 21, it must send A to A, it must send an element of order k to an element of order k, and it must send a product in the first group to the product of the images in the second group. (In fact, the map is determined by what it does to the generators -- but we do not yet have tools to determine the generators.)

20 orders
Group number 20 of Order 12
    1 elements of order  1:   A
    3 elements of order  2:   D I K
    8 elements of order  3:   B C E F
                              G H J L
    0 elements of order  4:
    0 elements of order  6:
    0 elements of order 12:

21 orders
Group number 21 of Order 12
    1 elements of order  1:   A
    3 elements of order  2:   E I K
    8 elements of order  3:   B C D F
                              G H J L
    0 elements of order  4:
    0 elements of order  6:
    0 elements of order 12:

20 table
 ________________________
A |A B C D E F G H I J K L
B |B C A E F D H I G K L J
C |C A B F D E I G H L J K
D |D G J A L H B F K C I E
E |E H K B J I C D L A G F
F |F I L C K G A E J B H D
G |G J D L H A F K B I E C
H |H K E J I B D L C G F A
I |I L F K G C E J A H D B
J |J D G H A L K B F E C I
K |K E H I B J L C D F A G
L |L F I G C K J A E D B H

21 table
 ________________________
A |A B C D E F G H I J K L
B |B C A E F D H I G K L J
C |C A B F D E I G H L J K
D |D I L G C K A F J B H E
E |E G J H A L B D K C I F
F |F H K I B J C E L A G D
G |G J E A L H D K B I F C
H |H K F B J I E L C G D A
I |I L D C K G F J A H E B
J |J E G L H A K B D F C I
K |K F H J I B L C E D A G
L |L D I K G C J A F E B H

If we map B to B, then we must map C to C, since C is B*B in both groups.  D must get mapped to an element of order 2.  Let’s try D to E. B*D is F in Group 20, B*E is F in group 21 so we should map F to F.  Continue working in this fashion.

   >XG ABCEFDGHIJKL
20 RTABLE
A |A B C D E F G H I J K L
B |B C A E F D H I G K L J
C |C A B F D E I G H L J K
D |D I L G C K A F J B H E
E |E G J H A L B D K C I F
F |F H K I B J C E L A G D
G |G J E A L H D K B I F C
H |H K F B J I E L C G D A
I |I L D C K G F J A H E B
J |J E G L H A K B D F C I
K |K F H J I B L C E D A G
L |L D I K G C J A F E B H

This can be seen to be the same as the table for group 21.  We have, therefore, shown that groups 20 and 21 are isomorphic by displaying an isomorphism between them.