Wednesday, 9 November 2022

Why Qt containers? And do we ❤️ them?

I have read the following post titled  "I ❤️ Qt containers! :)" on the Qt Development mailing list and found it extremely interesting. It is written by Volker Hilsheimer, the current chief maintainer of the Qt project, and elaborates on some design principles Qt libraries are using. The post was was written as a response to more general question of why isn't Qt switching to standard C++ library containers.

I hope nobody gets offended that I repost it here - I do it because not everyone can read the archives. I'd also like to be able to find it for myself in case I'd like to ponder on Qt containers and their design.

So happy reading (emphasizings and formattings are all mine):

" .... Historically, STL implementations were unusable and unreliable for cross platform development (we supported HP-UX, AIX, SGI, Sun back in those days), and generally incomplete (only a few associative containers pre-C++11). So, 30 or 20 years ago, or perhaps up to C++11 and until we could drop commercial Unix systems as irrelevant (esp for Nokia’s plans; although no idea about the quality of the STL for Symbian C++), the STL wasn’t really much of an option.

However, this is a more fundamental question about what we try to achieve with Qt. Qt has never tried to be a C++ library that follows the design principals of the std library. In many cases, we don’t even care that much about the single responsibility principle (hello, QWidget). Qt container classes have always been more than a dumb storage of data on top of which algorithms operate. QString is a very rich class with tons of functionality, specific to text handling. std::string is a sequence of characters. Working with QString vs std::string to deal with user-provided text input requires rather completely different mindsets.

Our core competence of designing intuitive APIs does not exclude container classes. That’s why with Qt containers, we can write
if (list.contains(value)) {
    // ...
}
rather than
if (std::find(list.begin(), list.end(), value) != list.end()) {
    // ...
}
Perhaps it makes me an inferior C++ developer, but I rather prefer the former. Well, std::map got a contains(), and std::string a starts_with() in C++ 20, only 25 years late(r).

Indeed, sometimes that convenience means that our users, and we ourselves, can do something silly like:
if (map.contains(key)) {
    value = map.value(key);
    // do stuff with value
}
Convenience is no excuse for us as developers of Qt to be sloppy. It is also no excuse for ignoring the new features we get into our toolbox when we move to C++ 20 or 23. But that C++ 20 finally introduces std::map::contains (but not std::vector::contains…), or adds std::span, is also no excuse for us to toss our own designs out of the window, and to demand that all Qt users must embrace the STL instead.

One of Qt’s goals has always been to make C++ accessible for people that come from other languages, with a programming model that is not rooted in how the C++ standard library does things. That programming language used to be Java - hence our Java-style iterators in Qt containers. Today, people perhaps rather learn programming with Python in school. There will always be more people that have learned programming with other languages, than those that have carefully studied the C++ standard and the impact of various constructs in Compiler Explorer. We must make it easy for the former, while also enabling the latter.

And there are the practical reasons why I don’t want to replace QList with std::vector and QHash with std::unordered_map: we store our data structures in the d-pointer, and we want to stay flexbile wrt the actual stored type. So copy-elision and return-value-optimization don't buy us much: we need to return copies of containers from our property getters. Not const references to containers, and not temporary lists that can be moved out. So we do need reference counting.

For the here and now, and the last 25 years of Qt and C++, it’s not helpful to argue that we will soon be able to return a type-erased span and get rid of “horrible and inefficient” APIs returning owning containers. std::span is a new tool, opening up new opportunities; the expressiveness of e.g. C++ ranges might even make it much easier for someone coming from e.g. Python to use Qt, while allowing us to write much more efficient code. So we do need to consider how we name and design our APIs today so that we can add new APIs to unlock that power in the future. And we need to keep looking for ways to improve what we have - with extra awareness of what potential changes mean for our users and co-contributors.

Those improvements cannot require that we force everyone to change significant amounts of existing code, all the time; or that they have to regularly unlearn established Qt patterns; or that they have to live without the convenience. Yes, I’m biased, but I honestly don’t see any universe where a Qt without our implicitly shared, owning, old-fashioned containers, and instead with only STL containers and programming paradigms, would have been as easy, or as much fun, to use.

Volker
" 
Summing up

As it was already said elsewhere, "Qt is known  for making C++ easy and accessible"! You might say it's C++ for the people.  Maybe it's for that reason that C++ didn't go the way of Haskell despite Commitee's best efforts? 😏


A screenshot (I forgot from which presentation...)

PS: I didn't remove anything from the original post for the sake of completeness


Tuesday, 27 September 2022

Guest post - An Extraterrestrial Guide to C++20 Text Formatting


This is a guest post which was written by Victor Zverovich* (aka @vzverovich) for C++ Stories and which I liked so much (not least because of the funny S. Lem references 😀 whose big fan I used to be in my time!) that I asked for permission to repost it here. And so, you can read it here including new, fresh pictures from Stanislaw Lem's works. 

My take on std::format
  • you can say what you want about C++20, but it allowed to solve the problems of both iostreams and printf by reusing their strenghts and transcending their limitations!
