But functions like the Ackermann function require us to develop a more general technique for doing recursion --- and having developed it, it will often be easier to use it even in the cases where, in principle, we didn't have to.
+The example used to illustrate this in Chapter 9 of *The Little Schemer* is a function `looking` where:
+
+ (looking '(6 2 4 caviar 5 7 3))
+
+returns `#t`, because if we follow the path from the head of the list argument, `6`, to the sixth element of the list, `7` (the authors of that book count positions starting from 1, though generally Scheme follows the convention of counting positions starting from 0), and then proceed to the seventh element of the list, `3`, and then proceed to the third element of the list, `4`, and the proceed to the fourth element of the list, we find the `'caviar` we are looking for. On other hand, if we say:
+
+ (looking '(6 2 grits caviar 5 7 3))
+
+our path will take us from `6` to `7` to `3` to `grits`, which is not a number but not the `'caviar` we were looking for either. So this returns `#f`. It would be very difficult to define these functions without recourse to something like `letrec` or `define`, or the techniques developed below (and also in that chapter of *The Little Schemer*).
+
+
## Using fixed-point combinators to define recursive functions ##
### Fixed points ###
symbol `LENGTH`. Technically, it has the status of an unbound
variable.
+<a id=little-h></a>
Imagine now binding the mysterious variable, and calling the resulting
term `h`:
Φ[...LENGTH...]
-where that whole formula is convertible with the term LENGTH itself. In other words, the term `Φ[...LENGTH...]` contains (a term that convertible with) itself --- despite being only finitely long. (If it had to contain a term *syntactically identical to* itself, this could not be achieved.)
+where that whole formula is convertible with the term `LENGTH` itself. In other words, the term `Φ[...LENGTH...]` contains (a term that convertible with) itself --- despite being only finitely long. (If it had to contain a term *syntactically identical to* itself, this could not be achieved.)
The key to achieving all this is finding a fixed point for `h`. The strategy we will present will turn out to be a general way of
finding a fixed point for any lambda term.
h h <~~> \xs. (empty? xs) 0 (succ (h (tail xs)))
-The problem is that in the subexpression `h (tail list)`, we've
+The problem is that in the subexpression `h (tail xs)`, we've
applied `h` to a list, but `h` expects as its first argument the
length function.
Shifting to `H` is the key creative step. Instead of applying `u` to a list, as happened
when we self-applied `h`, `H` applies its argument `u` first to *itself*: `u u`.
-After `u` gets an argument, the *result* is ready to apply to a list, so we've solved the problem noted above with `h (tail list)`.
+After `u` gets an argument, the *result* is ready to apply to a list, so we've solved the problem noted above with `h (tail xs)`.
We're not done yet, of course; we don't yet know what argument `u` to give
to `H` that will behave in the desired way.
BODY M <~~>
...
-You've written an infinite loop!
+You've written an infinite loop! (This is like the function `eternity` in Chapter 9 of *The Little Schemer*.)
However, when we evaluate the application of our:
sink true true false <~~> I
sink true true true false <~~> I
-Evidently, then, `sink true <~~> sink`. So we want `sink` to be the fixed point
+To get this behavior, we want `sink` to be the fixed point
of `\sink. \b. b sink I`. That is, `sink ≡ Y (\sb.bsI)`:
1. sink false