STRUCTURED PROGRAMMING

Sifting for Sharks' Teeth

  
TYPE     
	CharSet = SET OF Char;

Uh-uh, said the compiler. Sets in Modula-2 may have no more than 16 elements.

This is a serious semantic bite in the buns. Sets work well for me and I use them a lot, especially for building systems to handle characters moving from one place to another, as from the keyboard to the screen or from a serial port to the screen or to a disk file. Like Maxwell's Demon, a set is a filter that can pass odd characters among the ASCII throng while denying passage to others in a group just as odd. Consider the elegance of this classic construct:

  
IF AnswerChar IN ['Y','y']      
	THEN DoIt ELSE DontDoIt;

The alternative is this:

  
IF (AnswerChar = 'Y') OR      
   (Answer-Char = 'y')      
   	THEN ...

You might argue that the second form resolves to fewer machine instructions, and I'd argue back that you're rarely going to have to execute 17,000 such tests in a tight loop. Furthermore, what about this:

  
IF IncomingChar IN WhiteSpaceSet                       
	THEN ...

There's simply nothing like sets for character filters such as this. It was just possibly possible in some cases to pull tricks with subranges of fewer than 16 characters, but the whole notion offended me: Niklaus Wirth threw character sets out the window to make it easier to implement Modula-2. There are maybe two or three hundred potential Modula-2 compiler implementors in this world. There are hundreds of thousands of potential Modula-2 programmers. One suspects he skipped Marketing 101 as an undergrad.

About then Turbo Pascal happened, and Modula-2 slipped into eclipse for some years. Logitech held the torch alight all that time, but their product, while solid, was complex and slow and admittedly intended for internal use. It wasn't until JPI introduced TopSpeed Modula-2 that the language showed any serious life. Soon afterward, the Stony Brook compiler made its debut, and I've begun to do some serious work in Modula again.

The reason is pretty simple: TopSpeed and Stony Brook have done the Awful Thing: Extended Modula-2 by allowing sets to have as many as 65,536 elements. Horrors. You might not be able to port your dog kennel management package to the Lilith operating system. It is to cry real tears.

Duntemann's One Law of Portability

Remember this, chilluns: For any platform with I/O more complex than a batch system, semantic differences between platforms makes portability impossible. In other words, even if you wrote your character-based PC kennel manager in absolutely standard Modula-2, could you port it to the Macintosh? If you had written it for multiple terminals under Unix, could you port it to DOS? Get real -- the effort spent resolving semantic conflicts would far outweigh trifles like the shape of an IF statement.

So let's quit arguing about something that's never been worth a plugged nickel outside of academe anyway.

Watch the Corral, Not the Cows!

A set is an abstraction of a group of values, indicating whether one or more of those values are present or not present. It's like a corral on a farm with seven cows; at any given time a cow is either in the corral or not. The cows are in no particular order within the corral. They're either there or else out making things for the unwary to step in.

It's important to remember that the set is not the cows; the set is the corral. It's still a set even when it is empty.

In Modula-2, a set is defined in terms of some ordinal type or subrange of an ordinal type, including enumerations such as the insufferable list of colors that every writer on the subject (myself included) has used in books explaining the concept:

TYPE
   Colors = (Red, Orange, Yellow, Green, Blue, Indigo, Violet);
   WarmColors = [Red . . Yellow];
   ColorSet = SET OF Colors;
   WarmSet = SET OF WarmColors;
   CardSet = {0..65535}
   CharSet = SET OF CHAR; (* Yay! *)

Beneath it all, in physical memory, a set is a bitmap. There is one bit in the set for each value that may legally be present in the set. Each bit carries one Boolean fact: Whether the value that the bit stands for is present or not present in the set. Adding a value to the set is done by raising that value's bit to binary 1. Removing a value from the set is done by changing that value's bit back to a binary 0.

A "full" set (that is, one having all values present) is not one bit larger than an empty set. Again, the set is the corral, not the cows!

Set Operators

