August 26, 2018

Y Combinator

The Y combinator is a higher-order function which takes a single argument, which is a function that isn't recursive and returns a version of the same function which is recursive.

If that is not enough to blow your mind, please: What do you think recursion is?

More generally, Y gives us a way to get recursion in a programming language that supports first-class functions but that doesn't have recursion built in.

   

Introduction

    recursion

   

This post will be a comprehensive walk through the Chapter 9 of the Little Schemer. The idea is to reproduce the discussion about recursive functions and move straight to the Y combinator definition. I will be using Clojure and borrowing some explanations from this amazing article.

   

Part 1: Partial Functions and Unnatural Recursion

Partial functions have this strange property of being correct for some input values and to have no guarantee that it will produce the correct answer to other values.

For example the looking function below:

(defn looking [a lat]
  (keep-looking a (first lat) lat))

(defn keep-looking [val index coll]
  (let [new-val (get coll (- index 1))]
    (cond
      (= new-val val)
      true
      (not (integer? new-val))
      false
      :else
      (keep-looking val new-val coll))))

Give it a :keyword and a collection. The looking function will get the first element of the collection and verify if it is equal to the :keyword I passed. If true, returns true.

If false, use the first element of the collection to perform an index lookup.

For example:

(def lat [6 2 4 :caviar 5 7 3])
(looking :caviar lat)
=> true

The path:

6th index --> 7th index --> 3rd index --> 4th index (which is my keyword)

However the following example do not have an answer:

(def lat3 [7 1 2 :caviar 5 6 3])
(looking :caviar lat3)

The path:

7th index --> 3rd index --> 2nd index --> 1st index --> 7th index ---> ...

There are many functions that present this behavior. We are going to use this kind of functions to develop the idea of the Y combinator below. Why? They appear when you have the huge constrain to not define anything.

Think about it, if you understand recursion as the technique of defining some function f in terms of itself. Then, if you can't define the name of the function in your programming language, it will be ""impossible"" to write a recursive call, right?

   

Part 2: Let's get into it!

We are going to use the length function below in order to build our way through the Y Combinator function.

(defn length [coll]
  (if (empty? coll)
    0
    (inc (length (rest coll)))))

However, without the define constructor we can't write the name length inside the body of the function because there is no way to refer to the name of this function, it will be written as an anonymous function.

(fn [coll]
  (if (empty? coll)
    0
    (inc (????? (rest coll)))))

We still cannot write a better function to replace ?????, however the function above is all useless? Actually, not.

The following call will produce the correct value:

((fn [coll]
    (if (empty? coll)
      0
      (inc (??? (rest coll))))) ()) ; call with the empty list
;; => 0

IF we could define the function above, we could called it length-0 because it correctly returns the length of the empty list. However, is also possible to use this new length-0 function to write a new version which returns the correct answer to a list with only one element.

(def length-0
  (fn [coll]
    (if (empty? coll)
      0
      (inc (????? (rest coll))))))

((fn [coll]
   (if (empty? coll)
     0
     (inc (length-0 (rest coll))))) (list :A))
;; => 1

But, let's pretend we can't use define here, so the last function will become (I am only doing a substitution of the length-0 function):

(fn [coll]
  (if (empty? coll)
    0
    (inc ((fn [coll]
            (if (empty? coll)
              0
              (inc (????? (rest coll)))))
          (rest coll)))))

Ok, let's pay attention to the function above.

It cannot only answer correctly the length of a list with a single item, it can answer correctly when the input is a list UP to 1 element, therefore the empty list will also return the correct value.

Now, let's take another step on that direction, let's build the function that will return correctly when the input is UP to 2 elements:

(fn [coll]
  (if (empty? coll)
    0
    (inc ((fn [coll]
            (if (empty? coll)
              0
              (inc ((fn [coll]
                      (if (empty? coll)
                        0
                        (inc (????? (rest coll)))))
                    (rest coll)))))
          (rest coll)))))

UP to 3 elements:

(fn [coll]
  (if (empty? coll)
    0
    (inc ((fn [coll]
            (if (empty? coll)
              0
              (inc ((fn [coll]
                      (if (empty? coll)
                        0
                        (inc ((fn [coll]
                                (if (empty? coll)
                                  0
                                  (inc (????? (rest coll)))))
                              (rest coll)))))
                    (rest coll))))) (rest coll)))))

UP to 4 elements:

(fn [coll]
  (if (empty? coll)
    0
    (inc ((fn [coll]
            (if (empty? coll)
              0
              (inc ((fn [coll]
                      (if (empty? coll)
                        0
                        (inc ((fn [coll]
                                (if (empty? coll)
                                  0
                                  (inc ((fn [coll]
                                          (if (empty? coll)
                                            0
                                            (inc (????? (rest coll)))))
                                        (rest coll)))))
                              (rest coll)))))
                    (rest coll)))))
          (rest coll)))))

And now, Friedman asks you:

Now, what do you think recursion is?

and that is a tough question.

Looks like if you pile a lot of "incomplete" functions that for some primitive values it returns the correct answer, we can get along just fine.

Following this example, it looks like we could compute the length of any list if we knew beforehand the size of the list and we could pile the exact amount of incomplete functions ahead of time.

Crazy.. if you knew the size, you could pile the exact same amount of stacks to compute the size recursively. How nice is that... o.O

Let's organize the code above and abstract the ????? function from the implementation.

((fn [func-length]
   (fn [coll]
     (if (empty? coll)
       0
       (inc (func-length (rest coll))))))
 ?????)

Ok, the function above is important...It is another version of the length-0 function. The only difference here is that: as I don't know the function ?????, it could be "anything", so I will abstract that out of my main function and receive it as an argument

Something like this:

(main-function ?????) ;; got it?

Ok, the new versions of the length up to 2 and 3 elements will be:

;; length-1
((fn [func-length]
   (fn [coll]
     (if (empty? coll)
       0
       (inc (func-length (rest coll))))))


 ((fn [func2-length]
    (fn [coll]
      (if (empty? coll)
        0
        (inc (func2-length (rest coll))))))
   ?????))


;; length-2
((fn [func-length]
   (fn [coll]
     (if (empty? coll)
       0
       (inc (func-length (rest coll))))))


 ((fn [func2-length]
    (fn [coll]
      (if (empty? coll)
        0
        (inc (func2-length (rest coll))))))


  ((fn [func3-length]
     (fn [coll]
       (if (empty? coll)
         0
         (inc (func3-length (rest coll))))))
   ?????)))


;; length-3
((fn [func-length]
   (fn [coll]
     (if (empty? coll)
       0
       (inc (func-length (rest coll))))))


 ((fn [func2-length]
    (fn [coll]
      (if (empty? coll)
        0
        (inc (func2-length (rest coll))))))


  ((fn [func3-length]
     (fn [coll]
       (if (empty? coll)
         0
         (inc (func3-length (rest coll))))))

   ((fn [func4-length]
      (fn [coll]
        (if (empty? coll)
          0
          (inc (func4-length (rest coll))))))
    ?????))))

Let's try to remove all the repetition above, let's rewrite the length-0:

((fn [mk-length]
   (mk-length ?????))
 (fn [length]
   (fn [coll]
     (if (empty? coll)
       0
       (inc (length (rest coll)))))))

Let's follow the calls of the function above in order to see how it works to compute the length of the EMPTY list.

;;; the first parenthesis has 2 main blocks:
;; the function - Let's call it func0
(fn [mk-length]
  (mk-length ?????))

;; and the argument. Let's call it arg0
(fn [length]
  (fn [coll]
    (if (empty? coll)
      0
      (inc (length (rest coll))))))

;;; so the first call will be (func0 arg0)

;;; ok, now he will have the second level of calls

;; (arg0 ?????)
;; however, this level expand to another function like:
(fn [coll]
  (if (empty? coll)
    0
    (inc (????? (rest coll)))))

;; behold.. this is our first version of `length-0`

Ok, take some time to process this new notation. It only gets worse.

