The syntax of sort and templates

[Stanislav Blinov via Digitalmars-d-learn]

On Friday, 26 May 2017 at 09:59:26 UTC, zakk wrote:
> Hello everyone,
>
> I just started using D and I am a bit puzzled by the syntax of 
> the sort function is std.algorithm.sorting, which is
>
> sort!(comparingFunction)(list)
>
> where comparingFunction is often a lambda expression. For 
> instance in the Wolfram Language the equivalent function is
>
> Sort[list,comparingFunction]
>
> My questions are:
>
> 1) Why is D making using of the binary ! operator, which as far 
> as I understand introduces a template?

The ! operator is needed to distinguish template arguments, 
passed and known at compile time, from actual function arguments, 
passed and known at run time. "!" doesn't "introduce" a template. 
The definition of 'sort' is a template, sort!(fn)(list) is an 
instantiation of that template with concrete arguments.

In C++, template arguments are denoted with <>, which is more 
verbose and introduces syntax ambiguity in complex templates. D 
avoids that by using the !.

> 2) Why is a template needed here?

Templates are a form of polymorphism that works at compile time. 
It allows the programmer to write, and the compiler to generate, 
the most efficient an/or the most practical code given the 
concrete use case. The net effect is that at runtime you get the 
sorting function that is tailored for the specific types and 
comparison predicate, as if it was written by hand.


> 3) It seems to me like the argument passed to the template is a 
> lambda expression. I only know about templates taking types as 
> argument. What's going on?

In D, depending on their definition, templates can take types, 
values or symbols as arguments. In this case, sort takes the 
comparison function and inserts it directly into the algorithm, 
which enables the compiler to inline it and/or perform various 
other optimizations, which would've been harder or impossible to 
do if the function was only known at runtime.
Also, this enables writing concise code: in Phobos, algorithms 
that take predicates allow to pass them as string literals 
instead of full-blown functions:

sort!"a < b"(list);

The "a < b" will be transformed at compile time into (a, b) => a 
< b.