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