teaching machines

CS 330 Lecture 35 – Call by Name, Call by Need Cont’d

Agenda

  • what ?s
  • debug macro
  • until loop in Scala
  • lazy data structures

Note

Last time we looked at pass-by-name, which eschews the eager evaluation that we run into in many languages and instead delays evaluation to the point of reference. Sometimes pass-by-name is really useful. Suppose we wanted to write a debugging function that printed out the value of an expression, but also printed out the file name, the line number, and the expression itself. We might take this approach as a first attempt:

void debug(int i) {
  printf("[%s:%s:%d] %s -> %d\n", __FILE__, __func__, __LINE__, "expr?", i); 
}

But this approach has several problems. The __*__ variables point to the debug function, not the “debugger” function, making them not so useful. Additionally, we don’t have any way to print the expression, since eager evaluation has taken place long before debug got the CPU. Instead, we can use a macro with its pass-by-name semantics. We can turn the expression parameter into a C string with the # operator:

#define DEBUGI(expr) printf("[%s:%s:%d] " #expr " -> %d\n", __FILE__, __func__, __LINE__, expr)
int a = 20;
DEBUGI(a + 1);

Once again, we see that pass-by-name delays evaluation until an expression is needed, allowing us to do other things with the expression than evaluate it. Where else might we want to delay evaluation? 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. We’ll look at an example in Scala of an until loop that demonstrates this.

We saw last time that we might want a pass-by-scheme that has the evaluation cost advantage of pass-by-value and the lazy advantage of pass-by-name. 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

debug.c

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

void debugi(int value) {
  fprintf(stderr, "[%s:%s:%d] %s -> %d\n", __FILE__, __func__, __LINE__, "expr?", value);
}

#define DEBUGI(expr) \
  fprintf(stderr, "[%s:%s:%d] %s -> %d\n", __FILE__, __func__, __LINE__, #expr, expr)

int main(int argc, char **argv) {
  
  int nums[] = {0, 1, 2, 3, 4};
  int i = 3;

  debugi(nums[i + 1]);
  DEBUGI(nums[i + 1]);

  return 0;
}

Until.scala

object Main {
  // def until(condition: => Boolean, body: => Unit) {
  def until(condition: => Boolean)(body: => Unit) {
    while (!condition) {
      body
    }
  }

  def main(args: Array[String]) {
    var i = 0
    // while (i < 10) {
      // println(i)
      // i += 1
    // }

    until (i >= 10) {
      println(i)
      i += 1
    }
  }
}

lazy.rb

#!/usr/bin/env ruby

require 'open-uri'

class Lazy
  def initialize &block
    @thunk = block
    # @value = block.call -- this would over-eager
    @cache = nil
  end

  def value
    # if not @cache
      # @cache = @thunk.call
    # end
    # @cache

    @cache ||= @thunk.call
  end
end

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

image = Lazy.new do
  open('http://www.twodee.org/tests/slowimage/slowimage.php').read
end

# puts image.value.length
# puts image.value.length
# puts image.value.length
# puts image.value.length

class InfiniteList
  def initialize start
    @head = start
    @tail = Lazy.new do
      InfiniteList.new start + 1
    end
  end

  def head
    @head
  end

  def tail
    @tail.value
  end
end

list = InfiniteList.new 3
1000000000.times do
  puts list.head
  list = list.tail
end

Comments

Leave a Reply

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