Introduction to Programming Languages/Definition and Examples

Some programming languages treat functions as first class values. In other words, functions in these languages can be assigned to variables, and can be passed as parameters to and returned from other functions. This capacity opens up a vast horizon of possibilities to program developers. In this chapter we will explore some of these possibilities.

Definition and Examples

A fundamental notion that we will use in this chapter is the concept of high-order functions, which we define, recursively, as follows:

• A function that does not receive other functions as parameters or return functions has order zero.
• A function that receives or returns a function of order n - 1 has order n.

As an example, the function below, implemented in SML, receives a polymorphic list of type 'a list, plus another function of type 'a -> 'b, and returns a new list of type 'b list. We obtain this new list by applying the mapping function to every element of the input list:

fun map _ nil = nil
 | map f (h::t) = f h :: map f t

Our map function is very reusable. We can reuse the same algorithm with many different types of mapping functions and input lists. Below we have some examples:

- map (fn x => x + 1) [1, 2, 3, 4];
val it = [2,3,4,5] : int list

- map op + [(1, 2), (3, 4)];
val it = [3,7] : int list

- map op ~ [1, 2, 3, 4];
val it = [~1,~2,~3,~4] : int list

- map (fn x => "String: " ^ Int.toString x) [1, 2, 3, 4];
val it = ["String: 1","String: 2","String: 3","String: 4"] : string list

In the previous example, map is a function of order one, because it receives a function of order zero as a parameter. High order functions are very common among functional languages, such as SML, Haskell, ocaml, erlang, and F#. However, even languages that have a more imperative semantics, such as C#, Python and Lua provide this functionality. In fact, almost every modern programming language has some support to high-order functions. Below we see our initial example, the map function, coded in Python:

def map(f, l):
 return [f(x) for x in l]
 
print map(lambda x: x > 4, [2,3, 5, 7])

def inc(x): return x + 1
print map(inc, [2, 3, 5, 7])

It is also possible to use high-order functions in C, by passing pointers to functions as parameters of other functions. For instance, the code below implements our original map example. We point, however, that this coding style is not very typical of C, a fact that might justify the relatively verbose program.

#include <stdio.h>
#include <stdlib.h>
 
int* map (int* a, unsigned size, int (*f)(int)) {
 int i = 0;
 int* narray = (int*) malloc(size * sizeof(int));
 while (i < size) {
  narray[i] = (*f)(a[i]);
  i++;
 }
 return narray;
}
 
int inc(int x) {
 return x + 1;
}
 
int sqr(int x) {
 return x * x;
}
 
void printvec(int* a, unsigned size) {
 int i = 0;
 while (i < size) {
  printf("%8d", a[i++]);
  if (! (i % 10) ) {
   printf("\n");
  }
 }
 printf("\n");
}
 
int main(int argc, char** argv) {
 int* a = (int*) malloc((argc - 1) * sizeof(int));
 int* b;
 int* c;
 int i = 1;
 while(i < argc) {
  a[i++] = atoi(argv[i]);
 }
 printvec(a, argc - 1);
 b = map(a, argc - 1, inc);
 printvec(b, argc - 1);
 c = map(a, argc - 1, sqr);
 printvec(c, argc - 1);
}