Higher Order Functions

By Jonathan Bartlett
2005-05-13


Using functions as arguments
New programmers often have trouble seeing places where passing functions as arguments would be useful. In many programs, there will be one or two instances of what is basically the same algorithm coded multiple times but with slight variations. These are perfect candidates for functions as arguments.

What you can do is code the basic structure of the algorithm into one function. Then, you can take the pieces that vary and add them back in as function parameters. This allows a great amount of customization within the function. You can also add extra function parameters for future expansion. Combining functions like this removes redundancy from your programs, and by extension, reduces the errors that come from re-coding the same algorithm over and over within a program.

Suppose you have an order-processing algorithm composed of several parts that:

• Processes each line of the order and adds up the total.
• Calculates shipping on the order.
• Validates the credit line of the purchaser.
• If successful, charges the order, sends an order confirmation, and records it in the database.

Now let's say that different customers have different types of shipping to calculate, have their credit line calculated differently, and are charged differently for each order. For example, shipping might be calculated through a different service provider depending on the client. The credit line might be checked through your own business on some customers or through the credit-card company on others. Order charging might vary depending on whether the client was normally billed, charged through their credit card, or performs automatic withdrawal. Different customers may have different processing needs for each of these stages.

One way to code such a function would be to simply hardcode all of the possible pathways in your order-processing algorithm directly. Then the call to this function would include a list of flags indicating which style of processing was requested. However, as the number of possibilities gets larger, the order-processing algorithm would become unwieldy.

Another way to code the function is to have these stages handled by independent functions passed to the algorithm. This way, the order-processing algorithm needs to have only the general flow of the algorithm coded directly. The specifics of each major stage would be handled by functions passed in. Such an algorithm would need to have parameters for the shipping-calculation function, the credit-validation function, and the order-charging function.

Listing 6 demonstrates a function in Scheme that encodes such an algorithm.

Listing 6. Using functions as arguments in order processing

(define process-order

   ;;The function has one data record for the order and three functions as parameters

   (lambda (order ship-calc-func credit-validate-func charge-order-func)

      (let

         (

            ;;Here you execute functions to get the fields

            ;;from the order that you will need for later

            ;;processing

            (order-lines (get-order-lines order))

            (origin (get-origin-address order))

            (destination (get-destination-address order))

            (delivery-time (get-delivery-time order))

            (customer-email (get-customer-email order))



            ;;These values will be calculated when you

            ;;process the order

            (weight 0.0)

            (subtotal 0.0)

            (total 0.0)

            (shipping 0.0)

            (tax 0.0))

         ;;Iterate through each order line, running a function on each line

         ;;to add the weight and price to the weight and price of the order

         (for-each

            ;;Note that anonymous functions created within a function

            ;;have full access to the enclosing function's variables

            (lambda (order-line)

               (set! weight (+ weight (get-weight order-line)))

               (set! subtotal (+ total (get-price order-line))))

            order-lines)



         ;;This uses your shipping calculation function that was passed as a parameter.

         ;;Remember, this could be any number of things, such as calculating from

         ;;a shipping provider's remote database, calculating based on static

         ;;customer-specific tables, or any other method you wish.

         (set! shipping (ship-calc-func weight origin destination delivery-time))



         ;;For this exercise, tax will be considered fairly uniform, so you didn't pass

         ;;a tax-calculating function

         (set! tax (calculate-tax destination subtotal))



         ;;Now record the total

         (set! total (+ subtotal shipping tax))



         ;;Validate the user's credit line, according to the validation parameter

         (if (credit-validate-func total)

            (begin

               ;;Charge the order according to the validation parameter

               (charge-order-func total)

               (send-confirmation customer-email order-lines shipping tax total)

               (mark-as-charged order))

            (begin

               ;;Cancel the order

               (send-failure-message customer-email)

               (mark-as-failed order))))))

