code.org 42 KB

Y-combinator

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:

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

Furthermore we make use of:

  1. immeditately invoked functions

Prerequisites

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>>

Code

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?

Writing 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.

Endless inlining of 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.

Creating 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.

Creating 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.

Creating 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.

Creating 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.

Refactoring out the repeating part - making 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:

  1. 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.

  1. 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.

  1. 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.

Making all kinds of recursive procedures

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.

Separating the Y-combinator

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!

Renaming arguments

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:

  1. 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

  1. 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

  1. 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

  1. 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.

Final words

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.

Org-mode help notexported

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