The following is a way to get to the so called Y-combinator. It is a thought experiment assuming, that we have no `define`

form available and are trying to implement the function `length`

for lists without making use of `define`

. In the end a way will be found. This way is the Y-combinator, a function, which can turn a function *f* into a function *f-wrap*, which applies *f* again and again, as required by the nature of its input to recursively consume all of the input. Since no `define`

form is used anywhere to write the Y-combinator, the body of the Y-combinator cannot refer to any definitions, except for names of values in respective scopes. This property enables the Y-combinator to implement recursion in a programming language, which does not support recursion natively, as long as it has lambda expressions, function application and (not 100% sure it is required) lexical scope. If a language forbids calling a procedure from within itself, then the Y-combinator is still valid code, as it does not do so. It in turn can produce an *f-wrap*, which will apply an *f* over and over again, creating the same effect, as if *f* was recursive itself. To deny the use of the `define`

form actually is intentionally done in the book, because then only the Y-combinator or something with the properties of the Y-combinator can help us solve the problem.

On the way there, a few common refactoring steps or equivalent transformations for code are applied. Those are the following:

- inlining an implementation of a function where the call to it is made
- lambda wrapping of lambda expressions (explained when used)
- for pulling out parts of the code and making them arguments
- for delaying evaluation of expressions

Furthermore we make use of:

- immeditately invoked functions

Prerequisites contain code, which is needed to run examples, but is not given in the same chapter.

```
(define length
(lambda (lst)
(cond
[(null? lst) 0]
[else (+ (length (cdr lst)) 1)])))
```

```
(define eternity
(lambda (something)
(eternity something)))
```

```
<<length>>
<<eternity>>
```

The whole example works with the length function, so to start, here is the length function as usually defined for lists:

```
<<length>>
```

#

We can try it out:

```
<<length>>
(display (simple-format #f "~a\n" (length '(1 2 3 4 5 6))))
(display (simple-format #f "~a\n" (length '(1 2 3 4 5 (6)))))
```

6 6

There is a problem however. `length`

refers to itself in its definition. In a programming language, which does not support recursion, this would not be possible. If we do not make use of `define`

, then there is no way for length to directly refer to itself, as it is not bound to a name. So how could we write `length`

, without referring to itself?

`length-0`

To start figuring out the solution, we write `length-0`

, which calculates the length of the empty list, but does not return a value (gets stuck) for any list that contains elements:

```
<<eternity>>
(lambda (lst)
(cond
[(null? lst) 0]
[else (+ 1 (eternity (cdr lst)))]))
```

This does not recur on itself. It does not call itself in the body.

Using this as a starting point, we then try to get back our original `length`

functionality.

```
<<length-0>>
;; do not try for non-empty lists
;; (display
;; (simple-format
;; #f "~a\n"
;; ((lambda (lst)
;; (cond
;; [(null? lst) 0]
;; [else (+ 1 (eternity (cdr lst)))]))
;; '(1 2 3))))
(display
(simple-format
#f "~a\n"
((lambda (lst)
(cond
[(null? lst) 0]
[else (+ 1 (eternity (cdr lst)))]))
'())))
```

0

OK, this works for the empty list.

`length-0`

From `length-0`

, we can create a function for calculating the length of a list with 1 element or the empty list by replacing the `else`

branch with `length-0`

itself. As the case of the empty list is handled in the first branch, the else branch would then handle the case of the list having one element. This works because we give the `cdr`

of the list, which will be the empty list again, as an argument to the `length-0`

in the `else`

branch:

```
<<eternity>>
(lambda (lst)
(cond
[(null? lst) 0]
[else (+ 1
;; We insert length-0 here.
((lambda (lst)
(cond
[(null? lst) 0]
;; If there are more elements then 1, the function will still not return a value.
[else (+ 1 (eternity (cdr lst)))]))
;; length-0 will be applied to the cdr of the list
(cdr lst)))]))
```

Let's try it out:

