Lambda-style anonymous functions for C++ in less than 500 lines of code(matt.might.net)

111 pointsby adg001vor 16 Jahren40 comments

matt.might.net

Lambda-style anonymous functions for C++ in less than 500 lines of code

http://matt.might.net/articles/lambda-style-anonymous-functions-from-c++-templates/

40 comments

lolcraftvor 16 Jahren

To pull this off, the implementation exploits templates, operator overloading and function pointers (but, remarkably, not a single macro) to construct a type-safe domain-specific embedded language.

Yes, "exploiting" is exactly the word I was looking for. Cool hack, though.

jherikovor 16 Jahren

This is interesting, but I'm not upvoting it... I wrote something similar for dealing with calculus on tensor fields a few years back and most compilers I've written use something similar for dealing with expressions.

This is different though, it doesn't let you solve any new problems that C++ can't already solve, and it also happens to produce slower expressions than, e.g. a function object or a function being pointed to.

If you want lambdas (which let you solve exactly no problems you can't already solve with C++) then use a language that supports them instead of shoehorning them in badly.

I'd recommend Haskell...

fadmmattvor 16 Jahren

(Article author here.)

I'd love to use Haskell, but I'm helping out on an exascale DoE project, and C++ is all we're allowed to use. Ugh.

Of course, lambdas don't make C++ more powerful, but that's just reductio ad Turing tar-pit.

You can turn that argument around, too: there's no problem you can solve with C++ that you can't solve with lambdas alone:

http://matt.might.net/articles/church-encodings-demo-in-sche...

If programming languages were about computational power, we would have stopped with Fortran.

Programming languages are about the freedom of expressions.

jherikovor 16 Jahren

"If programming languages were about computational power, we would have stopped with Fortran.

Programming languages are about the freedom of expressions."

I strongly disagree, /some/ programming languages are about expressive power - others are about computational power.

We didn't stop with Fortran, we moved onto C then C++ - they might not be able to do anything more in the computer science theoretical sense, but in practice they produce faster executables, and in real world applications that means more computational power can be brought to bear on problems with these sorts of languages.

Maybe speed doesn't matter for your problem, or lambdas are an especially nice fit. Mainly I'm just worried that you are going to produce substandard code with this kind of mindset... good code is written with the language's strengths and weaknesses in mind, not to enable the flavour-of-the-month paradigm to be used in an extremely sub-optimal fashion.

eruvor 16 Jahren

> [...] but in practice they produce faster executables [...]

C++ is faster than Fortran?

jherikovor 16 Jahren

In all tests I've done - yes it is. Although I haven't tested every compiler and platform for obvious reasons.

growingconcernvor 16 Jahren

This doesn't make sense. You're saying adding lambdas doesn't help you solve any problems that can't already be solved in C++, but if you want to solve some of those problems you should use a language that supports lambdas?

jeyvor 16 Jahren

He's right. You can do anything in {C++, Python, a Turing machine}, but you might want to choose a language that's well suited for your task at hand even though any of them can do it in principle.

jherikovor 16 Jahren

That's exactly what I meant. My examples equally have solutions which use these C++ lambdas, but it would be a lot more work than necessary to actually produce or maintain them.

growingconcernvor 16 Jahren

That might be what you meant. But it's not what you said.

jherikovor 16 Jahren

I never said that problems exist which require lambdas either... I just said if you want to solve problems that way to use a language designed for it.

tbrownawvor 16 Jahren

Very cool, but fortunately soon to be unnecessary: http://en.wikipedia.org/wiki/C%2B%2B0x#Lambda_functions_and_...

Also, real currying in C++0x: http://pastebin.com/KRraz7iU

fadmmattvor 16 Jahren

Neat; but C++0x does this:

[](int x, int y) { return x + y; }

instead of this:

lambda<int> (x,y) --> x + y

Ironically, the template hack could be shorter in many cases.

tbrownawvor 16 Jahren

And those few extra characters give you an enormous amount of flexibility, such as not needing to define wrapper template specializations for all your types, not needing to have extra variables sitting around to define your argument placeholders, and being able to use more than just simple expressions.

tmanvor 16 Jahren

Unfortunate that this is one part of the C++0x g++ project that has yet to get serious. (At least the last time I checked out the g++ experimental code a few months ago.) C++0x lambdas are the one thing that I've been wanting to try out for years.

Instead, we got a lot of (now somewhat wasted) effort on concepts. I like concepts in principle, but too many C++ people saw concepts as a way to write provable code and unreadable library documentation instead of as a way to simplify compiler error messages.

scott_svor 16 Jahren

Prepare to be pleasantly surprised: http://gcc.gnu.org/projects/cxx0x.html

teamonkeyvor 16 Jahren

Oleg's method is shorter.

http://okmij.org/ftp/cpp-digest/Functional-Cpp.html

stingraycharlesvor 16 Jahren

I'm not sure whether it's more readable though, which imho is more important.

jclvor 16 Jahren

As written, though, isn't this limited to only multiplication and addition? If you wanted to include, for example, a function call in your anonymous function, wouldn't that require a pile of Var<>-based function overloads?

shin_laovor 16 Jahren

Or you can use Visual Studio 2010 and use C++ lambdas.

Nice post nevertheless.

Jachvor 16 Jahren

This is so much nicer than Boost's stuff. Quite the exploit but still awesome, it'll probably go into my next side-project.

sorbitsvor 16 Jahren

Though it doesn’t work with the standard algorithms.

For example you can’t do stuff like:

    std::transform(first, last, lambda<int> (x) --> 2*x);

Jachvor 16 Jahren

What are you talking about? You're missing an arg in your transform() call.

  int nums[] = {1, 2, 3};
  printf("nums: %i %i %i\n", nums[0], nums[1], nums[2]);
  std::transform(nums, nums+3, nums, (lambda<int> (x) --> 2*x));
  printf("new nums: %i %i %i\n", nums[0], nums[1], nums[2]);

Edit: And of course, there's the implemented map he gives in the example:

  int* incs = (lambda<int> (x) --> x + 1).map(3,nums);

The class needs a little bit of work obviously (like more operators overloaded), but it's pretty nice.

rbanffyvor 16 Jahren

Less than 500 lines of C++ code is very little? A lot? I don't know what to make of it.

eruvor 16 Jahren

500 lines is not a lot in C++. Or is it?

wrsvor 16 Jahren

Oh my. It's true what they say about teaching a pig to dance.

confuzatronvor 16 Jahren

Less than 500 lines of code. More than 500 lines of compiler errors if you get a character wrong somewhere. ;)

