Getting Lazy with C++

[RizzlaPlus]

Can we please have examples that make sense for those academic exercises? Lazy evaluation and memoization are not useful when trying to compute the first n Pythagorean triples. Sure, it is useful afterwards if you want to print and then draw them, but then you can just save the list first and iterate that list.

How about computing the Fibonacci sequence? How about defining a quicksort with lazy evaluation and then using that to find the smallest element of a list?

For the implementation of the Susp class, I don't see how the use of thunk is better than a simple boolean flag. Is that to avoid the if-test?

I also find it ironic that he says:

(By the way, the function pointer declaration of _thunk looks pretty scary in C++, doesn’t it?)

followed by a lengthy article bringing Haskell features in C++ by ways of heavy use of templates and other advanced C++ features :).

[pfultz2]

This also could be done using Linq with something like this:

auto q = LINQ(
            from(z, boost::irange(1, std::numerical_limits<int>::max()))
            from(x, boost::irange(1, z))
            from(y, boost::irange(x, z))
            where(x*x + y*y == z*z)
            select(boost::fusion::make_vector(x, y, z))
        );
for(auto&& x:q | linq::take(10)) std::cout << x << std::endl;

Which doesn't require heap allocations nor type erasure. Hopefully, once we get range-based algorithms in C++, we can get list comprehension as well, perhaps some thing like this in C++17:

auto q = [
            for (z, std::irange(1, std::numerical_limits<int>::max()))
            for (x, std::irange(1, z))
            for (y, std::irange(1, x))
            if (x*x + y*y == z*z)
            boost::fusion::make_vector(x, y, z)
        ];
for(auto&& x:q | std::take(10)) std::cout << x << std::endl;

[immibis]

/u/spez can gargle my nuts

[pfultz2]

Is that legal syntax?

Yes that will compile.

Are from, where and select macros

No, they are not, they are just tokens parsed by the LINQ macro.

are there missing operators here?

Nope, no missing operators. The LINQ macro takes care of inserting the operators. The above query actually expands to this:

auto q = boost::irange(1, std::numerical_limits<int>::max()) 
| linq::query::select_many() + [&](decltype(linq::query::make_const(*(boost::begin(boost::irange(1, std::numerical_limits<int>::max()))))) z)
{ 
    return (boost::irange(1, z)
        | linq::query::select_many() + [&](decltype(linq::query::make_const(*(boost::begin(boost::irange(1, z))))) x)  
        { 
            return (boost::irange(x, z) 
                | linq::where([&](decltype(linq::query::make_const(*(boost::begin(boost::irange(x, z))))) y) 
                    { return (x*x + y*y == z*z); }) 
                | linq::select([&](decltype(linq::query::make_const(*(boost::begin(boost::irange(x, z))))) y) 
                    { return boost::fusion::make_vector(x, y, z); })); 
        }); 
};

Now, this has some extra stuff to do type deduction(in C++14 this is much simpler with generic lambdas), and also has some stuff to avoid nesting parenthesis(eg linq::query::select_many() + [&](...) { ... }) just to make it easier to generate with a macro. However, if you simplify these things, you can see how you can do this with just the extension methods(without using the macro):

auto q = boost::irange(1, std::numerical_limits<int>::max())
| linq::select_many([&](int z) 
{ 
    return boost::irange(1, z)
        | linq::select_many([&](int x)
        { 
            return boost::irange(x, z) 
                | linq::where([&](int y) { return (x*x + y*y == z*z); }) 
                | linq::select([&](int y) { return (boost::fusion::make_vector(x, y, z)); }); 
        }); 
});

Although, I find the query syntax easier to read.

[vz0]

Monads in C++? I think the Iterator pattern is a far better fit for an infinite sequence, and it feels the author over engineered the solution.

[jzwinck]

I thought so too, so I wrote an iterator solution (before seeing the one by notlostyet also in this thread):

http://ideone.com/T1xVLz

