Self-application

Now that we have discovered that functions may have functions as arguments we are tempted to ask whether a function could take itself as an argument. Some functions certainly can: the identity function, fn x => x could be applied to itself. The application would be written as (fn x => x) (fn x => x) and would evaluate to fn x => x.

However, this mild example does not convey the difficulty inherent in the notion of a function which may be applied to itself. Consider the following example due to Joseph Stoy [Sto82]. First define the function a as shown below:

a (b, x)   =

1		if x = 0
x × b (b, x - 1)		otherwise

(2)

Now we may define the factorial function through reference to the function a.

fac (y) = a(a, y)

Notice that neither the function fac nor the function a are defined through recursion, even indirectly. The ability to pass the function a to itself as a parameter has allowed us to define the factorial function by a circuitous route which does not involve any recursion. Self-applying functions are difficult to comprehend and it is perhaps reassuring to know that Standard ML does not allow us to define functions such as the function a above.