H. S. Teoh
| I alluded to this in D.learn some time ago, and finally decided to take
the dip and actually write the code. So here it is: exact arithmetic
with numbers of the form (a+b√r)/c where a, b, c are integers, c!=0, and
r is a (fixed) square-free integer.
Code: https://github.com/quickfur/qrat
I wrote this code in just a little over a day, a testament to D's productivity-increasing features, among which include:
1) Built-in unittests: I couldn't have had the confidence that my code was correct if I hadn't been able to verify it using unittests, that also ensured that there would be no regressions, *and* also provided nice ddoc'd examples for the user. This is a killer combo, IMO.
2) Sane(r) operator overloading: even though there's still a certain amount of boilerplate, operator overloading in D is far saner than in C++, thanks to:
a) Templated opUnary / opBinary / opOpAssign with the operator
as a string template argument that can be used in mixins. This
saved me quite a bit of copy-pasta that would have otherwise
been necessary, e.g., in a C++ implementation.
b) Unification of <, <=, >, >= under opCmp, and !=, == under
opEquals. Again, tons of copy-pasta were avoided where they
would have been necessary in C++.
c) opBinaryRight, an underrated genius design decision, that
allowed easy support of expressions of the form `1 + q` without
C++ hacks like friend functions and what-not.
3) Sane template syntax, that, combined with opBinaryRight and the other
overloading features, made expressions like this possible, and
readable(!):
// So clear, so readable!
auto goldenRatio = (1 + surd!5)/2;
// This would have been a mess in C++ syntax due to template<x>
// clashing visually with operator <.
assert((10 + surd!5)/20 < (surd!5 - 1)/2);
4) Code coverage built into the compiler with -cov, that caught at least one bug in a piece of code that my unittests missed. Now with 100% code coverage, I feel far more confident that there are no nasty bugs left!
5) Pay-as-you-go template methods: I deliberately turned all QRat
methods into template functions, because of (a) template attribute
inference (see below), and (b) reducing template bloat from
instantiating methods that are never used in user code.
6) Template attribute inference: this allowed me, *after the fact*, to slap 'pure nothrow @safe @nogc' onto my module ddoc'd unittest, and instantly get compiler feedback on where exactly I'd inadvertently broke purity / nothrowness / safety / etc., where I didn't intend. And it was very gratifying, once I'd isolated those bits of code, to have the confidence that the compiler has verified that the core operations (unary / binary operators, comparisons, etc.) were all pure nothrow @safe @nogc, and thus widely usable. If I'd had to wrangle with explicitly writing attributes, I would've been greatly hampered in productivity (not to mention frustrated and distracted from focusing on the actual algorithms rather than the fussy nitty-gritties of the language). Attribute inference is definitely the way of the future, and I support Walter in pushing it as far as it can possibly go. And statically-verified guarantees too. That's another win for D.
Having said that, though, there were a few roadblocks:
1) std.numeric.gcd doesn't support BigInt. This in itself wouldn't have been overly horrible, if it weren't for the fact that:
a) The algorithm in std.numeric.gcd actually *does* work for
BigInt, but BigInt support wasn't implemented because there are
ostensibly better-performing BigInt GCD algorithms out there --
but they are too complex to implement so nobody has done it yet.
An unfortunate example of letting the perfect being the enemy of
the good, that's been plaguing D for a while now.
https://issues.dlang.org/show_bug.cgi?id=7102
b) There are no sig constraints in std.numeric.gcd even though
it doesn't support BigInts (or, for that matter, custom
numerical types). This means that once you import std.numeric,
you can't even provide your own overloads of gcd to handle
BigInt or whatever other types you wish to handle, without
running into overload conflicts. Not without unnecessarily
convoluted schemes of static imports, symbol aliasing, and all
the rest of that churn.
c) The only thing that's really standing in the way of BigInt in
std.numeric.gcd is an ill-advised (IMO) way to test if a numeric
type has sign, by assuming that that's equivalent to having a
.min property. That really only works for built-in types, which
again screams "missing sig constraints!", and basically fails
for everything else.
2) std.numeric.gcd isn't variadic, so I had to roll my own. Not a biggie, but it was still annoying and wasted my time writing code that calls gcd(a,b) multiple times when I first started coding, only to later realize I'd be doing this a *lot* and deciding to write variadic gcd myself.
Haha, it seems that the only roadblocks were related to the implementation quality of std.numeric.gcd... nothing that a few relatively-simple PRs couldn't fix. So overall, D is still awesome.
T
--
Those who don't understand Unix are condemned to reinvent it, poorly.
|