Better C++/D code
When I read the "The Little Schemer" I have done countless small coding exercises using recursion:
https://github.com/pkrumins/the-little-schemer
But later when I've started learning Haskell I've seen than explicit recursion is uncommon in good Haskell code. Most times in Haskell you use map, folds, and other higher order functions instead of recursion. (Sometimes in Haskell you use explicit recursion as an optimization).
C and C++ code contains lot of 'for' and 'while' loops, that are sometimes hard to read and understand.
Recently they have released videos and slides of the talks of the GoingNative 2013 conference. Among the interesting talks the one I have appreciated more is "C++ Seasoning" by Sean Parent (and from the comments I see that others agree with me, and even ask the speaker to write a book on the topic):
http://channel9.msdn.com/Events/GoingNative/2013/Cpp-Seasoning
I suggest to start reading the updated slides:
https://github.com/sean-parent/sean-parent.github.com/wiki/presentations/2013-09-11-cpp-seasoning/cpp-seasoning.pdf
The talk gives some suggestions for C++ code:
- No Raw Loops
- No Raw Syntonization Primitives
- No Raw Pointers
The first part suggests to reduce the number of loops in C++ code and replace them with algorithms (often with STL algorithms), a little like it's done in Haskell.
C++ is an abstraction over C, and the heavy usage of STL-like algorithms is kind of a new language that abstracts over raw loop-heavy C++ code. Writing code like that in C++ takes time and some brain power, but the resulting code is good, short, simpler to keep bug-free, and often efficient too.
In D language I suggest to use std.algorithm for similar purposes. I also suggest to make const/immutable all variables, unless they need to mutate, or unless something in D or in Phobos makes that impossible (like Ranges, that often can't be const).
Walter Bright calls "component programming" a variant of that coding style that relies on ranges a lot. I have shown several examples of such linear flow programming in past blog posts (that today is becoming very common, LINQ in C#, in Java8, with Python itertools, in F#, and so on).
Here is another simple example, the Euler Problem number 50 (http://projecteuler.net/problem=50 ), the problem:
The prime 41, can be written as the sum of six consecutive primes: 41 = 2 + 3 + 5 + 7 + 11 + 13
This is the longest sum of consecutive primes that adds to a prime below one-hundred.
The longest sum of consecutive primes below one-thousand that adds to a prime, contains 21 terms, and is equal to 953.
Which prime, below one-million, can be written as the sum of the most consecutive primes?
This is a simple imperative solution in D (modified and ported from Python code found here: http://blog.dreamshire.com/2009/04/12/project-euler-problem-50-solution/ ):
import std.stdio, std.algorithm, std.range, std.functional;
...
int euler50(in int top) {
/*const*/ auto primes = top.sieve.assumeSorted;
int[] prime_sum = [0];
int tot = 0, count = 0;
while (tot < top) {
tot += primes[count];
prime_sum ~= tot;
count++;
}
int terms = 1;
int max_prime = -1;
foreach (immutable i; 0 .. count)
foreach (immutable j; i + terms .. count) {
immutable n = prime_sum[j] - prime_sum[i];
if (j - i > terms && primes.contains(n)) {
terms = j - i;
max_prime = n;
}
}
return max_prime;
}
void main() {
1_000_000.euler50.writeln; // 997651
}The idea is to compute a cumulative of the prime numbers, and then take a subset of all the N^2 subintervals, removing the sum of the starting end of the interval from the sum of its end, to compute in O(1) the sum of its items. The contains() function is a linear search, so this code is kind of O(n^3), but for the given problem it's fast enough, finding the correct result of 997651 in less than half second.
A very simple sieve implementation used in that euler50() function could be:
uint[] sieve(in uint limit) {
if (limit < 2)
return [];
auto composite = new bool[limit];
foreach (immutable uint n; 2 .. cast(uint)(limit ^^ 0.5) + 1)
if (!composite[n])
for (uint k = n * n; k < limit; k += n)
composite[k] = true;
return iota(2, limit).filter!(i => !composite[i]).array;
}
If you take a look at the euler50() functions you see general patterns. The cumulative of an array could be written as general function (even better is to write this as a lazy range that works on any input range):
T[] accumulate(T)(in T[] items) pure nothrow {
auto result = new T[items.length];
if (!items.empty) {
result[0] = items[0];
foreach (immutable i; 1 .. items.length)
result[i] = result[i - 1] + items[i];
}
return result;
}
The iteration on all subsets could be done with a handy "Pairwise" range (imports not included):
struct Pairwise(Range) {
alias R = Unqual!Range;
alias Pair = Tuple!(ForeachType!R, "a", ForeachType!R, "b");
R _input;
size_t i, j;
this(Range r_) {
this._input = r_;
j = 1;
}
@property bool empty() {
return j >= _input.length;
}
@property Pair front() {
return Pair(_input[i], _input[j]);
}
void popFront() {
if (j >= _input.length - 1) {
i++;
j = i + 1;
} else {
j++;
}
}
}
Pairwise!Range pairwise(Range)(Range r)
if (isRandomAccessRange!Range && hasLength!Range && !isNarrowString!Range) {
return typeof(return)(r);
}
Then what's left is a search among all the subsequences, throwing away all the ones that are too much long and the ones that don't sum to a prime number. Also the pre-computed array of primes is sorted, so it's better to use a binary search. Now we can organize all the computation in few simple chains:
int euler50b(in int top) {
auto primes = top.sieve.assumeSorted;
auto primeSum = primes.release.accumulate;
return primeSum
.until!(p => p > top)
.walkLength
.iota
.pairwise
.map!(ij => tuple(ij[1] - ij[0], primeSum[ij[1]] - primeSum[ij[0]]))
.filter!(dn => primes.contains(dn[1]))
.reduce!max[1];
}This code works and runs in something like 0.3-0.4 seconds, so it's still fast enough.
This euler50b() function has several problems:
- A range like pairwise() is not yet present in std.range;
- Something like accumulate() (with a given reducing function) is missing in std.algoritm;
- In D there is no syntax to destructure (unpack) tuples, so you have to use things like: ij => tuple(ij[1] - ij[0] ...
- std.algorithm.max is not yet accepting a key function.
- Currently "primes" can't be immutable or even const because you can't call the "release" method on a const SortedRange;
- Currently "primeSum" can't be immutable otherwise reduce() doesn't work.
- Currently "iota" is not pure nor nothrow.
How the main function could look, once D and Phobos become more refined:
int euler50c(in int top) pure nothrow {
immutable primes = top.sieve.assumeSorted;
immutable primeSum = primes.accumulate!q{a + b};
return primeSum
.until!(p => p > top)
.walkLength
.iota
.pairwise
.map!({i, j} => tuple(j - i, primeSum[j] - primeSum[i]))
.filter!({d, n} => primes.contains(n))
.reduce!(max!({d, n} => d))[1];
}
The full code of the two versions:
http://www.fantascienza.net/leonardo/js/euler50.zip
https://github.com/pkrumins/the-little-schemer
But later when I've started learning Haskell I've seen than explicit recursion is uncommon in good Haskell code. Most times in Haskell you use map, folds, and other higher order functions instead of recursion. (Sometimes in Haskell you use explicit recursion as an optimization).
C and C++ code contains lot of 'for' and 'while' loops, that are sometimes hard to read and understand.
Recently they have released videos and slides of the talks of the GoingNative 2013 conference. Among the interesting talks the one I have appreciated more is "C++ Seasoning" by Sean Parent (and from the comments I see that others agree with me, and even ask the speaker to write a book on the topic):
http://channel9.msdn.com/Events/GoingNative/2013/Cpp-Seasoning
I suggest to start reading the updated slides:
https://github.com/sean-parent/sean-parent.github.com/wiki/presentations/2013-09-11-cpp-seasoning/cpp-seasoning.pdf
The talk gives some suggestions for C++ code:
- No Raw Loops
- No Raw Syntonization Primitives
- No Raw Pointers
The first part suggests to reduce the number of loops in C++ code and replace them with algorithms (often with STL algorithms), a little like it's done in Haskell.
C++ is an abstraction over C, and the heavy usage of STL-like algorithms is kind of a new language that abstracts over raw loop-heavy C++ code. Writing code like that in C++ takes time and some brain power, but the resulting code is good, short, simpler to keep bug-free, and often efficient too.
In D language I suggest to use std.algorithm for similar purposes. I also suggest to make const/immutable all variables, unless they need to mutate, or unless something in D or in Phobos makes that impossible (like Ranges, that often can't be const).
Walter Bright calls "component programming" a variant of that coding style that relies on ranges a lot. I have shown several examples of such linear flow programming in past blog posts (that today is becoming very common, LINQ in C#, in Java8, with Python itertools, in F#, and so on).
Here is another simple example, the Euler Problem number 50 (http://projecteuler.net/problem=50 ), the problem:
The prime 41, can be written as the sum of six consecutive primes: 41 = 2 + 3 + 5 + 7 + 11 + 13
This is the longest sum of consecutive primes that adds to a prime below one-hundred.
The longest sum of consecutive primes below one-thousand that adds to a prime, contains 21 terms, and is equal to 953.
Which prime, below one-million, can be written as the sum of the most consecutive primes?
This is a simple imperative solution in D (modified and ported from Python code found here: http://blog.dreamshire.com/2009/04/12/project-euler-problem-50-solution/ ):
import std.stdio, std.algorithm, std.range, std.functional;
...
int euler50(in int top) {
/*const*/ auto primes = top.sieve.assumeSorted;
int[] prime_sum = [0];
int tot = 0, count = 0;
while (tot < top) {
tot += primes[count];
prime_sum ~= tot;
count++;
}
int terms = 1;
int max_prime = -1;
foreach (immutable i; 0 .. count)
foreach (immutable j; i + terms .. count) {
immutable n = prime_sum[j] - prime_sum[i];
if (j - i > terms && primes.contains(n)) {
terms = j - i;
max_prime = n;
}
}
return max_prime;
}
void main() {
1_000_000.euler50.writeln; // 997651
}The idea is to compute a cumulative of the prime numbers, and then take a subset of all the N^2 subintervals, removing the sum of the starting end of the interval from the sum of its end, to compute in O(1) the sum of its items. The contains() function is a linear search, so this code is kind of O(n^3), but for the given problem it's fast enough, finding the correct result of 997651 in less than half second.
A very simple sieve implementation used in that euler50() function could be:
uint[] sieve(in uint limit) {
if (limit < 2)
return [];
auto composite = new bool[limit];
foreach (immutable uint n; 2 .. cast(uint)(limit ^^ 0.5) + 1)
if (!composite[n])
for (uint k = n * n; k < limit; k += n)
composite[k] = true;
return iota(2, limit).filter!(i => !composite[i]).array;
}
If you take a look at the euler50() functions you see general patterns. The cumulative of an array could be written as general function (even better is to write this as a lazy range that works on any input range):
T[] accumulate(T)(in T[] items) pure nothrow {
auto result = new T[items.length];
if (!items.empty) {
result[0] = items[0];
foreach (immutable i; 1 .. items.length)
result[i] = result[i - 1] + items[i];
}
return result;
}
The iteration on all subsets could be done with a handy "Pairwise" range (imports not included):
struct Pairwise(Range) {
alias R = Unqual!Range;
alias Pair = Tuple!(ForeachType!R, "a", ForeachType!R, "b");
R _input;
size_t i, j;
this(Range r_) {
this._input = r_;
j = 1;
}
@property bool empty() {
return j >= _input.length;
}
@property Pair front() {
return Pair(_input[i], _input[j]);
}
void popFront() {
if (j >= _input.length - 1) {
i++;
j = i + 1;
} else {
j++;
}
}
}
Pairwise!Range pairwise(Range)(Range r)
if (isRandomAccessRange!Range && hasLength!Range && !isNarrowString!Range) {
return typeof(return)(r);
}
Then what's left is a search among all the subsequences, throwing away all the ones that are too much long and the ones that don't sum to a prime number. Also the pre-computed array of primes is sorted, so it's better to use a binary search. Now we can organize all the computation in few simple chains:
int euler50b(in int top) {
auto primes = top.sieve.assumeSorted;
auto primeSum = primes.release.accumulate;
return primeSum
.until!(p => p > top)
.walkLength
.iota
.pairwise
.map!(ij => tuple(ij[1] - ij[0], primeSum[ij[1]] - primeSum[ij[0]]))
.filter!(dn => primes.contains(dn[1]))
.reduce!max[1];
}This code works and runs in something like 0.3-0.4 seconds, so it's still fast enough.
This euler50b() function has several problems:
- A range like pairwise() is not yet present in std.range;
- Something like accumulate() (with a given reducing function) is missing in std.algoritm;
- In D there is no syntax to destructure (unpack) tuples, so you have to use things like: ij => tuple(ij[1] - ij[0] ...
- std.algorithm.max is not yet accepting a key function.
- Currently "primes" can't be immutable or even const because you can't call the "release" method on a const SortedRange;
- Currently "primeSum" can't be immutable otherwise reduce() doesn't work.
- Currently "iota" is not pure nor nothrow.
How the main function could look, once D and Phobos become more refined:
int euler50c(in int top) pure nothrow {
immutable primes = top.sieve.assumeSorted;
immutable primeSum = primes.accumulate!q{a + b};
return primeSum
.until!(p => p > top)
.walkLength
.iota
.pairwise
.map!({i, j} => tuple(j - i, primeSum[j] - primeSum[i]))
.filter!({d, n} => primes.contains(n))
.reduce!(max!({d, n} => d))[1];
}
The full code of the two versions:
http://www.fantascienza.net/leonardo/js/euler50.zip