A Value Range Propagation usage example, and more

[bearophile via Digitalmars-d]

This is the first part of a function to convert to base 58 (some
letters are missing, like the upper case "I") used in the Bitcoin
protocol:


alias Address = ubyte[1 + 4 + RIPEMD160_digest_len];

char[] toBase58(ref Address a) pure nothrow @safe {
static immutable symbols = "123456789" ~
"ABCDEFGHJKLMNPQRSTUVWXYZ" ~
"abcdefghijkmnopqrstuvwxyz";
static assert(symbols.length == 58);

auto result = new typeof(return)(34);
foreach_reverse (ref ri; result) {
uint c = 0;
foreach (ref ai; a) {
c = c * 256 + ai;
ai = cast(ubyte)(c / symbols.length);
c %= symbols.length;
}
ri = symbols[c];
}
...
}


The D type system isn't smart enough to see that "ai" is always
fitting in an ubyte, so I have had to use a cast(ubyte). But
casts are dangerous and their usage should be minimized, and
to!ubyte is slow and makes the function not nothrow. So I've
rewritten the code like this with a bit of algebraic rewriting:


char[] toBase58(ref Address a) pure nothrow @safe {
static immutable symbols = "123456789" ~
"ABCDEFGHJKLMNPQRSTUVWXYZ" ~
"abcdefghijkmnopqrstuvwxyz";
static assert(symbols.length == 58);

auto result = new typeof(return)(34);
foreach_reverse (ref ri; result) {
uint c = 0;
foreach (ref ai; a) {
immutable d = (c % symbols.length) * 256 + ai;
ai = d / symbols.length;
c = d;
}
ri = symbols[c % symbols.length];
}
...
}


Now it can be a little slower because the integer division and
modulus has different divisors, so perhaps they can't be
implemented with a little more than a single division, as before
(I have not compared the assembly), but for the purposes of this
code the performance difference is not a problem. Now the D type
system is able to see that "ai" is always fitting in a ubyte, and
there's no need for a cast. The compiler puts a safe implicit
cast. This is awesome.

- - - - - - - - - - - - - -

But of course you often want more :-)

This is another case where the current D type system allows you
to avoid a cast:

void main() {
char['z' - 'a' + 1] arr;

foreach (immutable i, ref c; arr)
c = 'a' + i;
}



But if you want to use ranges and functional UFCS chains you
currently need the cast:


void main() {
import std.range, std.algorithm, std.array;

char[26] arr = 26
.iota
.map!(i => cast(char)('a' + i))
.array;
}


In theory this program has the same compile-time information as
the foreach case. In practice foreach is a built-in that enjoys
more semantics than a iota+map.

Currently iota(26) loses the compile-time information about the
range, so you can't do (note: the "max" attribute doesn't exists):

void main() {
import std.range: iota;
auto r = iota(26);
enum ubyte m = r.max;
}


Currently the only way to keep that compile-time information is
to use a template argument:

void main() {
import std.range: tIota;
auto r = tIota!26;
enum ubyte m = r.max; // OK
}

But even if you write such tIota range, the map!() will lose the
compile-time value range information. And even if you manage to
write a map!() able to do it with template arguments, you have
template bloat.

So there's a desire to manage the compile-time information (like
value range information) of (number) literals without causing
template bloat and without the need to use explicit template
arguments.

Bye,
bearophile