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
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
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
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
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
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
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
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
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
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
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