C++ Forget the templates. Use lambdas. Part 3

This time we go to the Lambda Top Gear. Forget the templates. Use lambdas. Part 3, can actually hurt the brain. If not feeling safe or no chaperone present, please leave now.

Or just jump back to Part 2, simple but useful text.

Lambda Top Gear
Lambda Top Gear. Forget the templates.

First and foremost I do know, I have not invented the core ideas in the code presented here.  But, I do not know the original author. If you are the one please let me know and I will state it clearly here.

LISP

Is a “LISt Processing language”. Importance (and beauty) of lists as a key concept in computing is proven way back in 1959. Here we will develop something very close to LISP Lists but using standard C++ lambdas and auto facility.

Thus, not LISP Lists but close approximation of them in modern C++.

Perhaps not an exact copy  (for that please use LISP) but still very functional and eminently usable C++ constructs.

For this journey you need one key ingredient: Open (and clear) mind.

Mind open to functional concepts, functional programing and “all that functional jazz” you have been listening about. And yes, if you are coming from JavaScript by any chance that will help a lot. RUST or HASKELL too. And now …

The Deep Dive

/*
The key abstraction : list lambda
*/
auto list = [&](auto ...xs) {
  /*return value is lambda */
  return [=](
/* whose single argument is lambda */
  auto proc_lambda
 ) {
/* which is called with variadic 
   arguments parameter pack 
   from the enclosing lambda 
   call stack 
 */
  return proc_lambda(xs...);
  };
};

Fig 0

First the usage

auto my_list = 
  list(
     1, '2', "3", false, 13.0f // param pack
  ); 
// result is lambda()

After this call my_list is an lambda. Exactly the one as declared inside  thelist() above. But. After the call it is with the defined closure around it. And that means  the arguments pack, the list() has been called with, is available to it as long as my_list variable exists.

This is the key to this code.  list( 1, '2', "3", false, 13.0f) lambda is a closure inside which my_list() was born and returned. The rules of language dictate the closure be available to my_list when my_list get’s called. And the closure call stack is part of it. Thus the parameters pack  1, '2', "3", false, 13.0f, is available inside my_list body.

So presented in some kind of “lambda implementation pseudo code” the first call to the list would be leaving this situation on the stack after it has happened.

/* conceptual view: pseudo implementation pseudo code */
auto list = [&](
  /*auto ...xs  -- parameter pack */ 
   1, '2', "3", false, 13.0f 
  ) 
  {
  /*return lambda */
  return [=](
    /* single argument is lambda */
    auto proc_lambda
    ) {
/* called with variadic arguments parameter pack 
   from the parent lambda call stack 
 */
  return proc_lambda(
    /* unpacked parameter pack ...xs */ 
      1, '2', "3", false, 13.0f );
  };
};

Fig 1

And the variable my_list is the lambda returned.

/*
 after 
 auto my_list = 
  list(1, '2', "3", false, 13.0f );
 this is the value of my_list
just a lambda
*/
[=] (auto proc_lambda) 
{
  return proc_lambda( 1, '2', "3", false, 13.0f );
};

Fig 2

To use it, you can call  my_list with exactly one argument that has to be a lambda .

my_list( some_other_lambda ) ;

This some_other_lambda will get called with list() parameters pack.

// first we called the list
auto my_list = list( 1, '2', "3", false, 13.0f )
// then we code lambda to be used as my_list argument
auto some_other_lambda = [] ( auto ... params )
{  /* implementation and return */
return true;

}
// then we use my_list with it
auto rezult = my_list( some_other_lambda ) ;
// some_other_lambda( 1, '2', "3", false, 13.0f )
// happens inside my_list() and return of
// some_other_lambda is passed back
// thus rezult is 'true'

Remember I am using here a conceptual view on the C++ lambda. C++ Lambdas are implemented as functors but we will keep it short and sweet and still true without mentioning this too much.

Thus we have our list (as params pack ) kept for us in the memory, on the calling stack of the list() lambda.  Opposite to LISP, this is lambda with list atoms (aka elements) preserved and present as parameter pack arguments of the lambda call.

Note: depending on the compiler the lambda arguments are not unpacked as above but might be unpacked from the original list(1, '2', "3", false, 13.0f) call above when and if needed. We just show it this way to make it simpler for you.

Into the known

John McCarthy has proven, in order to make them useful, only three commands are required to operate on lists. The three LISP lists core commands are: List, CAR and CDR.  List we have done. CAR returns the “head of the list” and CDR returns the  “tail of the list”.

The requirement for our standard C++ implementation, is this kind of usage:

/*
usage of 
3 key abstractions of 
modern C++
Lambda Lists
*/
auto my_list = list(1, '2', "3", false, 13.0f); 
// my_list is now lambda() internal to list()
auto my_head = head(my_list); 
// my_head is now list of one element -- list(1)
auto my_tail = tail(my_list); 
// my_tail is now list('2', "3", false, 13.0f)

Fig 3.

First the head(). Using my_list from above as explained, actually happens inside the head() implementation. The lambda that is argument to my_list is anonymous and inside the head() :

auto head = [&](auto list_lambda) {
/* list() has returned the list_lambda
   we call it here 
   it is executed in the closure of where
   it was created and that was the 
   call
   list ( 1, '2', "3", false, 13.0f ) 
*/
  return list_lambda(
  /* with anonymous lambda  */
  [=](auto first, auto ...rest) {
/*
first = 1, rest = '2', "3", false, 13.0f

 use the list() to return a new list
 */
   return list(first);
   }
  );
};

Fig 4.

Ok. This is a real head hurting code. Let us do it slowly step by step. Remember what was returned as a result of  the list() call above. Yes, just a lambda. Fig 2.

head() call uses that as its single argument. This is the list_lambda in the head() code. And that is given another anonymous lambda as its only argument. Huh.

So in pseudo code head() returns the following:

// conceptual view of the result 
// of the head(my_list) call
// my_list is the result of the list() 
// call above
return my_list (
  [=](auto first, auto ...rest) {
    return list(first);
   }
) ;

Fig 5.

But. my_list is coming from inside the call list(1, '2', "3", false, 13.0f); We say: list is the original closure where my_list was created.  Call stack of the list() call is still here.So,the lambda

[=](auto first, auto ...rest) {
    return list(first);
   }

Fig 6.

is the proc_lambda given to the result of  its closure: list(1, '2', "3", false, 13.0f); Again in pseudo code situation is this:

/*
 Fig 2 code with a proc_lambda 
 substitued with
 lambda from head() implementation 
*/
[=] ( /* proc_lambda given as argument inside the call  */ ) 
{
  return [=]( 
    /* first = */ 1, 
    /* ... rest = */ '2', "3", false, 13.0f )
    {
       return list( /* first */1) ; 
    }
};

Fig 7.

Please understand that the Fig 7 is executed back inside the closure of Fig 1.

I am sure not everyone is happy with this explanations. Again please comment and we will sort it out for you. Now please follow the rest, and then revisit.

The tail() implementation

auto tail = [&](auto list_lambda) {
   // use the lambda returned form list()
  return list_lambda(
    // this is the argument for it
    // proc_lambda from Fig 1 is 
    // substitued with this
     [=] (
      // the ...xs params pack
      // from the Fig 1
       auto first, auto ...rest
      ) 
     { 
       return list(rest...); 
     }
   );
};

Fig 8.

Again hopefully the comments should help.  We have list, head and tail let’s make two steps more to increase the usability of Lambda Lists.

auto length = [&](auto list_lambda) 
{
  return list_lambda(
  // elements of the list 
  // are params pack 
  // of the list() call stack
  // aka original closure
  // see Fig 1 and Fig 2
     [=](auto ...z) { return sizeof...(z); }
  );
};

Fig 9.

By now, I think you are beginning to like it?  Yes, the list elements  are the parameters pack of the list call. The rest is just lambdas reaching to it and using it.

Next step is quite useful and conceptually interesting. It opens a door to the rest of the “normal” standard C++ code to use Lambda Lists.

auto list_to_tuple = [&](auto list_lambda) {
 // 
 return list_lambda(
 [=](auto ...args) {
   return std::make_tuple(args...);
    }
  );
};

Fig 10

We simply collect all the argument of the list call and return them as tuple set.  And there is a lot of in the std library that uses tuples and nicely operates on them. For example my dbj::print() knows how to print the tuples but not how to print the list.

// usage
auto my_list = list(1, '2', "3", false, 13.0f); // return lambda() internal to list()
auto my_head = head(my_list); // returns list of one element -- list(1)
auto my_tail = tail(my_list); // returns list('2', "3", false, 13.0f)
/*
after playing with lambda lists we print what we need to print
we use list_to_tuple() because dbj::print() knows how to print touples
but not lambda lists
*/
dbj::print("\nlist: ", list_to_tuple(my_list));
dbj::print("\nhead: ", list_to_tuple(my_head));
dbj::print("\ntail: ", list_to_tuple(my_tail));

Fig 11

Would it be too cruel if we leave touple_to_list() implementation as an exercise to the reader :)

Dbj Lambda Lists
Dbj Lambda Lists in C++ notation