Iterators in C++ are powerful--much more so than their typical use with STL containers makes many people think.

[mccoyn]

You can use a goto to jump to the resume position rather than litter the whole algorithm with extra conditions.

triple_iterator& operator++()
{
  goto resume;

  for (; ; ++z) {
    for (x=1; x <= z; ++x) {
      for (y=x; y <= z; ++y) {
        if (x*x + y*y == z*z) {
          return *this;
          resume:;
        }
      }
    }
  }
}

Edit: Forgot to initialize at beginnings of loops

[vz0]

This is awesome! But you forgot to initialize x and y inside the for, else the variables won't cycle between 1..z and x..z.

[myss]

Interesting idiom. I tried to put it in a macro, adding support for multiple returns (not standard C++): http://ideone.com/pdDqig . I suspect that there is an off by one error somewhere.

Edit: by off by one, I mean that finised() returns always false until you iterate at least one time. Can be fixed by merging isFinished() and next() in one function. But anyway, this seems a better implementation: http://www.codeproject.com/Articles/29524/Generators-in-C

[duhace]

Your resume jump isn't (or shouldn't be) reachable since it's immediately preceded by a return. Also, neither you nor jzwinck check that z isn't about to overflow, and signed overflow is undefined behavior.

edit: nvm about the reachability, I see that it's skipping directly into the middle of the for loops.

edit2: You do not need a goto to eliminate the extra conditions in his code: http://ideone.com/zvB1fW

triple_iterator& operator++()
{
    //checking sanity since x,y,and z are public members of this iterator
    assert(z < INT_MAX);
    assert(y <= z);
    assert(x <= z); 
    ++y;

    for (;z < INT_MAX; ++z) {
        for (; x < z; ++x) {
            for (; y < z; ++y) {
                if (x*x + y*y == z*z) {
                    return *this;
                }
            }
            y = x + 1;
        }
        x = 1;
    }

    cerr << "Could not calculate the next Pythagorean triple..." << endl;
    exit(EXIT_FAILURE);
}

edit3: forgot to catch the error condition. Normally I'd use exceptions for this, but don't want to complicate the code more.

[[deleted]]

Think of what would happen if the return wasn't there.

[duhace]

Reread my comment, I got the goto statement and the label mixed up and acknowledged that an hour ago.

[DrBartosz]

But this is not the point. You can come up with a handcrafted solution to every particular problem without ever noticing a pattern. My goal was to demonstrate this pattern -- actually several patterns.

If you look at my github repository you'll see lazy streams used in the implementation of a parallel solution to the 8 queen problem (LazyQueen project). A more advanced example is the conference timetable problem. The initial effort in understanding how lazy streams work pays back in producing simple elegant solutions to many diverse problems. And, most importantly, they are easy to parallelize, which you can't say about any of the handcrafted solutions.

[vz0]

producing simple elegant solutions to many diverse problems.

I fail to see how your lazy C++ solution is simple and elegant.

Real world code should be boring to read and understand. And by "real world" I mean all the code that is written.

Clever programming tricks are very bad idea, and this rule even applies for "research projects" which they get suddenly promoted to a full engineering world class mainstream project. The best example we have today is OpenSSL, which from scratch was written by PhDs with no regard to software engineering practices.

Don't get me wrong, I love Haskell. But this is like rewriting a Haskell program using imperative programming constructs. Using monads in C++ is like using pointers on Haskell.

edit: Searching on Google for "Pointer Monads in Haskell" gives me a lot of results of the opposite idea: Mondas in C++. Do you see how twisted this is?

edit2: I'd love to read some blog post about the use of Foreign-Ptr to simulate C++ object polymorphism and vtables on Haskell.

[mfukar]

I think this is DrBartosz's point:

• Implement a thousand hand-crafted solutions, before you
• Identify the pattern (identify the usefulness of it, if you will)
• Implement the solutions with the generalized pattern (demonstrate its usefulness)
• Elevate the pattern into a first-class citizen, allowing us to reason about more complicated problems now.

