Functional programming, immutability and the World.

In C++  if you write a cooking_meat() function it returns NOT a new piece of meat, but one with a changed state.

In Clojure we have:

• immutability - so we get here a NEW piece of meat

In real life it'd be not a wholly new piece of meat!

• world -> constantly changing state, we cannot understand all of the Change
• thus -> functional programming - our unability to cope with Change, to understand the world we are living in?

The symbol-pointer equivalence.

Recently, I realized an interesting little fact when comparing LISP-type and C-type languages. It may seem that, by their design and philosophy, they cannot be more distant from each other, but well, it all boils down to memory locations and addresses.

Let's take the a LISP symbol a, and a C++ object obj. If you take a for itself, it resolves to its value, if you don't want that, you have to quote it. On the other side, of you take a pointer to the C++ obj, you have to dereference it directly if you want the underlying value:

  'a <=> &obj
   a <=> obj

and

   a <=> *obj_ptr
  'a <=> obj_ptr

I think it's cool. Think of symbols as pointers.

Birthday paradox, Lotto and learning

Warning: this post is about how we learn but in reality we don't.

You may know the "birthday paradox" - it's a cute little story in probability theory, and as it happens it might be useful to know in a programming interview. So many of us learn about it and might even be able to derive the probability bound and to reason about it. But do we really learn? Or do we just memorize some story which will be called out in the "technical interview"?

Let us apply it to the case of lottery gambling. ...

The hard question here is - which numbers should I choose to win the jackpot. Well, the answer is, we don't know. The not so hard question is - which numbers NOT to choose. Here we can definitely offer some responses. We shouldn't choose the numbers most people would choose. Can you sense the application here? Well, most people will use their birthday date in some form (as it's the number they are most accustomed to). And the birthday paradox teaches us that... we ourselves shouldn't use it!

Would you see that? Possibly not. No party, no room, no people talking to each other as in the classic setting of the story. That's sad. That's not what I like about maths (and programming). But isn't it like that in the real life? If you'll be interviewed you have to reproduce the known answer first. If you're good at it, some deeper questions will follow, most of them with a known answer. And we learn that stuff to be used in an interview... But is that learning?


PS: admittedly, this isn't any direct application of the paradox, but rather a "reverse" one, nevertheless I see it as cool math giving hints in seemingly unrelated problem. And when we learn about it, we don't play enough with ideas, we just want to "pack it in" and have it ready for that interview.

Some basic decltype-SFINAE

In this blog I'd like to give you the impression that I'd know everything ;-), but, alas, that's not true. Mainly because with the advent of C++11 there's a lot of things for me to learn. You may say I'm late to the party, and yes, I was somehow lazy playing (or rather not playing:) with C++11 compilers. That was because my clients didn't want to use the newest features yet (you know, a bunch of conservative ... etc.). But now, all of a sudden, I can use every C++11 and Boost feature I want in my daily work (yay!!!), and there's definitively a difference between playing with something and using it on a daily basis!

Back to the things I should learn. There are many of them, but we'll take the decltype-SFINAE as an example. The what-SFINAE? Or: the decltype-what?? Or, even worse: the what-what???

So what is SFINAE really? You can google it, or you can just take my word that SFINAE works by purposely introducing compile errors (thus the SF part in the name) which will be then ignored by compiler, (the INAE part in the name) just to remove one of template specializations to suit your purpose!

The idea is that for one class you'll have one set of template definitions (where the unwanted ones will be ignored by compiler), and for an another class a different one. Simple, isn't it? ( BTW as I'm getting older and older I came to recognize that most of the human ideas are simple, but some of them just aren't clearly stated; that seems to be an ego-thing for some people...)

So what is the decltype-SFINAE? Simple again, it's using SFINAE in the C++11 auto+decltype syntax for function declarations. Like here:

  template <class T> auto xxx() -> decltype(XXX, string) { ... }