```
<<eternity>>
;; do not try this
#;(display
(simple-format
#f "~a\n"
((lambda (lst)
(cond
[(null? lst) 0]
[else (+ 1
((lambda (lst)
(cond
[(null? lst) 0]
[else (+ 1 (eternity (cdr lst)))]))
(cdr lst)))]))
'(a b))))
(display
(simple-format
#f "~a\n"
((lambda (lst)
(cond
[(null? lst) 0]
[else (+ 1
((lambda (lst)
(cond
[(null? lst) 0]
[else (+ 1 (eternity (cdr lst)))]))
(cdr lst)))]))
'())))
(display
(simple-format
#f "~a\n"
((lambda (lst)
(cond
[(null? lst) 0]
[else (+ 1
((lambda (lst)
(cond
[(null? lst) 0]
[else (+ 1 (eternity (cdr lst)))]))
(cdr lst)))]))
'(a))))
```

0 1

Our function now works for the list lenghts 0 and 1. Great. We can continue nesting deeper, to get to any length we want. For example we can replace the call to `eternity`

again, in order to achieve a function, which can deal with lists up to length 2 as follows:

```
<<eternity>>
(lambda (lst)
(cond
[(null? lst) 0]
[else (+ 1
((lambda (lst)
(cond
[(null? lst) 0]
[else (+ 1
;; We insert length-0 here.
((lambda (lst)
(cond
[(null? lst) 0]
[else (+ 1 (eternity (cdr lst)))]))
(cdr lst)))]))
(cdr lst)))]))
```

And a little test:

```
<<eternity>>
(display
(simple-format
#f "~a\n"
((lambda (lst)
(cond
[(null? lst) 0]
[else (+ 1
((lambda (lst)
(cond
[(null? lst) 0]
[else (+ 1
((lambda (lst)
(cond
[(null? lst) 0]
[else (+ 1 (eternity (cdr lst)))]))
(cdr lst)))]))
(cdr lst)))]))
'(a b))))
```

2

Yep, it still works.

This way of proceeding by inlining `length-0`

over and over again, although working correctly, seems not practical at all. We cannot anticipate at all times, what length a list we have to deal with will have and in consequence cannot know how to write our `length`

function. Furthermore, this makes for very unreadable and very long code, only to have a function `length`

. Using this is not feasible.

We have to ask ourselves, how we could avoid having to inline the code of `length-0`

manually. This will involve multiple steps.

`length-0`

First, we can write a procedure, which creates `length-0`

for us:

```
<<eternity>>
((lambda (length)
(lambda (lst)
(cond
[(null? lst) 0]
[else (+ 1 (length (cdr lst)))])))
eternity)
```

All we did here is to wrap `length-0`

with a lambda and make that lambda take one argument, a procedure, which is used in place of the call to `eternity`

. To get back `length-0`

, we need to pass in `eternity`

, so that it gets back inside `length-0`

, where it will be called. (In foresight the argument is named `length`

, but it could really have any name.)

Let us call this equivalent transformation *lambda wrapping*. To generalize, it is always possible to wrap one lambda with another lambda this way, making one or more bindings come from the outer scope, where they are passed in, to get an equivalent lambda. This is formulated in the following code:

```
(λ (sth) (proc sth))
;; is equivalent to
((λ (arg)
(λ (sth) (arg sth)))
proc)
```

:9:0: In procedure module-lookup: Unbound variable: proc Entering a new prompt. Type `,bt' for a backtrace or `,q' to continue. scheme@(guile-user) [1]>

This is how we can create `length-0`

. Let us try to create `length-1`

and `length-2`

the same way and a pattern will emerge.

`length-1`

and `length-2`

Instead of giving the argument `eternity`

to the function, which creates `length-0`

, which will then be called in the `else`

branch, causing the produced `length-0`

to fail, if the list is not empty, we could give `length-0`

as an argument, so that we will have it called in the else branch. This in effect will create `length-1`

, as the function produced will only fail, when it enters the `else`

branch of the argument `length-0`

, as it has a call to `eternity`

there.

Let us see this in the following code.

`length-1`

This is the code before giving `length-0`

as an argument, still giving `eternity`

as an argument:

```
<<eternity>>
((lambda (length)
(lambda (lst)
(cond
[(null? lst) 0]
[else (+ 1 (length (cdr lst)))])))
;; notice how we give eternity as an argument to produce length-0
eternity)
```