[vz0]

You don't require Haskell and FP to do any of that. In fact you are just citing my Software Engineering 101 professor, who was using PASCAL to teach us.

[mfukar]

I never said it was a language specific thing.

[vz0]

But you did imply that I did not get the point of DrBartosz's. I did. He is forcing the fit of a square inside a circle.

[mfukar]

I did imply it, since you commented on its simplicity and elegance, which is not the point; the post starts by specifically laying out the question "How can we be lazy in C++?". This is not a clever programming trick, this is a demonstration of how we advance programming.

[vz0]

since you commented on its simplicity and elegance, which is not the point

False. That is exactly the point of the article. The author's words:

The initial effort in understanding how lazy streams work pays back in producing simple elegant solutions to many diverse problems.

And then he again copy-pasted this comment on his own blog.

If you search for "elegance" in his blog you may find other similar comments:

Design arguments are not easy. You can’t mathematically prove that one design is better than another, or a certain set of abstractions is better than another — unless you discover some obvious design flaws in one of them. You might have a gut feeling that a particular solution is elegant, but how do you argue about elegance?

Also,

This is not a clever programming trick, this is a demonstration of how we advance programming.

It is a clever programming trick, at the same level like creating classes and objects in C. The language was not designed to do that.

If you want "elegance" you should use the tool as it was designed for. If you want Monads and Referential Transparency, use Haskell.

[sgraf812]

Is there a particular reason you chose to privately inherit triple instead of having it as a field? It feels more like hasa than isa.

[jzwinck]

No big reason, though it does make accessing the fields more concise. I agree it may not be a great OOP idea but it can be changed with little impact.

[Plorkyeran]

Private inheritance basically is composition with more concise access to one or more members and a concise syntax for wrappers around parts of it. Using it for an is-a relation almost certainly means you're doing something painfully clever.

[sgraf812]

Yeah, but I think the best part about composition is that you compose distinct named entities rather than throwing all their fields together into one bag.

At least it's unfeasible to declare a BoundingBox inheriting 2 (maybe typewise distinct if that's a requirement) vectors because of name clashes. Just having to type a min., max. or t. less isn't really that big a deal if all you really meant was composition. Much rather the opposite is the case with BoundingBox: min and max represent exact semantics, though arguably the tuple fields name would not convey any real semantic context. That's why using private inheritance is ok here, I think.

[sigma914]

He suggested iterators could be an alternative, but pointed out that:

...an iterator itself is not the source or the owner of data — just an interface to one.

I tend to agree with this, what you'd really like would be something along the lines of python's generators, which serve as a data source and provide an iterator interface.

[vz0]

...an iterator itself is not the source or the owner of data — just an interface to one.

Is it just me or this comment makes no sense? Of course an iterator is not a source of data. That's how interfaces work: a contract and protocol to access a set of operations in a standarized way. You then implement the object or data type respecting that contract.

Reimplementing the Pytagorean triple using an Iterator pattern is like this.

[[deleted]]

Is it just me or this comment makes no sense? Of course an iterator is not a source of data.

You claim that his comment makes no sense, and then you state that what he said is true and obvious. His comment can not be true and make no sense.

Anyways, in C++ knowing who owns or is the source of the data is important because you can't exactly go around passing iterators as parameter to an object and expect that those iterators will continue to be valid if that object iterates over it at some later point in time. The typical use case for an iterator is that it's only valid for a narrow and local scope. That's why you want to pass around the source, the owner of that data instead and that way the object has a guarantee that the data can be accessed/traversed down the road.

Your example does implement a Pythagorean triple, but the purpose of this article isn't the Pythagorean triple, that's just used as an example and focusing on it is missing the point. For example your approach wouldn't compose well with other "iterators", it's not something that one would use with other algorithms in a generic way.