How's that? Remember, decltype takes an expression as argument, and comma operator in expressions renders the last part as the value, so everything before the comma (i.e. the XXX thing) can be used to fool the compiler into/out of SFINAE. Tada!

When I first saw this technique in action*, used for detecting if some method is defined in a given class, there was an utility test class defined:

  template<typename T> struct has_size_method 
  {  
    //...

    template&ltclass C> static yes test(SFINAE<C,&C::size>*); // won't explain this impl.!

  public:
    static constexpr bool value = std::is_same<decltype(test<T>(nullptr)),yes>::value;
  };

and then it could be used like that:

    cout << has_size_method<ClassXXX>::value;

I wanted the same functionality (i.e. detection of a special optional method) but I didn't want another utility class. Frankly speaking, I'm more for the direct approach, not for burying simple concept under irritating levels of indirections. I a word, there had to be a better way! So I tried this:

  // got get_channel_id()?
  template <typename T, typename U>
  auto mk_object_name(T* obj, U prefix) 
    -> decltype(std::declval<T>().get_channel_id() == 1, std::string()) 
  {            
    return format_strg(prefix * 1000 + obj->get_channel_id(), std::hex, typeid(*obj).name());
  }
  
  // nope!
  template <typename T, typename U>
  std::string mk_object_name(T* obj, U prefix, T* obj2 = nullptr) 
  {
    return format_strg(prefix, std::hex, typeid(*obj).name());
  }

The first overload will be removed by SFINAE if the type T doesn't have the get_channel_id() method, the second one will be always present in the normal case, and let's hope that it's sufficiently different for the first one. Simple, isn't it? Then I used it like this:

  struct XXX {
    int get_channel_id() { return 1; } 
  };
  struct YYY {
    int get_YYY_id() { return 1; } 
  };

  main()
  {
    XXX x;    
    std::string nameX = mk_object_name(&x, 100);
    std::cout << nameX << std::endl;

    YYY y;    
    std::string nameY = mk_object_name(&y, 200);
    std::cout << nameY << std::endl;
 }

Alas, it didn't work for the XXX struct. That is what comes from hoping that the templates will just match! The obvious problem here is, that in this case both overloads are enabled. You did spot it at once? Sorry, I said this is a post about basic(!) decltype-SFINAE! So what can we do to hide the base version if the extended version is possible? A template function for dispatching to the desired overload proved to be sufficient:

  // actual functions
  template <typename T, typename U>
  auto mk_object_name_helper(T* obj, U prefix, int) 
    -> decltype(std::declval<T>().get_channel_id() == 1, std::string()) 
  {            
    return format_strg(prefix * 1000 + obj->get_channel_id(), std::hex, typeid(*obj).name());
  }

  template <typename T, typename U>
  std::string mk_object_name_helper(T* obj, U prefix, long) 
  {
    return format_strg(prefix, std::hex, typeid(*obj).name());
  }

  // "dispatching" function
  template <typename T, typename U>
  std::string mk_object_name(T* obj, U prefix) 
  {
    return mk_object_name_helper(obj, prefix, 0);
  }

And then it worked like a charm**. I think, it's not too much overhead when compared to the has_size_method template shown above. The dispatching function just uses the fact that int is a better overload for zero than long.

You can compile the above code online, for example at http://gcc.godbolt.org/ - use g++-4.8 with the -std=c++11 option. The nice thing there is that in the assembler window you can see what template overload was selected. Additionally you'll see the famous template bloat in action! It's fun! If you'd only like to let it run online, try http://liveworkspace.org/.

PS: And what was it all for? Did you get it? We were generating object names for various "software device" types, some supporting only the board IDs, some offering additional support for channels.

--
* look for example here: http://dev.krzaq.cc/checking-whether-a-class-has-a-member-function-with-a-given-signature/

