Understanding Y Combinator Through Generic Lambdas

Understanding Y Combinator through generic lambdas

Here is a y combinate where the lambda is passed a recurs that doesn't need to be passed recurs:

template<class F>
struct y_combinate_t {
  F f;
  template<class...Args>
  decltype(auto) operator()(Args&&...args)const {
    return f(*this, std::forward<Args>(args)...);
  }
};
template<class F>
y_combinate_t<std::decay_t<F>> y_combinate( F&& f ) {
  return {std::forward<F>(f)};
};

then you do:

  return y_combinate(step)(acc, xs...);

and change

                   return self(self)(next, y_xs...);

to

                   return self(next, y_xs...);

the trick here is I used a non-lambda function object that has access to its own this, which I pass to f as its first parameter.

What is a Y-combinator?

If you're ready for a long read, Mike Vanier has a great explanation. Long story short, it allows you to implement recursion in a language that doesn't necessarily support it natively.

Y Combinator implementation Scheme

In a lazy language like Lazy Racket you can use the normal order version, but not in any of the applicative order programming languages like Scheme. They will just go into an infinite loop.

The applicative version of Y is often called a Z combinator:

(define Z
  (lambda (f)
    ((lambda (g) (g g))
     (lambda (g)
       (f (lambda args (apply (g g) args)))))))

Now the first thing that happens when this is applied is (g g) and since you can always substitute a whole application with the expansion of it's body the body of the function can get rewritten to:

(define Z
  (lambda (f)
    ((lambda (g)
       (f (lambda args (apply (g g) args))))
     (lambda (g)
       (f (lambda args (apply (g g) args)))))))

I haven't really changed anything. It's just a little more code that does exactly the same. Notice this version uses apply to support multiple argument functions. Imagine the Ackermann function:

(define ackermann
  (lambda (m n)
    (cond
      ((= m 0) (+ n 1))
      ((= n 0) (ackermann (- m 1) 1))
      (else (ackermann (- m 1) (ackermann m (- n 1)))))))

(ackermann 3 6) ; ==> 509

This can be done with Z like this:

((Z (lambda (ackermann)
      (lambda (m n)
        (cond
        ((= m 0) (+ n 1))
        ((= n 0) (ackermann (- m 1) 1))
        (else (ackermann (- m 1) (ackermann m (- n 1))))))))
 3
 6) ; ==> 509

Notice the implementations is exactly the same and the difference is how the reference to itself is handled.

EDIT

So you are asking how the evaluation gets delayed. Well the normal order version looks like this:

(define Y
  (lambda (f)
    ((lambda (g) (g g))
     (lambda (g) (f (g g))))))

If you look at how this would be applied with an argument you'll notice that Y never returns since before it can apply f in (f (g g)) it needs to evaluate (g g) which in turn evaluates (f (g g)) etc. To salvage that we don't apply (g g) right away. We know (g g) becomes a function so we just give f a function that when applied will generate the actual function and apply it. If you have a function add1 you can make a wrapper (lambda (x) (add1 x)) that you can use instead and it will work. In the same manner (lambda args (apply (g g) args)) is the same as (g g) and you can see that by just applying substitution rules. The clue here is that this effectively stops the computation at each step until it's actually put into use.

Is the Y Combinator a left fold or a right fold?

Fixed point combinators like Y merely enable anonymous recursion. What you do with this recursion is totally up to you. You can define both a left associative fold and a right associative fold with it. I hope you don't mind me illustrating this in Javascript:

// simplified Y combinator with eta abstraction due to eager evaluation
const fix = f => x => f(fix(f)) (x);
// left fold
const foldl = fix(rec => f => acc => ([x, ...xs]) =>  x === undefined    ? acc    : rec(f) (f(acc) (x)) (xs));    // right fold
const foldr = fix(rec => f => acc => ([x, ...xs]) =>  x === undefined    ? acc    : f(x) (rec(f) (acc) (xs)));         console.log(   foldl(x => y => x - y) (0) ([1,2,3])); // -6     console.log(   foldr(x => y => x - y) (0) ([1,2,3])); // 2

Is it possible to implement a TypeScript generic version of Y-combinator?

The short answer:

The TypeScript type of a fixed point combinator whose input is a one-argument function is:

type Y = <I, O>(F: (f: (i: I) => O) => ((i: I) => O)) => (i: I) => O;

The long answer follows:

---

The type of a fixed point combinator should be a generic function of the following form:

type Fixed = <T>(f: (t: T) => T) => T;

So if you had a value fixed of type Fixed, you should be able to call it on any one argument function whose output is the same type as the input, and (magically?) get a result which is a fixed point of that function:

console.log(fixed(Math.cos)) // 0.739085...

You can get something like this behavior for certain well-behaved functions f just by starting with some random value and iterating f a bunch of times:

