D - gregorymorrison/euler1 GitHub Wiki

D, introduced in 2001, is a modernized C. All of C's good parts were kept - programming-to-the-metal including inline assembly, compiling to native code, etc. Its bad parts were tossed out - memory management, C++'s complexity, etc. And many modern language developments were added - garbage collection, lambdas, concurrency support, etc. D supports multiple paradigms - imperative, OOP, functional, concurrent, and metaprogramming (whatever that last one is).

Since D is a superset of C, you can write plain-ass C code, which is just what I did for Euler1:

// Euler1 in D

import std.stdio;

int euler1(int n) {
    int retval = 0;
    for (int i=1; i<n; i++) {
        if (i%3 == 0 || i%5 == 0) {
            retval += i;
        }
    }
    return retval;
}

int main(char[][] args)
{
    writeln( "Euler1 = ", euler1(1000) );
    return 0;
}

Here's a functional version that uses tail recursion with an accumulator. One of the main points here is that the function euler() is deterministic - it will always return the same output for a given input. This is accomplished in part by the absence of any variable manipulation - there are instead only functions which return values. The other main point is that this recursion uses tail call optimization - it's written in such a way that an intelligent compiler can optimize its stack usage to be O(n) instead of O(n!). In English, this means that your program will probably not crash even for hugely recursive calls.

// Euler1 in D

import std.stdio;

int euler1(int n, int acc) {
    return n == 0 ? acc :
        euler1 (n-1, acc+(n%3==0 || n%5==0 ? n : 0) );
}

int main(char[][] args)
{
    writeln( "Euler1 = ", euler1(999, 0) );
    return 0;
}

Notice that we are not maintaining any state to solve our problem. No loops, no variables, no mutable state. We simply call euler() recursively to get the solution. This is an important part of the solution of the concurrency problem - how do you keep threads from stepping on each other's states? By eliminating mutable state!

I was thrilled to find out that D has a rich library of range functions. Here I use iota() to generate a range, and front(), drop(), and empty() to manipulate one. Here is a version of my Scheme program where I pass around an array of ints instead of n, peeling off the last one until the array is empty:

// Euler1 in D

import std.stdio, std.range;

int _euler(int n) {
    return n % 3 == 0 || n % 5 == 0 ? n : 0;
}

int euler(R)(R ints, int acc) {
    if (ints.empty()) {
        return acc;
    }

    acc += _euler(ints.front());
    ints = ints.drop(1);
    return euler(ints, acc);
}

int euler1(int size) {
    auto ints = iota(0, size);
    return sum = euler(ints, 0);
}

int main() {
    writeln("Euler1 = ", euler1(1000));
    return 0;
}

Here's another version using a Quicksort-based algorithm. Here we recursively break the list up in half and then reassemble it. Instead of sorting each half, though, we’ll filter the pivot value, converting it to 0 if it’s not divisible. Here, euler() returns euler() calculated on the half of the list before the pivot element, euler() calculated on the half of the list after the pivot element, and the pivot element or 0, all added together:

// Euler1 in D

import std.stdio : writeln;
import std.range;

int euler(R)(R ints) {
    if (ints.empty()) {
        return 0;
    }
    ulong pivot = ints.length / 2;

    int pre  = euler( iota(ints[0],       ints[pivot]) );
    int post = euler( iota(ints[pivot]+1, ints[ints.length-1]+1) );
    int pivotVal = (ints[pivot]%3 == 0 || ints[pivot]%5 == 0) ? ints[pivot] : 0;

    return pre + pivotVal + post;
}

int euler1(int size) {
    return euler(iota(0, size));
}

int main() {
    writeln("Euler1 = ", euler1(1000));
    return 0;
 }

This is much shorter than my C example. No pointers, no array bound to manually keep track of, no manually freeing memory, yay! D is definitely more productive than C.

Like most modern languages now, D has functional operations built-in, yay! Here's a version where I chain together calls to the canonical map(), filter(), and fold(). map() here is used only for illustration; we are not interested in mapping anything in this problem, so map() simply returns what was passed in. I could have written myMap(), myFilter(), and myFold() here as inline lambdas, but here I have defined them as standalone functions to show how D supports First-class functions:

// Euler1 in D