>>>> the original text starts here >>>>

Intro 
(with apologies to Stanisław Lem) 


Star Diaries, Latvian edition
Consider the following use case: you are developing the Enteropia[2]-first Sepulka[3]-as-a-Service (SaaS) platform and have server code written in C++ that checks the value of requested sepulka’s squishiness received over the wire and, if the value is invalid, logs it and returns an error to the client. Squishiness is passed as a single byte and you want to format it as a 2-digit hexadecimal integer, because that is, of course, the Ardrite[1] National Standards Institute (ANSI) standard representation of squishiness. You decide to try different formatting facilities provided by C++ and decide which one to use for logging. 

First you try iostreams:
#include <cstdint>
#include <iomanip>
#include <iostream>

void log_error(std::ostream& log, std::uint_least8_t squishiness) {
  log << "Invalid squishiness: "
      << std::setfill('0') << std::setw(2) << std::hex
      << squishiness << "\n";
}
The code is a bit verbose, isn’t it? You also need to pull in an additional header, <iomanip>, to do even basic formatting. But that’s not a big deal. 

Ardrites testing
However, when you try to test this code (inhabitants of Enteropia have an unusual tradition of testing their logging code), you find out that the code doesn’t do what you want. For example,
log_error(std::cout, 10);
prints
Invalid squishiness: 0
Which is surprising for two reasons: first it prints one character instead of two and second the printed
value is wrong. After a bit of debugging, you figure out that iostreams treat the value as a character on your platform and that the extra newline in your log is not a coincidence. An even worse scenario is that it works on your system, but not on the one of your most beloved customers. 

So you add a cast to fix this which makes the code even more verbose (see the code @Compiler Explorer)
log << "Invalid squishiness: "
    << std::setfill('0') << std::setw(2) << std::hex
    << static_cast<unsigned>(squishiness) << "\n";
Can the Ardrites do better than that? 

Yes, they can. 

Format strings 


Surprisingly, the answer comes from the ancient 1960s (Gregorian calendar) Earth technology, format strings (in a way, this is similar to the story of coroutines). C++ had this technology all along in the form of the printf family of functions and later rediscovered in std::put_time

Some current Ardrite technology
What makes format strings so useful is expressiveness. With a very simple mini-language, you can easily express complex formatting requirements. To illustrate this, let’s rewrite the example above using printf:
#include <cstdint>
#include <cstdio>
 
void log_error(std::FILE* log, std::uint_least8_t squishiness) {
  std::fprintf(log, "Invalid squishiness: %02x\n", squishiness);
}
Isn’t it beautiful in its simplicity? Even if you’ve somehow never seen printf in your life, you can learn
the syntax in no time. In contrast, can you always remember which iostreams manipulator to use? Is it std::fill or std::setfill? Why std::setw and std::setprecision and not, say, std::setwidth or std::setp

A lesser-known advantage of printf is atomicity. A format string and arguments are passed to a formatting function in a single call which makes it easier to write them atomically without having an interleaved output in the case of writing from multiple threads. 

In contrast, with iostreams, each argument and parts of the message are fed into formatting functions separately, which makes synchronization harder. This problem was only addressed in C++20 with the introduction of an additional layer of std::basic_osyncstream.** 

However, the C printf comes with its set of problems which iostreams addressed: 
  • Safety: C varargs are inherently unsafe, and it is a user’s responsibility to make sure that the type of information is carefully encoded in the format strings. Some compilers issue a warning if the format specification doesn’t match argument types, but only for literal strings. Without extra care, this ability is often lost when wrapping printf in another API layer such as logging. Compilers can also lie to you in these warnings. 

  • Extensibility: you cannot format objects of user-defined types with printf
With the introduction of variadic templates and constexpr in C++11, it has become possible to combine the advantages of printf and iostreams. This has finally been done in C++20 formatting facility based a popular open-source formatting library called {fmt}

The C++20 formatting library


Let’s implement the same logging example using C++20 std::format:
#include <cstdint>
#include <format>
#include <iostream>
 
void log_error(std::ostream& log, std::uint_least8_t squishiness) {
  log << std::format("Invalid squishiness: {:02x}\n", squishiness);
}
As you can see, the formatting code is similar to that of printf with a notable difference being {} used as delimiters instead of %. This allows us and the parser to find format specification boundaries easily and is particularly essential for more sophisticated formatting (e.g. formatting of date and time). 

Unlike standard printf, std::format supports positional arguments i.e. referring to an argument by its index separated from format specifiers by the ':' character:
log << std::format("Invalid squishiness: {0:02x}\n", squishiness);
Positional arguments allow using the same argument multiple times. 

Otherwise, the format syntax of std::format which is largely borrowed from Python is very similar to printf’s. In this case format specifications are identical (02x) and have the same semantics, namely, format a 2-digit integer in hexadecimal with zero padding. 

