Explain this implementation of the Y combinator in Scala?

Question

This is a implementation of the Y-combinator in Scala:

scala> def Y[T](func: (T => T) => (T => T)): (T => T) = func(Y(func))(_:T)
Y: [T](func: (T => T) => (T => T))T => T

scala> def fact = Y {
     |           f: (Int => Int) =>
     |             n: Int =>
     |               if(n <= 0) 1
     |               else n * f(n - 1)}
fact: Int => Int

scala> println(fact(5))
120

Q1: How does the result 120 come out, step by step? Because the Y(func) is defined as func(Y(func)), the Y should become more and more,Where is the Y gone lost and how is the 120 come out in the peform process?

Q2: What is the difference between

def Y[T](func: (T => T) => (T => T)): (T => T) = func(Y(func))(_:T)

and

def Y[T](func: (T => T) => (T => T)): (T => T) = func(Y(func))

They are the same type in the scala REPL, but the second one can not print the result 120?

scala> def Y[T](func: (T => T) => (T => T)): (T => T) = func(Y(func))
Y: [T](func: (T => T) => (T => T))T => T

scala> def fact = Y {
     |           f: (Int => Int) =>
     |             n: Int =>
     |               if(n <= 0) 1
     |               else n * f(n - 1)}
fact: Int => Int

scala> println(fact(5))
java.lang.StackOverflowError
  at .Y(<console>:11)
  at .Y(<console>:11)
  at .Y(<console>:11)
  at .Y(<console>:11)
  at .Y(<console>:11)

Answer 1

Unfortunately, the accepted answer is completely wrong. There is nothing magic about function parameters; in particular, they are not byname or lazy by default. Let's look at your code, slightly rewritten for readability:

def Y[T](F: (T => T) => (T => T)): (T => T) =
  t => F(Y(F))(t)

def F(f: Int => Int)(n: Int) =
  if (n <= 0) then 1 else n * f(n - 1)

val fact = Y(F)

Q1: How does the result 120 come out, step by step?

Let's run it by hand! In the following each line is the result of a step of reduction and each comment describes the reduction used for that step.

fact(5)
// { Apply `fact` }
Y(F)(5)
// { Apply `Y` }
(t => F(Y(F))(t))(5)
// { Apply the anonymous function }
F(Y(F))(5) // Here we learned that `F(Y(F))(5)` is the same as `fact(5)`
// { Reduce the first argument of F: Apply `Y` }
F(t => F(Y(F))(t))(5)
// { Apply `F` }
if (5 <= 0) then 1 else 5 * (t => F(Y(F))(t))(4)
// { Simplify the if }
5 * (t => F(Y(F))(t))(4)
// { Reduce the arguments of `*`: Apply the anonymous function }
5 * F(Y(F))(4)
// { Notice the repeated pattern }
5 * fact(4)
// { ... }

The key thing to understand here is that F(Y(F)) reduces just once before F is called: because of the anonymous function, the Y(F) becomes t => F(Y(F))(t), which can't be reduced further, and then F is called, and a step of factorial computation happens.

Q2. What is the difference between t => F(Y(F))(t) and F(Y(F))?

The first one uses an anonymous function which delays computation (a "thunk"). In t => F(Y(F))(t), the inner Y(F) does not get evaluated until a value for t is passed to the function. In F(Y(F)), an infinite nesting of function calls is constructed immediately. Let's see what happens to fact(5) with this new definition:

fact(5)
// { Apply `fact` }
Y(F)(5)
// { Apply `Y` }
F(Y(F))(5)
// { Reduce the first argument of F: Apply `Y` }
F(F(Y(F)))(5)
// { Reduce the first argument of F: Apply `Y` }
F(F(F(Y(F))))(5)
// { Reduce the first argument of F: Apply `Y` }
F(F(F(F(Y(F)))))(5)
// { Reduce the first argument of F: Apply `Y` }
F(F(F(F(F(Y(F))))))(5)
// { ... }

See the problem? Using an anonymous function prevents this infinite stack of calls from being built.

Answer 2

Complementing the accepted answer,