** There's another way, of course! Facebook's Folly library accomplishes it with enable_if and the pair of is_same and !is_same in the definition of the return value of a function:

  template <class T>
  typename std::enable_if<
    HasLockUnlock<T>::value && !std::is_same<T, boost::shared_mutex>::value>::type
  acquireRead(T& mutex) {
    mutex.lock();
  }
  //Special case for boost::shared_mutex.
  template <class T>
  typename std::enable_if<std::is_same<T, boost::shared_mutex>::value>::type
  acquireRead(T& mutex) {
    mutex.lock_shared();
  }

 Look here for overview of how the classic enable_if<> can be used. 

How does C++11 bugfixing in C++14 look like?

Maybe you've heard it already, but the planned C++14 standard will be a small, bugfixing release for the C++11 specification and not a true next version of C++.

Well, not really (see here), there are a couple of interesting genuine new features added! For example: generic lambdas (yay! see my old post...), lambda capture initialization expressions, function return type deduction (i.e. auto on functions), templates for variables, runtime-sized arrays (int arr[varX]), binary literals (011100b), shared mutexes and locks, std::optional, standard user-defined literals (like "xxx"s for std::string), std::dynarray, tuple access via type (get<int>(tupleX)). I don't know what you think, but for me that's quite a list of new features (and that's not a complete list) to be digested!

But some of the changes are real bugfixes. For myself, I couldn't imagine what bugfixing could be supposed to mean - are there bugs in the standard? With best C++ gurus working on that? Well, unfortunately there are! One of them is the absence of std::make_unique() counterpart to the std::make_shared(). What is is the reason for that? Herb Sutter explains:

" That C++11 doesn’t include make_unique is partly an oversight, and it will almost certainly be added in the future. "

 What, an oversight! But beacuse of that you cannot write a safe code for multiple resource initialization using std::unique_ptr! That (and hearing them speaking on Going Native 2013) convinces me that the gurus are just humans and developers like you and me!

Another case in point is taken from a discussion on complex initialization idiom. Here's the code:

  const int i = [&]{
    int i = some_default_value;
    if(someConditionIstrue)
    { 
      // Do some operations and calculate the value of i;
      i = some calculated value;
    }
    return i;
  } () // note: () invokes the lambda!

Well, it looks absolutely innocuous (and kind of JavaScript like!), and it will even compile. But Andrzej Krzemieński pointed out that:

I believe it is not a valid C++11 code. According to sect 5.1.2 para 4, when the body of the lambda is not a simple return statement its deduced return type is void. While the expectation that this example would work is logical, and likely acceptable in C++14, C++11 seems to refuse it.

And you know what? Herb explains:

The committee has already pretty much agreed that this should be allowed (which is why our compiler also already supports it, and with GCC and Clang that would make it de facto portable), and this extension is likely to be voted into the C++ working paper soon (this month, or September).

Thus making it a classic example of bugfixing! Well, not really, the standard says that lambda return type can be deduced, but only when there is exactly one statement, and that statement is a return statement that returns an expression. OK, but compilers can do much more than that already, so it's an unnecessary restriction we can do away with! Thus in this case it's not really an oversight, but rather lack of time to process feedback from compiler writers. Bjarne was always saying that the committee is doing unpaid work and that mostly in their free time.

Update:

Ooops, I forgot that std::optional and std::dynarray were moved out of the standard and parked in TS.  Thanks for correction goes to @meetingcpp!

Some life hacking.

As I started several C++ blog posts but cannot finish a single one, there's definitely time for some some life-changing advice! This couple of lines from a great post seemed adequate:

Make a Habit of Making Things 

Too many people die with their best ideas still inside of them. 

Your legacy is what you share, not what you know or harbor within yourself. Unshared knowledge is like potential energy. It’s great to have, but it will never do anything unless you turn it into something else. 

Turn your knowledge into a book. Turn your inspiration into art. Turn your words into music. Turn your ideas into a business. Build something. Write something. Create something.  

... 

You can either be judged because you created something or ignored because you left your greatness inside of you. Your call.

I just let it uncommented as reminder and reference.

Named function arguments for C++(11)

Some time ago I wrote a post about emulating named parameters in C++. But in the meantime I discovered another possibility of low-cost emulation of that feature: just use the tags! Use what? OK, let's have an example. If you look up the C++14 proposal number N3554  "A Parallel Algorithms Library for C++" you'll see things like:

  std::sort(exec, vec.begin(), vec.end());

  // parallel sort with non-standard implementation-provided execution policies:
  std::sort(vectorize_in_this_thread, vec.begin(), vec.end());
  std::sort(submit_to_my_thread_pool, vec.begin(), vec.end());
  std::sort(execute_on_that_gpu, vec.begin(), vec.end());
  std::sort(offload_to_my_fpga, vec.begin(), vec.end());
  std::sort(send_this_computation_to_the_cloud, vec.begin(), vec.end());

You are right, execute_on_that_gpu and offload_to_my_fpga are tags! So how could we use that to name the arguments? What about:

  bool ok = funcXXX(1, 2, 3, delete_data, true);

OK, that's perhaps not that readable. A better idea were maybe:

  bool ok = funcXXX(1, 2, 3);              // default is delete_data == false
  bool ok = funcXXX(1, 2, 3, delete_data); // now just use an empty tag!

That would be arguably more in line with the new C++11 (or is it C++14?) look and feel, considering these examples from the standard:

  std::optional b{std::in_place, "1"};    // C++14: calls Big{"1"} in place (no moving)
  std::unique_lock l(m, std::defer_lock); // don't lock now!

  // use my_alloc(2) to allocate 10 ints in a vector in a tuple
  std::tuple<int, std::vector<int, my_alloc>, double> 
    t5(std::allocator_arg, my_alloc(2), 42, v,  -3.14);

  std::tuple<int, float> t(1, 3.14);
  std::pair<Foo, Foo> p1(t, t);  // call the Foo(std::tuple<int, float>) overload
  std::pair<Foo, Foo> p2(std::piecewise_construct, t, t); // call the Foo(int, float) overload

Seems to be a nice new pattern in the standard library, isn't it? So maybe the way ahead just using tags for bools to simulate named parameters? The more general attempt:

  bool ok = funcXXX(obj_id, 1, obj_value, 2, env_value, 3, replace_data);

could be also of merit but isn't that readable to the general public. On the other hand, the std::tuple constructor above uses it in that exact manner. Maybe a thing worth pondering about.

C low level programming

Recently I was repeatedly exposed to low level Windows code using C and Win32, and you know what, I didn't hate it completely! Surprise!

Let's go through the usual complaints:

1. Windows coding style --> horrible at the first sight, but you get used to it (see my previous post).

  bool DeleteRegistryValue (HKEY hKeyRoot, LPCTSTR pszSubKey, LPCTSTR pszValue)
  {
    HKEY hKey;
    LONG lRes = RegOpenKeyEx (hKeyRoot, pszSubKey, 0, KEY_SET_VALUE, &hKey);

    if (lRes != ERROR_SUCCESS)
    {
        SetLastError ((DWORD)lRes);
        return false;
    }

    lRes = RegDeleteValue (hKey, pszValue);

    //... etc

You see what I mean? Hungarian notation, uppercase function names, weird data type macros... But as I said, you'll get used to everything :-\.

2. Low level, unsafe C-library APIs --> come on, every programmer should know C (vide Joel*) and after a while you just know it and can work as quickly with lstrcmp() and others as with std::string (Heaven forbid CString's!)

3. Ugly OS API? --> OK, that's a bummer if you, like me, grew up with clean Unix kernel interface**. But what the heck, it's still system programming, low level, dirty, cool. I a word, I like it!

And do you know what I liked best? It's clean! No DLL dependencies, no hassle with VisualStudio distributables, Qt versions, manifests, load paths etc. Just your code and the system libraries. Small and beautiful. If you have a penchant for software aesthetics, you'll appreciate it too!

--
* http://www.joelonsoftware.com/articles/CollegeAdvice.html
** somehow the feelings of a LISPer forced to code in OCaml or even worse, in Java!