» CS 330: Lecture 34 – Call-by-name

CS 330: Lecture 34 – Call-by-name

April 30, 2018 by Chris Johnson. Filed under cs330, lectures, spring 2018.

Dear students,

When you call a function, what happens? In particular, what happens in this code?

int m() {
  cout << "m" << std::endl;
  return 5;
}

int r() {
  cout << "r" << std::endl;
  return 7;
}

int multiply(int a, int b) {
  cout << "*" << std::endl;
  return a * b;
}

int main(int argc, char **argv) {
  cout << multiply(m(), r());
}

We should see the following output:

m
r
*

Our main effectively become this:

int a = m();
int b = r();
cout << multiply(a, b);

Could there be any other way for this code to have been executed? If you’ve grown up on Java and C, you probably have a hard time imagining any other possible way. But yes, there are other ways that this might have played out.

What’s happening here is that the parameters to multiply are being evaluated eagerly. Before multiply ever sees the light of day, its values have been readied. Eager evaluation tends to be a feature of languages that use call-by-value parameter passing. In call-by-value languages, a function gets a copy of the actual parameters it is given. In fact, a better term would be pass-a-copy. That’s why code like this has no lasting effect:

public static void swap(int a, int b) {
  int tmp = a;
  a = z;
  z = tmp;
}

Consider the cost of eager evaluation. If a parameter is never referenced in a function, how many times will we have we evaluated it? Once. If it’s referenced once? Still once. If it’s referenced many times? Still once. Let’s record this in a table.

scheme	0	1	n
call-by-value	1	1	1

Sometimes it would be nice to delay the evaluation. For example, suppose we are writing a testing framework and we tried this definition for assert:

void assert(int expected, int actual) {
  if (expected != actual) {
    printf("[%s:%s:%d] Expected: %d | Actual: %d\n", __FILE__, __func__, __LINE__, expected, actual); 
  }
}

Let’s test this:

int main(int argc, char **argv) {
  assert(4, 3 * 2);
  assert(4, 1 + 1 + 1 + 1 + 1);
  return 0;
}

Here’s the output:

[foo.c:assert:6] Expected: 4 | Actual: 6
[foo.c:assert:6] Expected: 4 | Actual: 5

Our definition of assert fails us. For one, the reference to the file is not helpful at all. For two, we don’t get much information about the code that produced the wrong result. That’s because by the time assert gets control, the actual value has been eagerly evaluated. But what if we could delay its evaluation? Well, we can’t naturally do that in C, but we can strip out the function mechanism altogether. We’ll use the preprocessor to change this code from a function that introduces a new isolated context into a macro that essentially gets copied and pasted into the calling context, where the actual value has yet to be evaluated.

On top of that, we can use another trick of the preprocessor to print the raw the source of the expression that generates the actual value. We can turn the unevaluated expression into a string with the # operator:

#define ASSERT(expected, actual) \
  if (expected != actual) \
    printf("[%s:%s:%d] Expected: %d | Actual: %s -> %d\n", __FILE__, __func__, __LINE__, expected, #actual, actual)

Here’s our new output:

[foo.c:main:15] Expected: 4 | Actual: 3 * 2 -> 6
[foo.c:main:16] Expected: 4 | Actual: 1 + 1 + 1 + 1 + 1 -> 5

Much better! What’s actually going on under the hood? Let’s compile with gcc -E to preprocess:

int main(int argc, char **argv) {
  if (4 != 3 * 2) printf("[%s:%s:%d] Expected: %d | Actual: %s -> %d\n", "foo.c", __func__, 15, 4, "3 * 2", 3 * 2);
  if (4 != 1 + 1 + 1 + 1 + 1) printf("[%s:%s:%d] Expected: %d | Actual: %s -> %d\n", "foo.c", __func__, 16, 4, "1 + 1 + 1 + 1 + 1", 1 + 1 + 1 + 1 + 1);
  return 0;
}

So, 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.

We should note that if your expression issues a side effect, macros are particularly dangerous. In the code above, our actual expression gets evaluated twice. Any side effect would also be triggered twice. Sometimes this is bad. 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, 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. Suppose we wanted to write our own repeat loop. Let’s try to do this in Ruby:

def repeat n, body
  i = 0
  while i < n
    body
    i += 1
  end
end

repeat(10, puts("Foobag!"))

What’s the output here?

Foobag!

Not exactly what we wanted. Control structures must not execute their parameters until they are needed! Imagine an if function:

if(condition, then, else);

In an eager evaluation scheme, both then and else will be executed before if is even called. That’s very not right. It defies the semantics of conditional statements. We want to delay parameter evaluation. A few modern languages support “real” delaying. R and Scala, for example. But not many.

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.

Let’s extend our table. 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	1	1	1
call-by-name	0	1	n

How about a loop-and-a-half control structure? Sadly, Ruby doesn’t let us pass more than one block to a function. We’ll use a lambda instead:

def loophalf n, outer, inner
  if n > 0
    outer.call
    n.times do
      inner.call
      outer.call
    end 
  end
end

loophalf 3, lambda { print 'x' }, lambda { print 'o' }

Even if call-by-name doesn’t exist in most of our languages, we can get close!

Another tool that supports call-by-name/pass-by-closure semantics is GNU Make. Consider this possible structure of a Makefile:

COMPILE = $(CC) $(CFLAGS) -c
CC = gcc
CFLAGS = -Wall -pedantic

main.o: main.c
  @echo Running " $(COMPILE) main.c"...
  $(COMPILE) main.c

When we run make, we see this output:

gcc -Wall -pedantic -c main.c

But when you stop and think about it, it’s kinda weird that this worked. If this were another language, we would have had an issue with the definition of COMPILE. Variables CC and CFLAGS don’t exist at the time of its definition. But in Make, operator = lazily assigns the right-hand side. In a sense, COMPILE is a function. It will get evaluated each time someone calls it with $(COMPILE).

Interestingly, we can exploit this idea to make a highly reusable COMPILE rule:

COMPILE = $(CC) $(CFLAGS) -c $<
CC = gcc
CFLAGS = -Wall -pedantic

main.o: main.c
  @echo Running " $(COMPILE)"...
  $(COMPILE)

Here’s your TODO list:

See you next time, when we discuss one last scheme for passing parameters: call-by-need.

Sincerely,

P.S. It’s time for a haiku!

“Four score and seven…”
Lincoln scribbled on his draft
“TODO: execute”

P.P.S. Here’s the code we wrote together:

foo.cpp

#include <iostream>

int m() {
  std::cout << "m" << std::endl;
  return 5;
}

int r() {
  std::cout << "r" << std::endl;
  return 7;
}

void magic(int a, int b) {
  int number = a + a + a + a + a + b + b;
  std::cout << "number: " << number << std::endl;
}

int main(int argc, char **argv) {
  /* magic(m(), r());   */
  int a = m();
  int b = r();
  magic(a, b);
  return 0;
}

asserter.h

#ifndef ASSERTER_H
#define ASSERTER_H

/* void assert(int expected, int actual); */
#define assert(expected, actual) \
  if (expected != actual) { \
    printf("[%s:%s:%d] Expected: %d | Actual (%s): %d\n", __FILE__, __func__, __LINE__, expected, #actual, actual); \
  } \

#endif

asserter.c

#include <stdio.h>
#include "asserter.h"
#include <stdio.h>

void assert(int expected, int actual) {
  if (expected != actual) {
    printf("[%s:%s:%d] Expected: %d | Actual: %d\n", __FILE__, __func__, __LINE__, expected, actual);
  }
}

main.c

#include <stdio.h>
/* #include <stdlib.h> */

#include "asserter.h"

int mass(int density, int volume) {
  return density * volume + 5;
}

int main(int argc, char **argv) {
  assert(300, mass(3, 100));
  return 0;
}

ruby.rb

#!/usr/bin/env ruby

def repeat n, body
  i = 0
  while i < n
    # puts "i: #{i}"
    body.call
    i += 1
  end
end

def repeatBlock n
  i = 0
  while i < n
    yield
    i += 1
  end
end

class Fixnum
  def times
    puts "FFOOOOFOFOFOFOF"
    i = 0
    while i < self
      yield
      i += 1
    end
  end
end

# result = puts("Jordan for Chancellor.")
# p result
# repeat(4, lambda { puts("Jordan for Chancellor!!!!") })
repeatBlock(4) do 
  puts("Jordan for Chancellor!!!!")
end

5.times do
  puts "Brendan for Vice CHanceLLOR!"
end

loophalf.rb

#!/usr/bin/env ruby

def fencepost(nPosts, outer, inner)
  if nPosts > 0
    i = 0
    while i < nPosts - 1
      outer.call 
      inner.call
      i += 1
    end
    outer.call
  end
end

fencepost(1, lambda { print('x') }, lambda { print('o') })

Makefile

COMPILE = $(CC) $(CFLAGS) $<
CC = gcc
CFLAGS = -Wall -pedantic

main.o: main.c
  $(COMPILE)