Now we will replace `eternity`

by ~length-0~:

```
<<eternity>>
((lambda (length)
(lambda (lst)
(cond
[(null? lst) 0]
[else (+ 1 (length (cdr lst)))])))
;; Now we give length-0, as produced by the lambda expression.
((lambda (length)
(lambda (lst)
(cond
[(null? lst) 0]
[else (+ 1 (length (cdr lst)))])))
;; eternity will be given to create the argument length-0.
eternity))
```

Instead of giving `eternity`

immediately, `eternity`

is now given as an argument for creating `length-0`

, which in turn will be given as an argument, in order to create `length-1`

.

Notice, that we used the identifier `length`

in both lambda expressions. They are however different, separated by scope.

Let us try to use this `length-1`

function.

```
<<eternity>>
(display
(simple-format
#f "~a\n"
;; make length-1 and immediately apply it
(((lambda (length)
(lambda (lst)
(cond
[(null? lst) 0]
[else (+ 1 (length (cdr lst)))])))
;; Now we give length-0, as produced by the lambda expression.
((lambda (length)
(lambda (lst)
(cond
[(null? lst) 0]
[else (+ 1 (length (cdr lst)))])))
;; eternity will be given to create the argument length-0.
eternity))
'())))
(display
(simple-format
#f "~a\n"
;; make length-1 and immediately apply it
(((lambda (length)
(lambda (lst)
(cond
[(null? lst) 0]
[else (+ 1 (length (cdr lst)))])))
;; Now we give length-0, as produced by the lambda expression.
((lambda (length)
(lambda (lst)
(cond
[(null? lst) 0]
[else (+ 1 (length (cdr lst)))])))
;; eternity will be given to create the argument length-0.
eternity))
'(a))))
```

0 1

It gives the expected result.

`length-2`

Just like we created `length-1`

by giving an on-the-fly produced `length-0`

to the function which originally created `length-0`

, we create `length-2`

, by again replacing the call to `eternity`

, by another `length-0`

, increasing the possible iteration depth of the whole created function again by 1, as the `eternity`

call will happen only in the innermost function, which is produced by creating `length-0`

using `eternity`

.

```
<<eternity>>
((lambda (length)
(lambda (lst)
(cond
[(null? lst) 0]
[else (+ 1 (length (cdr lst)))])))
((lambda (length)
(lambda (lst)
(cond
[(null? lst) 0]
[else (+ 1 (length (cdr lst)))])))
;; Now we give length-0, as produced by the lambda expression.
((lambda (length)
(lambda (lst)
(cond
[(null? lst) 0]
[else (+ 1 (length (cdr lst)))])))
;; eternity will be given to create the argument length-0.
eternity)))
```

We delayed the call of `eternity`

even more, by replacing `eternity`

with another creation of `length-0`

, which in turn does the call to `eternity`

.

While the code is not indented as much any longer, there are still repetitions, which are needed for each depth of recursion, so the problem is not yet solved.

`length`

If we could give a name to the repeating part, we could shorten the code a lot. We cannot use `define`

to give a name, but what we *can* do is to *lambda wrap* the whole code and give the repeating part as an argument, enabling us to give it a name inside the wrap. We will call it `make-length`

inside the wrap.

For `length-0`

we can do it as follows:

```
<<eternity>>
;; The wrapping lambda internally applies the given argument (the repeating part) to eternity.
((lambda (make-length)
(make-length eternity))
;; The wrapping lambda is immediately applied to the repeating part,
(lambda (something)
(lambda (lst)
(cond
[(null? lst) 0]
;; Notice how the repeating part applies `something` to the cdr of the list. `something` will
;; be `eternity` in this case.
[else (+ 1 (something (cdr lst)))]))))
```

If this is still `length-0`

, we should be able to use it as such:

```
<<eternity>>
(display
(simple-format
#f "~a\n"
(((lambda (make-length)
(make-length eternity))
(lambda (something)
(lambda (lst)
(cond
[(null? lst) 0]
[else (+ 1 (something (cdr lst)))]))))
;; Apply it to the empty list.
'())))
```

0

As we can see, this still works.

Previously, we applied the repreating part to itself. We named it `make-length`

