Andrei Alexandrescu

Speaker here. Slides at https://erdani.com/dconf2017-slides.pdf. Ask me anything!

Abstract: Over the years, a few programming paradigms have been successful enough to enter the casual vocabulary of software engineers: procedural, imperative, object-oriented, functional, generic, declarative. There's a B-list, too, that includes paradigms such as logic, constraint-oriented, and symbolic.

The point is, there aren't very many of them altogether. Easy to imagine, then, the immensely humbling pressure one must feel when stumbling upon a way to think about writing code that is at the same time explosively productive and firmly removed from any of the paradigms considered canon.

This talk shares early experience with Design by Introspection, a proposed programming paradigm that has enough demonstrable results to be worth sharing. The tenets of Design by Introspection are:

* The rule of optionality: Component primitives are almost entirely opt-in. A given component is required to implement only a modicum of primitives, and all others are optional. The component is free to implement any subset of the optional primitives.

* The rule of introspection: A component user employs introspection on the component to implement its own functionality using the primitives offered by the component.

* The rule of elastic composition: a component obtained by composing several other components offers capabilities in proportion with the capabilities offered by its individual components.

These…

Basically all comparison-based sort algorithms we use today stem from two basic algorithms: mergesort (stable sort, from 1945) and quicksort (unstable sort, from 1959).

Mergesort was improved by Tim Peters in 2002 and that became timsort. He invented a way to take advantage of pre-sorted intervals in arrays to speed up sorting. It's basically an additional layer over mergesort with a few other low-level tricks to minimize the amount memcpying.

Quicksort was improved by David Musser in 1997 when he developed introsort. He set a strict worst-case bound of O(n log n) on the algorithm, as well as improved the pivot selection strategy. And people are inventing new ways of pivot selection all the time. E.g. Andrei Alexandrescu has published a new method in 2017[1].

In 2016 Edelkamp and Weiß found a way to eliminate branch mispredictions during the partitioning phase in quicksort/introsort. This is a vast improvement. The same year Orson Peters adopted this technique and developed pattern-defeating quicksort. He also figured out multiple ways to take advantage of partially sorted arrays.

Sorting is a mostly "solved" problem in theory, but as new hardware emerges different aspects of implementations become more or less important (cache, memory, branch prediction) and then we figure out new tricks to take advantage of modern hardware. And finally, multicore became a thing fairly recently so there's a push to explore sorting in yet another direction...

[1]…

They are here:

https://isocpp.org/

http://cppcon.org/

https://github.com/isocpp/CppCoreGuidelines/blob/master/CppCoreGuidelines.md

http://erdani.com/index.php/books/modern-c-design/

https://msdn.microsoft.com/en-us/library/hh279654.aspx

http://stroustrup.com/Tour.html

http://elementsofprogramming.com/book.html

Most of the C++ bugs I found happened to be written by former C developers that disregard using C++ stronger type safety, RAII, the standard library containers and usually use naked pointers alongside malloc() and free().

And that is the biggest problem with C++, its copy-paste compatibility with C, which allowed its adoption by C compiler vendors, but made it as safe as C when developers disregard best practices.

You are right. D had some serious failures in the version 1 times, which tainted its image. However, the community is still growing. Slower than Rust, but moving in a positive direction.

During the last year the D foundation was founded and is spinning up operations. The 2016 D conference had a visitor record again with over 100 people. Downloads are growing over the years [0]. The package manager dub is now fully integrated. You can find success stories on the blog [1] and companies using it [2]. There are books.

[0] http://erdani.com/d/downloads.daily.png
[1] https://dlang.org/blog/
[2] https://dlang.org/orgs-using-d.html

It's a big world out there. Would you ever imagine that D would be taking market share from... Extended Pascal? But there's a naval architect who designs great big ships with a 500k sloc codebase he is exploring porting to D. Web guys get the attention but enterprise users are a much bigger world than just that.

If something is growing very quickly then saying it hasn't yet dethroned C, so it won't ever be significant seems to me to be a bit brittle thinking. Compound growth and the passage of time - thats what has been underway for some time now.

http://erdani.com/d/downloads.daily.png

"Modern C++" often refers specifically to techniques from Alexandrescu's book" http://erdani.com/index.php/books/modern-c-design/

Thanks to updates to the language, some of the hackery in there is no longer nearly so devilish, and there the language standard provides idioms that are simpler but "good enough if not better" for most people (tuples, smart pointers, move semantics, etc.), so a lot of the specific designs in the book _are_ starting to become passé. Still, it is a fantastic book for understanding the expressive power of C++'s multiparadigm design.