5 ms·

I have this funny question all the time: why dont we just use a bit boolean for representing option/nullable/unknown instead? (one bit of hasValue/isEmpty like

by stevefan1999 6y ago

I have this funny question all the time: why dont we just use a bit boolean for representing option/nullable/unknown instead? (one bit of hasValue/isEmpty like C# HasValue, but like struct uncertain_value<T> { T value; bool dont_care: 1; } and uninitialized value f<T>() => uncertain_value<T> { dont_care = 1 })

dllthomas 6y ago
What do you see as being the benefits of this approach?
mrkeen 6y ago
Given a 64-bit variable, you can fill it with 64 bits of value, or 64 bits of pointer to some value elsewhere. With your scheme that would be 63 (which I'm not objecting to). Pointers are already special-cased to only contain 0 already. There's no use-case for having 63 bits of pointer and an extra bit saying "ignore the other 63 bits". As for the value case, I think the argument is pretty similar. Why store 63 bits of value if the 64th bit says to ignore them? If you're not talking memory layouts and are looking at adding an extra field to a struct/class. Take you value field - if it's not initialised yet, and null doesn't exist, then what is its state?
- stevefan1999 6y ago
  if we extend the value to (value, is_null: bit<1>) we can have operated on the value field directly while also knowing whether the value is loaded or not. but you are right, maybe the compiler will outright "optimize" this to (value: align_pow2(sizeof T), is_null: byte) since the compiler will have to align value anyway, so that it will always have to expand the "sentinel". My original idea exactly contrary to your thinking: rather than making 0 NULL and give it the sentinel we always had, why don't we just avoid using it like using some data structure magic? You know, the null is infamous for causing the special case in integral constant expression that C++ inherited from C, and is confusing too, because then 0 is can be considered as (void ) and thus can cause an overload fiasco, that consider f(void) and f(int), what do you think f(0) would be? So the gist is I always think using x=0 to be able to represent NULL/false and !(x=0) to represent true is really really confusing (at least in C/C++). This also caused other languages to have some probable cases of negative number being cast to true so like `if (-1) console.log('lol')` it will print, wat? Also, with my configuration, not only we can always assume the value was intended to have a place to stay without indirection load, but the optional/null/don't-care/noninit will always have a stable state between 0 and 1 -- so we can clamp down without having to deal with extra states like I shown above, which is good from theoretical (because we can express its definite intent rather than guessing the type of the wrapped value) & logical standpoint (that we should not think in 3VL for null, rather, judge it by its concrete properties), not quite so in practice however (again, optimization kicks in nullifying all the good works), this might not entirely escape the pointer-not-null-then-consider-valid problem (what if we loaded a garbage value that might have a random 0/1? nowhere to tell also). In fact, this kind of configuration is not rare to be found: an open addressing hash table can use this kind of setting to represent "tombstone"/deleted field, but in a more optimized manner that we "bit set" because we are going to allocate a contiguous block of memory anyway so like the current universe can have 32 entries then we use lg(32) bytes bit-set at the beginning/end, if insert or delete value at entry x then toggle bit-tombstone of x, if search value y then find first i, x in entries if compare(x, y) = exact and !bit-tombstone[i] then (yes, i) else no...so on. But at the end of the day even that I don't like using 3VL to represent NULL, and my configuration is still like mapping 3VL into double binary anyway, iirc its like if value = U then don't care (either true and false; neither true nor false) else value. An analogy for NULL: if addr = NULL then value is no where to be found/random garbage value else load memory from addr.

dllthomas 6y ago

What do you see as being the benefits of this approach?

mrkeen 6y ago

Given a 64-bit variable, you can fill it with 64 bits of value, or 64 bits of pointer to some value elsewhere. With your scheme that would be 63 (which I'm not objecting to). Pointers are already special-cased to only contain 0 already. There's no use-case for having 63 bits of pointer and an extra bit saying "ignore the other 63 bits". As for the value case, I think the argument is pretty similar. Why store 63 bits of value if the 64th bit says to ignore them? If you're not talking memory layouts and are looking at adding an extra field to a struct/class. Take you value field - if it's not initialised yet, and null doesn't exist, then what is its state?

stevefan1999 6y ago
if we extend the value to (value, is_null: bit<1>) we can have operated on the value field directly while also knowing whether the value is loaded or not. but you are right, maybe the compiler will outright "optimize" this to (value: align_pow2(sizeof T), is_null: byte) since the compiler will have to align value anyway, so that it will always have to expand the "sentinel". My original idea exactly contrary to your thinking: rather than making 0 NULL and give it the sentinel we always had, why don't we just avoid using it like using some data structure magic? You know, the null is infamous for causing the special case in integral constant expression that C++ inherited from C, and is confusing too, because then 0 is can be considered as (void ) and thus can cause an overload fiasco, that consider f(void) and f(int), what do you think f(0) would be? So the gist is I always think using x=0 to be able to represent NULL/false and !(x=0) to represent true is really really confusing (at least in C/C++). This also caused other languages to have some probable cases of negative number being cast to true so like `if (-1) console.log('lol')` it will print, wat? Also, with my configuration, not only we can always assume the value was intended to have a place to stay without indirection load, but the optional/null/don't-care/noninit will always have a stable state between 0 and 1 -- so we can clamp down without having to deal with extra states like I shown above, which is good from theoretical (because we can express its definite intent rather than guessing the type of the wrapped value) & logical standpoint (that we should not think in 3VL for null, rather, judge it by its concrete properties), not quite so in practice however (again, optimization kicks in nullifying all the good works), this might not entirely escape the pointer-not-null-then-consider-valid problem (what if we loaded a garbage value that might have a random 0/1? nowhere to tell also). In fact, this kind of configuration is not rare to be found: an open addressing hash table can use this kind of setting to represent "tombstone"/deleted field, but in a more optimized manner that we "bit set" because we are going to allocate a contiguous block of memory anyway so like the current universe can have 32 entries then we use lg(32) bytes bit-set at the beginning/end, if insert or delete value at entry x then toggle bit-tombstone of x, if search value y then find first i, x in entries if compare(x, y) = exact and !bit-tombstone[i] then (yes, i) else no...so on. But at the end of the day even that I don't like using 3VL to represent NULL, and my configuration is still like mapping 3VL into double binary anyway, iirc its like if value = U then don't care (either true and false; neither true nor false) else value. An analogy for NULL: if addr = NULL then value is no where to be found/random garbage value else load memory from addr.