Porting programs from Modula 2

[Marc Brandis]

In article <646 at caslon.cs.arizona.edu> dave at cs.arizona.edu (Dave P. Schaumann) writes:
>As for sets, you will have to write a group of subroutines to deal with that.
>The traditional way is to use an array of character (one for each set element),
>or a bit-vector (if space is a critical issue).
>

The bit-vector solution is the preferable solution even if space is not a
critical issue. It is neither simpler nor faster to use the array of character
approach. The operations "+", "*", "-", "/" on SETs as well as the comparison
become a loop with the array solution, while they are simple operations when
the bit-vector approach is used. Look at the following case for "+":

	Modula-2:
	
	VAR a, b, c: SET;
	BEGIN
	  a := b+c

	C with array approach:

	char a[n], b[n], c[n];
	int i;

	for (i = 0; i < n; i++) a[i] = b[i] | c[i];

	C with bit vector approach:

	unsigned long a, b, c;

	a = b | c;

The same holds for the assignment of SETs. The other set of operations, INCL,
EXCL and the test IN can be coded as follows (example for IN):

	Modula-2:

	VAR a: SET; i: INTEGER;
	BEGIN
	  IF i IN a THEN ...

	C with array approach:

	char a[n]; int i;
	
	if (a[i]) ...

	C with bit vector approach:

	unsigned long a; int i;

	if ((1 << i) & a) ...

The array approach will typically be translated to an indexed load followed
by a compare against zero followed by a branch. The bit-vector approach will
translate to the load of an immediate value followed by a shift, an and and 
a branch (if all operands are in register, which is reasonable for modern
machines and compilers). On many machines, the second sequence will not be
slower than the first one. Depending on the architecture of the machine, the
bit-vector version can be even improved. If the shift operation sets a 
condition code bit for a special bit in the word (e.g. the sign bit or the 
least significant bit), you can directly shift a and get the result.


Marc-Michael Brandis
Computer Systems Laboratory, ETH-Zentrum (Swiss Federal Institute of Technology)
CH-8092 Zurich, Switzerland
email: brandis at inf.ethz.ch