CS 430: Lecture 5 - Functions

Dear students:

Your reading was on functions, and today we'll focus on two main topics related to this theme: parameter-passing schemes and higher-order functions.

Parameter Passing Schemes

Because the world is on fire, there's a page missing from the book on the various schemes for passing parameters. If you a function as a box with inputs and outputs, these schemes define how the box is wired up in its larger context. Like almost every other concept in the world of programming languages, there are several different approaches to this wiring.

Pass-by-value

The subprogram gets its own copy of the actual parameter values. Because any changes to the parameters will be applied to the copied value and not the caller's values, pass-by-value implements in parameter semantics. C, Java, JavaScript, and Ruby are all pass-by-value.

Pass-by-value is a simple scheme to implement and understand. It pervades modern languages. The copying of values can incur extra runtime costs if structs and arrays themselves are cloned. In Java, Ruby, and JavaScript, we have implicit pointers to any non-primitive, and only the pointers are copied, which tend to be 4- or 8-bytes.

Pass-by-result

The subprogram handles an out parameter by storing the value to be returned in a local variable and copying the value over to the caller's memory space when the subprogram finishes.

Pass-by-copy or pass-by-value-result

The subprogram handles an inout parameter by copying the passed value to a local variable, which is referenced in the body of the subprogram, and copying the value back into the caller's memory space with the subprogram finishes.

Pass-by-reference

The caller shares its actual parameters with the subprograms. Assignments to the formal parameters will effect changes in the caller's memory. C++ is one of the only modern mainstream languages that truly supports this passing scheme. Some folks will try to tell you Java or Ruby are pass-by-reference, perhaps claiming that a method can change a parameter, like this:

public void budge(ArrayList<String> names) {
  names.add(0, "Chris");
}

public void budge(ArrayList<String> names) {
  names.add(0, "Chris");
}

They are right that the method is changing memory beyond itself. But the caller's parameter is not being changed. The object the parameter refers to is what's changing. If you tried to change the parameter, that change would be local:

public void budge(ArrayList<String> names) {
  names = new ArrayList<String>();
  names.add("Chris");
  names.add("Chris");
  names.add("Chris");
  names.add("Chris");
}

public void budge(ArrayList<String> names) {
  names = new ArrayList<String>();
  names.add("Chris");
  names.add("Chris");
  names.add("Chris");
  names.add("Chris");
}

In C++, we can see true pass-by-reference at work in the canonical swap routine:

void swap(int &a, int &b) {
  int tmp = a;
  a = b;
  b = tmp;
}

void swap(int &a, int &b) {
  int tmp = a;
  a = b;
  b = tmp;
}

Those assignments to a and b modify the caller's actual parameters. That makes pass-by-reference an implementation of inout parameter semantics.

Most of this argument is due to terminology, as reference is an overloaded term. We need better distinction between C++ references and the implicit pointers of Java, Ruby, and JavaScript that we call references.

Pass-by-name

The caller shares an unevaluated form of its actual parameters with the subprogram. Each time the subprogram refers to the parameter, the unevaluated form is evaluated. Not many modern languages support this scheme; Scala is a notable exception. One benefit of pass-by-name semantics is that they allow the user to define their own control structures as functions, perhaps like this:

function repeatAround(n, outerBlock, innerBlock)
  for i to n - 1
    outerBlock()
    innerBlock()
  outerBlock()

// prints xoxoxox
repeatAround(4, print "x", print "o")

function repeatAround(n, outerBlock, innerBlock)
  for i to n - 1
    outerBlock()
    innerBlock()
  outerBlock()

// prints xoxoxox
repeatAround(4, print "x", print "o")

We want the second and third parameters to get evaluated each time they are called in the repeatAround function, not just once.

In most of our languages, the parameters are evaluated eagerly—before the subprogram takes over. With pass-by-name, we delay their evaluation. We can simulate delayed evaluation by manually turning the second and third parameters into lambdas. Here's how we might write repeatAround in JavaScript:

function repeatAround(n, outerBlock, innerBlock)
  for (let i = 0; i < n - 1; i += 1) {
    outerBlock();
    innerBlock();
  }
  outerBlock();
}

// prints xoxoxox
repeatAround(4, () => console.log("x"), () => console.log("o"))

function repeatAround(n, outerBlock, innerBlock)
  for (let i = 0; i < n - 1; i += 1) {
    outerBlock();
    innerBlock();
  }
  outerBlock();
}

// prints xoxoxox
repeatAround(4, () => console.log("x"), () => console.log("o"))

Higher-order Functions

Regex

We use regular expressions for several tasks: validating input, finding matches in a body text, and substituting text in place of other text. We'll see how these tasks are completed in Ruby to meet these needs:

expand placeholders in templates like Dear #NAME to several different names
reformat camel-case variables like peopleToThank to People to thank
replace math expressions in {{{ and }}} with their value

Each

class Array
  def my_each
    keepers = []
    each do |item|
      if yield item
        keepers.push(item)
      end
    end
    keepers
  end
end

p (0..10).to_a.my_each { |x| x % 2 == 0 }

class Array
  def my_each
    keepers = []
    each do |item|
      if yield item
        keepers.push(item)
      end
    end
    keepers
  end
end

p (0..10).to_a.my_each { |x| x % 2 == 0 }

Filter

class Array
  def my_filter
    keepers = []
    each do |item|
      if yield item
        keepers.push(item)
      end
    end
    keepers
  end
end

p (0..10).to_a.my_filter { |x| x % 2 == 0 }

class Array
  def my_filter
    keepers = []
    each do |item|
      if yield item
        keepers.push(item)
      end
    end
    keepers
  end
end

p (0..10).to_a.my_filter { |x| x % 2 == 0 }

Map

class Array
  def my_map
    new_items = []
    each do |item|
      new_items.push(yield item)
    end
    new_items
  end
end

p (0..10).to_a.my_map { |x| x * 2 }

class Array
  def my_map
    new_items = []
    each do |item|
      new_items.push(yield item)
    end
    new_items
  end
end

p (0..10).to_a.my_map { |x| x * 2 }

Fold

class Array
  def my_fold(accum0)
    accumulator = accum0 
    each do |item|
      accumulator = yield accumulator, item
    end
    accumulator
  end
end

p (0..10).to_a.my_fold(0) { |accumulator, x| x + accumulator }

class Array
  def my_fold(accum0)
    accumulator = accum0 
    each do |item|
      accumulator = yield accumulator, item
    end
    accumulator
  end
end

p (0..10).to_a.my_fold(0) { |accumulator, x| x + accumulator }

TODO

Here's your list of things to do before we meet next:

Make progress on project 1. You are expected to spend 3–5 hours per week on your project, and you must submit a progress report to a private channel that I will make for you on Discord. Your channel will include a few of your classmates, and your job is to cheer each other on and keep each other accountable.

See you next time.

Sincerely,

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

If code is magic Then my functions must be spells And I'm Mickey Mouse