bevan@cs.man.ac.uk (Stephen J Bevan) (04/05/91)
To provide a reasonably portable implementation of Icon like character sets in Scheme I need the equivalent of CommonLisp's logical operations on integers i.e. logand, logior ... etc. As these sort of operations are not in Scheme, I'm going to add them to the Scheme I use. In an effort to maintain some sort of compatibility, I'd like to use the same name as any existing extensions. So, if these sorts of operations are in some Scheme implementations (e.g. T, CScheme, Chez, Mac ... etc.), what are they called? Regarding portability :- Shouldn't logical operations of this sort be included in a standard? Not necessarily in the base language, but perhaps something along the lines of ``if logical operations are provided they should be called X, Y, Z and they should do P, Q, R when applied to integers'' Note I don't advocate adding everything to the language (I know where Common Lisp is if I want it), but rather adding features that are difficult to or cannot be implemented using other Scheme primitives. For example I would like Icon like Csets. However, I don't advocate adding them to the language, as I can implement them as vectors of integers using logical operations on the integers. I would guess there are other things that could benefit from this sort of definition (not that I can think of any at the moment) thanks Stephen J. Bevan bevan@cs.man.ac.uk
jinx@zurich.ai.mit.edu (Guillermo J. Rozas) (04/07/91)
In article <BEVAN.91Apr5092119@panda.cs.man.ac.uk> bevan@cs.man.ac.uk (Stephen J Bevan) writes:
Path: ai-lab!mintaka!think.com!zaphod.mps.ohio-state.edu!sdd.hp.com!elroy.jpl.nasa.gov!decwrl!deccrl!bloom-beacon!eru!hagbard!sunic!mcsun!ukc!mucs!m1!bevan
From: bevan@cs.man.ac.uk (Stephen J Bevan)
Newsgroups: comp.lang.scheme
Date: 5 Apr 91 08:21:19 GMT
Sender: news@cs.man.ac.uk
Distribution: comp
Organization: Department of Computer Science, University of Manchester
Lines: 31
To provide a reasonably portable implementation of Icon like character
sets in Scheme I need the equivalent of CommonLisp's logical
operations on integers i.e. logand, logior ... etc.
As these sort of operations are not in Scheme, I'm going to add them
to the Scheme I use. In an effort to maintain some sort of
compatibility, I'd like to use the same name as any existing
extensions. So, if these sorts of operations are in some Scheme
implementations (e.g. T, CScheme, Chez, Mac ... etc.), what are they
called?
Regarding portability :-
Shouldn't logical operations of this sort be included in a standard?
Not necessarily in the base language, but perhaps something along the
lines of ``if logical operations are provided they should be called X,
Y, Z and they should do P, Q, R when applied to integers''
Note I don't advocate adding everything to the language (I know where
Common Lisp is if I want it), but rather adding features that are
difficult to or cannot be implemented using other Scheme primitives.
For example I would like Icon like Csets. However, I don't advocate
adding them to the language, as I can implement them as vectors of
integers using logical operations on the integers.
I would guess there are other things that could benefit from this sort
of definition (not that I can think of any at the moment)
thanks
Stephen J. Bevan bevan@cs.man.ac.uk
MIT CScheme (>= 7.0) provides a bit-string data type on which these
operations are defined, and procedures to convert between integers and
bit-strings and viceversa.
In addition (>= 7.1), for efficiency, it provides fixnum logical
operations as well.
They are all documented in the 7.1 MIT Scheme manual. Look for example,
for fix:lsh, bit-string-xor, and bit-string->signed-integer.freeman@argosy.UUCP (Jay R. Freeman) (04/07/91)
In article <BEVAN.91Apr5092119@panda.cs.man.ac.uk> bevan@cs.man.ac.uk (Stephen J Bevan) writes: >To provide a reasonably portable implementation of Icon like character >sets in Scheme I need the equivalent of CommonLisp's logical >operations on integers i.e. logand, logior ... etc. [...] > I'd like to use the same name as any existing >extensions. So, if these sorts of operations are in some Scheme >implementations (e.g. T, CScheme, Chez, Mac ... etc.), what are they >called? Pixie Scheme (shareware for the Macintosh) has these; I call them e::bit-and e::bit-not e::bit-or e::bit-shift-left e::bit-shift-right-arithmetic ; sign-extends e::bit-shift-right-logical ; shifts in zeros e::bit-xor The "e::" business is *not* part of a package system, it is just my convention for how I name extensions. I selected the "bit-" prefix rather than Common Lisp's "logic..." prefix, because strictly, the existing operations "and" and "or" *are* logic operations, hence the Common Lisp names might confuse someone. Each operation takes arguments that are integers, and requires that they be small enough to fit into the machine representation for a fixnum (garden-variety 32-bit). The operation returns a new fixnum obtained by performing the indicated bit operation. For the shifts, the number to be shifted is the first argument, and the number of bits by which to shift is the second. "E::bit-and", "e::bit-or" and possibly "e::bit-xor" might reasonably be defined to take more than two arguments; I happened to set them up to take exactly two. (There are different definitions of what the "xor" of three or more arguments ought to be, hence the qualifier.) I put these in mostly for my own use in developing a compiler: Pixie Scheme is a tagged-object Lisp, and built-in bitwise operations are invaluable for dealing quickly with tags. There are lots of other extensions that I found useful to implement. Many of them are system-dependent, and cannot be part of the standard simply because their existence and utility depends on what computer and what operating system the implementation runs on. Some of more general value might be: e::bound-instance? ; Takes a symbol, answers whether it has a ; value in any environment in scope. e::closed-port? ; Takes a port, answers whether it is closed. e::cons-with-continuation ; One flavor of "eval". e::exit ; Back to the operating system. e::full-gc ; Force a complete garbage collection. e::inf? ; Is the object an IEEE infinity? e::nan? ; Is the object an IEEE not-a-number? e::promise? ; Is the object a promise? e::reset ; Abort calculation, restart top-level loop. Other useful classes of operations might be ones to deal with the existence and non-existence of files, location and motion within the directory hierarchy, amount of main store used and remaining (before a garbage collection), storage class of certain objects (typically numbers), obtaining and changing the maximum length and depth to print lists and vectors, saving and restoring "worlds", inspecting and altering low-level data structures not normally seen by the user (this last for the curious, the demented, and the developer), and perhaps creating and using macros. Another handy class of entity -- not quite an operation -- is top-level loop variables, like Common Lisp's, which contain recent values of forms evaluated and values returned, for use by the hapless user who forgot to bind the value of an hour-long calculation to some place from which it could be recovered. Pixie Scheme has facilities for all of these, but I have no great claim to wisdom in the names I have chosen. -- Jay Freeman <canonical disclaimer -- I speak only for myself>
manis@cs.ubc.ca (Vincent Manis) (04/09/91)
Listening to this discussion of what to call logand gave me a thought: why not set up some sort of central registry of extensions? This registry could be organized as a file of entries, in the same format as R^nRS. The first person to design a particular extension would then document it in entry format, and submit it to the registry. Other implementors could then look at the registry, and implement those extensions they find to their taste. There would be no connotation of compliance in the registry; implementors would be free to select or reject, or even to change as they see fit, any specification they find therein. However, it would ensure that people didn't simply invent new syntax for things capriciously. Am I being hopelessly idealistic? -- \ Vincent Manis <manis@cs.ubc.ca> "There is no law that vulgarity and \ Department of Computer Science literary excellence cannot coexist." /\ University of British Columbia -- A. Trevor Hodge / \ Vancouver, BC, Canada V6T 1W5 (604) 228-2394
freeman@argosy.UUCP (Jay R. Freeman) (04/09/91)
In article <1991Apr8.181518.23292@cs.ubc.ca> manis@cs.ubc.ca (Vincent Manis) writes: >Listening to this discussion of what to call logand gave me a thought: >why not set up some sort of central registry of extensions? What!? You mean ... document our implementations!! Surely you jest!! > However, it would ensure that people didn't simply invent new >syntax for things capriciously. Shucks, that's most of the fun ... >Am I being hopelessly idealistic? Only in the real world ... -- Jay ":-)" Freeman <canonical disclaimer -- I speak only for myself>
carlton@husc10.harvard.edu (david carlton) (04/09/91)
In article <BEVAN.91Apr5092119@panda.cs.man.ac.uk> bevan@cs.man.ac.uk (Stephen J Bevan) writes:
To provide a reasonably portable implementation of Icon like character
sets in Scheme I need the equivalent of CommonLisp's logical
operations on integers i.e. logand, logior ... etc.
Shouldn't logical operations of this sort be included in a standard?
Not necessarily in the base language, but perhaps something along the
lines of ``if logical operations are provided they should be called X,
Y, Z and they should do P, Q, R when applied to integers''
Do these really make sense when operating on bignums? And and or I
can buy, at least when operating on non-negative bignums, but not not.
Of course, at least one of the standards mentions fixnums - maybe it
could encourage implementors to stick them in if the implementation
supports fixnums. I think that it would be a bit ugly, though.
david carlton
carlton@husc9.harvard.edugyro@cymbal.reasoning.COM (Scott Layson Burson) (04/09/91)
Date: 9 Apr 91 00:18:36 GMT
From: david carlton <carlton@husc10.harvard.edu>
Organization: Citizens for Boysenberry Jam
In article <BEVAN.91Apr5092119@panda.cs.man.ac.uk> bevan@cs.man.ac.uk (Stephen J Bevan) writes:
To provide a reasonably portable implementation of Icon like character
sets in Scheme I need the equivalent of CommonLisp's logical
operations on integers i.e. logand, logior ... etc.
Shouldn't logical operations of this sort be included in a standard?
Not necessarily in the base language, but perhaps something along the
lines of ``if logical operations are provided they should be called X,
Y, Z and they should do P, Q, R when applied to integers''
Do these really make sense when operating on bignums? And and or I
can buy, at least when operating on non-negative bignums, but not not.
Of course, at least one of the standards mentions fixnums - maybe it
could encourage implementors to stick them in if the implementation
supports fixnums. I think that it would be a bit ugly, though.
Of course they 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.
Here's a related puzzle: suppose one were to implement a language which
was like C except that it supported infinite-precision integers. (In C,
unsigned integers are integers mod 2^n where n is the word length.)
What would be the sensible semantics for unsigned integers given that
they can be of arbitrary precision? (It turns out that there is a
surprisingly reasonable answer.)
-- ScottAlan@lcs.mit.EDU (Alan Bawden) (04/11/91)
Date: Mon, 8 Apr 91 23:02:43 PDT From: Scott Layson Burson <gyro@cymbal.reasoning.com> ... What would be the sensible semantics for unsigned integers given that they can be of arbitrary precision? (It turns out that there is a surprisingly reasonable answer.) I'm not confident that there is a -unique- sensible semantics, but the 2-adic integers is certainly -one- sensible semantics. Indeed, it would be easy (in principle) to extend the domains of the logical operations to include not just all real integers, but all real rationals of the form p/q where q is odd. It might be harder to support the full 2-adic ring of integers, which includes things like sqrt(17). While I -can- compute (LOGIOR 2/3 3/5) = -7/15 I don't actually know if (LOGIOR (SQRT 17) 3/5) corresponds to any real number or not. (I was tempted to say that if it did, it would have to be irrational, but I now realize I can't even show that!)
carlton@husc10.harvard.edu (david carlton) (04/13/91)
In article <9104090602.AA06996@cymbal.reasoning.com.> gyro@cymbal.reasoning.COM (Scott Layson Burson) writes:
[ I write, talking about logical operations on integers: ]
Do these really make sense when operating on bignums? And and or I
can buy, at least when operating on non-negative bignums, but not not.
Of course, at least one of the standards mentions fixnums - maybe it
could encourage implementors to stick them in if the implementation
supports fixnums. I think that it would be a bit ugly, though.
Of course they 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. Yes, you can define them in the
manner that you suggested, but why define them at all? 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.) And the only uses that I can think of
them that make much sense when you are thinking of numbers as
mathematical abstractions, rather than a sequence of bits, are special
cases of quotient and remainder. 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)
any more than it should for floating-point numbers (which at least
have a representation that is encouraged, though not required, by the
standard.)
david carlton
carlton@husc9.harvard.edu
Very little immediate tradition lies behind _Le Sacre du
printemps_, however, and no theory. I had only my ear to help
me; I heard and I wrote what I heard. I am the vessel through
which _Le Sacre_ passed.
- Igor StravinskyAlan@lcs.mit.EDU (Alan Bawden) (04/13/91)
Date: Wed, 10 Apr 91 21:24:53 EDT
From: Alan Bawden <Alan@lcs.mit.edu>
Date: Mon, 8 Apr 91 23:02:43 PDT
From: Scott Layson Burson <gyro@cymbal.reasoning.com>
...
What would be the sensible semantics for unsigned integers given that
they can be of arbitrary precision? (It turns out that there is a
surprisingly reasonable answer.)
I'm not confident that there is a -unique- sensible semantics, but
the 2-adic integers is certainly -one- sensible semantics.
Since comparing notes with Scott reveals that we had different notions in
mind, allow me to explain myself:
2's-complement arithmetic is normally defined over only those semi-infinite
bitstrings that are -eventually- always 0 or always 1. The 2-adic numbers
are the set of -all- semi-infinite bitstrings with arithmetic defined in
exactly the same way. So we have:
3 = [0]11 ; "[]" indicates repetition
-5 = [1]011
11 = [0]1011
as usual, but we also have beasts like:
X = [01]1
What is X? Well, if you compute 3 * X, you will find:
( [11]0 ) ; carry
[10]11 ; 1 * X
+ [01]1 ; 2 * X
--------
[00]01 ; sum = 3 * X = 1
so 3 * X = 1, and we are forced to conclude that X = 1/3.
In fact, all odd integers have inverses in the ring of 2-adic numbers, and
since the ring is closed under + and *, we can represent any rational p/q,
where q is odd. Now you can see why (LOGIOR 2/3 3/5) = -7/15:
2/3 = [01]10 = [0101]10
3/5 = [0011]1 = [1001]11
-7/15 = [0111] = [1101]11
But the 2-adic numbers don't just include the semi-infinite bitstrings that
eventually fall into a repeating pattern (which are all rational), but all
kinds of other weird things -- for example sqrt(17) is a non-repeating
sequence whose low order bits are:
...100110011110100110010011011101001
I don't have any idea if you can say -which- root this is -- but you can,
of course, negate it to get the other one. In fact, the 2-adic numbers
also contain many other algebraic numbers (including sqrt(-7)) as well as
having its own transcendentals.gyro@cymbal.reasoning.COM (Scott Layson Burson) (04/15/91)
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.
-- Scottok@goanna.cs.rmit.oz.au (Richard A. O'Keefe) (04/15/91)
In article <CARLTON.91Apr8201836@husc10.harvard.edu>, carlton@husc10.harvard.edu (david carlton) writes: > Do <bitwise logical operations> really make sense when operating on bignums? If they make sense on any integers at all, they make sense on bignums. > And and or I > can buy, at least when operating on non-negative bignums, but not not. "not" is actually the one that doesn't need special treatment: (define (bit-not x) (- -1 x)) The Common Lisp definitions work fine for integers of all sizes. -- It is indeed manifest that dead men are formed from living ones; but it does not follow from that, that living men are formed from dead ones. -- Tertullian, on reincarnation.