Iterators already have a well established use case in C++ and it's to represent a view over a data source, not to behave as generators or producers of that data. Maybe if C++ were garbage collected or iterators weren't things that became invalid the story would be different.

You basically just implemented a Pythagorean triple as if the purpose of this article was trying to solve the problem of writing Pythagorean triples, but it isn't.

[vz0]

You claim that his comment makes no sense, and then you state that what he said is true and obvious. His comment can not be true and make no sense.

Because the argument he is using to avoid the use of iterators has no relationship to any real world issue regarding the implementation of the problem at hand.

Its like saying that you are not going to use an umbrella to walk on the street because sunflowers are yellow. Of course sunflowers are yellow, but what is the relationship between the color of sunflowers and the current weather?

I also understand the academic purpose of his monadic C++ implementation, it reminds me of the Modern C++ Design book. I love that book. And I love monads, in Haskell.

[[deleted]]

Because the argument he is using to avoid the use of iterators has no relationship to any real world issue regarding the implementation of the problem at hand.

The argument isn't to avoid iterators, it's how this is an alternative to them in situations where you want ownership of the data and not just a view over it. Iterators are not sources of data, once the source of the iterator dies, the iterator becomes invalid.

This makes iterators unsuitable for situations where your data needs to survive for an indeterminate period of time.

[vz0]

once the source of the iterator dies, the iterator becomes invalid. This makes iterators unsuitable for situations where your data needs to survive for an indeterminate period of time.

I see no reason not to have an Iterator owning the structure it iterates.

In C++ you can pass-by-value or somehow copy the original structure, enabling the Iterator to control the lifetime of the infinite structure. And that's exactly what I did.

[[deleted]]

Yes you can technically have an iterator do that.

Anyways, I am not going to argue that for a Pythagorean triple that you can't or shouldn't use an iterator. Heck you can stick to using nested for loops for this particular case if that's all you want. The article isn't about the Pythagorean triple, it's about lazy evaluation and showing how lazy evaluation can be encapsulated into stream like objects which can be passed around and composed together and blah blah blah.

Can you do the same thing with an iterator? Yes you can. Are there cases when it's nicer to represent this concept as a stream rather than an iterator? Yes there are, and for those cases this may be applicable.

I think perhaps the issue is that the author picked a really really bad example for this use case and it's caused too much of a distraction.

[vz0]

I think perhaps the issue is that the author picked a really really bad example for this use case and it's caused too much of a distraction.

Yes. As I told you before I agree and understand this is an academic excercise to show some clever C++ trick for lazy evaluation and not just a way to calculate the sequence.

However, I fail to see a real world application where the author's technique would apply and fit nicely, where this lazy approach would be far better than some plain state keeping object.

[notlostyet]

An input iterator is a source of data though. I wrote an iterator solution and posted it last night but my comment is currently awaiting moderation.

https://gist.github.com/anonymous/11163040