Now, how can we write the length-1 and length-2 using the concise definition above?

;; length-1
(
 ;; func
 (fn [mk-length]
    (mk-length
     (mk-length ?????)))

 ;; arg
 (fn [length]
   (fn [coll]
     (if (empty? coll)
       0
       (inc (length (rest coll))))))
 )


;; length-2
(
 ;; func
 (fn [mk-length]
   (mk-length
    (mk-length
     (mk-length ?????))))

 ;; arg
 (fn [length]
   (fn [coll]
     (if (empty? coll)
       0
       (inc (length (rest coll))))))
 )

Wait a second... what just happened? It looks like the amount of levels we need to build DOES NOT DEPEND OF THE TASK AT HAND. WoW.. we factor out the length-specific portion of the code and we started to pile up some sort of stack of incomplete calls.

Up to this point, everything was fine. Now, the magic starts to kick-in. The problem at hand is that we don't know beforehand how many calls of mk-length we will need to do when we receive any list to perform the length operation.

If we choose a lower number of mk-length to perform the length task, we will receive an error because it will try to call the ????? function by passing the argument (rest coll) but ????? does not exist. ... Friedman suggests... let's substitute the function ????? for another call of mk-length... :X.... :X ... afterwards mk-length creates another "stack of calls" to enable us to compute one extra element in the list.

Ok...

...

Now, the length-0 will become:

((fn [mk-length]
   (mk-length mk-length))

 (fn [length]
   (fn [coll]
     (if (empty? coll)
       0
       (inc (length (rest coll)))))))

So, if we apply mk-length one time, we will have length-1:

((fn [mk-length]
   (mk-length mk-length))

 (fn [mk-length]
   (fn [coll]
     (if (empty? coll)
       0
       (inc ((mk-length ?????)
             (rest coll))))))
 )

The above code is working equivalently to length-1, but it will failed for a list with 2 elements. However, let's get wild. keep passing mk-length to itself..., you will create as many frames as you need...

(
;;; func0
(fn [mk-length]
     (mk-length mk-length))

;;; arg0
   (fn [mk-length]
     (fn [coll]
       (if (empty? coll)
         0
         (inc ((mk-length mk-length)
               (rest coll))))))
   )

Are you kidding me... there is a problem though. The second function, arg0 in the comments above, does not remember the function that actually computes the length operation as we started.

So, let's get rid of the (mk-length mk-length) call in there. Just add another layer of function call and abstract that away.

((fn [mk-length]
     (mk-length mk-length))
 (fn [mk-length]
   ((fn [length]
       (fn [coll]
         (if (empty? coll)
           0
           (inc (length (rest coll))))))
    (mk-length mk-length))))

However, if you run the code above.. it will give you an StackOverflow Error because you are applying mk-length to itself indefinitely. What you need to do is a "lazy" call, only call it when needed. So you must wrap it under another function call layer.

((fn [mk-length]
     (mk-length mk-length))
 (fn [mk-length]
   ((fn [length]
       (fn [coll]
         (if (empty? coll)
           0
           (inc (length (rest coll))))))
    (fn [x]
      ((mk-length mk-length) x)))))

Alright, the next step is just re-arranging the code to factor out the portion of the code that is related to the length operation that we desire.

(;;func0
 (fn [non-recursive-func]
   ((fn [mk-length]
      (mk-length mk-length))
    (fn [mk-length]
      (non-recursive-func
       (fn [x]
         ((mk-length mk-length) x))))))

 ;;; arg0
 (fn [length]
   (fn [coll]
     (if (empty? coll)
       0
       (inc (length (rest coll)))))))

Congratulations... func0 above is the Y combinator function. It receives one function and return another function which is recursive.

Changing the name of the variables:

(def Y
  (fn [non-recursive-func]
    ((fn [f] (f f))
     (fn [f]
       (non-recursive-func (fn [x] ((f f) x)))))))

This chapter of The Little Schemer could not have ended better:

           

Q: Do you now know why Y works?

A: Read this chapter just one more time and you will.

Tags: clojure programming functional