Evolution of a Computer Application

6a.iii. Details

We are storing the elements of a subgroup in SGtable.  The first byte of SGtable is the number of elements already in the table. The others are the stored subgroup elements (the data) in whatever order they have been generated. Let us say we have already found that elements B, F, and E are in the subgroup and have been found in that order. The SGtable will look like this:

The word SGtable puts the address of the table on the stack (marked addr).  The standard Forth word COUNT takes the address of a counted structure and returns the pair address_of_data and count.  Thus COUNT would return the pair addr1 3  in this case. The sequence COUNT + will take addr and return addr_end (the next available position at the end of the table).

We would like to add a new element to the table if it is not already there. We use a clever (but well known) trick to do this.  The strategy is to put the new element in the position at the end of the table and then scan to see if it is found.  It will be found, of course.

I am torn, in this section, between clarity and authenticity.  I have decided to present code in the form in which it appears in some of the transitional versions of the system. I have, however, presented the code with component sections separated by blank lines. For clarity, >SGtable should have been factored.  The structure is

: >SGtable ( ele -- )
  \ add ele to table if new
     DUP 
     Put_at_end
     Find_position ( pos )
     Found_at_end? ( t/f ) 
     IF Update-count THEN ;

There are obvious inefficiencies in the code:  SGsweep, for example, recomputes products that have already been computed.  It really should take only products with any newly added elements.  Remember, however, this code is intended to display a subgroup as elements are added from the keyboard -- so its speed is really limited by the input and output.

Auxiliary Words

 
CREATE SGtable 40 ALLOT
   
: SG.  SGtable COUNT 0 
     ?DO DUP C@ .ELE 1+ LOOP
     DROP CR ;

Print the subgroup

 
: SG@  ( k - ele[k] )
     SGtable 1+ + C@  ;

Return the k-th element, k = 0, 1, 2, ... .

 
:  SG-init  SGtable 40 ERASE  ;
   
:  >SGtable  ( ele -- )
  DUP  SGtable COUNT +   C!
             
  SGtable COUNT + 1+  
  SGtable 1+ 
  DO ( ele )
    I C@ OVER =  
    IF  DROP I LEAVE THEN  
  LOOP
             
  SGtable COUNT + =
  IF  SGtable C@ 1+ 
        SGtable C!  THEN  ;


Put the element at the end of the table.



Loop over data addresses.
Check if stored element is ele.
If so, put address where found on stack.

Check if found at end of table (where we stored it) -- if so, increment count of table.

 
: SGord ( -- sgord)
     SGtable C@  ;
   
: SG*  ( k1 k2 - prod )
    SG@ SWAP SG@ SWAP G* ;
   
: SGsweep  
   SGord 0= 
   ABORT"  Table is Empty "
   BEGIN  SGord
     SGord 0  DO  SGord 0 DO
         J I SG*  >SGtable
     LOOP LOOP
         SGord =  UNTIL  ;

Take products of existing elements in SGtable and add to table. Repeat this until no new elements are added.

Top Level Words

 
: SGfirst ( ele -- ) 
     SG-init >SGtable 
     SGsweep SG. ;

Use this for first element to initialize the table.

 
: SGnext ( ele -- )
     >SGtable SGsweep SG.  ;

Use this for remaining elements.