here, so we can implement `length-1`

and `length-2`

by applying `make-length`

to `make-length`

inside the wrap as follows:

```
<<eternity>>
((lambda (make-length)
(make-length
;; Apply make-length to make-length.
(make-length eternity)))
(lambda (something)
(lambda (lst)
(cond
[(null? lst) 0]
[else (+ 1 (something (cdr lst)))]))))
```

```
<<eternity>>
((lambda (make-length)
;; This is length-2.
(make-length
;; Apply make-length to make-length applied to make-length applied to eternity, which is length-1.
(make-length
;; Apply make-length to make-length applied to eternity, which is length-0.
(make-length eternity))))
(lambda (something)
(lambda (lst)
(cond
[(null? lst) 0]
[else (+ 1 (something (cdr lst)))]))))
```

Let us try `length-2`

defined like this:

```
<<eternity>>
(display
(simple-format
#f "~a\n"
(((lambda (make-length)
(make-length
(make-length
(make-length eternity))))
(lambda (something)
(lambda (lst)
(cond
[(null? lst) 0]
[else (+ 1 (something (cdr lst)))]))))
;; Apply it to the empty list.
'())))
(display
(simple-format
#f "~a\n"
(((lambda (make-length)
(make-length
(make-length
(make-length eternity))))
(lambda (something)
(lambda (lst)
(cond
[(null? lst) 0]
[else (+ 1 (something (cdr lst)))]))))
;; Apply it to the list with 1 element.
'(a))))
(display
(simple-format
#f "~a\n"
(((lambda (make-length)
(make-length
(make-length
(make-length eternity))))
(lambda (something)
(lambda (lst)
(cond
[(null? lst) 0]
[else (+ 1 (something (cdr lst)))]))))
;; Apply it to the list with 2 elements.
'(a b))))
```

0 1 2

It gives the correct results.

At this point it seems like recursion actually is a conditionally infinite tower of applications of a procedure. Notice the multiple nested applications of `make-length`

in the code above.

The problem is still, that the `make-length`

is repeated once per iteration though. We notice however, that we apply `eternity`

, when we do not have sufficient applications of the procedure any longer to process the list given. This means there will be no error, but also no result. Instead we will have infinite useless recursion going on. This is kind of like an error, even if no error or exception is raised. We will have to stop the recursion at some point to be able to do something more useful. However, this only happens in the bad case, where the list is too long to be processed by our number of applications of the procedure. This means, that we actually do not really care about how it goes wrong there. We do not ever want to get to the case, where we do not have sufficient applications. This means we could use any other procedure instead of `eternity`

. That would only change the error case. Let us try to raise an error, when the list has too many elements to process, by giving a lambda, which raises an error, instead of giving eternity:

```
(catch
'list-too-deep
;; thunk (procedure that takes 0 arguments) producing the exception
(lambda ()
(((lambda (make-length)
(make-length
(make-length
(make-length
;; here we use an error raising procedure instead of eternity
(lambda (rest-of-list)
(throw 'list-too-deep rest-of-list))))))
(lambda (something)
(lambda (lst)
(cond
[(null? lst) 0]
[else (+ 1 (something (cdr lst)))]))))
;; Apply it to the list with 3 (1 too many) elements.
'(a b c)))
;; handler
(lambda (key . args)
(display
(simple-format #f "~a args: ~a\n" "The list is too deep." args))))
```

(The above code uses GNU Guile Scheme speciifc exception handling.)

As we can see a useful error message is output, because that is the behavior in the bad case, that the list is too long.

The idea now is, that we can use the fact, that it does not matter which procedure we give as an argument. Instead of giving `eternity`

or a procedure for error handling, we can give a procedure, which in the bad case creates another application of `length-0`

, so that we never run out of applications of `length-0`

! We already know a procedure creating `length-0~: ~make-length`

applied to any procedure.

Here is how we are going to do it:

```
((lambda (make-length)
;; apply make-length to itself
(make-length make-length))
(lambda (proc)
(lambda (lst)
(cond
[(null? lst) 0]
[else
(+ 1
;; apply the given procedure (make-length in this case) to itself
((proc proc)
(cdr lst)))]))))
```