But because std::format is based on variadic templates instead of C varargs and is fully type-aware (and type-safe), it simplifies the syntax even further by getting rid of all the numerous printf specifiers that only exist to convey the type information. The printf example from earlier is in fact incorrect exhibiting an undefined behaviour. Strictly speaking, it should have been
#include <cinttypes> // for PRIxLEAST8
#include <cstdint>
#include <cstdio>
 
void log_error(std::FILE* log, std::uint_least8_t squishiness) {
  std::fprintf(log, "Invalid squishiness: %02" PRIxLEAST8 "\n",
               squishiness);
}
Which doesn’t look as appealing. More importantly, the use of macros is considered inappropriate in a civilized Ardrite society

What's in vogue in the Ardrite society?
Here is a (possibly incomplete) list of specifiers made obsolete: hh, h, l, ll, L, z, j, t, I, I32, I64, q, as well as a zoo of 84 macros:
    Prefix  intx_t  int_leastx_t    int_fastx_t     intmax_t    intptr_t
    --------------------------------------------------------------------
    d       PRIdx   PRIdLEASTx      PRIdFASTx       PRIdMAX     PRIdPTR
    i       PRIix   PRIiLEASTx      PRIiFASTx       PRIiMAX     PRIiPTR
    u       PRIux   PRIuLEASTx      PRIuFASTx       PRIuMAX     PRIuPTR
    o       PRIox   PRIoLEASTx      PRIoFASTx       PRIoMAX     PRIoPTR
    x       PRIxx   PRIxLEASTx      PRIxFASTx       PRIxMAX     PRIxPTR
    X       PRIXx   PRIXLEASTx      PRIXFASTx       PRIXMAX     PRIXPTR
In fact, even x in the std::format example is not an integer type specifier, but a hexadecimal format specifier, because the information that the argument is an integer is preserved. This allows omitting all format specifiers altogether to get the default (decimal for integers) formatting:
log << std::format("Invalid squishiness: {}\n", squishiness);

User-defined types 


Following a popular trend in the Ardrite software development community, you decide to switch all your code from std::uint_least8_t to something stronger-typed and introduced the squishiness type:
enum class squishiness : std::uint_least8_t {};
Also, you decide that you always want to use ANSI-standard formatting of squishiness which will hopefully allow you to hide all the ugliness in operator<<:
std::ostream& operator<<(std::ostream& os, squishiness s) {
  return os << std::setfill('0') << std::setw(2) << std::hex
            << static_cast<unsigned>(s);
}
Now your logging function looks much simpler:
void log_error(std::ostream& log, squishiness s) {
  log << "Invalid squishiness: " << s << "\n";
}
Then you decide to add another important piece of information, sepulka security number (SSN) to the log, although you are afraid it might not pass the review because of privacy concerns:
void log_error(std::ostream& log, squishiness s, unsigned ssn) {
  log << "Invalid squishiness: " << s << ", ssn=" << ssn << "\n";
}
To your surprise, SSN values in the log are wrong, for example:
log_error(std::cout, squishiness(0x42), 12345);
gives
Invalid squishiness: 42, ssn=3039
After another debugging session, you realize that the std::hex flag is sticky, and SSN ends up being formatted in hexadecimal. So you have to change your overloaded operator<< to
std::ostream& operator<<(std::ostream& os, squishiness s) {
  std::ios_base::fmtflags f(os.flags());
  os << std::setfill('0') << std::setw(2) << std::hex
     << static_cast<unsigned>(s);
  os.flags(f); // restore state!
  return os;
}
A pretty complicated piece of code just to print out an SSN in decimal format. 

A complicated user type waiting to be printed
std::format follows a more functional approach and doesn’t share formatting state between the calls. This makes reasoning about formatting easier and brings performance benefits because you don’t need to save/check/restore state all the time. 

To make squishiness objects formattable you just need to specialize the formatter template and you can reuse existing formatters:
#include <format>
#include <ostream>
 
template <>
struct std::formatter<squishiness> : std::formatter<unsigned> {
  auto format(squishiness s, format_context& ctx) {
    return format_to(ctx.out(), "{:02x}", static_cast<unsigned>(s));
  }
};
 
void log_error(std::ostream& log, squishiness s, unsigned ssn) {
  log << std::format("Invalid squishiness: {}, ssn={}\n", s, ssn);
}
You can see the message "Invalid squishiness: {}, ssn={}\n" as a whole, not interleaved with <<, which is more readable and less error-prone. 

Custom formatting functions 


Now you decide that you don’t want to log everything to a stream but use your system’s logging API instead. All your servers run the popular on Enteropia GNU/systemd operating system where GNU stands for GNU’s, not Ubuntu, so you implement logging via its journal API. Unfortunately, the journal API is very user-unfriendly and unsafe. So you end up wrapping it in a type-safe layer and making it more generic:
#include <systemd/sd-journal.h>
#include <format> // no need for <ostream> anymore
 
void vlog_error(std::string_view format_str, std::format_args args) {
  sd_journal_send("MESSAGE=%s", std::vformat(format_str, args).c_str(),
                  "PRIORITY=%i", LOG_ERR, nullptr);
}
 