There are a number of operators and standard procedures that work on sets in Modula-2. The two most obvious are INCL, which places a value in a set, and EXCL, which removes a value from a set. These are not present in Pascal. IN is still there, doing exactly what it does in Pascal: Return a Boolean value indicating whether the value on the left is present in the set on the right. Ditto >= (set inclusion, right in left), and <= (set exclusion, left in right) which do much the same but for whole sets: >= returns TRUE if all values of the set on its right are present in the set on its left; and <= returns TRUE if all values in the set on its left are present in the set on its right.

There are actually only four operators that are true set operators in that they act on sets and return sets: + (set union) - (set difference) * (set intersection) and / (set symmetric difference). Of these, only the first three are present in Pascal.

Set union of two sets returns the set that contains all the elements present in both of the sets taken as one. Set intersection of two sets returns the set of values that are present in both sets, but none of those values that may be present in one or the other but not both.

Set difference is a little trickier; my Pascal prof explained it badly (getting it mixed up with symmetric difference, see below) and I misunderstood it through ten years and two editions of my book. Set difference of two sets returns the set that consists of the elements in the set on the left once those in the set on the right have been removed from it.

Basically, set difference is a way of pulling several elements out of a set without using EXCL to do it one element at a time:

  
{'A'..'Z'} - {'M'..'Z'}

This set expression returns the set {'A'..'L'}. (Keep in mind that Modula-2 uses curly brackets for set constructors rather than straight brackets.)

