Higher-Order Procedures

........in Mathematics, Common Lisp, Python

Higher-Order procedures are procedures which manipulate procedures- accept procedures as parameters or return newly constructed procedures to the caller. The best discussion on the topic is in Section 1.3 of Structure and Interpretation of Computer Programs. Language implementations which offer such facilities are said to treat procedures as first class objects. The idea is simple: you should be able to toss around procedures/functions as if they are simple numbers, strings, or as we call them, values

Differential Calculus

A very simple example of a higher-order procedure is found in differential calculus. The derivative of a function is another function. The derivative operator operates on a function to generate another function. For the sake of completeness: d/dx f(x) => f'(x), where f(x), f'(x) are functions in a variable quantity, x. Similar examples are found in Integral Calculus, where the indefinite integral of any function is another function.

Procedures as Parameters

When you are thinking in a language which supports higher-order procedures, you should think of tossing around procedures between procedure calls, like they were just another variable.  Lets We shall now implement Simpson's rule of Integration as a simple demonstration of passing around procedures in Python and Common Lisp.

The following Python script calculates the Integral of a function by Simpson's rule:

# Integration by Simpson's rule

def simpsons(f,a,b,n):

summation = 0.0
h=(b-a)/n
for k in range(2,n-1,2):
summation = sum(summation,2*f(a+(k*h)))
for k in range(1,n,2):
summation = sum(summation,4*f(a+(k*h)))

summation = sum(summation, f(a) + f(a+(n*h)))
print "The Integral is (%.2f)" % float(summation*(h/3))

def sum(accumulator, term):
return accumulator+term


# This is the function for which the Integral is calculated. You can replace
# it with any other function.

def cube(x):
return x*x*x

simpsons(cube,2,5.0,4) # passing around the function to be integrated as a parameter


Here is the Common Lisp code:

;; Integration by Simpson's rule; CL code
;; Found to be working correctly with 'clisp'

(defun simpsons (f a b n)
(let ((summation 0)
(h (/ (- b a) n)))
(loop for k from 2 below (- n 1) by 2 do
(setf summation (+ summation (* 2 (funcall f (+ (* k h) a))))))
(loop for k from 1 below n by 2 do
(setf summation (+ summation (* 4 (funcall f (+ (* k h) a))))))
(setf summation (+ (funcall f a) (funcall f (+ (* n h) a))))
(format t "~d" (* (/ h 3.0) summation))))

(defun cube(x)
(* x x x))

;; Passing around the function to be integrated

(simpsons 'cube 2 3 8) ; demonstrating higher-order functions

For understanding the above code, you should know about procedures/functions in Common Lisp. Chapter 5 of Practical Common Lisp is a good reference.

Constructing and Returning Procedures- lambdas

Similar to the Integration, we could also find the derivative of a function at a point. However, what if we want the derivative function itself, not the value. So we are now looking at constructing a new procedure, say f'(x) and return it, not a numerical value. We shall use lambdas, to construct and return the new procedure. Given a function f(x) and a infinitesimal value dx, the derivative f'(x) of the function f(x)value at any number x is given by f'(x)=(f(x+dx)-f(x))/dx, where dx -> 0 ). Instead of calculating the derivative, we shall construct the new function and return it to the calling procedure.

I shall be demonstrating Common Lisp code here. Let us first defun the function which will calculate the derivative:

(defun deriv (fn x dx) ; fn-> Function for which derivative is to be calculated, x-> a integer, dx -> a very small value ~ 0
( lambda (x)
(/ (- (funcall fn (+ x dx)) (funcall fn x))
dx)))

Now, define a function for which the derivative is to be calculated, say cube:

(defun cube(x); Any number I get, I will triple it and return
(* x x x))

(deriv 'cube 3 0.02)

Let us now define another function to call the deriv function to calculate the derivative of cube:

(defun deriv-square() (deriv 'cube 3 0.02))
and call it:
(deriv-square)
what we see is this:
< FUNCTION :LAMBDA (X) (/ (- (FUNCALL FN (+ X DX)) (FUNCALL FN X)) DX)>
The FUNCTION: object indicating that we just got back a function as the return value

Python supports lambdas as well. Try to code the above in Python as an exercise

The best method to express Higher-Order procedures is perhaps given in A short introduction to the Lambda Calculus as: T== lambda f (lambda x f(f (f x)))

References and Resources

  1. Formulating abstractions with Higher-Order procedures
  2. Procedures as first class objects
  3. Higher-order functions
  4. GNU CLISP
  5. Practical Common Lisp 
  6. Functional Programming in Python

Revisions:

  1. First Version: 18th Feb, 2009
  2. Added expressing Higher-Order procedures as a lambda: 27th Feb, 2009