teaching machines

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

April 27, 2016 by . Filed under cs330, lectures, spring 2016.

Agenda

TODO

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.

/usr/lib/ruby/2.7.0/rubygems/dependency.rb:311:in `to_specs': Could not find 'coderay' (>= 0) among 56 total gem(s) (Gem::MissingSpecError)
Checked in 'GEM_PATH=/.gem/ruby/2.7.0:/var/lib/gems/2.7.0:/usr/lib/ruby/gems/2.7.0:/usr/share/rubygems-integration/2.7.0:/usr/share/rubygems-integration/all:/usr/lib/x86_64-linux-gnu/rubygems-integration/2.7.0:/home/johnch/.gems', execute `gem env` for more information
	from /usr/lib/ruby/2.7.0/rubygems/dependency.rb:323:in `to_spec'
	from /usr/lib/ruby/2.7.0/rubygems/core_ext/kernel_gem.rb:62:in `gem'
	from ./coderay:24:in `
'
#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

/usr/lib/ruby/2.7.0/rubygems/dependency.rb:311:in `to_specs': Could not find 'coderay' (>= 0) among 56 total gem(s) (Gem::MissingSpecError)
Checked in 'GEM_PATH=/.gem/ruby/2.7.0:/var/lib/gems/2.7.0:/usr/lib/ruby/gems/2.7.0:/usr/share/rubygems-integration/2.7.0:/usr/share/rubygems-integration/all:/usr/lib/x86_64-linux-gnu/rubygems-integration/2.7.0:/home/johnch/.gems', execute `gem env` for more information
	from /usr/lib/ruby/2.7.0/rubygems/dependency.rb:323:in `to_spec'
	from /usr/lib/ruby/2.7.0/rubygems/core_ext/kernel_gem.rb:62:in `gem'
	from ./coderay:24:in `
'

expensive.rb

/usr/lib/ruby/2.7.0/rubygems/dependency.rb:311:in `to_specs': Could not find 'coderay' (>= 0) among 56 total gem(s) (Gem::MissingSpecError)
Checked in 'GEM_PATH=/.gem/ruby/2.7.0:/var/lib/gems/2.7.0:/usr/lib/ruby/gems/2.7.0:/usr/share/rubygems-integration/2.7.0:/usr/share/rubygems-integration/all:/usr/lib/x86_64-linux-gnu/rubygems-integration/2.7.0:/home/johnch/.gems', execute `gem env` for more information
	from /usr/lib/ruby/2.7.0/rubygems/dependency.rb:323:in `to_spec'
	from /usr/lib/ruby/2.7.0/rubygems/core_ext/kernel_gem.rb:62:in `gem'
	from ./coderay:24:in `
'