template <typename... Args>
inline void log_error(std::string_view format_str,
                      const Args&... args) {
  vlog_error(format_str, std::make_format_args(args...));
}
Now you can use log_error as any other formatting function and it will log to the system journal:
log_error("Invalid squishiness: {}, ssn={}\n",
          squishiness(0x42), 12345);
The reason why we don’t directly call sd_journal_send in log_error, but rather have the intermediary vlog_error is to make vlog_error a normal function rather than a template and avoiding instantiations for all the combinations of argument types passed to it***. This dramatically reduces binary code size. log_error is a template but because it is inlined and doesn’t do anything other than capturing the arguments, it doesn’t add much to the code size either. 

Ardrite custom formatter machine
The std::vformat function performs the actual formatting and returns the result as a string which you then pass to sd_journal_send. You can avoid string construction with std::vformat_to which writes to an output iterator, but this code is not performance critical, so you decide to leave it as is. 

Date and time formatting 


Finally you decide to log how long a request took and find out that std::format makes it super easy too:
void log_request_duration(std::ostream& log,
                          std::chrono::milliseconds ms) {
  log << std::format("Processed request in {}.", ms);
}
This writes both the duration and its time units, for example: 
Processed request in 42ms. 
std::format supports formatting not just durations but all chrono date and time types via expressive format specifications based on strftime, for example:
std::format("Logged at {:%F %T} UTC.",
            std::chrono::system_clock::now());

Beyond std::format 


In the process of developing your SaaS system you’ve learnt about the features of C++20 std::format,
namely format strings, positional arguments, date and time formatting, extensibility for user-defined types as well as different output targets and statelessness, and how they compare to the earlier formatting facilities. 

Hello Earthlings!
Note to Earthlings: your standard libraries may not yet implement C++20 std::format but don’t panic 🚀: all of these features and much more are available in the open-source {fmt} library. Some additional features include: 
  • formatted I/O high-performance 
  • floating-point formatting 
  • compile-time format string checks 
  • better Unicode support 
  • text colors and styles 
  • named arguments 
All of the examples will work in {fmt} with minimal changes, mostly replacing std::format with  fmt::format and <format> with <fmt/core.h> or other relevant include. 

More about std::format 


If you like to read more about std::format here are some good resources: 

Glossary 


[1]
Ardrites – intelligent beings, polydiaphanohedral, nonbisymmetrical and pelissobrachial, belonging to the genus Siliconoidea, order Polytheria, class Luminifera. 
[2] Enteropia – 6th planet of a double (red and blue) star in the Calf constellation
[3] Sepulka – pl: sepulki, a prominent element of the civilization of Ardrites from the planet of Enteropia; see “Sepulkaria” 
[4] Sepulkaria – sing: sepulkarium, establishments used for sepuling; see “Sepuling” 
[5] Sepuling – an activity of Ardrites from the planet of Enteropia; see “Sepulka” 

The picture and references come from the book Star Diaries by Stanislaw Lem. 

>>>> and here ends the original text... >>>>

C++23 improvements 


(Added by Bartlomiej Filipek, aka Bartek 🙂): 

std::format doesn’t stop with C++20. The ISO Committee and C++ experts have a bunch of additions to this powerful library component. Here’s a quick overview of changes that we’ll get****:
  • P2216R3: std::format improvements - improving safety via compile-time format string checks and also reducing the binary size of format_to. This is implemented as Defect Report against C++20, so compiler vendors can implement it earlier than the official C++23 Standard will be approved! 
  • P2093 Formatted output - a better, safer and faster way to output text! std::print("Hello, {}!", name);
  • possibly in C++23: P2286 Formatting Ranges - this will add formatters for ranges, tuples and pairs. 
As you can see, a lot is going on in this area! 

Artworks 


Victor* originally wrote that guest blog post for Fluent C++, then this one on C++ Stories, updated with information about C++20.  I just reposted that later version, but also added some of Daniel Mróz's iconic illustrations for S. Lem's Cyberiad and Fables of Robots books.

Fables of Robots in original
The Cyberiad in German

Fables of Robots:
the new illustrations
for an Estonian edition
   
I know, I know... - these aren't about sepuling, sepulkaria and Ardrites, but the Ion Tichy stories didn't have illustrations as I read them. On the other side, the works of Daniel Mróz are simply out of this world 🚀! Thus I took a littlte bit of licentia poetica and misused robot images to represent Ardrites and their life. I hope you won't be mad with me because it conveys a kind of sci-fi feeling this guest post needed.

Now, this is the end, at last!

PS: I found the illustrations on internet, so should the links disappear, please let me know!!!

 --
 * Victor Zverovich is a software engineer at Facebook working on the Thrift RPC framework and the author of the popular {fmt} library, a subset of which is proposed into C++20 as a new formatting facility. He is passionate about open-source software, designing good APIs, and science fiction.You can find Victor online on Twitter, StackOverflow, and GitHub.

 ** C++20 std::osyncstream will:
"std::osyncstream(std::cout) << "Hello, " << "World!" << '\n';

