I finally found the time to grok the Y-combinator. There are already multiple examples available but I am to thick to get them and, therefore, wanted to derive it myself.

The Y-combinator is a wonderful piece of software that allows you to create self-referential programs without built-in support. That is, it allows me to create **anonymous** recursive functions. This is best shown by an example.

; The factorial function(definefact(lambda(n) (if(< n 2) 1 (* n (fact (- n 1))))))

In the recursive function above the **fact** refers to itself by name. This relies on the name being available before it is actually defined. To avoid this we can send the function as a parameter to itself. Like so:

; Define a local variable g as the function.; The function takes a function (itself) as an extra parameter.; The function is called with itself as a parameter: (g g 5)).; This doesn't compile since the function h (that is g) requires; an additional parameter.(let((g (lambda(h n) (if(< n 2) 1 (* n (h (- n 1))))))) (g g 5)); The working version needs h to also call itself (h h (- n 1)).(let((g (lambda(h n) (if(< n 2) 1 (* n (h h (- n 1))))))) (g g 5))

We can now abstract over the **h** parameter with a technique reminiscent of currying.

; A new lambda is abstracted over h.; Note that the function calls to g and h need to change ((g g) 5)); and ((h h) (- n 1)) to ensure that they agree with the definitions.(let((g (lambda(h) (lambda(n) (if(< n 2) 1 (* n ((h h) (- n 1)))))))) ((g g) 5))

We can now abstract over **n** and **(h h)** creating a new lambda with the parameters **q** and **m**.

; Function f is declared locally with the parameters q and m; and then called directly (f (h h) n).(let((g (lambda(h) (lambda(n) (let((f (lambda(q m) (if(< m 2) 1 (* m (q (- m 1))))))) (f (h h) n))))) ((g g) 5)))

Notice that **f** is independent of it’s context and can be moved to the top level.

; f moved to the top level.(let((f (lambda(q m) (if(< m 2) 1 (* m (q (- m 1))))))) (let((g (lambda(h) (lambda(n) (f (h h) n))))) ((g g) 5)))

I can now abstract over **q** to isolate the definition of **fact**.

; Notice that the inner function of f is the original fact function.(let((f (lambda(q) (lambda(m) (if(< m 2) 1 (* m (q (- m 1)))))))) (let((g (lambda(h) (lambda(n) ((f (h h)) n))))) ((g g) 5)))

Now I abstract over the local variable **f** and declare a new variable **Y**. The call to **((g g) 5)** is replaced **(g g)** and moved to the Y function instead.

; A new variable Y is created for the abstraction over f.; The function call is moved to the application of Y.(let((Y (lambda(f) (let((g (lambda(h) (lambda(n) ((f (h h)) n))))) (g g))))) ((Y (lambda(q) (lambda(m) (if(< m 2) 1 (* m (q (- m 1))))))) 5))

Finally we replace the local variable **Y** with a the function **Y**, the **Y-combinator**.

(defineY(lambda(f) (let((g (lambda(h) (lambda(n) ((f (h h)) n))))) (g g))))

Excellent!

## No comments:

Post a Comment