........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

- Formulating abstractions with Higher-Order procedures
- Procedures as first class objects
- Higher-order functions
- GNU CLISP
- Practical Common Lisp
- Functional Programming in Python

**Revisions:**

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