...provide the guarantee that all output made to the same final destination buffer (std::cout in the examples above) will be free of data races and will not be interleaved or garbled in any way, as long as every write to the that final destination buffer is made through (possibly different) instances of std::basic_osyncstream."
See, I learned something new!!! Reading blogposts is helpful!

*** As stated in P0645R10:
"Exposing the type-erased API rather than making it an implementation detail and only providing variadic functions allows applying the same technique to the user code." 👍
**** pending C++23 format improvements: 
  • P2216(R3): checking of format strings in compile-time (metaprogramming FTW!)

  • P2093(R1):
    a) using std::print(...) instead of std::cout << std::format(...) - because it:
    "avoids allocating a temporary std::string object and calling operator<< which performs formatted I/O on text that is already formatted. The number of function calls is reduced to one which, together with std::vformat-like type erasure, results in much smaller binary code" !!!
    b) support for Unicode strings, like: std::print("Привет, κόσμος!") <=> printf("Hello world!")  
All in all, this will add the open points Victor complained about it his post here: std::format in C++20!

Friday, 26 August 2022

Do we need the Y-combinator in C++?


You may (or may not...) have heard of the Y-combinator proposal for the C++ standard library. If you are like me, then you may have been asking yourself why should we need such a thing in C++? Is that because of the current functional programming fad? Keeping up with the (programming-) Joneses? At that point you probably shrugged and went on with your life (like me)...

But then I met with a similar problem in some template metaprogramming contexts ans I think it is worth a separate blogpost. So I started writing this post... back in 2017 and finished it only now (2022) 😐.

Y-What???

So let us start with a question: what is the Y-combinator exactly? Do not fear, I won't be citing Wikipedia or some heavy CS-volume, I'll tell you just what it is, as it is. Shortly, it is a device (or more like - a trick) to add recursion to languages which does not support it natively.

It originates from lambda calculus - this, in its turn is a simple formalization of the notion of mathematical function. And lambda calculus does not have (BTW: did you notice that in modern days you have to know more and more of the CS-gibberish as working programmer?) recursion: a function can call another functions, as this is all that got formalized (see above). No looping there... You cannot loop when everything you have is function call with some parameters. Or can you?

The inventor of lambda calculus didn't think so, but his PhD student (some guy called, that's not a joke (!!!), Haskell Curry*) disabused him of that notion - he found the trick. We don't want to discuss it here (this post isn't about lambda calculus** in the end!) but you will maybe get a feeling of it after you have seen the C++ implementation.

Why in C++?

Ok, the Y-combinator stuff is clear now, but why do we need in in C++? AFAIK we have recursion in C++, by Jove, we even are blessed with iteration! Not so fast young Padawan, there is a context in the language where this is not true. Guess what... Of course, the lambdas.

The problem is, that we cannot refer to the current lambda in its body. When you try *this, this will give you the captured context class - does it ring a bell? Yes, thats the situation we have in Javascript's callbacks! So what can we do about it? in Javascript you just save the value of this in the self variable and forward it to the function. Can we do that in C++ too?

Well, not really: we'd need the type of lambda to declare a pointer to it, to be given in it's constructor... You see, it's a vicious circle :-/. Loosely typed languages escape this predicament by just not typing anything, but what can we do with our oldskool C++ type system?

First, we could request a new language feature - why not? It's so obvious, that somebody even tried to do this (guess who?***):
  auto foo = [] self (int x) -> int
  {
     if(x == 0) 
       return 0;
     else
       return self(x - 1);
  }
Here there is additional "parameter" in lambda's definition (i.e. self) that can be used inside of the lambda. But as Bjarne is known to dislike solutions which require a new language features if the problem can be solved in library (written 2017) , the question is: can we have a workaround for this?

How?

The easy way is to use std::function to wrap the lambda. As it uses type erasure, there's no need for the exact type and thus we can duplicate the solution of loosely typed languages! Here is the xample code from the proposal:
  std::function<int(int, int)> gcd = [&](int a, int b) 
  {
    return b == 0 ? a : gcd(b, a % b);
  };
  
  // use:
  int res = gcd(20, 110);  
Bingo? Not really, this solution shares one weekness with dynamically typed languages - it sucks at performance! Why's that? I won't discuss it in detail here, let it be enough to say that std::function generally isn't by any means a paragon of performance.

However, we can work around the problem by just defining a, let's call it, "almost"-lambda, and then invoking it form the outside passing its own reference as one of the parameters! But how would that look like? Show me the code! Voila, here is an example implementation for a left fold of a sequence using lambdas:
template <typename Acc, typename F, typename... T>
  // wrapper
  constexpr auto foldLeft(F func, Acc acc, T... xs)
  {
    // the "almost"-foldLeft-lambda
    auto step = [=](auto self, auto acc_, auto x_, auto... xs_) 
    {        
      // calculation
      auto sum = func(acc_, x_);

      // recursion?
      if constexpr(sizeof...(xs_) != 0)
        return self(self, sum, xs_...);
      else
        // finish
        return sum;        
    };

    // result: the fully recursive lambda!
    return step(step, acc, xs...);
  }
