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.
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
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
/* 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
|
1 2 3 4 5 |
auto my_list = list( 1, '2', "3", false, 13.0f // param pack ); // result is lambda() |
After this call my_list is an lambda as made and returned from inside thelist() closure. Fig 0 tells you, resulting closure “sees” the closure around it, from which it was made and returned. And that means the arguments pack, (the list() has been called with) is available to the closure returned, as long as my_list variable exists.
This is the key:
list( 1, '2', "3", false, 13.0f)is a closure (aka lambda) inside which the resultmy_list()was born and returned. The rules of language dictate the param pack, is available inside my_list. Ditto; the parameters pack1, '2', "3", false, 13.0f,is available inside the closuremy_list.
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.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
/* conceptual view: pseudo implementation pseudo code, not C++ */ auto list = [&]( /*auto ...xs -- parameter pack example */ 1, '2', "3", false, 13.0f ) { /* make and return lambda */ return [=]( /* whose single argument when called, is lambda */ auto callback_ ) { /* internal lambda returns the result of calling the callback_ with the parameter pack available in the closure from the parent lambda */ return callback_( /* unpacked parameter pack ...xs */ 1, '2', "3", false, 13.0f ); }; }; |
Fig 1
And the variable my_list is the lambda returned.
|
1 2 3 4 5 6 7 8 9 10 11 |
/* after auto my_list = list(1, '2', "3", false, 13.0f ); this is the value of my_list just a lambda */ [=] (auto lambda_callback) { return lambda_callback( 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.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
// 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 ) preserved for us in the closure, 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. That is not C++. We just show it that 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 future usage:
|
1 2 3 4 5 6 7 8 9 10 |
/* 3 key abstractions of 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 -- (1) auto my_tail = tail(my_list); // my_tail is now ('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() :
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
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, regularly declaring the param pack into the first and the rest */ [=](auto first, auto ...rest) { /* first = 1, rest = '2', "3", false, 13.0f return a new list(1) */ return list(first); } ); }; |
Fig 4.
Ok. I know. 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 a pseudo code head() returns the following:
|
1 2 3 4 5 6 7 8 9 |
// 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
|
1 2 3 |
[=](auto first, auto ...rest) { return list(first); } |
Fig 6.
is the lambda given to the result of its closure: list(1, '2', "3", false, 13.0f); Again in pseudo code situation is this:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
/* Fig 2 code with a lambda substituted with lambda from head() implementation */ [=] ( /* 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
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
auto tail = [&](auto list_lambda) { // argument is the lambda returned form list() // we call it here return list_lambda( // callback from Fig 1 is // substituted with this [=] ( // the ... params pack // from the Fig 1 auto first, auto ...rest ) { // unpack the param pack into // the list of arguments 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. Let’s make the length() :
|
1 2 3 4 5 6 7 8 9 10 11 |
auto length = [&](auto list_lambda) { return list_lambda( // elements of the list // are params pack // of the list() // aka original closure // see Fig 1 and Fig 2 [=](auto ...z) { return sizeof...(z); } ); }; |
Fig 9.
By now, I think you are maybe 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.
|
1 2 3 4 5 6 7 8 |
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.
|
1 2 3 4 5 6 7 8 9 10 11 12 |
// 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 tuples 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
Here is the result:
Would it be too cruel if we leave touple_to_list() implementation as an exercise to the astute reader?
