Streams – Lazy evaluation in C++14
jscheiny.github.io
jscheiny.github.io
lazy evaluation is one of those features where i have absolutely no idea what benefit it actually provides
Good question.
Let's say you have a program like this little python example:
inputs = [raw_read() for i in range(1000)] # Read numbers from command line
numbers = map(int, inputs) # Turn them into integers
for num in numbers: # Check for 42
if num == 42:
return true
return false # It's not there
If you use greedy evaluation, it will map all strings to integers at once, which might be wasteful.
There are other benefits as well; this is the most obvious.
for (auto& num = file.line_iterator(); num != file.end(); num++) {
if (atoi(num) == 42)
return true;
return false;
Lazy evaluation gets you all that, with no extra code, all the time.
Imagine writing that iterator stuff for every single applicable thing in the entire program. There are also other places where lazy evaluation is useful and you can't use iterators, like a function that will only use a portion of its arguments depending on some condition.
Side-effect free, functional style of programming.
[1] http://www.quora.com/Programming-Languages/When-did-you-real...
For example, let's look at a canonical quicksort in Haskell:
quicksort :: Ord a => [a] -> [a]
quicksort [] = []
quicksort (p:xs) = (quicksort lesser) ++ [p] ++ (quicksort greater)
where
lesser = filter (< p) xs
greater = filter (>= p) xs
In Python, this would probably be done like this:
def min_list(lst):
current_minimum = lst[0]
for e in lst[1:]:
if e < current_minimum:
current_minimum = e
return current_minimum
minimum xs = head (quicksort xs)
Now, if have the slightest care for efficiency, you would never, ever write a function like this in a strict language.
However, in Haskell, minimum [5,2,7,1,3] would be evaluated like this:
> minimum [5,2,7,1,3]
> head (quicksort [5,2,7,1,3])
> head (lesser ++ ...) [p = 5]
> head ((quicksort (filter (<5) [2,7,1,3]) ) ++ ...)
> head ((quicksort (2:(filter (<5) [7,1,3])) ++ ...)
> head ((quicksort (filter (<2)
xs) ++ ... ) ++ ...) [p = 2, xs = filter (<5) [7,1,3]]
Filter will run through the entire list, comparing each element to 5,2 and 1 in order, and find nothing, returning [], which will hit the base case for quicksort []= []
> head ( [] ++ [1] ++ ...)
> head ([1] ++ ...)
> 1
I personally believe that the expressiveness gained through this procedure(we wrote quicksort and gained minimum for free!) offsets the loss in efficiency.
> is there any reason to add lazy evaluation to c++ [...]
I think you are suffering from a misapprehension. Nothing is being added to C++ the language. This is just an implementation of lazy streams in C++14. Think of it as an optional 3rd party library.
> lazy evaluation is one of those features where i have absolutely no idea what benefit it actually provides
Let me give you two examples. First try and solve this problem in your favorite language. Produce a sequence of k numbers that are multiples of 2,3 and 5 only, but produce them in sorted order. Yes of course this is contrived, but it will give you and idea of the conveniences that laziness can give you. [sorry, I gave away the important spoiler]
Second example say you want to compute
(x + y)*z - w
[EDIT: If one has laziness one need not instantiate the actual vector (x+y). One can return an object that only represents the operation. So one can keep building on the parse tree and finally when the result is actually used somewhere do you evaluate the expression encoded in the parse tree. Now since you have the entire expression tree you can evaluate it in just one loop. If you are curious you can search for deforestation and expression templates. You can of course do the same thing even if the language does not support laziness, but laziness is the key enabler here, if the language does not support it, _you_ have to implement it]. Without this features it is pretty much impossible to approach Fortran like speeds and expressiveness in array operations in C++.
A reason why basic Numpy is slow is because is that written naively it creates all these temporaries. There are a few ways to avoid it. Numexpr uses laziness (and tiling). You could also use the 'out' feature of Numpy functions creatively.
So in short, laziness has a lot of practical value, and I am not even bringing up aspects of purity etc. I had to roll something on my own for these needs. Would have been happier if there were such libraries available. [Ok full disclosure, I would have likely rolled my own anyway to understand how it works] There are a few libraries that do these things or help a lot in building these things. Some of the are Spirit and Fusion. Although I am conflating two different topics (i) fusion/deforestation and (ii) laziness, but they are related enough.
@dang thanks for the clarification, wwwwwwww's comment was indeed showing up as dead on this thread. wwwwwwww must have deleted his comment because at that time there was only one.
That is false. A comment was killed because it was a duplicate. We unkilled it.
Fortran is strict, though, is it not?
(x + y) * z - w
where each of them are long vectors but want to keep the look of the code readable and explicit. Naive way to do it will create lots of temporaries and unnecessary loops. Every binary operation is going to create a temporary (and entail a loop). But if you have laziness you just need one loop.
Can you elaborate on this? Why can laziness provide better code here?
A better way to do all that would be to allocate a single result vector and populate it with the full computed expression for each element. This can be much faster for large vectors. Python's numexpr (among others) is designed to do just this.
2. loop: (x[i,...,n] + y[i,...,n]) * z[i,...,n] - w[i,...,n]
although I don't think the loops are going to be the main overhead in this case.
BTW your handle rung a bell. I was wracking my brain to remember where have I heard of it before, then finally, oh yes MacSTL. It really deserves more love. Have not used it, but sure browsed the code.