If you pay attention to the comments and give it a little thought, this code should be clear enough. Now let us test it:
  #include <iostream>

  int main()
  {  
    std::cout << "sum 1,2,3,4,5 = " 
              << foldLeft([](int a, int b) { return a + b; }, 
                          0,
                          1,2,3,4,5);

    std::cout << "\nfact 1,2,3,4,5 = " 
              << foldLeft([] (int a, int b) { return a * b; }, 
                          1,
                          1,2,3,4,5);                          
  }
and indeed we get the following output:
  sum 1,2,3,4,5 = 15
  fact 1,2,3,4,5 = 120
Good, seems to be working!

Abstracting things away?  

As programmers, we are are trying to separate the functionalities for sake of code clarity. Could we somehow abstract away this whole business of forwarding the reference to self? As it seems, this is possible with followintg trick:
  #include <utility>

  template<class F>
  struct y_combinator_impl 
  {
    F func; // recursive lambda (taking self as 1st parameter)

    template<class...Args>
      decltype(auto) operator()(Args&&...args) const 
    {
      // forward the reference to self when called!
      return func(*this, std::forward<Args>(args)...);
    }
  };

  template<class F>
  y_combinator_impl<std::decay_t<F>> make_y_combinator(F&& func) 
  {
    return {std::forward<F>(func)};
  };
The trick here is that we do not forward the reference of a lambda directly, but use a plain, old C++ class wrapping the lambda instead! Out of a sudden we have no problems whatsoever with getting a reference of the recursive function object! Problem solved using an additonal level of abstraction! 🙂 

With the above code we can simplify our implementation of left fold as follows:
template <typename Acc, typename F, typename... T>
  constexpr auto foldLeft(F func, Acc acc, T... xs)
  {
    // the "almost"-foldLeft-lambda
    auto step = [=](auto self, auto acc_, auto x_, auto... xs_) 
    {        
      auto sum = func(acc_, x_);

      if constexpr(sizeof...(xs_) != 0)
        // simplify: no passing of self-reference needed!
        return self(sum, xs_...);
      else
        return sum;        
    };

    // "bless" the almost-lambda, invoke it with arguments
    return make_y_combinator(step)(acc, xs...);
  }
  
  // use:
  std::cout << "sum 1,2,3,4,5 = " 
            << foldLeft([](int a, int b) { return a + b; }, 
                         0,
                         1,2,3,4,5);  
In fact, we can simplify it even further:
  auto almost_lfold = [=](auto self, auto func, auto acc_, auto x_, auto... xs_) 
  {        
    auto sum = func(acc_, x_);

      if constexpr(sizeof...(xs_) != 0)
        return self(func, sum, xs_...);
      else
        return sum;        
  };

  auto fold_left = make_y_combinator(almost_lfold); // curried with "almost_lfold"!

  // use:
  std::cout << "sum 1,2,3,4,5 = " 
            << fold_left([](int a, int b) { return a + b; }, 
                         0,
                         1,2,3,4,5);
Now the trick becoms even clearer - the make_y_combinator() function call only wraps the lambda in a plain, old C++ class and leaves the call operator unspecified at first. Only when the call operator is invoked, will it be generated from its template specification, thus leaving us with the impression of a preexisting curried function. Nice!

The proposal

The proposal we mention (P0200R0) includes following example implementation of the Y combinator:
  template<class Fun>
  class y_combinator_result {
    Fun fun_;
  public:
    template<class T>
    explicit y_combinator_result(T &&fun): fun_(std::forward<T>(fun)) {}

    template<class ...Args>
    decltype(auto) operator()(Args &&...args) {
        return fun_(std::ref(*this), std::forward<Args>(args)...);
    }
  };

  template<class FunT>
  decltype(auto) y_combinator(Fun &&fun) 
  {
    return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun));
  }
On a cursory look upon it, we can see that its std::y_combinator() function corresponds to our make_y_combinator() and the std::y_combinator_result class to our y_combinator_impl structure with the applied technique being exactly the same. After having understood our home-made implementation from above, we shouldn't have any problems reading the example implementation from the proposal!

Let us finally show the recursive lambda example used in the proposal. The code follows below:
  auto almost_gcd = [](auto gcd, int a, int b) -> int 
  {
    return b == 0 ? a : gcd(b, a % b);
  };
  
  auto gcd = std::y_combinator(std::ref(almost_gcd));
  
  std::cout << gcd(20, 30) << std::endl;
Here you can see the pattern present in all the explanations of the Y combinator - first we define an "almost" implementation, then we "bless" it with the Y combinator and voila, the recursion is automagically there!

OK, next let us try and find out if the above example can be written with our home-made code for Y combinator:
  // lambda from the proposal:
  auto almost_gcd = [](auto gcd, int a, int b) -> int 
  {
    return b == 0 ? a : gcd(b, a % b);
  };
  
  // use our own impl. to "bless" it
  auto gcd = make_y_combinator(std::ref(almost_gcd));
  
  // test:
  std::cout << "\ngcd 20,30 = " << gcd(20, 30) << std::endl;
  std::cout << "\ngcd 77,122 = " << gcd(77, 122) << std::endl;
