: 2^N ( n - 2^n ) \ integer with bit n set 1 SWAP 0 ?DO 2* LOOP ;: Singleton ( n - set ) 2^N ;: Contains ( set1 set2 - t/f ) \ TRUE if set1 contains set2 SWAP OVER AND = ;: Member? ( ele subg - t/f ) SWAP Singleton Contains ;: Member! ( ele subg -- subg' ) SWAP Singleton OR ;
Notice the use of "bitwise" operations AND and OR. 5 2 OR gives 7 while 5 2 AND gives 0.
5 ( 1 0 1 )
2 ( 0 1 0 )
Here is a word for printing a set:
: SubGrp. ( subg -- ) \ print subg
." { " 1 ( bit mask )
16 0 DO 2DUP AND \ check if bit is set
IF I .ELE THEN
2* \ left shift mask
LOOP 2DROP ." } " ;
Notice that the idea of representing sets (and subgroups) as arrays has been abandoned in favor of using a representation as integers. The word SubGrp. here is defined to print a subgroup represented as an integer -- it supercedes the early version of SG. in which a set is represented as an array -- but it has the same function.
: Set. SubGrp. ;
Here is a word for inputting a set. The definition uses some features of Forth compilation to make it "state smart" (i.e., it acts differently if the system is compiling). Notice that, when interpreting, this word produces an integer, which is put on the stack. When the system is compiling, it stores the integer in the definition. This definition is not included in Groups32, since the command completion interface used there prompts for input of sets. The details of this definition are beyond the scope of this article.
: { ( -- set ;;; interpret string up to } as a set )
0 \ start with empty set
ASCII } WORD \ get string up to }
COUNT 2DUP UPPER \ convert to upper case
0 DO DUP C@ ID - DUP 0 15 BETWEEN \ check if valid
IF ROT Member! SWAP \ set addr
ELSE DROP THEN 1+ \ next address
LOOP DROP
STATE @ IF [COMPILE] LITERAL THEN ; IMMEDIATE
Some basic set operations:
: Set- ( set1 set2 -- set1-set2 ) \ set difference OVER AND XOR ;: Set+ ( set1 set2 -- union ) \ set union OR ;: Set& ( set1 set2 -- intersection ) \ set intersection AND ;: #Set ( set -- #ele ) 0 SWAP BEGIN ( cnt n ) DUP WHILE 0 2 ( cnt lsb msb 2 ) UM/MOD ( cnt r n/2 ) >R + R> \ update cnt REPEAT DROP ;
In #Set we shift bits to the right by dividing by 2. The Forth word
UM/MOD ( ud un - ur uq )
takes a double precision unsigned integer and divides by a single precision integer. It produces an unsigned remainder and unsigned quotient. In each step in the loop we are dividing by 2, the remainder (0 or 1) is added to the count, and the quotient is used in the next step.
A double precision integer is represented by two stack elements; the top of the stack is the most significant part.
An important operation on subsets of a group is to form 
Here is the high-level Forth version:
VARIABLE Stemp : Stemp! ( ele -- ) Stemp @ Member! Stemp ! ;: Set* ( set1 set2 -- set1*set2 ) 0 Stemp ! For-All-Elements DO OVER I SWAP Member? IF ( first ele is member of set1 ) For-All-Elements DO I OVER Member? IF ( second ele is member of set2 ) J I G* Stemp! THEN LOOP THEN LOOP 2DROP Stemp @ ;