{"id":841,"date":"2017-06-05T14:15:39","date_gmt":"2017-06-05T14:15:39","guid":{"rendered":"http:\/\/dlang.org\/blog\/?p=841"},"modified":"2021-10-08T11:11:54","modified_gmt":"2021-10-08T11:11:54","slug":"compile-time-sort-in-d","status":"publish","type":"post","link":"https:\/\/dlang.org\/blog\/2017\/06\/05\/compile-time-sort-in-d\/","title":{"rendered":"Compile-Time Sort in D"},"content":{"rendered":"

Bj\u00f6rn Fahller recently wrote a blog post showing how to implement a compile-time quicksort in C++17<\/a>. It’s a skillful demonstration that employs the evolving C++ feature set to write code that, while not quite concise, is more streamlined than previous iterations. He concludes with, “…the usefulness of this is very limited, but it is kind of cool, isn’t it?”<\/p>\n

There’s quite a bit of usefulness to be found in evaluating code during compilation. The coolness (of which there is much) arises from the possibilities that come along with it. Starting from Bj\u00f6rn’s example, this post sets out to teach a few interesting aspects of compile-time evaluation in the D programming language.<\/p>\n

The article came to my attention from\u00a0Russel Winder’s provocative query in the D forums, “Surely D can do better”, which was quickly resolved with a “No Story”-style answer by Andrei Alexandrescu. “There is nothing to do really. Just use standard library sort,” he quipped, and followed with code:<\/p>\n

Example 1<\/strong><\/p>\n

void main() {\r\n    import std.algorithm, std.stdio;\r\n    enum a = [ 3, 1, 2, 4, 0 ];\r\n    static b = sort(a);\r\n    writeln(b); \/\/ [0, 1, 2, 3, 4]\r\n}<\/pre>\n
Though it probably won’t be obvious to those unfamiliar with D, the call to sort<\/code> really is happening at compile time. Let’s see why.<\/p>\n
Compile-time code is runtime code<\/h3>\n
It’s true. There are no hurdles to jump over to get things running at compile time in D. Any compile-time function is also a runtime function and can be executed in either context. However, not all runtime functions qualify for CTFE (Compile-Time Function Evaluation).<\/p>\n
The fundamental requirements for CTFE eligibility are that a function must be portable, free of side effects, contain no inline assembly, and the source code must be available. Beyond that, the only thing deciding whether a function is evaluated during compilation vs. at run time is the context in which it’s called.<\/p>\n
The CTFE Documentation<\/a> includes the following statement:<\/p>\n
In order to be executed at compile time, the function must appear in a context where it must be so executed…<\/p><\/blockquote>\n
It then lists a few examples of where that is true. What it boils down to is this: if a function can be executed in a compile-time context where it must be, then it will be. When it can’t be excecuted (it doesn’t meet the CTFE requirements, for example), the compiler will emit an error.<\/p>\n
Breaking down the compile-time sort<\/h3>\n
Take a look once more at Example 1<\/strong>.<\/p>\n
void main() {\r\n    import std.algorithm, std.stdio;\r\n    enum a = [ 3, 1, 2, 4, 0 ];\r\n    static b = sort(a);\r\n    writeln(b);\r\n}<\/pre>\n
The points of interest that enable the CTFE magic here are lines 3 and 4.<\/p>\n
The enum<\/code> in line 3 is a manifest constant<\/a>. It differs from other constants in D (those marked immutable<\/code> or const<\/code>) in that it exists only at compile time. Any attempt to take its address is an error. If it’s never used, then its value will never appear in the code.<\/p>\n
When an enum<\/code> is used, the compiler essentially pastes its value in place of the symbol name.<\/p>\n
enum xinit = 10;\r\nint x = xinit;\r\n\r\nimmutable yinit = 11;\r\nint y = yinit;<\/pre>\n
Here, x<\/code> is initialized to the literal 10<\/code>. It’s identical to writing int x = 10<\/code>. The constant yinit<\/code> is initialized with an int<\/code> literal, but y<\/code> is initialized with the value of yinit<\/code>, which, though known at compile time, is not a literal itself. yinit<\/code> will exist at run time, but xinit<\/code> will not.<\/p>\n
In Example 1<\/strong>, the static variable b<\/code> is initialized with the manifest constant a<\/code>. In the CTFE documentation<\/a>, this is listed as an example scenario in which a function must be evaluated during compilation. A static variable declared in a function can only be initialized with a compile-time value. Trying to compile this:<\/p>\n
Example 2<\/strong><\/p>\n
void main() {\r\n    int x = 10;\r\n    static y = x;\r\n}<\/pre>\n
Will result in this:<\/p>\n
Error: variable x cannot be read at compile time<\/pre>\n
Using a function call to initialize a static variable means the function must be executed at compile time and, therefore, it will be if it qualifies.<\/p>\n
Those two pieces of the puzzle, the manifest constant and the static initializer, explain why the call to sort<\/code> in Example 1<\/strong> happens at compile time without any metaprogramming contortions. In fact, the example could be made one line shorter:<\/p>\n
Example 3<\/strong><\/p>\n
void main() {\r\n    import std.algorithm, std.stdio;\r\n    static b = sort([ 3, 1, 2, 4, 0 ]);\r\n    writeln(b);\r\n}<\/pre>\n
And if there’s no need for b<\/code> to stick around at run time, it could be made an enum<\/code> instead of a static variable:<\/p>\n
Example 4<\/strong><\/p>\n
void main() {\r\n    import std.algorithm, std.stdio;\r\n    enum b = sort([ 3, 1, 2, 4, 0 ]);\r\n    writeln(b);\r\n}<\/pre>\n
In both cases, the call to sort<\/code> will happen at compile time, but they handle the result differently. Consider that, due to the nature of enum<\/code>s, the change will produce an equivalent of this: writeln([ 0, 1, 2, 3, 4 ])<\/code>. Because the call to writeln<\/code> happens at run time, the array literal might trigger a GC allocation<\/a> (though it could be, and sometimes will be, optimized away). With the static initializer, there is no runtime allocation, as the result of the function call is used at compile time to initialize the variable.<\/p>\n
It’s worth noting that sort<\/code> isn’t directly returning a value of type int[]<\/code>. Take a peek at the documentation<\/a> and you’ll discover that what it’s giving back is a SortedRange<\/code><\/a>. Specifically in our usage, it’s a SortedRange!(int[], \"a < b\")<\/code>. This type, like arrays in D, exposes all of the primitives of a random-access range<\/a>, but additionally provides  functions that only work on sorted ranges and can take advantage of their ordering (e.g. trisect<\/code><\/a>). The array is still in there, but wrapped in an enhanced API.<\/p>\n
To CTFE or not to CTFE<\/h3>\n
I mentioned above that all compile-time functions are also runtime functions. Sometimes, it's useful to distinguish between the two inside the function itself. D allows you to do that with the __ctfe<\/code> variable. Here's an example from my book, 'Learning D<\/a>'.<\/p>\n
Example 5<\/strong><\/p>\n
string genDebugMsg(string msg) {\r\n    if(__ctfe)\r\n        return \"CTFE_\" ~ msg;\r\n    else\r\n        return \"DBG_\" ~ msg;\r\n}\r\n\r\npragma(msg, genDebugMsg(\"Running at compile-time.\"));\r\nvoid main() {\r\n    writeln(genDebugMsg(\"Running at runtime.\"));\r\n}<\/pre>\n
The msg<\/code> pragma<\/a> prints a message to stderr<\/code> at compile time. When genDebugMsg<\/code> is called as its second argument here, then inside that function the variable __ctfe<\/code> will be true<\/code>. When the function is then called as an argument to writeln<\/code>, which happens in a runtime context, __ctfe<\/code> is false<\/code>.<\/p>\n
It's important to note that __ctfe<\/code> is not<\/strong> a compile-time value. No function knows if it's being executed at compile-time or at run time. In the former case, it's being evaluated by an interpreter that runs inside the compiler. Even then, we can make a distinction between compile-time and runtime values inside the function itself. The result of the function, however, will be a compile-time value when it's executed at compile time.<\/p>\n
Complex compile-time validation<\/h3>\n
Now let's look at something that doesn't use an out-of-the-box function from the standard library.<\/p>\n
A few years back, Andrei published 'The D Programming Language<\/a>'. In the section describing CTFE, he implemented three functions that could be used to validate the parameters passed to a hypothetical linear congruential generator<\/a>. The idea is that the parameters must meet a set of criteria, which he lays out in the book (buy it for the commentary -- it's well worth it), for generating the largest period possible. Here they are, minus the unit tests:<\/p>\n
Example 6<\/strong><\/p>\n
\/\/ Implementation of Euclid\u2019s algorithm\r\nulong gcd(ulong a, ulong b) { \r\n    while (b) {\r\n        auto t = b; b = a % b; a = t;\r\n    }\r\n    return a; \r\n}\r\n\r\nulong primeFactorsOnly(ulong n) {\r\n    ulong accum = 1;\r\n    ulong iter = 2;\r\n    for (; n >= iter * iter; iter += 2 - (iter == 2)) {\r\n        if (n % iter) continue;\r\n        accum *= iter;\r\n        do n \/= iter; while (n % iter == 0);\r\n    }\r\n    return accum * n;\r\n}\r\n\r\nbool properLinearCongruentialParameters(ulong m, ulong a, ulong c) { \r\n    \/\/ Bounds checking\r\n    if (m == 0 || a == 0 || a >= m || c == 0 || c >= m) return false; \r\n    \/\/ c and m are relatively prime\r\n    if (gcd(c, m) != 1) return false;\r\n    \/\/ a - 1 is divisible by all prime factors of m\r\n    if ((a - 1) % primeFactorsOnly(m)) return false;\r\n    \/\/ If a - 1 is multiple of 4, then m is a multiple of 4, too. \r\n    if ((a - 1) % 4 == 0 && m % 4) return false;\r\n    \/\/ Passed all tests\r\n    return true;\r\n}<\/pre>\n
The key point this code was intended to make is the same one I made earlier in this post: properLinearCongruentialParameters<\/code> is a function that can be used in both a compile-time context and a runtime context. There's no special syntax required to make it work, no need to create two distinct versions. <\/p>\n
Want to implement a linear congruential generator as a templated struct with the RNG parameters passed as template arguments? Use properLinearCongruentialParameters<\/code> to validate the parameters. Want to implement a version that accepts the arguments at run time? properLinearCongruentialParameters<\/code> has got you covered. Want to implement an RNG that can be used at both compile time and run time? You get the picture.<\/p>\n
For completeness, here's an example of validating parameters in both contexts.<\/p>\n
Example 7<\/strong><\/p>\n
void main() {\r\n    enum ulong m = 1UL << 32, a = 1664525, c = 1013904223;\r\n    static ctVal = properLinearCongruentialParameters(m, a, c);\r\n    writeln(properLinearCongruentialParameters(m, a, c));\r\n}<\/pre>\n
If you've been paying attention, you'll know that ctVal<\/code> must be initialized at compile time, so it forces CTFE on the call to the function. And the call to the same function as an argument to writeln<\/code> happens at run time. You can have your cake and eat it, too.<\/p>\n
Conclusion<\/h3>\n
Compile-Time Function Evaluation in D is both convenient and painless. It can be combined with other features such as templates<\/a> (it's particularly useful with template parameters and constraints), string mixins<\/a> and import expressions<\/a> to simplify what might otherwise be extremely complex code, some of which wouldn't even be possible in many languages without a preprocessor. As a bonus, Stefan Koch is currently working on a more performant CTFE engine<\/a> for the D frontend to make it even more convenient. Stay tuned here for more news on that front.<\/p>\n
Thanks to the multiple members of the D community who reviewed this article.<\/em><\/p>\n","protected":false},"excerpt":{"rendered":"
Bj\u00f6rn Fahller recently wrote a blog post showing how to implement a compile-time quicksort in C++17. It’s a skillful demonstration that employs the evolving C++ feature set to write code that, while not quite concise, is more streamlined than previous iterations. He concludes with, “…the usefulness of this is very limited, but it is kind […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":[],"categories":[26],"tags":[],"_links":{"self":[{"href":"https:\/\/dlang.org\/blog\/wp-json\/wp\/v2\/posts\/841"}],"collection":[{"href":"https:\/\/dlang.org\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/dlang.org\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/dlang.org\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/dlang.org\/blog\/wp-json\/wp\/v2\/comments?post=841"}],"version-history":[{"count":44,"href":"https:\/\/dlang.org\/blog\/wp-json\/wp\/v2\/posts\/841\/revisions"}],"predecessor-version":[{"id":885,"href":"https:\/\/dlang.org\/blog\/wp-json\/wp\/v2\/posts\/841\/revisions\/885"}],"wp:attachment":[{"href":"https:\/\/dlang.org\/blog\/wp-json\/wp\/v2\/media?parent=841"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/dlang.org\/blog\/wp-json\/wp\/v2\/categories?post=841"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/dlang.org\/blog\/wp-json\/wp\/v2\/tags?post=841"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}