Parameters that are functions are passed just like any other parameter, the only difference being their use within the program. This technique allows you to have the algorithm code the general flow of control but still have the specifics of the processing parameterized. Many programmers who do not know this technique often have lots of flags that control the processing and that's not a bad idea when you have a few simple variations in processing. But it starts to get cumbersome as the number of differences grows.

It is difficult to determine at what point passing functions as parameters is more beneficial than having special cases and/or flags control the processing in a function. However, there are some guidelines:

• When the options are few and specific, special-casing is often the better method.
• When the options are so closely tied to the algorithm that it takes several functions using most of the algorithm's local variables to generate the desired options, special-casing is probably the better method.
• When each option needs completely different sets of variables to determine the answer, special-casing is probably the better method.
• When the options are many or if new options are anticipated, functions as parameters is often the better method.
• When the options are very clear and logically separate from the code, functions as parameters is often the better method.

The C language can also have functions passed as parameters, but writing a parameter specification for a function in C is a little confusing. C is statically typed -- that is, types are checked at compile-time -- while Scheme is not. Therefore, declaring a variable or parameter as holding a function requires that you also specify what types of parameters that function takes.

For example, take a look at how you might code the map function mentioned earlier. That function needed to take as a parameter a function of one integer that also returns an integer. The prototype of your square function looked like this: int square(int x). Therefore, to declare a variable that holds a pointer to such a function, you would write the following code:

Listing 7. Variable declaration for a function pointer in C

/* This creates a variable called "the_function" which you can store

 * pointers to functions

 */

int (*the_function)(int);

The first int indicates that the return value is an integer. Then in parenthesis, you have the pointer notation and the name of the variable. In another set of parentheses after the function name is a comma-separated list of the types of arguments the function takes.

Assigning and using functions is actually very straightforward because all functions in C are actually function pointers.

Listing 8. Operations on function pointers in C

int main()

{

   /* Declare function pointer */

   int (*the_function)(int);



   /* assign function pointer */

   the_function = square;



   /* call function */

   printf("The square of 2 is %d\n", the_function(2));



   return 0;

}

Using this knowledge about function pointers in C, you can easily implement a version of Scheme's map function in C. However, your version will be much more limited because it will be handling only integers and integer arrays instead of any type of data and linked lists, as it would in Scheme.

Listing 9. Implementation of the map function in C

void map(int (*mapping_function)(int), int src[], int dst[], int count)

{

   int i;

   for(i = 0; i < count; i++)

   {

      dst[i] = mapping_function(src[i]);

   }

}

For an even more general approach, you could use the type-tag mechanism mentioned in "Better programming through effective list handling" and have the mapping function, the source array, and the destination array all be of type data.

When third-party libraries are used, functions passed to the library as arguments are usually called callback functions. This is because they are used to "call back" into the programmer's custom code from the library. This allows the library writers to write very generic functions which can then call back to the programmer's code for more specific processing.

With callback functions, the library can be extended by the programmer without having to directly modify the source code. For example, most GUI toolbox API's use callback functions for event handling. Callback functions are passed to the GUI API, which are then stored until the user triggers them with events such as mouse clicks and button pushes. The GUI API certainly doesn't know what actions the program needs to take in response to these events so it simply uses the callback functions provided by the calling program to direct the course of action.

Now, having covered functions that can be passed as parameters, I'm going to go a step further and discuss functions that can be created according to a programmer-defined template.

Tutorial Pages:
» Using functions for such higher order purposes as arguments, function-generating functions, and anonymous functions
» Creating anonymous functions
» Functions as function arguments
» Using functions as arguments
» Building functions at runtime
» Functions and object-oriented programming
» Of the highest order
» Resources


First published by IBM DeveloperWorks

Related Tutorials: » How to Install PHP 5 on Linux » How to Install Apache 2 on Linux » How to Install MySQL 5.0 on Linux » SMB Caching » Mound --Bind » Tar Wild Card Interpretation