[m-dev.] for review: change semantics of integer shifts

[Fergus Henderson]

On 18-Mar-1999, Simon Taylor <stayl at cs.mu.OZ.AU> wrote:
> 
> Change the bit shift operators to perform checking to avoid
> implementation defined behaviour.
> 
> library/int.m:
> 	Add checking to `int:<<' and `int:>>'.
> 
> compiler/code_util.m:
> 	Replace `int:<<' and `int:>>' with `int:unchecked_left_shift' and
> 	`int:unchecked_right_shift' in the builtin table.
> 
> NEWS:
> 	Mention the changes to int.m.

This looks much better this time.
However, I have some suggestions about the library documentation.

> --- int.m	1998/01/23 12:33:19	1.52
> +++ int.m	1999/03/18 01:47:02
> @@ -106,14 +106,50 @@
>  :- func int rem int = int.
>  :- mode in rem in = uo is det.
>  
> -	% left shift
> +	% X << Y returns X left shifted by Y bits. 
> +	%
> +	% If Y is negative, X >> -Y is returned.
> +	%
> +	% If Y is greater than or equal to the
> +	% result of `int__bits_per_int/1', 0 is returned.
> +	% Vacated bit positions are filled with 0-bits.

I think that

	% Left shift.
	% X << Y returns X "left shifted" by Y bits.
	% To be precise, if Y is negative, the result is
	% X div (2^(-Y)), otherwise the result is X * (2^Y).

would be a better definition.

The behaviour in case of overflow should be the same as for
other operations; there should be a general section somewhere
at the top of the module discussing this.

> +	% X >> Y returns X (arithmetic) right shifted by Y bits.
> +	%
> +	% If Y is negative, X << -Y is returned.
> +	%
> +	% Otherwise, the vacated bit positions are filled with 1-bits if
> +	% X is negative or 0-bits if X is positive.
> +	% Note: this assumes two's complement arithmetic.
> +	% tests/hard_coded/shift_test.m will fail if this is not the case.
>  :- func int >> int = int.
>  :- mode in  >> in  = uo  is det.

The comment about tests/hard_coded/shift_test.m is 
a dangling comment, since tests/hard_coded/shift_test.m
does not exist and is not added by this change.

That comment is also not really appropriate for the library reference manual
(remember that everything in the interface of the library goes into the
library reference manual).
If you define the specification precisely, in terms of the mathematical
values rather than by talking about the bits (i.e. representation),

	% Right shift.
	% X >> Y returns X "arithmetic right shifted" by Y bits.
	% To be precise, if Y is negative, the result is
	% X * (2^(-Y)), otherwise the result is X div (2^Y).

then it's only the implementation which is assuming two's complement.
So the comment about assuming two's complement should go in the
implementation section.

> +	% unchecked_right_shift(X, Y) returns X (arithmetic) right shifted
> +	% by Y bits using the C '>>' operator.
> +	%
> +	% Vacated bit positions are filled with 1-bits if
> +	% X is negative or 0-bits if X is positive.
> +	% Note: this assumes two's complement arithmetic.
> +	% tests/hard_coded/shift_test.m will fail if this is not the case.
> +	%
> +	% The result is implementation defined if Y is negative,
> +	% or is greater than or equal to the result of `int__bits_per_int/1'.
> +:- func unchecked_right_shift(int, int) = int.
> +:- mode unchecked_right_shift(in, in) = uo is det.

It should be "the behaviour is undefined" rather than
"the result is implementation defined".

I suggest changing the documentation to

	% unchecked_right_shift(X, Y) is the same as X >> Y
	% except that the behaviour is undefined if Y is negative,
	% or greater than or equal to the result of `int__bits_per_int/1'.
	% It will typically be implemented more efficiently than X >> Y.

-- 
Fergus Henderson <fjh at cs.mu.oz.au>  |  "I have always known that the pursuit
WWW: <http://www.cs.mu.oz.au/~fjh>  |  of excellence is a lethal habit"
PGP: finger fjh at 128.250.37.3        |     -- the last words of T. S. Garp.