www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - The syntax of sort and templates

reply zakk <zakk87 gmail.com> writes:
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?

2) Why is a template needed here?

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?

Many thanks!
May 26 2017
next sibling parent reply Gary Willoughby <dev nomad.so> writes:
On Friday, 26 May 2017 at 09:59:26 UTC, zakk wrote:

 1) Why is D making using of the binary ! operator, which as far 
 as I understand introduces a template?


The exclamation mark here is not a binary operator, it's used in 
D templates to define where compile-time parameters are.


 2) Why is a template needed here?


It's a template so you can use differently typed ranges. Remember 
a range is an interface and very different types can implement it.


 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?


The function parameter is defined as an alias which is also valid 
at compile-time.

https://dlang.org/phobos/std_algorithm_sorting.html#sort
May 26 2017
parent Adam D. Ruppe <destructionator gmail.com> writes:
On Friday, 26 May 2017 at 11:05:37 UTC, Gary Willoughby wrote:

 The exclamation mark here is not a binary operator, it's used 
 in D templates to define where compile-time parameters are.


It actually is a binary operator, its left-hand-side is a 
template and its right-hand-side is a template argument list. 
Together, it instantiates the template.

Terminology nitpick, but stiil.
May 26 2017
prev sibling next sibling parent reply Stanislav Blinov <stanislav.blinov gmail.com> writes:
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.
May 26 2017
parent reply zakk <zakk87 gmail.com> writes:
On Friday, 26 May 2017 at 11:18:44 UTC, Stanislav Blinov wrote:

 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.


Thanks Gary and Stanislav for your replies.

I have a followup question: my background is C and in Wolfram 
Mathematica, so my knowledge of templates is limited to trivial 
examples in C++, like:

template <class T>
const T& min(const T& lhs, const T& rhs)
{
     return lhs < rhs ? lhs : rhs;
}

where the template argument is a type, and the function does the 
same job for different types.

It seems to me that when programming in D templates are something 
more powerful, is it correct of thinking of them as some argument 
which is known at compile time? Is this misleading?

Many thanks again for your replies!
May 26 2017
next sibling parent nkm1 <t4nk074 openmailbox.org> writes:
On Friday, 26 May 2017 at 11:27:19 UTC, zakk wrote:

 I have a followup question: my background is C and in Wolfram 
 Mathematica, so my
 knowledge of templates is limited to trivial examples in C++... 
 It seems to me that
 when programming in D templates are something more powerful


Even in C++ templates can work with more than just types (e.g., 
C++ templates accept other templates, numbers and pointers). And 
of course, D templates are even more powerful than in C++, so 
they can work with even more things:

TemplateTypeParameter
TemplateValueParameter
TemplateAliasParameter
TemplateSequenceParameter
TemplateThisParameter

(you can read about it here: 
https://dlang.org/spec/template.html#TemplateParameters)
May 26 2017
prev sibling parent Stanislav Blinov <stanislav.blinov gmail.com> writes:
On Friday, 26 May 2017 at 11:27:19 UTC, zakk wrote:


 I have a followup question: my background is C and in Wolfram 
 Mathematica, so my knowledge of templates is limited to trivial 
 examples in C++, like:

 template <class T>
 const T& min(const T& lhs, const T& rhs)
 {
     return lhs < rhs ? lhs : rhs;
 }

 where the template argument is a type, and the function does 
 the same job for different types.

 It seems to me that when programming in D templates are 
 something more powerful, is it correct of thinking of them as 
 some argument which is known at compile time? Is this 
 misleading?


It is :) Given your example above, 'template' doesn't mean just 
'type'. The whole definition is a template, i.e. that is a 
template function min. Or, in case of the original question, 
'sort' is a template. Not just it's arguments, but it itself.
But yes, templates are purely compile-time constructs. When you 
instantiate them with different arguments, you effectively get 
different functions in your code. Hence the name: compiler takes 
an existing definition (a template) and builds a whole new 
concrete function from it.

So if you were to call that C++ min function like this:

min(1, 2);

the compiler would generate a concrete function min, instantiated 
with T that is int, and then if you make this call:

min(1.5, 2.0);

then the compiler would generate *another* min, this time for 
type double. Note that double is of different size than int (i.e. 
usually int is 4 bytes, double is 8), and is also a 
floating-point type, not integral. So the compiler would have to 
issue different CPU instructions when generating code for it.

So now you get two different functions, but code for both of them 
has only been written once, the compiler takes care of the rest. 
Had 'min' not been a template, the programmer would have to write 
a new version by hand for every type needed, to get the most 
efficient code from the compiler.
May 26 2017
prev sibling next sibling parent Mike Parker <aldacron gmail.com> writes:
On Friday, 26 May 2017 at 09:59:26 UTC, zakk wrote:


 My questions are:

 1) Why is D making using of the binary ! operator, which as far 
 as I understand introduces a template?


The ! operator *instantiates* a template. Whenever you need to 
specify compile-time arguments to match the template parameters, 
you need to use !. Templated functions are implemented like this:

template myTemplateFunc(<Template parameters go here>) {
     void myTemplateFunc(<Function parameters go here>) {
         ....
     }
}