import std.stdio, std.range;
import std.algorithm.iteration : map, filter, fold;

int myMap(int i) {
   return i;
}
bool myFilter(int i) {
        return i % 3 == 0 || i % 5 == 0;
}
int myFold(int i, int j) {
        return i + j;
}

int euler1(int size) {
    return iota(0, size)
        .map!myMap
        .filter!myFilter
        .fold!myFold;
}

int main() {
    printf("Euler1 = %i\n", euler1(1000));
    return 0;
}

Here's a version where we generate three ranges - multiples of 3, 5, and 15, and we subtract the multiples of 15 since they're going to be the duplicate values found in the other two sequences:

// Euler1 in D

import std.algorithm.iteration;
import std.stdio, std.range;

int euler1(int n) {
    return sum(iota(0, n, 3)) + sum(iota(0, n, 5)) - sum(iota(0, n, 15));
}

int main(char[][] args) {
    writeln( "Euler1 = ", euler1(1000) );
    return 0;
}

Here's a different version - I simply generate three arrays of ints up to 999, one step 3, one step 15 starting at 5, and one step 15 starting at 10. This covers all the ints divisible by 3 or 5 with no overlaps, and we simply sum them all up. Cool!

// Euler1 in D

import std.algorithm.iteration;
import std.stdio, std.range;

int euler1(int n) {
    return sum(iota(0, n, 3)) + sum(iota(5, n, 15)) + sum(iota(10, n, 15));
}

int main(char[][] args) {
    writeln( "Euler1 = ", euler1(1000) );
    return 0;
}

As expected, D is object-oriented. What do classes look like in D? Pretty much what they look like in Java. I wanted to write a representative version of Euler1, but OOP is terribly overkill for what is essentially a simple math problem. Please don't actually write anything this stupid yourself - your coworkers will laugh at you behind your back. I will write it for you - here is a version where we instantiate a class using a constructor, call a method on it to solve the problem, then call an accessor function to return the value.:

// Euler1 in D

import std.algorithm.iteration;
import std.stdio, std.range;

class Euler1 {
    private int size;
    private int result;

    this(int size) {
        this.size = size;
    }

    void solve() {
        this.result = sum(iota(0, this.size, 3)) + sum(iota(0, this.size, 5)) - sum(iota(0, this.size, 15));
    }

    int getResult() {
        return this.result;
    }
}

int euler1(int n) {
    Euler1 euler1 = new Euler1(n);

    euler1.solve();

    return euler1.getResult();
}

int main(char[][] args) {
    writeln( "Euler1 = ", euler1(1000) );
    return 0;
}

Here’s one more – an elegant algorithm based on an observation by little Carl Friedrich Gauss. It operates in O(1) constant time. Don’t sweat it if this seems inscrutable; click the blog link above for an explanation:

// Euler1 in D
import std.stdio;
import std.math;

double mySum(int n, int size) {
    float myFloor = floor(cast(float)(size/n));
    return (pow(myFloor, 2) + myFloor) * n / 2;
}

double euler1(int size) {
    return mySum(3, size) + mySum(5, size) - mySum(15, size);
}

int main() {
    writeln("Euler1 = ", euler1(999));
    return 0;
}

I tried using the LDC under Linux, but failed to get it to work. I did get the GDC compiler to work, easily, under Cygwin, but Cygwin only supports D 1.x, not the more recent D 2.x.

I was very intrigued to explore D's additions of the functional and concurrent paradigms. Alas, these were added in D 2.x, so I didn't get to play with them. This language looks like it has a lot of potential, but my experience with D was that it still feels immature in its support, documentation, etc.

To run your code under GDC, simply compile to an executable, then, um, execute:

$ gdc euler.d -o euler1
$ ./euler1
Euler1 = 233168
$

I also tried to install the DMD reference compiler in an Ubuntu container, but the apt-get version complained about obsolete dependencies, and apparently you can't install snap packages inside a container? Luckily, I found a D docker image, dlang2/dmd-ubuntu, which I was able to get working immediately. Well alright, we're in business!

$ docker run --rm -ti -v $(pwd):/src dlang2/dmd-ubuntu bash
$ cd /src
$ dmd euler1.d
$ ./euler1
Euler1 = 233168
$