4D47—y-combinator

The Y Combinator Functional

The Y combinator is a functional, or higher-order function which takes in as input a non-recursive function and outputs a version of that function which is recursive. It gives us a way to get recursion in any programming language which makes use of first-class functions but that doesn't have recursion baked into it already.

The most important Y combinators are the normal-order and the applicative-order Y combinators. These work for lazy-evaluated and strictly-evaluated languages, respectively, with the evaluation type referring to whether the language evaluates only however much of an expression is required to get the result or the entire expression deterministically.

Statically typed: Expression types determined at compile time.
Dynamically typed: No type-checking until run time.
Strongly typed: A value can have only one type.
Weakly typed: Some values can have multiple types (consider malloc o/p in C).

What is a combinator?

A combinator is just a lambda expression with no free variables . This means that there are no variables contained in the body of the expression which have the saem name as one of the arguments of the expression.

For example: (lambda (x) x) is a combinator because the argument x is bound by the lambda expression and thus there are no free variables.
So is (lambda (x) (lambda (y) (x y))) since both the x and y are bound.

First we need to get rid of any recursive calls within our function. We can do this by removing the name in the body and replacing this with a parameter, and then simply wrapping the function in another function which takes as argument the parameter. Something like this:

    (define factorial-maker 

      (lambda (f) 

        (lambda (n) 

          (if (= n 0) 

            1 

            (* n (f (- n 1)))))))

where this example defines a functional which takes an input function f and returns a different function, which is the factorial function, completely conditionally on whether f is the correct form (also the factorial function).

Now that we have our factorial-maker functional, how can we go about creating factorial functions? Can we (define factorial (factorial-maker factorial))? Actually if your language is lazy-evaluated then yes.

The more interesting thing is that applying the factorial-maker functional recursively on the identity function (lambda (x) x) will create a function which can compute one more value of the factorial. What this means is:

      (define factorial_n
        (factorial-maker
          (factorial-maker
            ...                // n times
             (factorial-maker identity))))

will actually give you a function factorial_n which can calculate all factorial values from 0 to n (try this out for yourself with a simple version for an exercise). The factorial function that we actually want is the fixpoint of factorial-maker, where a fixpoint of a function is the input which when evaluted by the function is itself. Repeatedly applying cosine to 0, e.g., will result in the function converging to its fixpoint of ~0.739