dirtyauravor 16 Jahren

Yes. However, in my experience, on a small team, benefits of readable code by using templates to implement DSLs in C++ still outweighs burden of prosaic error messages. You quite quickly learn to pattern match error messages to find the real problem.

We might be bitten this later when new guys and gals join the team. Code is very readable for being C++, but newbies might have hard first few weeks with these error messages.

srequevor 16 Jahren

If you've ever tried starting a debugger in a program that uses the Boost Lambda library you might disagree. My program was only a few hundred lines long, a toy, but I for the first time had to turn pagination on in gdb to view my program's stacktrace because the it filled two entire screens! Even worse, compile times on my program were ridiculously high and I was wasting a ton of my time in long compile-run feedback cycles. Eventually I threw my hands up in disgust and started hand-rolling my own structs. Compile times dropped to under a second and I was able to easily spot my mistakes in the debugger.

What was I doing? I was just writing a simple program to try to understand Boost's spirit parser, somewhat of a monstrosity in its own right, and thought I'd use the lambda library along with it. While we're on the subject of crazy DSL's in C++ templates, I ended up concluding that Flex together with Bison or Lemon are much more pleasant to use than Spirit if you don't need a full recursive descent parser.

Using C++ templates to implement crazy meta-languages might seem like a cool idea, and it is, but in practice I've found it to mostly be a waste of time and very unproductive.

dirtyauravor 16 Jahren

We have noticed that debugger is not a very good debugging tool for our apps: interactive games with lots of events, animation, multiple threads etc. Stepping through in debugger has turned out to be waste of time.

What has worked? It's much better to produce detailed logs of some of the subsystems and analyze them. This way you get much better understanding of the big picture of what is happening. Why? In UI code (or event-driven code in general) state changes that cause bugs happen over time, not inside one step of an event loop. You just can't get the big picture of event-driven code with a debugger, which is optimized for going up and down callstack.

We have build a custom tracing library (and yes, it uses a lot of MACROs) that allows us to do select what is traced in a very granular level. I can proudly say that it's wonderful tool, every UI platform should ship with something like that.

By the way, tracing is also better for debugging parsers, their behavior often have similarities to event-driven systems

But you are right about compile times. Those get worse with templates.

loup-vaillantvor 16 Jahren

All this can be traces back to a root problem: using, maybe even needing, C++. Solution: don't use C++, or run away. (And spread the word[1]) I am dead serious: I don't follow my own advice, and that makes me miserable at work.

[1]: http://yosefk.com/c++fqa/ (I actually learned quite a few things there)

_deliriumvor 16 Jahren

I second the recommendation of Yosef K's FQA. It's not just an anti-C++ rant, but a pretty detailed explanation of a lot of C++'s features, interactions between features, and corner cases (and how those will bite you in the ass).

bad_uservor 16 Jahren

Btw, I've had great experiences with Antlr (instead of Yacc) and can use Java/C/C# as targets, although you might have problems redesigning your grammars to be LL(*).

confuzatronvor 16 Jahren

Yeah, really it's a more general problem with the extreme expressiveness of C++ meaning that the compiler is less able to give a helpful error message than in other languages I've used. It seems that you can do anything in C++, but step out of line and you'll have trouble deciphering where you went wrong.

eruvor 16 Jahren

> extreme expressiveness of C++

You probably mean that the boundary between meaningful C++ programs and typos is not very well defined?

confuzatronvor 16 Jahren

Exactly. Very well put.

wheelsvor 16 Jahren

Nah, it's actually more of a GCC problem than a C++ problem. Intel's compiler produces surprisingly sane error messages.

zokiervor 16 Jahren

llvm/clang is supposed to have nice error messages

confuzatronvor 16 Jahren

I can confirm it is also an MSVC problem.

growingconcernvor 16 Jahren

It's not that hard parsing template compiler errors (though I am looking forward to better errors in C++0x). Are you saying this is a good reason not to use templates at all? With a little practice they start to make sense. I'm sure for novice programmers the first time they see 500+ error messages stemming from a missed semi colon or curly brace (in regular code) it can be pretty bewildering too, but just like with template error messages you just ignore virtually all of it.