We apply `make-length`

to itself, in order to get another procedure, which we can use for the recursive call in the case, that the list has more elements. We already know, that `make-length`

will create another `length-0`

, which has had a bad `else`

case, which would have led to no result or an error. Previously we solved this issue in a bad way, by writing more and more calls to `make-length`

which we wrapped around an innermost `length-0`

, which made use of `eternity`

or raised an error. Now we produce an ad-hoc `length-0`

, only in case the list has more elements, to apply it to the rest of the list. It can in turn produce another `length-0`

, if it needs to do so. This way, the list can have arbitrary length and our `length`

function will still work.

We can demonstrate, that the above code works:

```
(display
(simple-format
#f "~a\n"
(((lambda (make-length)
(make-length make-length))
(lambda (proc)
(lambda (lst)
(cond
[(null? lst) 0]
[else
(+ 1
((proc proc)
(cdr lst)))]))))
'(a b c d))))
(display
(simple-format
#f "~a\n"
(((lambda (make-length)
(make-length make-length))
(lambda (proc)
(lambda (lst)
(cond
[(null? lst) 0]
[else
(+ 1
((proc proc)
(cdr lst)))]))))
'(a b c d e f g h))))
```

4 8

This is an implementation of `length`

, without using its name anywhere.

What happened here is actually the following: We could not use the name `length`

anywhere in the definition, because we cannot use any `define`

form and furthermore we want to get to some other construct, which can implement recursion in programming languages, which do not support calling a procedure within its own body. What we did instead is to have the name in another scope, another lambda receiving the logic of `length`

as an argument, to give a name to this argument. That argument `make-length`

is the logic of `length`

, but with one difference. It takes a procedure too (`proc`

) and gives it a name (`proc`

), so that it can call that procedure wih the same procedure `proc`

as an argument. The procedure `proc`

however, is nothing else than what the other lambda gives as an argument, which in turn is the logic of `length`

again. This way the recursive call does not need a binding defined using a `define`

form and can work completely anonymously.

Another way to describe it is the following: `make-length`

gets a procedure `proc`

as argument, only to be able to have it named inside the inner lambda expression. This way the inner lambda expression can make use of the given procedure. The given procedure then is `make-length`

itself, given by the sibling lambda expression, which will allow creating ad-hoc procedures, lambdas, which to use in case there are more elements in the list. All of the parts are necessary:

- application of
`make-length`

to itself:

#+NAME: length-anonymous-parts-1 #+BEGIN_SRC scheme :noweb no :results output :exports code :eval never-export ((lambda (make-length) (make-length make-length)) ...) #+END_SRC

The application to itself is only possible by wrapping with a lambda, to give an argument a name `make-length`

.

`make-length`

, taking a procedure as an argument:

#+NAME: length-anonymous-parts-2 #+BEGIN_SRC scheme :noweb no :results output :exports code :eval never-export (... (lambda (proc) (lambda (lst) (cond [(null? lst) 0] [else (+ 1 ((proc proc) (cdr lst)))])))) #+END_SRC

This contains the logic of `length`

in it, as well as the production of new lambdas in the `else`

branch.

- The outer application of the 1. part to the 2. part:

#+NAME: length-anonymous-parts-3 #+BEGIN_SRC scheme :noweb no :results output :exports code :eval never-export (... ...) #+END_SRC

This part is necessary for actually creating the function `length`

by application of the 1. part to the 2. part.

After the function `length`

is made, `length`

can be applied to any list.

Now that `length`

has been implemented, we would like to have the whole concept of how that was done generalized, so that we can use it for any procedure. In order to achieve that, one last problem needs to be addressed. In order to use the concept for any procedure, we need to be able to give any procedure as an argument at some point. Currently however, the logic of `length`

is somewhere inside and not given as a parameter.

To get to a version, where we give the logic of `length`

as an argument let us look at the current definition again:

```
((lambda (make-length)
(make-length make-length))
;; lambda wrapping around the logic of length -- make-length
(lambda (proc)
(lambda (lst)
(cond
[(null? lst) 0]
[else
(+ 1
;; usage of proc, argument to outer lambda
((proc proc)
(cdr lst)))]))))
```