Template parameters are used at compile time, usually to generate 
the code for the function, and function parameters are used at 
runtime. When the template and the function have the same name, 
you can shorten the declaration like so:

void myTemplateFunc(<Template parameters>)(<Function parameters>);

With many templated functions, the template parameters can be 
inferred by the compiler from the function parameters:

void myFunc(T)(T arg) {...}

In this case, you can call myFunc using the instantiation 
operator:

myFunc!(int)(10);

Or, since the compiler has enough information to infer T (10 is 
an int, arg is a T, therefore T is int), you can call it like a 
normal function:

myFunc(10);

Template parameters can be given default values, just like 
function parameters. If all of the template parameters have 
default values or can be inferred, the ! can be omitted in the 
function call.

If you look at the documentation for sort [1], you'll see it's 
declared to take three template arguments. The first two are 
given default values. The last one is not, but since it is the 
type of the function parameter, it can be inferred and not 
specified. So sort *can* be called like this:

sort(myList);

And this will use the default comparison function, the default 
SwapStrategy, and the type of myList will be inferred. If you 
want to change the default comparison function or SwapStrategy, 
you need to use the instantiation operator to specify them. 
That's why it's needed in your example.



 2) Why is a template needed here?


It's not that a template is needed, but that sort is implemented 
as a templated function. I think my answer to number 1 should 
clear this one up, too.



 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?


There are a few different kinds of template parameters [2]. Types 
are perhaps the most common, but there are also template value 
parameters (any compile-time constant), template alias parameters 
(which can be any symbol or compile-time constant), and more. In 
the declaration of sort, you can see three kinds in action:

SortedRange!(Range, less)
sort(alias less = "a < b", SwapStrategy ss = 
SwapStrategy.unstable, Range)(Range r)

The first template parameter, less, is an alias parameter. The 
default value is a string literal which can be mixed in. But you 
could also pass a function name, a function literal (lambda), or 
even an object with a compatible opCall implementation (assuming 
the symbol is in the template's scope). The second parameter is a 
value parameter. SwapStrategy is an enum, the values of which are 
known at compile time. Finally, Range is a type. We know this 
because there's no "alias" or type name in front of it -- it's 
just a solitary symbol.

[1] http://dlang.org/phobos/std_algorithm_sorting.html#sort
[2] http://dlang.org/spec/template.html
May 26 2017
prev sibling parent reply Patrick Schluter <Patrick.Schluter bbox.fr> writes:
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?


! here indicates where the template parameter start in a template 
invocation

templatename!(compile time parameter)(runtime parameter)


 2) Why is a template needed here?


The template allows to generate the code so that the comparison 
is known at compile time and can be optimised properly. If you 
look for example in C, where sorting is done via the qsort() 
function. The comparison function must be provided by a function 
pointer. This means that the qsort function must call a function 
for doing even the simplest comparison. Furthermore, this call is 
indirect which on some processors can not be predicted and takes 
an inordinary long time to run.
Another nuisance associated with qsort and function pointer in C 
is that you have to define a specific function, with a specific 
name doing the type conversions because qsort only works with 
void * as parameter. This makes it slow, cumbersome and error 
prone.
All these defaults are inexistant in D thanks to the template, 
which take the lambda, i.e. an anonymous function, which is 
defined with the right types and inserts it in the sort code as 
if it had been written by hand.
The template replaces the macro preprocessor of C, but at more 
profound and intimate language level.


 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?


That's the strength of D that templates are not limited to types. 
Almost anything can be templatized which opens possibilities that 
other languages don't even start to be able to conceive.


 Many thanks!
May 26 2017
parent reply =?UTF-8?Q?Ali_=c3=87ehreli?= <acehreli yahoo.com> writes:
On 05/26/2017 05:10 AM, Patrick Schluter wrote:


 in C, where sorting is done via the qsort() function. The comparison
 function must be provided by a function pointer. This means that the
 qsort function must call a function for doing even the simplest
 comparison.


For example, Stroustrup has the article "Learning Standard C++ as a New 
Language"[1]. It compares sorting performance of C to C++ in section 3, 
"Efficiency". With those old C and C++ compilers he used (in May 1999), 
C++ was 1.74 to 4.62 times faster than C.

Ali

[1] http://www.stroustrup.com/new_learning.pdf
May 26 2017
parent Ola Fosheim Grostad <ola.fosheim.grostad gmail.com> writes:
On Friday, 26 May 2017 at 15:49:06 UTC, Ali Çehreli wrote:

 For example, Stroustrup has the article "Learning Standard C++ 
 as a New Language"[1]. It compares sorting performance of C to 
 C++ in section 3, "Efficiency". With those old C and C++ 
 compilers he used (in May 1999), C++ was 1.74 to 4.62 times 
 faster than C.


c++ language advocacy bullshit. C++ template bloat wouldn't be 
able to run on the low end machines from that era. The only thing 
from C stdlib you would use in performance code is memcpy and 
math.h, the rest is convinience and baggage...

If people have to use C stdlib as an example then they have 
already lost the argument...
May 26 2017