First Class Elements in Languages

In general, programming languages impose restrictions on the ways in which computational elements can be manipulated. Elements with the fewest restrictions are said to have first-class status, an idea originally due to Christopher Strachey

Some of the “rights and privileges” of first-class elements are that they may be:

• Named by variables
• Passed as arguments to functions
• Returned as the results of functions
• Included in data structures

Lisps, unlike other common programming languages, awards functions full first-class status. This poses challenges for efficient implementation, but the resulting gain in expressive power is enormous.

The major implementation cost of first-class functions is that allowing functions to be returned as values requires reserving storage for a function’s free variables even while the function is not executing. In the Scheme implementation we will study in Section 4.1, these variables are stored in the function’s environment.

Higher-Order Functions

We have seen that functions are, in effect, abstractions that describe compound operations on numbers independent of the particular numbers. For example, when we write

(defn cube [x]
  (* x x x))

we are not talking about the cube of a particular number, but rather about a method for obtaining the cube of any number. Of course we could get along without ever defining this function, by always writing expressions such as

(* 3 3 3)
(* x x x)
(* y y y)

and never mentioning cube explicitly. This would place us at a serious disadvantage, forcing us to work always at the level of the particular operations that happen to be primitives in the language (multiplication, in this case) rather than in terms of higher-level operations. Our programs would be able to compute cubes, but our language would lack the ability to express the concept of cubing. One of the things we should demand from a powerful programming language is the ability to build abstractions by assigning names to common patterns and then to work in terms of the abstractions directly. Functions provide this ability. This is why all but the most primitive programming languages include mechanisms for defining functions.

Yet even in numerical processing we will be severely limited in our ability to create abstractions if we are restricted to functions whose parameters must be numbers. Often the same programming pattern will be used with a number of different functions. To express such patterns as concepts, we will need to construct functions that can accept functions as arguments or return functions as values. Functions that manipulate functions are called higher-order functions .

Functions as Arguments

Have a look at these two functions

(defn sum-integers [a b]
  "compute the sum of the integers from a through b"
  (if (> a b)
      0
      (+ a (sum-integers (inc a) b))))

(defn sum-cubes [a b]
  "compute the sum of the cubes of the integers from a through b"
  (if (> a b)
      0
      (+ (cube a)
         (sum-cubes (inc a) b))))

These functions clearly share a common underlying pattern. They are for the most part identical, differing only in the name of the function, the function of a used to compute the term to be added .

We could generate each of the functions by filling in slots in the same template:

(defn <name> [a b]
  (if (> a b)
      0
      (+ (<term> a)
         (<name> (inc a) b))))

We would like our language to be powerful enough so that we can write a function that expresses the concept of summation itself rather than only functions that compute particular sums. We can do so readily by taking the common template shown above and transforming the 'term' slot into a formal parameter:

(defn sum-terms [term a b]
  (if (> a b)
      0
      (+ (term a)
         (sum-terms term (inc a) b))))

Notice we cannot recur here as it is not in a tail position, trying to do so helpfully throws

java.lang.UnsupportedOperationException: Can only recur from tail position

So we can us this to find the sum of the the first 10 cubes

> (sum-terms cube 1 10)
3025

Or the numbers 1 to 10

> (sum-terms identity 1 10)
55

identity is a clojure built-in function that just returns whatever you pass it

At the REPL

You can ask at the repl for the docs of a function

> (doc identity)
-------------------------
clojure.core/identity
([x])
  Returns its argument.
  nil

Or look at it's source, this comes in very handy

> (source identity)
(defn identity
  "Returns its argument."
  {:added "1.0"
   :static true}
  [x] x)
nil

Anonymous Functions

Sometimes you only use a function once, and it is simple enough for it's purpose to be obvious without naming it, you can use an anonymous function

The function square from before can be created with

(fn [x]
  (* x x))

And can be called immediately

> ((fn [x] (* x x))
        2)
4

Clojure even has a shorter form implemented as a reader macro

#(* % %)

For example to sum the first 10 squares we can

> (sum-terms #(* % %) 1 10)
385

If an anonymous function has more than one argument, they can be referenced as %N for each variable, eg

> (#(str %2 " " %1)
        "arg1"
        "arg2")
"arg2 arg1"

Functions as Return Values

Take a look at this function

(defn adder [n]
  (fn [m]
    (+ m n)))

This function takes an argument n and returns a function (using our anonymous function syntax) that adds n to it's argument.

We can create a function add-2

> (def add-2 (adder 2))
#'user/add-2

> (add-2 11)
13

Functions as both arguments and return values

We can do things like create a function that takes a function and returns a function that calls it with it's arguments reversed

(defn flip [f]
  (fn [x y]
    (f y x)))

Exercises

Clojure built-ins

Take a look at juxt and complement, and try and create examples of their use.

Exercise 1.41:

Define a function double that takes a function of one argument as argument and returns a function that applies the original function twice. For example, if inc is a function that adds 1 to its argument, then (double inc) should be a function that adds 2. What value is returned by

(((double (double double)) inc) 5)

Exercise 1.42:

Let f and g be two one-argument functions.

The composition of f and g, denoted $ f \circ g $ is defined to be the function

$$ x \rightarrow f(g(x)) $$

Define a function compose that implements composition.

You should find that

> ((compose square inc) 6)
49

After you are done, take a peek at (source comp) to see how clojure does it in a variadic way

Exercise 1.43:

If f is a numerical function and n is a positive integer, then we can form the n^th repeated application of f , which is defined to be the function whose value at x is

$$ f (f (\dots (f (x )) \dots )) $$

For example, if f is the function $ x \rightarrow x + 1 $ then the n^th repeated application of f is the function $ x \rightarrow x+n $

If f is the operation of squaring a number, then the n^th repeated application of f is the function

$$ x \rightarrow x^{2^n} $$

Write a function that takes as inputs a function that computes f and a positive integer n and returns the function that computes the n^th repeated application of f . Your function should be able to be used as follows:

=> ((repeated square 2) 5)
625