As we can see, the logic of `length`

is wrapped in something we called `make-length`

before. Inside the logic of `length`

the argument `proc`

is used, so the logic depends on the wrapper. If we managed to pull out the usage of `proc`

, the logic of `length`

would not depend on the wrap any longer. Then it can be imagined, that we could even give this logic as argument, in effect giving `length`

as argument, allowing us to give any other procedure as well. So let us try to pull it out.

First we can try to naively pull it out by *lambda wrapping* as follows:

```
((lambda (make-length)
(make-length make-length))
(lambda (proc)
;; We need acces to the given procedure proc, so the lambda wrapping needs to
;; be inside the wrapper. We name the argument length, because it is really
;; the simple definition of length, with an external binding of length by a
;; wrapping lambda expression now.
(lambda (length)
(lambda (lst)
(cond
[(null? lst) 0]
[else
(+ 1
;; usage of length
(length (cdr lst)))]))
;; Here we produce the lambdas for usage in the else branch of length ...
(proc proc))))
```

However, there is a problem with this code. It does not work. While previously the application of `proc`

to `proc`

was inside the `else`

branch and only evaluated, when that branch was entered. Now however, it is evaluated when the call `(make-length make-length)`

is made. That means in order to evaluate the whole thing, one needs to know what `(proc proc)`

is. But `proc`

is the argument given to `make-length`

, which is the same lambda expression, for whose evaluation we need to know what `(proc proc)`

is. This will result in an endless expansion of code.

Previously, the call `(proc proc)`

was inside the `else`

branch. Evaluating it would still need to know what `(proc proc)`

is and evaluate it. However, since in the evaluation of a `(proc proc)`

is inside the `else`

branch and in its evaluation the `proc`

appears again in the `else`

branch, it would not get evaluated over and over again. The code in an `else`

branch of `cond`

is only evaluated, when `else`

is the case that is entered. This is because `cond`

is a macro, not a procedure! This is what actually prevents endless code execution.

What can be done about this? We cannot put the call back into the `else`

branch again, as we wanted to extract it. Instead, we need make use of *delayed evaluation* of the application of `proc`

to itself to delay creating endless expansion of expressions, until the `else`

branch is entered. Delayed evaluation of the application of `proc`

to itself can be done using *lambda wrapping* again. Note, that `length`

in the `else`

branch takes 1 argument, which is the rest of the list. The delayed evaluation thus done as follows:

```
((lambda (make-length)
(make-length make-length))
(lambda (proc)
((lambda (length)
(lambda (lst)
(cond
[(null? lst) 0]
[else
;; usage of length, just like before, using 2 argument
(+ 1 (length (cdr lst)))])))
;; lambda wrapping -- delayed evaluation of (proc proc)
(lambda (rest-of-list)
;; (proc proc) is not evaluated, until the wrapping lambda is called
((proc proc) rest-of-list)))))
```

Let us try to use it:

```
(display
(simple-format
#f "~a\n"
(((lambda (make-length)
(make-length make-length))
(lambda (proc)
((lambda (length)
(lambda (lst)
(cond
[(null? lst) 0]
[else
;; usage of length, just like before, using 2 argument
(+ 1 (length (cdr lst)))])))
;; lambda wrapping -- delayed evaluation of (proc proc)
(lambda (rest-of-list)
;; (proc proc) is not evaluated, until the wrapping lambda is called
((proc proc) rest-of-list)))))
;; apply to a list of 3 elements
'(a b c))))
(display
(simple-format
#f "~a\n"
(((lambda (make-length)
(make-length make-length))
(lambda (proc)
((lambda (length)
(lambda (lst)
(cond
[(null? lst) 0]
[else
;; usage of length, just like before, using 2 argument
(+ 1 (length (cdr lst)))])))
;; lambda wrapping -- delayed evaluation of (proc proc)
(lambda (rest-of-list)
;; (proc proc) is not evaluated, until the wrapping lambda is called
((proc proc) rest-of-list)))))
;; apply to a list of more elements
'(a b c d e f))))
```

3 6

That is the correct and expected result.

We have managed to pull the call of `proc`

to itself out of the `length`