and indeed we get the following output:
  gcd 20,30 = 10
  gcd 77,122 = 11 
Seems to be working too, cool!

Needed?

Now, at last we can respond to the question we posed in the title - do we really need the Y combinator in C++? The short answer is: it depends. The longer answer is: maybe. The long answer follows below.

To  begin with, passing the self parameter down in the recursion isn't that difficult. We can even get more into functional programming style and write the foldLeft example as follows****:

template <typename Acc, typename F, typename... T>
  constexpr auto foldLeft(Acc acc, F func, T... xs)
  {
    auto step = [=](auto self)
    {
      return [=](auto acc_, auto x_, auto... xs_)
      {
        auto sum = func(acc_, x_);

        if constexpr(sizeof...(xs_) != 0) 
          return self(self)(sum, xs_...); 
        else
          return sum;                     
      };
    };

    return step(step)(acc, xs...);        
  }
Depending on your background this style can be more or less eaysy on your eyes (admittedly the self(self)/step(step) syntax can look pretty confusing at first 😨).  What we are doing here is to define a lambda returning a lambda and then first call the outer lambda to access the inner lambda and call it in its turn. Calling the outer lambda with a parameter is what we call currying in functional languages like Haskell (Haskell's curry anyone? 😉).

From this perspective the answer is a maybe, because the Y combinator takes care of  passing the self parameter down in the recursion, provided, of course, you know what a Y combinator is. The problem is, not many imperative programmers seem to know that. Maybe recurse() would be a better name for it? 

In C++23, however, we will have an entire new situation! As it seems, will wil get a new language feature: the "Deducing this". As stated in the recent P0847R7 proposal, we can now (as its side-effect) implement recursive lambdas like that:
  // this proposal
  auto fib = [](this auto self, int n) {
      if (n < 2) return n;
      return self(n-1) + self(n-2);
  };
So you have it - in C++23 we don't need it al all! 

So the second answer is then it depends, namely, it depends on what C++ version you are using... Admittedly, the syntax of the of the above recursive lamba maybe isn't that self-explaining, but as this one is already getting too long, I will defer discussion of P0847 to a separate post. See you there!

PS: Get the code to play with from this Github gist: https://gist.github.com/mrkkrj/712ad5c1e6cfb6d91262b3582bd691a6

--
* he's name should rather be Curry Haskell or Currying Haskell or Haskell "Is-By-Default" Curried! 😊

** you can read about lambda calculs and C++ here: https://yongweiwu.wordpress.com/2014/12/14/y-combinator-and-cplusplus/

*** yes, you guessed it: proposal P0200R0 (Add Y Combinator to the Standard Library), but only as a side note. Also a separate proposal allowing just that existed: P0839R0 (Recursive lambdas)



Thursday, 30 June 2022

Some praise for my Qt book

You might perhaps already know that I recently wrote a book (blogged about it here)! In the book I discussed various general program performance topics but also some more specific, Qt related ones, for example Qt's graphical or networking performance.
 
Recently I was very happy (and very surprozed) to have read some kind words about my book, and I just wanted to show off a little 😇 and cite them here. So let's start!

First Ivica* mentioned he had my book, and it wouldn't be that bad:


After I thanked him, he said he actually liked it!


What I was particularly pleased about is (beside the "well written" phrase) that:
  • 95% ... can be applied to other frameworks
  • very good read for intermediate/advanced C++ developer
Why? Because all of that were my goals when writting the book, so I can congratulate myself on a good job! What can I say, thanks a lot, Ivica!

Thank you!

You may ask what the book was about, really? Let's have a look:
  • Part I - Basics
    • Intro - basic performance wisdom and techniques, hardware architecture and its impact.
    • Profiling - performance tools and how to use them. As I said, we don't want to make it easy for us and look at the Windows platform!
    • C++ - how performant is C++ really? And what are optimizations the compiler (and linker) can do?
  • Part II - General Techniques
    • Data structures and algorithms - what is the performance of Qt containers and strings? Do we have to use them?
    • Multithreading - Qt's take on threading and how to speed up your program with concurrency.
    • Fails - some more memorable performance problems I encountered in my programming career.
  • Part III - Selected Qt Modules
    • File I/O etc - Qt and file system performance, JSON and XML parsing. Also memory mapped files and caching.
    • Graphic - GUI, OpenGL, widget and QML performance. Probably the most interesting part of the book.
    • Networking - network performance and network support in Qt. Because we live in the ubiquitous connectivity era!
  • Part IV - Goodies
    • Mobile and embedded - how to use Qt on mobile and embedded (a kind of advanced chapter applying all we have learned before to two specific platforms)
    • Testing - a goodie chapter about testing techniques, GUI testing and performance regression tests. At the end this chapter turned out pretty interesting!
Got you interested? Then read my detailed blogpost introducing the book!

--
* I maybe have to mention, that Ivica has a well established reputation in the performance community -  just look up these links:
Impressive, isn't it?

Tuesday, 4 January 2022

Named parameters for C++11 with variadic templates vs a language feature


As I'm a little obsessed with emulating Python-style named parameters in C++ (of which several previous posts on this blog could serve as witnesses) when I saw the following line of code*:
  auto p = Popen({"cat", "-"}, input{PIPE}, output{"cat_fredirect.txt"});
I wanted to see how named parameters are implemented in this library. 

Variadic templates implementation

So, without much ado, here is the implementation of Popen. It is using variadic templates, but don't fear, it's not as complicated as it sounds:
  // 1. named parameters are bound to the variadic param set ...args

  template <typename... Args>
  Popen(std::initializer_list<const char*> cmd_args, Args&& ...args)
  {
    vargs_.insert(vargs_.end(), cmd_args.begin(), cmd_args.end());
    init_args(std::forward<Args>(args)...);
 
    // ...
  }

  // 2. named params are forwarded to:

  template <typename F, typename... Args>
  inline void Popen::init_args(F&& farg, Args&&... args)
  {
    // 3. let ArgumentDeducer do the job!
    detail::ArgumentDeducer argd(this);    
    argd.set_option(std::forward<F>(farg));
    
    // 4. now process next named param from variadic parameter pack:
    init_args(std::forward<Args>(args)...);
  }

  // the ArgumentDeducer class has an overload for each of the named parameter types

  inline void ArgumentDeducer::set_option(output&& out) {
    if (out.wr_ch_ != -1) popen_->stream_.write_to_parent_ = out.wr_ch_;
    if (out.rd_ch_ != -1) popen_->stream_.read_from_child_ = out.rd_ch_;
  }
  
  inline void ArgumentDeducer::set_option(environment&& env) {
    popen_->env_ = std::move(env.env_);
  }
  
  // etc, etc...  
  
This all is very nice, but also very tedious. You can implement it as part of your library to be friendly to your users, but most people won't be bothered to go to that lengths. What about some support from our language? Let have a look at the shiny new C++ standard (most of us aren't allowed to use yet...): 


