It’s Different in the Lazy World
“Know your worth. Then add tax.” — Anonymous
One of the unspoken society-imposed behavioral norms is that you should not defer things you can do today. In contrast with the “real” world, waiting until the very last moment is pretty commonplace and is even encouraged in the world of programming (or at least in some of its areas). The reason? It’s simple: not everything is worth it.
The Lazy World of Programming
The concept of Lazy Evaluation is largely based on this idea of “worthiness”: if an expression is too expensive and there’s no particular need to evaluate it, then don’t do it. For instance, if you’re recursively defining an infinite data structure, each layer of recursion can be evaluated only on a “call-by-need” basis.
To illustrate, here’s a piece of code (written in a pseudo-language) that defines an infinite list of points and recursively adds a squared number to it:
Contrary to strict evaluation, data will not be evaluated in the lazy world (after all, it’s an infinite list and you might just run out of memory while doing so!). Instead, you can ‘evaluate’ just the points you need by writing something along the lines of data[:5], which will return the first five elements from the list. The advantage is a boost in your program’s performance, as you avoid needless computations.
Lazy evaluation is common across functional programming languages, such as Haskell.
How Is It Implemented?
For lazy evaluation to actually work, a special evaluation rule has to be added to a language and for this purpose, a new datatype called thunk was invented.
Thunk can effectively be in two states:
(1) unevaluated (the expression value hasn’t been needed so far and hence, we don’t know what its value is), and
(2) evaluated (the expression value has been needed — or at least some part of it, in the case of infinite data — hence, we have some of its values stored).
The Thunk class keeps track of an expression and its environment (it must do so because the expression can potentially get evaluated in some other environment).
In Python, we can write this class down as follows (Source of the code below):
_evaluated: a tracker for whether the expression has evaluated or not,value: a tracker for values once the expression has evaluated,forceeval: call it when the expression value is needed,meval: call it when the expression value is not needed (i.e. you want to delay the evaluation).
To support delayed evaluation, the following has to take place in the language:
[…] we need to redefine the
evalApplicationprocedure. Instead of evaluating all the operand subexpressions, the new procedure creates Thunk objects representing each operand. Only the first subexpression, that is, the procedure to be applied, must be evaluated (Source).
Extra Info on Memoization
Usually, the concept of Lazy Evaluation goes hand in hand with the term memoization — an optimization technique for data storage. Here’s a bit of information in case you do stumble upon this concept.
In basic words, memoization is the creation of a lookup table where all the evaluated values are stored. The next time you call a particular function (which will have already been called before), it won’t have to re-compute anything if the value sought-after already exists in that lookup table. This saves computation time and, not to mention, a lot of memory.
So, in the case of the infinite list defined above, if we call data[:5], the five values will get stored in the lookup table and will not need to be recomputed the next time you call this expression somewhere in your code.
Feel free to consult the referenced links below for more information, if needed.
References:
https://www.cs.virginia.edu/~evans/cs150/book/ch13-laziness.pdf