logic. Now we can extract that as well, as it does not depend on the wrapping lambda expression, which we call `make-length`

any longer. Let us do that, in order to make this part interchangable with other procedures. To be clear about what shall be pulled out, here is the part of the code:

```
(lambda (length)
(lambda (lst)
(cond
[(null? lst) 0]
[else
(+ 1 (length (cdr lst)))])))
```

We want to give this part of the code as an argument to the other part of the code, so that it can come from the outside. This means, that we need to wrap the other part of the code on the outermost level as follows:

```
;; Here is the wrapping lambda expression at the outermost level.
((lambda (extracted-proc)
((lambda (make-length)
(make-length make-length))
(lambda (proc)
(extracted-proc
;; Here is the lambda that shall be applied to the rest of the list.
(lambda (rest-of-list)
((proc proc) rest-of-list))))))
;; Here is the extracted logic of length. As an argument it requires the
;; lambda that shall be applied to the rest of the list.
(lambda (length)
(lambda (lst)
(cond
[(null? lst) 0]
[else
(+ 1 (length (cdr lst)))]))))
```

Let us test this code again with a few examples:

```
(display
(simple-format
#f "~a\n"
(((lambda (extracted-proc)
((lambda (make-length)
(make-length make-length))
(lambda (proc)
(extracted-proc
(lambda (rest-of-list)
((proc proc) rest-of-list))))))
(lambda (length)
(lambda (lst)
(cond
[(null? lst) 0]
[else
(+ 1 (length (cdr lst)))]))))
;; apply to a list of 3 elements
'(a b c))))
(display
(simple-format
#f "~a\n"
(((lambda (extracted-proc)
((lambda (make-length)
(make-length make-length))
(lambda (proc)
(extracted-proc
(lambda (rest-of-list)
((proc proc) rest-of-list))))))
(lambda (length)
(lambda (lst)
(cond
[(null? lst) 0]
[else
(+ 1 (length (cdr lst)))]))))
;; apply to a list of more elements
'(a b c d e f))))
```

3 6

Still working.

If we go back to the first formulation of `make-length`

, which is able to create `length-0`

, we will see, that this is exactly, what we extracted.

We can now go ahead and give other procedures as arguments. For example we can give a procedure, which sums up all the numbers in a simple, not nested list as follows:

```
((lambda (extracted-proc)
((lambda (make-length)
(make-length make-length))
(lambda (proc)
(extracted-proc
(lambda (rest-of-list)
((proc proc) rest-of-list))))))
;; the procedure make-sum
(lambda (sum)
(lambda (lst)
(cond
[(null? lst) 0]
[else
(+ (car lst)
(sum (cdr lst)))]))))
```

Let us check, whether that works:

```
(display
(simple-format
#f "~a\n"
(((lambda (extracted-proc)
((lambda (make-length)
(make-length make-length))
(lambda (proc)
(extracted-proc
(lambda (rest-of-list)
((proc proc) rest-of-list))))))
;; the procedure make-sum
(lambda (sum)
(lambda (lst)
(cond
[(null? lst) 0]
[else
(+ (car lst)
(sum (cdr lst)))]))))
'(1 2 3))))
```

6

Yes, we got the correct result! Let us make one for nested lists containing numbers:

```
(display
(simple-format
#f "~a\n"
(((lambda (extracted-proc)
((lambda (make-length)
(make-length make-length))
(lambda (proc)
(extracted-proc
(lambda (rest-of-list)
((proc proc) rest-of-list))))))
;; the procedure make-sum
(lambda (sum)
(lambda (lst)
(cond
[(null? lst) 0]
[(pair? (car lst))
(+ (sum (car lst))
(sum (cdr lst)))]
[else
(+ (car lst)
(sum (cdr lst)))]))))
'(1 2 (3 4 5) 6))))
```

21

The result is correct as well. We see, that we can define procedures for arbitrarily structured lists or other data structures, if we create the procedures accordingly and use them like this.

There is a question however. What is this other part of the code, which we do not change, when we adapt the lambda expression for length of a list or sum of all numbers in a list? This part seems to do all the magic, that allows us to write `length`

, `sum`

and `sum*`

without creating a binding using a `define`