The C++ 20 hack

In C++20 we can employ the following hack** that is using C99's init designators:
  struct Named 
  { 
    int size; int defaultValue; bool forced; bool verbose; 
    Named() : size(0), defaultValue(0), forced(false), verbose(false) {};
  };

  void foo(Named);

  void bar()
  {
    foo({ .size = 44, .forced = true});
  }
Discussion: OK, this just looks like a hack, sorry! We could as well use a JSON literal as input parameter and circumvent the normal C++ function parameter mechanism altogether: 
  foo({ "size": 44, "forced": true});
The difference is that the Named-hack will result in members passed in registers, and JSON-hack won't. Unfortunately, the latter is more readable, and that's why we are doing all that in first place! 😞
 
The language proposal

As so often with C++, the various workarounds don't really cut it. So please, please Mr. Stroustrup, can we have named parameters as a language feature?

As a  matter of fact, there's even a "minimal" proposal for this feature:

    http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2018/p0671r2.html

but unfortunately, I don't know what it's status is just now... Is there even a possibility to check for status of different standard proposals??? Does anybody know?  🤔 (Please respond in the comments!)

If accepted, we could write in our case:
  void bar()
  {
    foo(size: 44, forced: true);
  }
Another example taken from the proposal:
  gauss(x: 0.1, mean: 0., width: 2., height: 1.);
Here you can see the benefits of that feature in its entirety as all the parameter passed to the gauss() functions are floats!!! 

Alas, althought this minimalistic proposal stems from 2018 it not part of C++20 (nor of C++23
AFAIK). What can I say - this just fits nicely in the more general notion of legendary user-unfriendliness of C++... 😞 To cheer everybody up - a classic: "but... we have ranges!".

Update

Reading the "2021 C++ Standardization Highlights" blogpost*** I stumbled upon following formulation:
"Named Arguments Making a Comeback? 
While it has not yet been officially submitted as a P-numbered paper, nor has it been reviewed by EWG, I’ve come across a draft proposal for named arguments (in this formulation called designated arguments) which was circulated on the committee mailing lists (including the public std-discussion list); there’s also an accompanying video explainer. 
This looks to me like a thorough, well-researched proposal which addresses the concerns raised during discussions of previous proposals for named arguments ..."

 So maybe there's hope after all? Never say never!

--
   Blogpost: http://templated-thoughts.blogspot.de/2016/03/sub-processing-with-modern-c.html

** source: https://twitter.com/jfbastien/status/941740836135374848 -> "Actually you don't even need to repeat "Named". The wonderful ({ .params }) style!"

*** found here: https://botondballo.wordpress.com/2022/01/03/2021-c-standardization-highlights/. the referenced quasi-proposal is: "D2288R0 Proposal of Designated Arguments DRAFT 2" to be found at Google Docs here.