SCIP 1.3 Formulating Abstractions with Higher-Order Procedures

Mix.install([])

1.3

Higher Order Procedure: a procedure that manipulates a procedure.

1.3.1 Procedures as Arguments

When you observe muliple procedures share the same pattern or structure it is indicative of a useful abstraction waiting to be brought to the surface. In such a case, you would map out the common structure and then pass the actual computation as an argument. This is not a new concept as mathematicians have identified such abstractions for centuries, e.g. sigma notation and “summation of a series”.

1.3.2 Constructing Procedures Using Lambda

It would be cumbersome to define a named abstraction for trivial operations only so that they could be passed as arguments. Programming languages will provide a lambda.

lambda definitions are used to create procedures with no name.

multiply = fn a, b -> a * b end
multiply.(5, 5)

perform_operation = fn operation, a, b -> operation.(a, b) end
perform_operation.(multiply, 5, 5)

We will often need local variables in our procedures other than those bound as formal parameters.

Let’s say we wanted to compute:

$f(x, y) = x(1 + xy)^2 + y(1 - y) + (1 + xy)(1-y)$

That’s confusing! It could be simplified as:

$a = 1 + xy$

$b = 1 - y$

$f(x, y) = xa^2 + yb + ab$

If we were simply using functions, we could use lambda functions to facilitate this local binding.

f = fn x, y ->
  (fn a, b ->
     x * (a * a) + y * b + a * b
   end).(1 + x * y, 1 - y)
end

f.(3, 4)

That’s not very readable! We are using an anonymous function to capture (a, b) as local parameters. Scheme has a let special form that allows you do define local parameters. (Fun fact: the let special form is in fact syntactic sugar for the underlying lambda application).

Elixir has function level scope, allowing for the above to be refactored:

f = fn x, y ->
  a = 1 + x * y
  b = 1 - y
  x * (a * a) + y * b + a * b
end

f.(3, 4)

1.3.3 Procedures as General Methods

The above are instances where we are using procedures to express general methods of computation independent of the particular functions involved. Let’s dive into concrete applications of this new knowledge.

A number x is called a fixed point of a function f if x satisfies the equation f(x) = x. For some functions f we can locate a fixed point by applying f repeatedly: f(x), f(f(x)), f(f(f(x)))...

tolerance = 0.00001

fixed_point = fn f, first_guess ->
  close_enough? = fn v1, v2 ->
    abs(v1 - v2) < tolerance
  end

  try_guess = fn guess, recur ->
    next = f.(guess)
    IO.puts(guess)

    if close_enough?.(guess, next) do
      next
    else
      recur.(next, recur)
    end
  end

  try_guess.(first_guess, try_guess)
end

fixed_point.(fn x -> :math.cos(x) end, 1.0)

We can now use fixed_point in cases where we are searching for an answer using iteratively improved guesses.

sqrt = fn x ->
  fixed_point.(fn y -> x / y end, 1.0)
end

# 36.0
# 1.0
# 36.0
# 1.0
# 36.0
# 1.0
# 36.0
# 1.0
# etc

Unfortunately this never converges, with the large oscillations in guesses causing an infinite loop. We can control this by preventing the guesses from changing so much. We can use Average Damping to average successive approximations toward a solution. Instead of iterating over x / y, we can make a new guess by averaging y with x / y so as to locate something that is not as far from y as x / y.

average = fn x, y ->
  (x + y) / 2
end

sqrt = fn x ->
  fixed_point.(fn y -> average.(y, x / y) end, 1.0)
end

sqrt.(36)

1.3.4 Procedures as Returned Values

Just as the ability to pass procedures as arguments increases a language’s expressiveness, so does the ability to return procedures.

As a programmer one should always be on the look out for abstractions appropriate to the task.

Programming languages will impose limits on the ways in which computation elements can be manipulated. Elements with the fewest restrictions are said to be First-Class.

First-class elements can be:

• named by variables
• passed as arguments to procedures
• returned as results of procedures
• included in data structures

Returning to average damping, we can extract that logic into its own named procedure. Let’s make a procedure that:

• takes as its argument a procedure f
• returns as its value a procedure that
  • takes as its argument the value x
  • produces an average of x and f(x).

average_damp = fn f ->
  fn x -> average.(x, f.(x)) end
end

average_damp.(sqrt).(36)

We can now refactor the sqrt procedure to use the average_damp procedure.

sqrt = fn x ->
  fixed_point.(average_damp.(fn y -> x / y end), 1.0)
end

sqrt.(36)

We can then abstract this further by observing that the method begins with a function and finds a fixed point of some transformation of the function. This very general procedure:

• takes as its arguments a procedure g, a procedure that transforms g, and an initial guess
• returns a fixed point of the transofmred function

fixed_point_of_transform = fn g, transform, guess ->
  fixed_point.(transform.(g), guess)
end

sqrt = fn x ->
  fixed_point_of_transform.(fn y -> x / y end, average_damp, 1.0)
end

sqrt.(36)