teaching machines

CS 330 Lecture 34 – Call by Value, Name, and Need

Agenda

  • what ?s
  • C preprocessor
  • pass by name
  • pass by need
  • lazy evaluation

TODO

  • Regex talk tonight! Register here.

Note

We begin with an exercise that will help us understand the C preprocessor a little better. For each of the following code snippets, write down what you expect the result to be. We’ll go through all of them before discussing them in further detail.

#define SQUARE(x) x * x
int n = 5;
printf("%d\n", SQUARE(n + 1));
#define NTIMES(n, val) \
for (int i = 0; i < n; ++i) { \
  printf("%d\n", val); \
}
int nums[] = {1, 2, 3, 4, 5};
int i = 0;
NTIMES(4, nums[i]);
#define EZMALLOC(n, type) (type *) malloc(size(type) * n)
int few = 10;
int many = 100;

int *ns = EZMALLOC(few + many, int);
for (int i = 0; i < few + many; ++i) {
  ns[i] = i;
}

char *s = calloc(1000, sizeof(char));

printf("%d\n", ns[64]);

As we run the code, we might be surprised by the results. That’s because parameters to C preprocessor macros are “sent” to these macros unevaluated. The parameters are substituted in as raw program text in the macro definition. When an expression is sent to a function unevaluated, we say it is passed by name. (This is a pretty meaningless term.) We can see exactly what’s happening with gcc -E.

Pass-by-name is in different than pass-by-value. With pass by value, actual parameter expressions are eagerly evaluated before the function takes over. We saw this when we investigated assembly. The parameters get pushed onto the stack before the function is called.

Sometimes pass-by-name is really useful. Like this debugging macro, which automatically labels the printed value with the expression that generated it:

#define DEBUGI(expr) printf(#expr ": %d\n", expr)
int a = 20;
DEBUGI(a + 1);

Pass-by-name delays evaluation until an expression is needed. Where else might we want this? If statements and loops. We want to pass the bodies to these structures but we don’t want to automatically execute them until we have more information.

One issue that comes up with pass-by-name is that it evaluates the passed expression each time it is referenced. Let’s draw a table of the costs and benefits of these two approaches. Just like Mendeleev, we’ll see that we need a pass-by scheme that strikes somewhere in the middle of these two. That’s called pass-by-need. We need to switch from eager evaluation to lazy evaluation, but once evaluated, we want to hang on to the expression’s value so that future references can reuse the previous result.

It turns out that lazy evaluation is how Haskell supports infinite data structures. Thinking how it models [1..] will lead us to an implementation of lazy structures in Ruby.

Code

macros.c

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

int main(int argc, char **argv) {

#define SQUARE(x) x * x
  int n = 5;
  printf("%d\n", SQUARE(n + 1)); 

/* #define SQUARE(x) (x) * (x) */

#define NTIMES(n, val) \
  j = 6; \
  for (int i = 0; i < n; ++i) { \
      printf("%d\n", val); \
  }
  int nums[] = {1, 2, 3, 4, 5};
  int i = 0;
  int j = 4;
  NTIMES(j, nums[i]);

#define EZMALLOC(n, type) (type *) malloc(sizeof(type) * n)
/* #define EZMALLOC(n, type) (type *) malloc(sizeof(type) * (n)) */
  int few = 10;
  int many = 100;

  int *ns = EZMALLOC(few + many, int);
  for (int i = 0; i < few + many; ++i) {
    ns[i] = i;
  }

  for (int i = 0; i < few + many; ++i) {
    printf("ns[%d] -> %d\n", i, ns[i]);
  }

  char *s = calloc(1000, sizeof(char));

  printf("%d\n", ns[64]);

  return 0;
}

expensive.rb

#!/usr/bin/env ruby

require 'open-uri'

def image
  open('http://www.twodee.org/tests/slowimage/slowimage.php').read
end

puts image.length

Comments

Leave a Reply

Your email address will not be published. Required fields are marked *