Anonymous recursion

From Wikipedia, the free encyclopedia

In computer science, anonymous recursion is a recursion technique that uses anonymous functions.

Contents

[edit] Construction

Suppose that f is an n-argument recursive function defined in terms of itself:

f(x_1, x_2, \dots, x_n) := \mbox{expression in terms of } x_1, x_2, \dots, x_n \mbox{ and } f(\dots).

We want to define an equivalent recursive anonymous function f * which is not defined in terms of itself. One possible procedure is the following:

  1. Define a (n + 1)-argument function h like f, except that h takes one extra argument, which is the function f itself. (Function h inherits its first n arguments from f.)
  2. Change f, the last argument of h, from an n-argument function to an (n + 1)-argument function by feeding f to itself as f′s last argument for all instances of f within the definition of h. (This puts function h and its last argument f on an equal footing.) The functions f and h are now defined by
    f(x_1, x_2, \dots, x_n, f) := \mbox{expression in terms of } x_1, x_2, \dots, x_n \mbox{ and } f(\dots,f).
    h(x_1, x_2, \dots, x_n, f) := \mbox{expression in terms of } x_1, x_2, \dots, x_n \mbox{ and } f(\dots,f).
  3. Pass on h to itself as h's own last argument, and let this be the definition of the desired n-argument recursive anonymous function f * :
    f^* (x_1, x_2, \dots, x_n) := h(x_1, x_2, \dots , x_n, h) \

[edit] Example

Given

f(x):= \begin{cases} 1 & \mbox{if} \ x = 0 \\ x \cdot f(x - 1) & \mbox{otherwise} \end{cases}

The function f is defined in terms of itself: such circular definitions are not allowed in anonymous recursion (because functions are not bound to labels). To start with a solution, define a function h(x,f) in exactly the same way that f(x) was defined above:

h(x,f) := \begin{cases} 1 & \mbox{if} \ x = 0 \\ x \cdot f(x - 1) & \mbox{otherwise} \end{cases}

Second step: change f(x − 1) in the definition to f(x − 1,f):

h(x,f):=\begin{cases} 1 & \mbox{if} \ x = 0 \\ x \cdot f(x-1, f) & \mbox{otherwise} \end{cases}

so that the function f passed on to h will have the same number of arguments as h itself.

Third step: the factorial function f * of x can now be defined as:

f^*(x) := h(x, h). \,

[edit] Relation to the use of the Y combinator

The above approach to constructing anonymous recursion differs, but is related to, the use of fixed point combinators. To see how they are related, perform a variation of the above steps. Starting from the recursive definition (using the language of lambda calculus):

\bar f := (\lambda n. \, \mbox{if}(n = 0, 1, n \cdot \bar f (n - 1))).

First step,

\bar h:= (\lambda f. \lambda n. \, \mbox{if} (n = 0, 1, n \cdot f (n - 1))).

Second step,

\bar g:= (\lambda g. \lambda n. \ \mbox{if} (n = 0, 1, n \cdot g (g) (n-1)))

where g (g) (n - 1) \equiv g (g, n - 1) . Note that the variation consists of defining \bar g in terms of g(g,n − 1) instead of in terms of g(n − 1,g).

Third step: let a "Z combinator" be defined by

Z:= (\lambda g. \ (g \ g))

such that

\bar f^* := Z \bar g.

Here, \bar g is passed to itself right before a number is fed to it, so \bar f^* n \equiv n! for any Church number n.

Note that g \ (g) \ n \equiv (g \ (g)) \ n \equiv (g \ g) \ n, i.e. g (g) \equiv (g g).

Now an extra fourth step: notice that

\bar g \equiv (\lambda g. \ \bar h \ (g \ g))

(see first and second steps) so that

\bar f^* \equiv (\lambda. \, g \ (g \ g)) (\lambda g. \, \bar h\ (g \ g))
\equiv (\lambda h. \, (\lambda g.\, (g \ g)) (\lambda g.\, h \ (g \ g))) \ \bar h.

Let the Y combinator be defined by

Y:= (\lambda h. \, (\lambda g.\, h \ (g \ g)) (\lambda g.\, h \ (g \ g)))

so that

Z \bar g \equiv Y \bar h.

[edit] External links