form. It seems special, so let us write it down:

```
(lambda (extracted-proc)
((lambda (make-length)
(make-length make-length))
(lambda (proc)
(extracted-proc
(lambda (rest-of-list)
((proc proc) rest-of-list))))))
```

This is the so called Y-combinator!

In topic specific literature, the arguments in the lambda expressions of the Y-combinator are usually named differently. In order to get the same naming let us consider a few things:

- The argument
`proc`

can actually be called`make-length`

, because it only ever will be`make-length`

, as that lambda expression it is called as follows:`(make-length make-length)`

. So let us write down a changed version:

#+NAME: y-combinator-other-names-2 #+BEGIN_SRC scheme :noweb no :results output :exports code :eval never-export (lambda (extracted-proc) ((lambda (make-length) (make-length make-length)) (lambda (make-length) (extracted-proc (lambda (rest-of-list) ((make-length make-length) rest-of-list)))))) #+END_SRC

- As we may work with other data structures than lists and accordingly adapted procedures we give to the Y-combinator, let us not use
`rest-of-list`

any longer as an argument name and instead use`x`

, because it can really be anything:

#+NAME: y-combinator-other-names-3 #+BEGIN_SRC scheme :noweb no :results output :exports code :eval never-export (lambda (extracted-proc) ((lambda (make-length) (make-length make-length)) (lambda (make-length) (extracted-proc (lambda (x) ((make-length make-length) x)))))) #+END_SRC

- The argument name
`extracted-proc`

does not help, when seeing the Y-combinator in this form, as it is not clear, what the procedure given was extracted from. We might as well simply name it`proc`

only:

#+NAME: y-combinator-other-names-4 #+BEGIN_SRC scheme :noweb no :results output :exports code :eval never-export (lambda (proc) ((lambda (make-length) (make-length make-length)) (lambda (make-length) (proc (lambda (x) ((make-length make-length) x)))))) #+END_SRC

- Lastly, the name
`make-length`

is no longer appropriate, since we can make all kinds of recursive procedures, not only`length`

, using the Y-combinator. So let us name it`f`

, as it can be any recursive procedure or function:

#+NAME: y-combinator-other-names-5 #+BEGIN_SRC scheme :noweb no :results output :exports code :eval never-export (lambda (proc) ((lambda (f) (f f)) (lambda (f) (proc (lambda (x) ((f f) x)))))) #+END_SRC

Or with different line-breaking:

#+NAME: y-combinator #+BEGIN_SRC scheme :noweb no :results output :exports code :eval never-export (lambda (proc) ((lambda (f) (f f)) (lambda (f) (proc (lambda (x) ((f f) x)))))) #+END_SRC

To be precise, literature calls this form of the Y-combinator the *applicative-order Y-combinator*.

Let us see it in action one more time using a standard example:

```
(display
(simple-format
#f "Fibonacci of 10: ~a\n"
(((lambda (proc)
((lambda (f) (f f))
(lambda (f)
(proc
(lambda (x) ((f f) x))))))
(lambda (fibonacci)
(lambda (num)
(cond
[(<= num 2) 1]
[else
(+ (fibonacci (- num 1))
(fibonacci (- num 2)))]))))
10)))
```

Fibonacci of 10: 55

One can see, this also works on numbers. Basically it works on any data structure and how it works with a data structure depends only on the implementation of the procedure, which we give to the Y-combinator.

Without the help of the book "The Little Schemer", I would most likely not have been able to derive the Y-combinator on my own. I had to think long and hard about some of the steps, why one would perform the equivalent transformations and how to describe these steps, so that there is more description than in the book. The book however, with its rather rare way of asking questions, making me think about the content a lot, helped me being able to write about the Y-combinator and how it can be derived.

I encourage everyone, who is a software developer to read "The Little Schemer". It can be an enormously insightful and enlightening read. It may take a lot of time to work through it and understand all or at least most of the content, but you really owe it to your computer science education.

https://orgmode.org/manual/Exporting-code-blocks.html https://orgmode.org/manual/Comment-lines.html#Comment-lines https://orgmode.org/manual/Export-settings.html https://emacsclub.github.io/html/org_tutorial.html