First of all, note that this is not a Y-combinator, since the lambda version of the function uses the free variable Y. It is the correct expression for Y though, just not a combinator.

A combinator isn't allowed to be explicitly recursive; it has to be a lambda expression with no free variables, which means that it can't refer to its own name in its definition. In the lambda calculus it is not possible to refer to the definition of a function in a function body. Recursion may only be achieved by passing in a function as a parameter.

Given this, I've copied the following implementation from rosetta code that uses some type trickery to implement Y combinator without explicit recursion. See here

  def Y[A, B](f: (A => B) => (A => B)): A => B = {
    case class W(wf: W => A => B) {
      def get: A => B =
        wf(this)
    }
    val g: W => A => B = w => a => f(w.get)(a)

    g(W(g))
  }

Hope this helps with the understanding.

Answer 3

First of all, note that this is not a Y-combinator, since the lambda version of the function uses the free variable Y. It is the correct expression for Y though, just not a combinator.

So, let’s first put the part which computes the factorial into a separate function. We can call it comp:

def comp(f: Int => Int) =
  (n: Int) => {
    if (n <= 0) 1
    else n * f(n - 1)
  }

The factorial function can now be constructed like this:

def fact = Y(comp)

Q1:

Y is defined as func(Y(func)). We invoke fact(5) which is actually Y(comp)(5), and Y(comp) evaluates to comp(Y(comp)). This is the key point: we stop here because comp takes a function and it doesn’t evaluate it until needed. So, the runtime sees comp(Y(comp)) as comp(???) because the Y(comp) part is a function and will be evaluated only when (if) needed.

Do you know about call-by-value and call-by-name parameters in Scala? If you declare your parameter as someFunction(x: Int), it will be evaluated as soon as someFunction is invoked. But if you declare it as someFunction(x: => Int), then x will not be evaluated right away, but at the point where it is used. Second call is “call by name” and it is basically defining your x as a “function that takes nothing and returns an Int”. So if you pass in 5, you are actually passing in a function that returns 5. This way we achieve lazy evaluation of function parameters, because functions are evaluated at the point they are used.

So, parameter f in comp is a function, hence it is only evaluated when needed, which is in the else branch. That’s why the whole thing works - Y can create an infinite chain of func(func(func(func(…)))) but the chain is lazy. Each new link is computed only if needed.

So when you invoke fact(5), it will run through the body into the else branch and only at that point f will be evaluated. Not before. Since your Y passed in comp() as parameter f, we will dive into comp() again. In the recursive call of comp() we will be calculating the factorial of 4. We will then again go into the else branch of the comp function, thus effectively diving into another level of recursion (calculating factorial of 3). Note that in each function call your Y provided a comp as an argument to comp, but it is only evaluated in the else branch. Once we get to the level which calculates factorial of 0, the if branch will be triggered and we will stop diving further down.

Q2:

This

func(Y(func))(_:T)

is syntax sugar for this

x => func(Y(func))(x)

which means we wrapped the whole thing into a function. We didn’t lose anything by doing this, only gained.

What did we gain? Well, it’s the same trick as in the answer to a previous question; this way we achieve that func(Y(func)) will be evaluated only if needed since it’s wrapped in a function. This way we will avoid an infinite loop. Expanding a (single-paramter) function f into a function x => f(x) is called eta-expansion (you can read more about it here).

Here’s another simple example of eta-expansion: let’s say we have a method getSquare() which returns a simple square() function (that is, a function that calculates the square of a number). Instead of returning square(x) directly, we can return a function that takes x and returns square(x):

def square(x: Int) = x * x
val getSquare: Int => Int = square
val getSquare2: Int => Int = (x: Int) => square(x)

println(square(5)) // 25
println(getSquare(5)) // 25
println(getSquare2(5)) // 25

Hope this helps.

Answer 4

I don't know the answer, but will try to guess. Since you have def Y[T](f: ...) = f(...) compiler can try to substitute Y(f) with simply f. This will create an infinite sequence of f(f(f(...))). Partially applying f you create a new object, and such substitution becomes impossible.