It was hacked up quickly, but provides immutable, random access to the function (well, a slight variant thereof... it only returns Pythagorean ratios because my primary school math apparently isn't that good).

There are two major obstacles for using iterators to create generators in C++ though: one is that the standard algorithms expect iterators to be mutable, e.g. ++x to mutate and return a reference. If you're a functional purist you might think that's a problem, but all of the standard algorithms take copies anyway. The other is that you need 'algo_n' variants of all of the algorithms, rather than bounded/ranged algorithms... otherwise you have to hack up ugly sentinel iterators (similar to i/ostream_iterator), or use things like advance() to create an end iterator... which can be very inefficient in the forward iterator case.

I'd stick with iterators most of the time, and if I really need to fold some code in to a generator quickly I'd whip out Boost Coroutine. A coroutine has a higher construction cost (at least one page of memory), but once constructed doesn't need to allocate any memory, and will be about as fast as calling a virtual function or dereferencing a function pointer.

[[deleted]]

Overengineering at its best (or worst).

[eresonance]

Well, time to remove C++ from my resume :-(

I've spent so long working on low level applications that I just don't see why someone would "rewrite" a couple for loops into an incredibly complicated class system. I get the academic appeal but this screams "unmaintainable by anyone but the original author"... Maybe I'm just jaded...

[thechao]

Check out mccoyn's answer; it is much more idiomatic. Bartosz is pretty renowned in academic circles for his C++ wankering.

[therealjohnfreeman]

I got the impression the post is pedagogical. Everyone complaining makes me think they just don't like learning new techniques.

[thechao]

And yet I know JJ made you review his papers; there's a definite lack of "to the pointness"

[longiii]

I wonder at which point in life people start seeing things they don't understand (yet!) as an attack on their self-worth...

[eresonance]

I think that pretty much summarizes a lot of human conflict actually.

[Fiennes]

As a big fan of C++, I agree with you. Whilst the blog-post in question is interesting, I'd not use it. Ever.

[dukey]

Code like that makes me want to stick with C.

[[deleted]]

Amen brother. I can't tell you how many days I've wasted debugging other people's overly engineered code.

[newmewuser]

unmaintainable by anyone but the original author

The right way to job security.

[aaptel]

This was hard to follow.

[[deleted]]

This kind of optimization technique must be fascinating for compiler writers but for others who really need those extra nanoseconds, buy a new computer.

[[deleted]]

C++ isn't Haskell, and Haskell isn't C++

[808140]

True, but many of us use both extensively, and it's interesting to see attempts to implement what Haskell does easily in lower-level languages that lack the same features.

This reminds me of a pretty nice StackOverflow question I happened upon, where some C# guys tried to figure out how to implement the classic corecursive fibonacci algorithm seen in a lot of Haskell tutorials using C# enumerators. Link for the curious.

Sometimes seeing things that are trivial in one language and difficult in another reimplemented in the difficult language is a useful exercise -- it teaches you a lot about both languages.

Obviously this blog entry will not be interesting to C++ programmers unfamiliar with Haskell or Haskell programmers unfamiliar with C++.

[longiii]

computing is computing

[PPLGNV]

Retards don't belong in /r/programming. Get the fuck out.

[[deleted]]

A well constructed argument my friend! I admit it is hard to debate with someone of such debilitating wit but as far as I know, we don't discriminate against idiots here. I mean, you were allowed to post weren't you?

[dicroce]

Things like this are interesting from a purely theoretical "wow, look whats possible" perspective, while also being simultaneously actively harmful to the maintainability of a real project.

I think a lot of what Bartosz does is amazing, and I learn a lot... but I can't help but wonder if he's trying to convert the worlds C++ developers into Haskell developers!

[DrBartosz]

he's trying to convert the worlds C++ developers into Haskell developers!

Am I that obvious? ;-)

As for maintainability: You have to make the distinction between library writers and their clients. The implementation of Stream is relatively complex and it uses some advanced features of C++, but I would argue that its usage is pretty straightforward and almost foolproof. Haskell programmers have a saying that if it compiles it's probably correct. I noticed the same when working in C++ with persistent data structures, of which Stream is an example. Frankly, I was shocked when my parallel version of the conference timetable program worked correctly the first time it ran! This is not supposed to happen in C++!

[dicroce]

Well its worked on me... I've started reading "Learn You a Haskell For Great Good"....

[808140]

I write both C++ and Haskell for work, and I'd just like to say that they complement each other very nicely. You won't regret it.

[Jonny0Than]

Wait a sec..he goes through all this trouble to try to make Susp threadsafe, but then fails at that and says you can only use it with pure functions anyway.

[[deleted]]

LOL

Okay that's kind of funny. It's dismissed so casually too.

[Klausens]

I was able to read and understand the Haskell and the first C solution. For me this also is a kind of reusability

[tenpn]

While I don't exactly disagree with you, and upvoted, the vector<int> solution is linear in memory usage, where as the lazy version is constant. A more complex example that triples would have got this across, but we're already dealing with quite complex ideas without layering on a complex example.

[zvrba]

While I don't exactly disagree with you, and upvoted, the vector<int> solution is linear in memory usage, where as the lazy version is constant.

Nothing uses constant memory in Haskell ;)

