CS 330: Lecture 35 – Call-by-need
Dear students,
Last time we introduced a different way of passing parameters. Instead of eagerly evaluating them, we delayed evaluation until they were referenced inside the function. We looked at two examples of delaying evaluation: C preprocessor macros and writing our own control structures. I want to discuss the first of these a little bit more.
Macros in C provide one way of “delaying” execution. A macro’s parameters enter into the macro without first having been evaluated. They are evaluated as needed. But if your expression issues an undesirable side effect, macros are particularly dangerous. Consider this code:
#define PRINTDIGIT(c) if (isdigit(c)) printf("%c", c)
PRINTDIGIT(getchar());
PRINTDIGIT(getchar());
PRINTDIGIT(getchar());
Let’s run this on this input:
1a2b3c4d5f6e
Our output is this:
abc
That’s not quite what we wanted. What’s the issue? gcc -E reveals all:
int main(int argc, char **argv) {
if (isdigit(getchar())) printf("%c", getchar());
if (isdigit(getchar())) printf("%c", getchar());
if (isdigit(getchar())) printf("%c", getchar());
return 0;
}
Because getchar() is not eagerly evaluated but lazily evaluated, it is duplicated in its raw form in both the condition and the printf call.
That’s one danger of macros. Here’s another. Consider this wrapper intended to make malloc easier to call:
#define EZMALLOC(n, type) (type *) malloc(sizeof(type) * n)
int *p = EZMALLOC(5 + 1, int); // we want six ints!
But what do we actually get? gcc -E says this:
int *p = (int *) malloc(sizeof(int) * 5 + 1);
Whoops. Because the preprocessor lives outside the language and is really just a textual substituter, it knows nothing about precedence. When we write macros, we must be careful. Here we can use parentheses to ensure the proper association:
#define EZMALLOC(n, type) (type *) malloc(sizeof(type) * (n))
Okay, so macros have at least two issues: repeated execution of the “parameters” and association troubles. (They also have scope issues, no type checking, and lots of other problems, probably.) But the repeated execution issue is not always bad. It leads us to one of the beauties of delaying evaluation. Delayed evaluation allows us to write our own control structures. Like loops and conditionals. We saw this last time. I want to look at one more example in a language that truly recognizes call-by-name semantics: Scala.
Let’s try writing an until control structure in Scala. Here’s our first attempt:
object Main {
def until(condition: Boolean, body: Unit) {
while (!condition) {
body
}
}
def main(args: Array[String]) {
var i = 0
until(i == 10, {
println(i)
i += 1
})
}
}
We see 0 printed and then we enter an infinite loop. Why? The condition and body are eagerly evaluated. The condition enters until as false, so we enter the while, which does nothing to change the already evaluated condition. But Scala gives us the power to delay:
object Main {
def until(condition: => Boolean, body: => Unit) {
while (!condition) {
body
}
}
def main(args: Array[String]) {
var i = 0
until(i == 10, {
println(i)
i += 1
})
}
}
Now we see our countup! Lazily evaluating a function’s parameters like this is called call-by-name. It’s not the greatest term in the world. A better term would pass-as-function or pass-as-closure.
But we can do one better. It’d be awesome if we could make our own control structures look like the builtin ones:
until (i == 10) {
println(i)
i += 1
}
We can do this if we make until behave as all Haskell functions do. If we give it just one parameter, it yields a new function awaiting the remaining parameters. We’ll feed it the condition first, and we’ll feed the body to the partially evaluated function that it returns. In reality, it’ll look something like this:
var until10 = until(i == 10)
until10({
println(i)
i += 1
})
Scala doesn’t automatically let us do this partial evaluation. But we can explicitly allow it by chunking up the parameter list:
def until(condition: => Boolean)(body: => Unit) {
while (!condition) {
body
}
}
Freeing up the parameter list like this to allow partial application is called currying. Haskell does it automatically.
You are probably thinking, “Call-by-name. Big deal. How many new control structures am I going to need in my life?” Probably not many, but I think the bigger deal is that just as Stroustrup made our new types indistinguishable from the builtin types, call-by-name lets our code get the same special treatment that builtin structures get. Call-by-name is just another step in the path to a language designer granting you full citizenship in the world centered on that language.
Suppose a call-by-name function never references its lazily evaluated parameter. How many times will it have been evaluated? None. That’s a win compared to eager evaluation, especially if evaluating it was expensive. What if it’s referenced once? It will be evaluated once. What if it’s referenced many times? It will be evaluated many times.
| scheme | 0 references | 1 reference | n references |
|---|---|---|---|
| call-by-value/pass-by-copy | 1 | 1 | 1 |
| call-by-name/pass-by-closure | 0 | 1 | n |
There’s another scheme for passing parameters that we should look at. It too is lazy, but instead of reevaluating the parameter on every reference, we only evaluate it the first time and record the result so future references are really fast. This is termed call-by-need, and it too needs a better name. Like pass-by-jit. JIT stands for just-in-time, hinting at the lazyness of this scheme. Let’s round out our table:
| scheme | 0 | 1 | n |
|---|---|---|---|
| call-by-value/pass-by-copy | 1 | 1 | 1 |
| call-by-name/pass-by-closure | 0 | 1 | n |
| call-by-need/pass-by-jit | 0 | 1 | 1 |
Call-by-need semantics are all over Haskell. What are they good for, those lazy sods? Well, let’s see how they work first, and then I think we’ll be better equipped to answer that question. We will demonstrate the ideas of call-by-need in Ruby, even though it doesn’t technically support it. Let’s create a Lazy class that encapsulates the big ideas of call-by-need:
- The programmer expresses a computation, but it is not executed until later.
- When the programmer does need the real value, the computation is executed and the result is stored for immediate later retrieval.
How do we expression a computation but not execute it? We do it all the time. Push it into a function. Or a lambda. Or a block. Someone will therefore use our class like this:
image = Lazy.new do
open('http://www.twodee.org/tests/slowimage/slowimage.php').read
end
puts "The lazy image has been constructed, but not executed."
if some condition
puts "Ugh! This is gonna be slow."
puts image.eval.length
puts "But these will be fast!"
puts image.eval.length
puts image.eval.length
puts image.eval.length
puts image.eval.length
puts image.eval.length
puts image.eval.length
else
puts "we never paid the cost of evaluating the image!"
end
Retrieving that image is a costly operation. We can avoid that cost if we don’t need it. But if we need it a lot, we’ll only take the hit once.
Alright, so how do this? Lazy‘s constructor will need to receive and hang on to a block. This is often called a thunk:
class Lazy
def initialize &block
@thunk = block
end
end
We will need to evaluate that thunk when the user really needs the value:
class Lazy
def initialize &block
@thunk = block
end
def evaluate
@thunk.call
end
end
But there’s no performance benefit yet. We also need to hold on to (memoize) the value after the first execution. Subsequent calls will not reevaluate. They will simply return the previously cached result:
class Lazy
def initialize &block
@thunk = block
@cache = nil
end
def evaluate
if @cache.nil?
@cache = @thunk.call
end
@cache
end
end
So, there’s an obvious performance benefit from call-by-name semantics. In fact, this laziness can let us create infinite data structures: lists that go on forever, trees that have no leaf nodes. Let’s make an infinite list. It’s always good to start off designing a class by looking at it from the client’s perspective. We want to start it off at a particular number and have it jump by some delta between elements. We can iterate through like this for as many elements as we wish:
l = InfiniteList.new 10, 5
40.times do
puts l.head
l = l.tail
end
We can start to write the constructor. We know the list will have the given number as its head:
class InfiniteList
def initialize start, delta
@head = start
end
end
What about its tail? That’ll be another InfiniteList whose head is start + delta. But that InfiniteList will itself have a tail that’s an InfiniteList, and things will get out of hand quickly. We need to be lazy about the tail:
def initialize start, delta
@head = start
@tail = Lazy.new
InfiniteList.new start + delta, delta
end
end
Now, we need some methods for accessing the list’s head and tail. The head is pretty easy:
def head
@head
end
But remember that we need delayed evaluation of the tail until it is needed. That time is now. We force evaluation of the tail:
def tail
@tail.eval
end
Will you use call-by-name a lot in life? Well, you wouldn’t if you didn’t know it was possible. But the idea of postponing an evaluation until later and caching its result is definitely not crazy. Call-by-need semantics actually build that behavior into a data structure so that the delaying and caching is transparent to the developer. You are probably using software that uses the call-by-name idea without realizing it. I can think of a few applications:
- Consider an SQL query that yields thousands or millions of records. Not all of them are probably given to you when you issue your
SELECTstatement. Perhaps you are given the first 100, and the remainder are lazily waiting around to be needed. - Consider a game with a large 3D world to explore. A smart game engine won’t immediately load in the 3D models and textures for parts of the world that you aren’t currently in. Eagerness and graphics cards don’t get along.
- Consider visualizing a social graph. If you want see who is friends with someone else, you don’t need to load the entire graph into memory at once. You can load the graph lazily. Only when a node is selected do you retrieve its connected nodes.
A data structure that abstracts this laziness improves performance without burdening the clients.
See you next time, when we discuss some how to tame recursion that gets out of hand.
P.S. It’s time for a haiku!
I don’t have clean bowls
It’s not because I’m lazy
I just wash by need
P.P.S. Here’s the code we wrote together:
macrodanger.c
#include <stdio.h>
#include <stdlib.h>
#include <stdlib.h>
#include <ctype.h>
#define PRINTDIGIT(c) if (isdigit(c)) printf("%c", c);
int main(int argc, char **argv) {
PRINTDIGIT(getchar());
PRINTDIGIT(getchar());
PRINTDIGIT(getchar());
return 0;
}
malloc.c
#include <stdio.h>
#include <stdlib.h>
#define EZMALLOC(type, n) (type *) malloc(sizeof(type) * (n))
int main(int argc, char **argv) {
/* int *p = (int *) malloc(sizeof(int) * 10); */
int *p = EZMALLOC(int, 10 - 1);
int *q = EZMALLOC(int, 10 - 1);
for (int i = 0; i < 10; ++i) {
p[i] = 12;
q[i] = 7;
}
for (int i = 0; i < 10; ++i) {
printf("p[%d]: %d\n", i, p[i]);
}
free(p);
return 0;
}
lazy.rb
#!/usr/bin/env ruby
require 'open-uri'
class Lazy
def initialize &block
@thunk = block
@cache = nil
end
def eval
if @cache.nil?
@cache = @thunk.call
end
@cache
end
end
class InfiniteList
def initialize(start, delta)
@head = start
@tail = Lazy.new do
InfiniteList.new(start + delta, delta)
end
end
def head
@head
end
def tail
@tail.eval
end
end
l = InfiniteList.new(0, 5)
l2 = l
10000000.times do
puts l.head
l = l.tail
end
# image = Lazy.new do
# open('http://www.twodee.org/tests/slowimage/slowimage.php').read
# end
# puts "The image has been constructed but not evaluated."
# puts "This is gonna take forever."
# puts image.eval.length
# puts "Whew..."
# puts image.eval.length
# puts image.eval.length
# puts image.eval.length
# puts image.eval.length
# puts image.eval.length
# puts image.eval.length
# puts image.eval.length
# puts image.eval.length
# puts image.eval.length