Finally, set symmetric difference (which is not in any Pascal implementation I'm aware of) is rather like set union turned inside out. The symmetric difference of two sets is the set of all elements that are present in one or the other set, but not in both sets. In a sense, the symmetric difference of two sets is what the two sets don't have in common; for example, what remains once their intersection (overlap) has been removed.

Among them, these operators allow you to do just about anything with a set that you'd ever want to do. And now that sets can have up to 65,535 elements in Modula-2, that's a lot.

The Naked Set

Wirth's original language definition did not hard-code 16 as the number of elements in a set. The number of elements in a Modula-2 set was originally defined as the number of elements in the machine word used by the system for which the compiler was implemented. In other words, in a system with a 32-bit word there would be 32 possible elements in a Modula-2 set.

This makes those limited set operations very easy to implement, and very fast, because they can be done using the native bit-manipulation instructions present in all modern-day CPUs. Remember that sets are bitmaps. Furthermore, the four true set operators bear a certain uncanny functional resemblance to certain logical operators such as AND, OR, and XOR.

OR the bits of two sets together and whammo, suddenly you have the union of the two sets. AND the bits of two sets together, and what remains is the intersection of the two sets. AND the bits of one set with the complement (reversed) bits of another set, and you remove the bits of the complemented set from the other set, that is, set difference. Finally, XOR the bits in two sets together and what's left are the bits that are present in one set or the other but not in both sets, since XOR drives identical bit pairs to 0. Voila: Symmetric set difference.

This is, of course, exactly what Wirth intended, and he intended for it all to happen within the accumulator of the host CPU, ensuring speed and minimal fussing. Happily, in this brave new world of fast global optimizing compilers (Stony Brook's is fabulous) we can have it both ways: When we're fiddling small sets we can do it fast at one shot inside the accumulator; when we're fiddling big sets we can do it a word at a time and take the performance hit.

Now, Wirth defined a specific kind of set that has no true analog in Pascal: BITSET, a standard type supported in all Modula-2 compilers. A BITSET is a machine word used as a bitmap. All of the set operators operate on BITSET values. A BITSET's nominal values are 0 .. 15, but these are bit numbers more than values. A BITSET is thus a sort of naked set, in which the bitmap nature of the set is laid bare and can be manipulated directly. A bit in a BITSET does not abstract a color, or a character, or a cardinal number, or a cow; a bit in a BITSET represents a bit, period.

Twiddling Bits in Other Types

With very little futzing, this fills an apparent gap in Modula-2: The lack of explicit bit-manipulation facilities. Turbo Pascal has explicit bitwise AND, OR, NOT, and XOR operators for numeric ordinal types, and it can also shift bits in numeric ordinal values with its SHR and SHL operators. Modula-2 has none of these ... or does it?

It does ... but they only operate on values of type BITSET.

No problem -- just ask Pizza Terra. (For those unfamiliar with the reference, see my May 1989 column.) Modula-2 has explicit type casting (which Wirth calls type coercion), so if you want to fiddle bits in type CHAR, cast type CHAR onto type BITSET, and fiddle away! Any type can be cast onto any other type of identical size, and there are transfer functions such as Ord to cast 8-bit types like CHAR and BOOLEAN onto 16-bit types like CARDINAL.

For example, to AND a CARDINAL variable MyCard with the value 128, you could do this:

  
NewCard := CARDINAL(BITSET          
	(MyCard) * BITSET (128));

Here, MyCard and the value 128 are both cast onto BITSETs, which are then ANDed together by using the set intersection operator, which is equivalent (on a bit level) to AND. Finally, the result of the set intersection operation is cast back onto a CARDINAL for assignment to the CARDINAL variable NewCard.

This works ... but it sure as hell isn't obvious. Unfortunately, in Modula this is how the game is played. Better to disguise all this arm-twisting of types (coercion is such a lovely word!) behind some procedures with more mnemonic names. This is what I've done in the listings for this column, which present a Modula-2 module called Bitwise. Listing One, page 150, is the definition module for Bitwise, and Listing Two, page 150, is the implementation module.

Bitwise provides function procedures to perform bitwise AND, OR, XOR, and NOT operations. (See Table 1.) Note that the capitalization is different from that used here in the descriptive text, in order to differentiate my procedure And from the existing (and incompatible) Boolean logical operator AND. (Case is significant in Modula-2, and this is the first time in my career I've caught myself being glad. Crazy world, ain't it?) Additionally, Bitwise contains procedures to set, clear, and test individual bits, and also to shift values right or left by up to 16 bits. This suite of routines provides roughly the same bit-banging power you get stock in Turbo Pascal. This seems to be the lot of Modula-2 programmers: To perpetually build what those Turbo guys have come to take for granted!

Table 1: Relating bitwise operators to set operations

  Bitwise operators                     Set operation
  -------------------------------------------------------------

  AND                *                  Intersection
  OR                 +                  Union
  XOR                /                  Symmetric difference
  NOT                {0..15} - BITSET   "Full" set - target set

The formal parameters for all of the routines in Bitwise are type CARDINAL, because CARDINAL is the unsigned 16-bit numeric type in Modula-2, equivalent to Word in Turbo Pascal. It's a good basic foundation upon which to cast all other ordinal types in Modula-2. (And it's used quite a bit by itself.) If you want to set bit number 3 in a character, for example, you could do this:

  NewChar := CHAR(SetBit(ORD('A'),3));

The ORD transfer function casts the character value onto a CARDINAL value for passing to the SetBit function procedure, and finally the CARDINAL value returned by SetBit is cast back onto a character for assignment to NewChar.

Read over the code implementing Bitwise and it all makes sense to you. Again, understand type casting/coercion and you've got it in your hip pocket.

When Words Runneth Over

There is something a little bit hazardous about Bitwise. The SHR and SHL routines can cause overflow errors if you shift bits to the extent that 1-bits roll out of either side of the 16-bit word in which they exist. Stony Brook Modula-2 code checks for overflow errors and will crash your program when you shift bits out of the word they live in.

Now, shifting bits off the edge of their word is not necessarily a bad thing. Sometimes you do it deliberately to get rid of the bits in question. There's nothing inherently damaging about it, because on a machine level the bits get shunted first into the carry flag and then off into nothingness. (What we affectionately call "the bit bucket.") Adjacent data is never overwritten, no matter if we try to shift a bit by (a meaningless) 245 positions.

The way out is to turn off overflow error checking. Enter here one of my major arguments with Modula-2: For portability's sake (gakkh!) there are no compiler toggles. Turbo Pascal has a whole raft of them, things like {$R-} and so on. The situation would seem to call for bracketing the SHR and SHL routines between compiler toggles that switch overflow checking off only for the duration of the routine, then on again once the routine terminates.

Sorry, Charlie. As every good tuna fish knows, compiler toggles are implementation dependent and destroy the prospects for portability. Lord knows, we can't have that, now, can we? The best that can be done with the Stony Brook compiler is to turn off overflow checking entirely within the Bitwise module by changing the compile options on a by-module basis. Be sure to do this when you compile and use Bitwise! If you're using a Modula compiler in which overflow checking cannot be turned off, you'd better add safety belts to any code that uses SHL and SHR.

The Boss DOS Book

There is a certain type of book I call a "category killer;" it's the book on a certain subject and tends to keep other books of its type from being published. One of these is Ray Duncan's Advanced MS-DOS (Microsoft Press), a book that has never been very far from my left hand while sitting in this particular chair. I'm pleased to report that Ray has company, in the form of Que Corporation's DOS Programmer's Reference, by Terry Dettmann. On 892 pages Terry has managed to summarize every BIOS function through PS/2, every DOS call through V4.0, all mouse function calls, all EMS function calls, and a blizzard of other information including low-level disk structure, device driver and interrupt programming, serial port programming, and lots more.

The very best part about this book, however, may well be its index. Having 892 pages of information is small comfort if you can't find anything when you need it in a hurry. The index occupies 33 pages, with about 100 citations per page, set small in two columns. Everything I tried to look up was either indexed or not covered in the book. (And things that weren't covered really shouldn't have been anyway, like VGA hardware architecture details.)

Products Mentioned

Memory Commander V Communications 3031 Tisch Way, Ste. 802 San Jose, CA 95128 408-296-4224 $129.95

Invisible RAM Invisible Software 1165 Chess Drive, Ste. D Foster City, CA 94404 415-570-5967 $39.95

Unibind Unibind Systems 7900 Capwell Drive Oakland, CA 94621 415-638-1060 Various configurations and prices Contact the vendor for specifics

Desktop Stereo Optronics Technology P.O. Box 3239 Ashland, OR 97520 503-488-5040 $199

DOS Programmer's Reference, 2nd edition Terry Dettmann, revised by Jim Kyle Que Corporation, 1989 ISBN 0-88022-458-4 Softcover, 892 pages, $27.95

Altogether, the best hacker's book to cross my desk in a good long while. Get it.

Dredging the Channel

There are millions -- nay, tens of millions -- of DOS machines out there, and various research reports I've seen indicate that the greatest growth potential lies in machines of modest cost and capabilities: The "bare bone" 88 and 286 clones that fill Computer Shopper to a depth of 800+ pages every month. There are already 30 million of them (conservative estimate) and in another few years there could be as many as 100 million of them out there, plugging away. This is an utterly unbelievable market for software products, and yet the distribution channel has closed up to the point that a small-time operator (like most of us) has no chance to make those millions of people even aware of the existence of their products.

There has got to be a way. Any ideas? Pass them by me. I'll be talking about this subject in future months, and I'll share some guerrilla marketing concepts I've devised, and will discuss how the little guys can shove some very big rear ends out of their monopoly position in the retail channel.

Write to Jeff Duntemann on MCI Mail as JDuntemann, or on CompuServe to ID 76117, 1426.

STRUCTURED PROGRAMMING COLUMN by Jeff Duntemann [LISTING ONE]



(*---------------------------------------------------*)
(*                  BITWISE.MOD              *)
(*               Definition Module                   *)
(*                                                   *)
(*     Bit-manipulation routines for Modula-2        *)
(*                                                   *)
(*                            by Jeff Duntemann      *)
(*                            For DDJ : March 1990   *)
(*                            Last modified 11/25/89 *)
(*---------------------------------------------------*)


DEFINITION MODULE Bitwise;

PROCEDURE And(A,B : CARDINAL) : CARDINAL;

PROCEDURE Or(A,B : CARDINAL) : CARDINAL;

PROCEDURE Xor(A,B : CARDINAL) : CARDINAL;

PROCEDURE Not(Target : CARDINAL) : CARDINAL;

PROCEDURE SetBit(Target : CARDINAL; BitNum : CARDINAL) : CARDINAL;

PROCEDURE ClearBit(Target : CARDINAL; BitNum : CARDINAL) : CARDINAL;

PROCEDURE TestBit(Target : CARDINAL; BitNum : CARDINAL) : BOOLEAN;

PROCEDURE SHR(Target : CARDINAL; By : CARDINAL) : CARDINAL;

PROCEDURE SHL(Target : CARDINAL; By : CARDINAL) : CARDINAL;

END Bitwise.

[LISTING TWO]



(*---------------------------------------------------*)
(*                  BITWISE.MOD              *)
(*             Implementation Module                 *)
(*                                                   *)
(*     Bit-manipulation routines for Modula-2        *)
(*                                                   *)
(*                            by Jeff Duntemann      *)
(*                            For DDJ : March 1990   *)
(*                            Last modified 11/25/89 *)
(*                                                   *)
(*  NOTES ON THE CODE:                               *)
(*                                                   *)
(*  In all cases below, BitNum MOD 16 is used as a   *)
(* means of ensuring that BitNum will be in the      *)
(* range of 0..15.  MOD 16 divides by 16 but returns *)
(* the remainder, which cannot be over 15 when you   *)
(* divide by 16.                                     *)
(*---------------------------------------------------*)

IMPLEMENTATION MODULE Bitwise;

VAR
  I       : CARDINAL;
  TempSet : BITSET;


PROCEDURE And(A,B : CARDINAL) : CARDINAL;

BEGIN
  RETURN CARDINAL(BITSET(A) * BITSET(B));
END And;


PROCEDURE Or(A,B : CARDINAL) : CARDINAL;

BEGIN
  RETURN CARDINAL(BITSET(A) + BITSET(B));
END Or;


PROCEDURE Xor(A,B : CARDINAL) : CARDINAL;

BEGIN
  RETURN CARDINAL(BITSET(A) / BITSET(B));
END Xor;


PROCEDURE Not(Target : CARDINAL) : CARDINAL;

BEGIN
  RETURN CARDINAL({0..15} - BITSET(Target));
END Not;


PROCEDURE SetBit(Target : CARDINAL; BitNum : CARDINAL) : CARDINAL;

BEGIN
  TempSet := BITSET(Target);  (* INCL does not operate on expressions! *)
  INCL(TempSet,BitNum MOD 16);
  RETURN CARDINAL(TempSet);   (* Cast the target back to type CARDINAL *)
END SetBit;


PROCEDURE ClearBit(Target : CARDINAL; BitNum : CARDINAL) : CARDINAL;

BEGIN
  TempSet := BITSET(Target);  (* EXCL does not operate on expressions! *)
  EXCL(TempSet,BitNum MOD 16);
  RETURN CARDINAL(TempSet);   (* Cast the target back to type CARDINAL *)
END ClearBit;


PROCEDURE TestBit(Target : CARDINAL; BitNum : CARDINAL) : BOOLEAN;

BEGIN
  IF (BitNum MOD 16) IN BITSET(Target) THEN
    RETURN TRUE;
  ELSE
    RETURN FALSE;
  END;
END TestBit;


PROCEDURE SHR(Target : CARDINAL; By : CARDINAL) : CARDINAL;

BEGIN
  FOR I := 1 TO By DO
    Target := Target DIV 2;
  END;
  RETURN Target;
END SHR;


PROCEDURE SHL(Target : CARDINAL; By : CARDINAL) : CARDINAL;

BEGIN
  FOR I := 1 TO By DO
    Target := Target * 2;
  END;
  RETURN Target;
END SHL;


END Bitwise.