freenode/lisp - IRC Chatlog
Search
22:26:05
edgar-rft
Does anybody here know some historical reference *why* bit-vectors were introduced in Common Lisp? I learned Assembly as my first programming language and until today I'm using fixnums instead of bit-vectors. Somehow it appears to me as if I haven't understood what bit-vectors are good for at all. But maybe that't because I'm particularly stupid. Anybody knows some historical background?
22:33:18
_death
they pre-date Common Lisp.. in some scenarios they may be convenient because they are sequences, so sequence functions are applicable.. they also have an identity and are mutable
22:37:47
edgar-rft
yes, I know, bit-vectors are not only a Common Lisp thing, but (logior #b00000001 #bXXXXXXXX) reads *much* easier to me than all that back-and-forth conversion hassle above.
22:37:54
_death
their type makes clear their use, and they are printed in a way that can be convenient to the programmer
22:39:39
fe[nl]ix
edgar-rft: often you don't really care about representation, whether the index 0 is the most or least significant
22:40:41
edgar-rft
I agree that making them distinguishable from fixnums *is* an advantage. I'm not against bit-vectors (like I'm not against gravity) but I try to understand their advantage in practical code.
22:41:44
aeth
You use bit vectors when there's a clear boolean true/false (although you have to wrap it to turn it into 1/0 instead of using t/nil) for very long sequences
22:42:13
aeth
One example would be a prime sieve (possibly prime or definitely not prime), where you really are only limited by memory.
22:42:49
aeth
Another example would be if you're organizing your data (probably in the KBs) into multiple parallel arrays that you iterate over simultaneously and you only need one bit of data for something.
22:44:58
_death
I don't know that back-and-forth conversion is necessary.. for example I have some classifier code that takes a bit-vector for input (the number of bits is known at construction time and can be large).. I could've chosen to take an integer instead, but that would be a hassle
22:45:27
aeth
(defstruct foo (foos (make-array 30000 :element-type 'single-float :initial-element 0f0) :type (simple-array single-float (30000))) (active? (make-array 30000 :element-type 'bit :initial-element 0) :type (simple-array bit (30000))))
22:46:00
aeth
Then you iterate over active? and unless (zerop (aref (active? foo) i)) you do something with (aref (foos foo) i)
22:46:30
aeth
This is much simpler than having an array of, say, (unsigned-byte 64)s and manually mapping a bit in that array to the index of the foos
22:48:18
aeth
(And it's also simpler and safer, but more memory wasteful, than having some kind of invalid value, like using a NaN, which isn't even portable, and which you might get as a result from your calculations)
22:48:55
fe[nl]ix
of course, file-systems that need to scale beyong a TB or so use specialized trees
22:49:50
aeth
Anyway, I use bits in integers when I want to associate multiple boolean things with one index, and I use bit-vectors when I want to associate one boolean thing with one index.
22:51:14
_death
for "flags" I'd often use an unsigned-byte and not a bit-vector, if not a list (set) of keywords or somesuch
22:51:44
edgar-rft
yes, that only was a pitiful joke, semaphores (many booleans in one variable) are the first thing when I think about bit-vectors.
22:54:29
aeth
_death: Right, one collection of bits for one thing, use an integer. One bit for a sequence of things, use a bitvector and iterate both sequences simultaneously in one LOOP/DO/etc.
22:55:23
aeth
You can even get sophisticated and have a 2D array, where the first part of the AREF is the same as the AREF for the bitvector
23:06:50
edgar-rft
summary so far: bit-vectors are useful to distinguish fixnums (number family) from semaphores (boolean family), everything else so far I consider as "esoteric use-cases", any disagreements? :-)
23:08:08
phoe
bit vectors have constant performance characteristics whereas integers don't when they evolve into bignums
23:09:11
fwoaroof[m]
because that means that bit-vectors can also be used with non-fixed-length sequences of bits
23:10:05
aeth
edgar-rft: In C, everything's a sequence of bits, in CL, the underlying hardware is unspecified. This makes CL closer to the underlying hardware, because floats are iirc stored in special registers as a separate thing and treating them as just bits like C treats them is inefficient and probably requires a conversion.
23:12:56
aeth
fwoaroof[m]: I'd say being able to use them in MAP is more useful. That is, going back to the earlier struct... (defstruct foo (foos (make-array 30000 :element-type 'single-float :initial-element 0f0) :type (simple-array single-float (30000))) (active? (make-array 30000 :element-type 'bit :initial-element 0) :type (simple-array bit (30000))))
23:13:01
aeth
you can do this: (let ((foo (make-foo))) (map nil (lambda (foo active?) (unless (zerop active?) (format t "~A~%" foo))) (foo-foos foo) (foo-active? foo)))
23:13:37
aeth
You can't do that by manually creating your own bitvectors out of fixnums whose indices don't match the other sequence's indices
23:14:45
aeth
I could definitely see myself doing something like this if I could remember that such a thing can be done, but odds are I'd forget and write a messy LOOP instead
23:15:49
aeth
You could even map-into the foos array based on what the bit-vector tells you to do, although you might want to reorder things, so at that point the built in higher order functions might not be that useful
23:17:56
aeth
You could also make that an octet vector and assign a meaning to each bit and get really fancy and low-level-ish.
23:21:41
aeth
You could go much further if there were a lot of buildings for working with multidimensional arrays since 2D array rows gives you so much more here.
23:24:27
phoe
I would like living in a CL building because then I could just leave trash anywhere in my flat and then it would get automatically collected
23:27:42
edgar-rft
Thank you all, I think I have really learned something! And you can be proud ouf yourselves because makinge edgar learn something is a really remarkable achievement.
3:51:54
aeth
Speaking of CL buildings, "edifice" would be a great name for a text editor. It's probably already in use as a name, though.
4:10:02
edgar-rft
it doesn't even matter what words mean at all because I'm using them like *I* want
5:41:13
fe[nl]ix
beach: Google does semantic search nowadays, so try searching for "edifice software"