Formal comment #199 (defect)

right shift formula and bit-field signedness
Reported by: 	Daniel Villeneuve
Version: 	5.92

R6RS component: Exact bitwise arithmetic

SUMMARY

Several fixes to the bitwise library.

DESCRIPTION

This comment covers several (9) items, not all with the same importance.

1) I assume that the intent of all bitwise procedures is to return
   exact integers. If this is so, the formula used to define
   bitwise-arithmetic-shift does not cover the case of negative ei2. A
   possible one would be:

(->exact (floor (* ei1 (expt 2 ei2))))

This is akin to sign-extending right shift, so

(bitwise-arithmetic-shift -6 -1) => -3
(bitwise-arithmetic-shift -5 -1) => -2
(bitwise-arithmetic-shift -4 -1) => -2
(bitwise-arithmetic-shift -3 -1) => -2
(bitwise-arithmetic-shift -2 -1) => -1
(bitwise-arithmetic-shift -1 -1) => -1

2) Bit fields are always defined using a finite number of bits,
   contrary to 2's complement representation which implicitly uses an
   infinite extension of $0$ bits or $1$ bits to the left.

Either a) we specify that the leftmost value bit of a bit-field is
understood to be repeated infinitely to the left, or b) that $0$ bits
are used no matter the value of the leftmost bit. With a), we can have
negative values as output to bitwise-bit-field but we have problems
with 0-bit and 1-bit bit fields, with shifting and masking, etc. With
b), we only have positive bit fields.

I suggest that b) is more useful/intuitive:

  (bitwise-bit-set?
    (bitwise-bit-field #b00101100 0 6) 8) => a) #t; b) #f

  (bitwise-arithmetic-shift-right
    (bitwise-bit-field #b00101100 0 6) 4) => a) -2; b) 2

  (bitwise-arithmetic-shift-right
    (bitwise-bit-field #b00101100 0 7) 4) => a)  2; b) 2

Either way, a clarification on the signedness of bit-fields should be
added to the introduction.

3) The domain of bitwise-rotate-bit-field should restrict ei2 and ei3
   as for the other bit-field procedures, and ei4 can be left
   unrestricted (though non-negative), as this is both intuitive and
   supported by the proposed implementation.

4) The primitive bitwise-zero? is used in the implementation of
   bitwise-bit-set? but is not defined. It should be replaced with
   zero?.

5) The primitive bitwise-negative? is used in the implementation of
   bitwise-length but is not defined. It should be replaced with
   negative?.

6) The spec of bitwise-length should start as "Returns ..." instead of
   "These procedures return ...".

7) The spec of bitwise-bit-set? should start as "Returns ..." instead
   of "Otherwise, returns ...". There seems to be an extra newline
   after the domain.

8) General: replace "The XXX procedure returns ..." by "This procedure
   returns ..." when unambiguous, for homogeneity.

9) In the spec of bitwise-reverse-bit-field, replace "from the ei1" by
   "from ei1".


RESPONSE:

The editors accept all of this comment's recommendations,
including alternative 2b) over 2a).

Note that (bitwise-arithmetic-shift -5 -1) should actually
evaluate to -3 rather than -2, which we assume is a typo in
the comment.