Newsgroups: comp.lang.scheme
Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!zaphod.mps.ohio-state.edu!think.com!mintaka!bloom-beacon!dont-send-mail-to-path-lines
From: gyro@cymbal.reasoning.COM (Scott Layson Burson)
Subject: Logical operations on integers.
Message-ID: <9104150119.AA03535@cymbal.reasoning.com.>
Sender: daemon@athena.mit.edu (Mr Background)
Reply-To: Gyro@reasoning.com
Organization: The Internet
References: <CARLTON.91Apr12234636@husc10.harvard.edu>
Date: 15 Apr 91 01:19:18 GMT
Lines: 67

   Date: 13 Apr 91 03:46:36 GMT
   From: david carlton <carlton@husc10.harvard.edu>

   In article <9104090602.AA06996@cymbal.reasoning.com.> gyro@cymbal.reasoning.COM (Scott Layson Burson) writes:
      Of course [bitwise logical operations] make sense on bignums.  One way to
      think about it is that the sign bit of an integer, whether fixnum or
      bignum, is repeated infinitely to the left.  Another way is simply to
      define (assuming two's complement)

	(lognot x) = (- -1 x)

      In one's complement, of course, LOGNOT and unary negation are the same
      operation.

   All right - I misspoke.  None of them really make sense, and and or no
   more than not.  All three of them are implementation-dependent -
   operations which are defined on the bits of integers depend on the
   representation of those bits in the computer, and since bignums have
   (in my opinion, at least) no one representation that is inherently
   superior to all others, I don't think that it really makes sense to
   define bitwise operations on them.

Bignums are not different from fixnums in this regard.

Common Lisp defines (quite reasonably, in my opinion) that all bitwise
operations shall behave as if the underlying representation were two's
complement.  That doesn't mean that the implementation of either fixnums or
bignums has to be two's complement; only that if it is not, the appropriate
modification has to be made to the algorithm.  I don't know what IEEE and R4RS
have to say about this -- does anyone?

				       Yes, you can define them in the
   manner that you suggested, but why define them at all?

The point, as ever, is to eliminate semantic differences between fixnums and
bignums.  Why *not* define them?

							   Bitwise
   operations are (in my experience) used mainly as a manner for packing
   data, and are only particularly useful if they are efficient.  But in
   Scheme, it is a good deal less likely that these will be efficient for
   bignums, and since there are no guarantees about the size of numbers a
   given implementation will support, you can't even use them to portably
   pack data.  (And, for that matter, packing data is something fairly
   foreign to the Scheme mindset.)

You are forgetting about the integer representation of sets (more precisely, of
subsets of a given set).  This is very important and valuable in certain
applications.  The additional overhead involved in consing bignums is trivial
compared to the cost of less efficient representations such as lists of
members.

				     I really don't think that the
   standard should define bitwise operations for bignums (and hence for
   integers, since fixnums haven't really made it into the standard yet)

I think this is a very curious position.  These operations are utterly trivial
to implement by comparison with, e.g., bignum multiplication and division.
They add only minimally to the size and complexity of a Scheme implementation.

A position you could take which would in my opinion be more reasonable would be
to oppose the definition of bitwise operations on negative integers (either
fixnums or bignums).  I would still disagree, however, inasmuch as the
corrections required to give them two's complement behavior in a one's
complement or sign-magnitude implementation are quite simple.

-- Scott