teaching machines

CS 330: Lecture 35 – Call-by-need

May 2, 2018 by . Filed under cs330, lectures, spring 2018.

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:

  1. The programmer expresses a computation, but it is not executed until later.
  2. 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:

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.

Sincerely,

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