const fixed: Fixed = f => {
  let r = null as any;
  for (let i = 0; i < 1000; i++) r = f(r);
  return r;
}

That's a silly implementation (or at least not the classic one) but it works well enough for the normal use case of finding a fixed point of a function whose input is itself a function.

For example, let's define a protoFactorial function whose fixed point calculates the factorial of a non-negative integer via recursion:

const protoFactorial = (f: (n: number) => number) =>
  (n: number) => n === 0 ? 1 : n * f(n - 1)

Note that the input f is a function of type (n: number) => number, and the output is another function of this type, whose input n is the n is the number whose factorial we want to calculate. If n is 0 it returns 1; otherwise it returns n * f(n - 1).

If we have a fixed point combinator fixed, we should be able to get the desired factorial function like so:

const factorial = fixed(protoFactorial);
console.log(factorial(7)); // 5040

And the above fixed does work for this.

---

But for the Y combinator in particular we tend to require that the type T on which it operates is itself a function type (although in untyped lambda calculus there's not really a distinction), and therefore I'd be inclined to give Y a generic type that specifically depends on the input and output of the T function type:

type Y = <I, O>(F: (f: (i: I) => O) => ((i: I) => O)) => (i: I) => O;

That is like Fixed if you replace T with (i: I) => O. Anyway, with a value Y of type Y, we should presumably be able to call Y(protoFactorial) and get the correct factorial.

Here's an implementation of Y in TypeScript:

interface Ω<T> {
  (x: Ω<T>): T;
}

const Y: Y = <I, O>(F: (f: (i: I) => O) => (i: I) => O) =>
  ((x: Ω<(i: I) => O>) => F(x(x)))((x: Ω<(i: I) => O>) => F(x(x)));

Note that in order to strongly type the Y combinator implementation we need the recursive type Ω<T>; the x parameter has to be of such a type in order to allow a call like x(x) to compile and produce an output of type (i: I) => O.

This is the same as your g => (x => g(x(x)))(x => g(x(x))) implementation with g renamed to F and with type annotations to help the compiler.

---

That's the answer to the question as asked, but unfortunately the Y combinator cannot be used as-is in JavaScript, which eagerly evaluates all function inputs before evaluating the function body:

try {
  const factorial = Y(protoFactorial);
} catch (e) {
  console.log(e); // too much recursion
}

Oops, calling Y(protoFactorial) eagerly expands out to the unending F(F(F(F(F(F(.... and explodes.

---

To get a viable fixed-point combinator in JavaScript, we need something more like the Z combinator which delays the calculation of x(x) by using eta abtraction (see What is Eta abstraction in lambda calculus used for?) to produce v => x(x)(v):

const Z: Y = <I, O>(F: (f: (i: I) => O) => (i: I) => O) =>
  ((x: Ω<(i: I) => O>) => F(v => x(x)(v)))((x: Ω<(i: I) => O>) => F(v => x(x)(v)));

Now if we use Z in place of Y it works at runtime:

const factorial = Z(protoFactorial);
// const factorial: (i: number) => number
console.log(factorial(7)); // 5040

---

Of course, if all we care about are the typings and we are don't need to pretend that JavaScript and TypeScript lack first-class recursion at runtime, then we can just implement a function of type Y recursively with a lot less hassle:

const R: Y = f => f(x => R(f)(x))    
console.log(R(protoFactorial)(7)) // 5040

---

From the perspective of the type system, all of fixed, Y, Z, and R are values of type Y:

function acceptY(y: Y) { }
acceptY(fixed)
acceptY(Y)
acceptY(Z)
acceptY(R)

And so we can say fairly confidently that the TypeScript type of a fixed point combinator whose input is a one-argument function is:

type Y = <I, O>(F: (f: (i: I) => O) => ((i: I) => O)) => (i: I) => O;

Playground link to code

Different stack depth for lambdas and regular functions in C++?

std function does not mean the same thing as lambda. A std function is an object capable of storing some lambdas, or a function pointer, or a pointer to member function, or a pointer to member data, or almost any object that overrides operator() compatibly.

When you store a lambda within a std function, there is some overhead. Not much, but some. Some of this overhead may show up as using the stack more (and the overhead will be larger in unoptimized builds).

You can more directly recurse using a lambda by using the y combinator, but even there you'll be passing a reference-to-self as a parameter, and unless the recursion is eliminated by the optimizer it will probably use more stack. (A highly tweaked optimizer could notice that a stateless lambda reference argument could be eliminated, but that seems tricky to work out).

How to make a SFINAE-based Y combinator in C++?

It is not possible in C++14 return type deduction to deduce int(int) out of int(T, int) as OP desires.

However, we can mask the first parameter of the result using the following approach. The struct YCombinator is instantiated with a non-recursive function object member, whose first argument is a version of itself without the first argument. YCombinator provides a call operator that receives the arguments of the non-recursive function and then returns its function object member after substituting itself for the first argument. This technique allows the programmer to avoid the messiness of myself(myself, ...) calls within the definition of the recursive function.

template<typename Functor>
struct YCombinator
{
    Functor functor;

    template<typename... Args>
    decltype(auto) operator()(Args&&... args)
    {
        return functor(*this, std::forward<Args>(args)...);
    }
};

A make_YCombinator utility template allows for a streamlined usage pattern. This compiles run runs in GCC 4.9.0.

template<typename Functor>
decltype(auto) make_YCombinator(Functor f) { return YCombinator<Functor> { f }; }

int main()
{
    auto fib = make_YCombinator([](auto self, int n) -> int { return n < 2 ? 1 : self(n - 1) + self(n - 2); });

    for (int i = 0; i < 10 ; ++i)
        cout << "fib(" << i << ") = " << fib(i) << endl;

    return 0;
}

Since the non-recursive function is not defined at time that the recursive function is defined, in general the recursive function must have an explicit return type.

Edit:

However, it may be possible for the compiler to deduce the return type in certain cases if the programmer takes care to indicate the return type of the recursive function before use of the non-recursive function. While the above construction requires an explicit return type, in the following GCC 4.9.0 has no problem deducing the return type:

    auto fib = make_YCombinator([](auto self, int n) { if (n < 2) return 1; return self(n - 1) + self(n - 2); });

To pin this down just a bit further, here is a quote from the draft C++14 standard on return type deduction [7.1.6.4.11]:

If the type of an entity with an undeduced placeholder type is needed
to determine the type of an expression, the program is ill-formed.
Once a return statement has been seen in a function, however, the
return type deduced from that statement can be used in the rest of the
function, including in other return statements. [ Example:

auto n = n; // error, n’s type is unknown
auto f();
void g() { &f; } // error, f’s return type is unknown
auto sum(int i) {
if (i == 1)
    return i; // sum’s return type is int
else
    return sum(i-1)+i; // OK, sum’s return type has been deduced
}

—end example ]

Two-layer Y-style combinator. Is this common? Does this have an official name?

Yes, it is an applicative-order Y combinator. Using U inside it is perfectly OK, I did it too (cf. fixed point combinator in lisp). Whether the usage of U to shorten code has a name or not, I don't think so. It's just an application of a lambda-term, and yes, it makes it clearer IMO too.

What does have a name, is eta-conversion, used in your code to delay evaluation under applicative order, where arguments' values must be known before functional application.

With U applied through and through and eta-reduction performed on your code ( (λa.(f (s s)) a) ==> f (s s) ), it becomes the familiar normal-order Y combinator - i.e. such that works under normal-order evaluation, where arguments' values aren't demanded before functional application, which might end up not needing them (or some of them) after all:

Y = λf . (λs.f (s s)) (λs.f (s s))

BTW the delaying can be applied in slightly different way,

Y_ = λf . (λx.x x) (λs.f (λa.(s s) a)) 

which also works under applicative-order evaluation rules.

What is the difference? let's compare the reduction sequences. Your version,

Y_ = λf . (λx . (λv . (f (x x)) v)) (λx . (λv . (f (x x)) v))

((Y_ f) a) = 
  = ((λx . (λv . (f (x x)) v)) (λx . (λv . (f (x x)) v))) a
  = (λv . (f (x x)) v) a    { x := (λx . (λv . (f (x x)) v)) }
  = (f (x x)) a
  = | ; here (f (x x)) application must be evaluated, so 
    | ; the value of (x x) is first determined
    | (x x) 
    | = ((λx . (λv . (f (x x)) v)) (λx . (λv . (f (x x)) v))) 
    | = (λv . (f (x x)) v)     { x := (λx . (λv . (f (x x)) v)) }

and here f is entered. So here too, the well-behaved function f receives its first argument and it's supposed not to do anything with it. So maybe the two are exactly equivalent after all.

But really, the minutia of lambda-expressions definitions do not matter when it comes to the real implementation, because real implementation language will have pointers and we'll just manipulate them to point properly to the containing expression body, and not to its copy. Lambda calculus is done with pencil and paper after all, as textual copying and replacement. Y combinator in lambda calculus only emulates recursion. True recursion is true self-reference; not receiving copies equal to self, through self-application (however smart that is).

TL;DR: though language being defined can be devoid of such fun stuff as assignment and pointer equality, the language in which we define it will most certainly have those, because we need them for efficiency. At the very least, its implementation will have them, under the hood.

see also: fixed point combinator in lisp , esp. In Scheme, how do you use lambda to create a recursive function?.

Y-combinator in D?

See an extensive explanation here.

---

Related Topics