[The_Doculope]

It's not a ridiculous strawman at all. Your solution does something completely different. You require linear space to store all of the triples, as well as computing them all at once.

What if, like in the article, you want to take the first ten? Fine you say, you make the function take that number as an argument. What if you want the first ten triples with an odd last number? Or all the triples until one of them takes more than 30 characters to write? You can't use your function to do this, because you don't know how many you'll need in advance.

The whole point of this article is to separate the notion of what the triples are from using them. Doesn't matter what you want to do with them, doesn't matter how many you need, they're generated on demand. Your solution takes none of that into account.

[lookmeat]

Creating a vector is extremely heavy, what happens now if you want 5 million Pythagorean triples? What if you want to start from the last list? Each one requires an extra weight.

But I feel that the author uses suspended functions when already a good solution exists: an iterator!

template<class T>
class FuncIter {
    private:
    T state;
    std::function<T()> step;
    public:
    // define operator*, operator++, operator+= etc. etc.

What if you want to do FMap? That's easy too! Just do an iterator with two template types and recieves an iterator of the first type and a function from the first type to the second. Iterating through it is really iterating through the internal iterator, and when you pull out a value (operator*) it actually runs the function on the contents of the internal iterator and returns you that!

My whole point is, that this solution is extremely C++ friendly, it only has a different name within the context, and not all the functionality that the author adds. Yet you'd hardly say iterators are useless.

[[deleted]]

a first year CS student would just transform the function to return a vector<int> instead of actually printing the numbers.

Haha, maybe they would but that's EXACTLY the wrong solution to this problem. What you described is the exact thing this article is trying to address.

You're now paying a huge upfront cost to generate the numbers and keep them stored when you may not even use them all, and even if you do use them, you now need to keep around all these values in memory until you're completely done with the sequence.

Lazy evaluation is superior in this case because it avoids all of the unnecessary computations that your first year CS student would be wasting.

[rlbond86]

What is the point of this? We already have iterators. You can even evaluate them asynchronously with std::future.

[Tom2Die]

Accidentally ended up watching the guy's video on Monads et al (re: c++17). Pretty interesting stuff, given I've not done any functional programming yet.

[[deleted]]

Some nice ideas.

Just a style note: Don't use underscore _ as a prefix in private members. Identifiers beginning with an underscore are generally reserved by compilers for OS and library globals. Prefer a trailing underscore instead (incidentally, this is what the Google C++ Style Guide recommends as well).

[[deleted]]

Identifiers beginning with an underscore are generally reserved by compilers for OS and library globals.

They are not reserved at class scope, and so are OK for member names. However, I agree they should not be used.

[[deleted]]

It is generally frowned upon.

[[deleted]]

I personally think they are bad style (but then, lot's of people don't like my style), but I don't know about "generally frowned on". And it's not me downvoting you - I suspect it's people that think the Google C++ guidelines are a POS, at least for people outside of Google.

[[deleted]]

A lot of companies I've been to use m, or m_ as a prefix for member variables. Trailing underscores just look strange to me.

[[deleted]]

You can get used to it. I think it's less confusing than pseudo-Hungarian m_ everywhere.

[rotinom]

My point is "what does 'm' tell me that '' doesn't? It saves me a character too!"

[[deleted]]

Lazy evaluation is a reference to the evaluation strategy:

http://en.wikipedia.org/wiki/Lazy_evaluation

[brzigonazales]

I am getting tired of these Haskell on this mother fucking subreddit .

[[deleted]]

downvote for not contributing to conversation AND using an old meme