What is Lazy Evaluation? — Programming Word of the Day
When a compiler encounters an expression, usually it tries to evaluate it. Evaluation is the process of getting the root meaning of a piece of code. The meaning of 5 + 3 is 8. Our brains also do this: when somebody tells you, "She's a good programmer!", your brain is evaluating the "she" in the sentence. If "she" was defined earlier, it will evaluate to a pointer to a person. :)
While most languages do this immediately, it’s not very efficient. Not all expressions are worth evaluating. For instance, function parameters might go unused, so we don’t need to evaluate them.
def someFunction(x, y) =
return x + 1someFunction(3, 3 + 2)
In the example above there is no point in evaluating 3 + 2, because it's not used. The style of only evaluating what's needed is called lazy evaluation, while the opposite (evaluating immediately) is called strict evaluation.
It’s called “lazy” because the compiler will procrastinate. It will not be a good student and study in advance. Instead, it will postpone the evaluation until it’s absolutely needed, and only then will it say, “Sigh. All right, I’ll evaluate your darn expression.”
Just like lazy students, a lazy compiler can be much more efficient if it makes smart choices. For lazy evaluation to be efficient, it needs to use memoization. In other words, it needs to keep a dictionary where the key is the name of the variable, and the value is the result of the evaluation. When it encounters an already evaluated variable, it can simply look up the value in the dictionary.
Aside from performance benefits, there are a couple of other things that make lazy evaluation really cool. Most languages have what’s called short circuiting behavior for a logical AND (&&). An AND is true only if both of the operands evaluate to true. Most languages, then, first evaluate the left-hand side, and if it's false, don't even bother with the right side. If the left side is false, the whole ANDexpression will be false.
Short circuiting is something that is “hard-coded” into compilers: they have specific code somewhere in their guts to do this. With lazy evaluation, you get this for free. There’s no need to code that logic into the compiler. This makes the actual compiler simpler and easier to understand. You can write the code for an if statement as a plain old function. With lazy compilers, ifs are not primitives (built into the compiler) but instead a part of the standard library of the language.
Another cool side effect of lazy evaluation is the ability to work with infinite lists. In a regular compiler, the concept of an infinite list doesn’t really exist, since it would crash the program. The compiler eagerly evaluates so it will try to evaluate all of the infinite list, eventually running out of memory.
On the other hand, a lazy compiler only evaluates what it absolutely needs to. Even though you defined an infinite list, it won’t bother with evaluating all of it. An infinite list looks something like this:
def addOne(n) = [n] + addOne(n + 1)// [1, 2, 3, 4, 5, 6, ...]
list = addOne(1)
addOne will recursively keep adding its argument to a list. Contrary to what we said in a previous article on recursion, this recursion doesn't have a base case: it will keep going forever.
We can then define an infinite list that will be the result of a call to this function with 1. Since we're not evaluating list, the code will not crash at this point. You might be asking yourself "Why even define the list if we can't use it?" While we can't use the whole list, we can use parts of it!
oneToThree = list.takeFirst(3)
print(oneToThree) // [1, 2, 3]def range(start, end) =
list.takeElementsBetween(start - 1, end - 1)print(range(5, 10)) // [5, 6, 7, 8, 9]
Taking only the first few elements or elements between a certain range, we can use an infinite list! We can use this to define ranges, sequences, cycles, consecutive dictionary keys, input streams and other useful concepts.
Languages that support lazy evaluation are usually functional programming languages like Haskell, which is lazy by default. Some languages, like OCaml and Scheme, let you opt into lazy behavior. Other languages like Swift and Perl 6 support it only for lists. The reason so few compilers support lazy evaluation is that it makes writing an imperative, OOP-style compiler tricky.
Lazy evaluation is performant (and correct) only when correctly mixed with referential transparency. If the state of your variables is constantly changing, you can forget about memoization, and suddenly lazy evaluation becomes slower than doing it eagerly.
So, for all you lazy students out there: if you make the right choices, you can be more efficient than the ones studying weeks in advance! :)
This post was first posted on programmingwords.com, a site dedicated to writing about new terms from computer science each month!
