Fix point types and Y combinator - in Scala.

Posted on April 15, 2021

Let’s do some math.

If we continuously do cosine of 0 and keep on applying cosine over the result, we end up in a number finally that gets fixed forever. The number is 0.73908513321516067.


  cos(cos(cos(cos(x))))

Ofcourse this example is a blatant copy from one of the most wonderful blogs ever written about fix-points in Scheme language - https://mvanier.livejournal.com/2897.html.

You can choose to read it. This blog is a mere adoption of the ideas presented in the blog, but in Scala language.

Fix point being a function

So, yes, the fix-point of cos is x if cos(x) = x. But a fix-point may not be always a real number. It could be even a type. A function is a type indeed.

Sure what does that mean? Well if fix-point of a function like cos is a real-number, and if you say that a fix-point can be a function itself, that means the following:


There exists a `function`, whose fix-point can be a `funtion` itself. Hmmmmm.

Stop explaining. Show an example.

A factorial of a number 3 is 3 * 2 * 1. It’s implementation is as follows:


  val factorial: Int => Int =
    n => if (n == 0) 1 else n * factorial(n - 1)

Sure, that’s easy. But let’s say someone asked you to implement the same factorial such that the name of the function shouldn’t come in the body. Why? I think, answering this Why leads to applications that use Fix Points.

So, I request you to consider it as a challenge and a first step towards the understanding of Fix and Recursion Schemes and its wonderful application level usages in various other talks/blogs.

Answering the question, well may be I can do


  def factorial(f: Int => Int): Int => Int =
    n => if (n == 0) 1 else n * f(n - 1)

Ah, sure, but that’s not a factorial.

Ofcourse, that’s not a factorial, so let’s call it as almostFactorial.


   def almostFactorial(f: Int => Int): Int => Int =
     n => if (n == 0) 1 else n * f(n - 1)

Now we need to implement a sensible factorial in terms of almostFactorial. All of us know, the real factorial exists when the f( now staying as an argument in almostFactorial) is almostFactorial itself.

i.e,


  val factorial: Int => Int =
    almostFactorial(almostFactorial(almostFactorial(.....)))

Well if you try to implement it, you will be writing it forever. Anyone who is not convinced yet, please try it out.

Fine, let’s take a different approach then.


 val factorial0: Int => Int =
   almostFactorial(identity)

  factorial0(0) // returns 1 ==> works
  factorial0(1) // doesn't work, coz identity(n - 1) == identity(1 - 1) == identity(0) == 0

So factorial0 works only for zero. That’s fine for now.

Let’s implement for factorial1.




 val factorial1 =
   almostFactorial(factorial0) // that works

 val factorial2 =
   almostFactorial(factorial1) // that works too.

 val factorial2_ =
   almostFactorial(almostFactorial(almostFactorial(identity))) // that works too.

 val factorialInfinity: Int => Int =
      almostFactorial(almostFactorial(almostFactorial.............almostFactorial(.........))) // forever


Ah, kind of making sense now. factorialInfinity is a function, which is a fixpoint of almostFactorial. Infact factorialInfinitiy is our real factorial implementation.


 factorial = fix-point-of almostFactorial

Hmmm. I think its time to figure out what is this fix-point-of. Is there a function called fix-point-of that allows us to pass almostFactorial and return a real factorial. In other words, is there a function called fix-point-of that takes a function and returns the fix-point of that function.


def fixPointOf(f: <someFn>): fixPointOf_SomeFn

This fixPointOf is also called “y combinator”. The Y combinator is the one that converts a function to its fix-point. However, before we call it as a combinator, let’s call it as a function, because, to be a combinator it needs to satisfy a few conditions that we will explain later.

So, let’s implement y such that it can take a function and returns its fix-point



// val factorial = almostFactorial(factorial)

// implies the following:

// If we are building a function called toFixPoint that takes `fn` as an argument then,
// that means the following

// toFixPoint (fn: Fn) = fn(toFixPoint(fn))
// Rename toFixPoint as Y, we will see later why
// Y(fn: Fn) = fn (Y(fn))

The above pseudo-code in Scala is


 // (A => A) => (A => A) is alligned to the signature of almostFactorial
  def Y[A](f: (A => A) => (A => A)) = f(Y(f))
  val factorial = Y(almostFactorial) // Stack overflow haha

Stack overflow is, when you call Y the following thing happens:


 f(Y(f)) ==
   f(f(f(f(f.......))))

In other words, it tries to compute the fix-point function for you and it never ends.

Lambda saves us from this stack overflow - in a surprising way.


  def Y[A](f: (A => A) => (A => A)): A => A = f(Y(f)) // Stack unsafe
  // same as
  def Y[A](f: (A => A) => (A => A)): A => A = f(a => Y(f)(a)) // Stack safe

Now my factorial implementation is


 val factorial = Y(almostFactorial)

 // factorial(3) is 6

Now, that works. However, we could further improve things.

The Y function that we defined (the function that takes another function and returns a fix-point function) has a restricted shape.


  def Y[A](f: (A => A) => (A => A)): A => A = f(Y(f)) // Stack unsafe

(A => A) => (A => A) is equivalent to A => A in types. In other words.

The following will compile.


    def Y[A](f: A => A): A = f(Y(f)) // Stack unsafe
    val factorial = Y(almostFactorial)

However, it’s sort of fairly hacky to make our latest Y stacksafe using our lambda technique. Try yourself if you are having a doubt. This is sort of solveable though. However, for the time being, we can keep the same original Y as it is but with only a minor change. We can make the return type a B instead of A to allow more flexiblity.

In the case of factorial which is Int => Int, B is A itself.


  def Y[A](f: (A => B) => (A => B)): A => B = f(a => Y(f)(a)) // Stack safe
  val factorial = Y(almostFactorial)

Is our y a combinator - No!

To become a combinator, the implementation of y shouldn’t have any free variables in it.

For example: The below lambda is a combinator, because you can replace f with its implementation in all occurances of f.


val f = (x: Int) => x + 1

However, our y is not a combinator, the implementation f(y(f)) has a free variable, and that’s y itself. An explicit recursion here made it not call as a combinator.


def y[A, B] = (f: (A => B) => (A => B)) => f(y(f))

Well let’s revisit our factorial, and try abstracting out recursion again, and call our function partFactorial. You will see why we are not calling it as almostFactorial later.

  def partFactorial(f: Int => Int): Int => Int = n => if (n == 0) 1 else n * f(n - 1)

Our real factorial is when f is partFactorial itself.


// Will not compile
// well partFactorial _ is of the type `Int => Int => Int => Int`.
// However, `partFactorial` method above accepts `Int => Int`
def factorial = partFactorial(partFactorial _) 

Ok, let’s do a hack. We have Any in scala, and see how it goes.


def partFactorialv0(self: Any): Int => Int = 
  n => if (n == 0) 1 else n * self.asInstanceOf[Any => (Int => Int)](self)(n - 1)

def factorial(n: Int) = partFactorialv0(partFactorialv0 _)

// Works, factorial(3) == 6

Why did we do this? Well, let’s extract out our almostFactorial discussed above from this implementation.

Repeating almostFactorial here:


def almostFactorial(f: Int => Int): Int => Int = 
  n => if (n == 0) 1 else n * f(n-1)

 def partFactorialv1(self: Any): Int => Int = {
    val f = self.asInstanceOf[Any => (Int => Int)](self) // val f = self(self) 
    n => if (n == 0) 1 else n * f(n - 1) // almost n factorial
  }

// Hmmm, almost there. But it could be written as:


def partFactorialv2(self: Any): Int => Int = {
    val f = self.asInstanceOf[Any => (Int => Int)](self) // val f = self(self) 
    n => if (n == 0) 1 else n * f(n - 1) // almost n factorial
  }

def partFactorialv3(self: Any): Int => Int = {
    val selfSelf = self.asInstanceOf[Any => (Int => Int)](self) // val f = self(self) 
    almostFactorial(selfSelf) // almost n factorial
  }

// stack safety issues come into picture here, hence factorialV3(4) will not work
def factorialV3 = partFactorialv3(partFactorialv3 _) 

Sure, we kind of extracted/reused almostFactorial in our latest implementations. You might be wondering why we are we doing this long loop of refactoring. I agree, but I request you to keep your patience and read on.

All our implementations of factorial is partFactorial*(partFactorial* _). Let’s get rid of it and try having only one single function called factorial. That means partFactorial implementation will become part of the factorial itself.


 // This was our partFactorial
 def partFactorialv4: Any => (Int => Int) = {
    (self: Any) => almostFactorial(self.asInstanceOf[Any => (Int => Int)](self)) // almostFactorial self self
  }

 // Moved inside our factorial implementation now.
 def factorialV4: Int => Int = {
    val partFactorial = 
       (self: Any) => almostFactorial(self.asInstanceOf[Any => (Int => Int)](self)) // almostFactorial self self

    partFactorial(partFactorial)   
  }  

// Well, lets rename this partFactorial to x
 def factorialV5: Int => Int = {
    val x = 
       (self: Any) => almostFactorial(self.asInstanceOf[Any => (Int => Int)](self)) // almostFactorial self self

    x(x)   
  }

// Let's apply our trick: Replace { val x: A = a; x(x) } with { ((x: A) => x(x))(a) }
 def factorialV6: Int => Int = {
    ((x: Any => (Int => Int)) => x(x))(
      (self: Any) => almostFactorial(self.asInstanceOf[Any => (Int => Int)](self))
    )
  }

// Just renaming self to x, and obviously it doesn't change the meaning of the program.
// At this stage, I really recommend you try this code compile in your IDE
// instead of reasoning it without a code, because languages are always complex in some way.
  def factorialV7: Int => Int = {
    ((x: Any => (Int => Int)) => x(x))(
      (x: Any) => almostFactorial(x.asInstanceOf[Any => (Int => Int)](x))
    )
  }

As functional programmers, we cannot allow almostFactorial to be part of the implementation. Let’s abstract that out.


// It's no more factorial because we extracted out almostFactorial as `f`.
def makeRecursive(f: (Int => Int) => (Int => Int)) = {
        ((x: Any => (Int => Int)) => x(x))(
      (x: Any) => f(x.asInstanceOf[Any => (Int => Int)](x))
    )
  }


def factorialV8 = makeRecursive(almostFactorial)
// Works? stack overflow again. But we will fix it later. Hold tight.

Before we fix the stack overflow error, let’s simply try to prove that makeRecursive is our y(implemented above).

And why do we need to prove ? makeRecursive is our real y that is devoid of free variables. In other words, we are going to prove that there is a combinator version of def y(f) = f(y(f))


// makeRecursive is renamed to yCombinator0
def yCombinator0(f: (Int => Int) => (Int => Int)) = {
  ((x: Any => (Int => Int)) => x(x))(
    (x: Any) => f(x.asInstanceOf[Any => (Int => Int)](x))
  )
}

def factorialV9 = yCombinator0(almostFactorial)

// Below code summarises the following:
// y f = (lambdaXfxx)((lambdaXfxx))
// where lambdaXfxx =  (x: Any) => f(x.asInstanceOf[Any => (Int => Int)](x))
def yCombinator1 = 
    (f: (Int => Int) => (Int => Int)) => {
       (
         (x: Any) => f(x.asInstanceOf[Any => (Int => Int)](x))
        )(
         (x: Any) => f(x.asInstanceOf[Any => (Int => Int)](x))
        )
  }

 // The final refactoring
 def yCombinator2 = 
    (f: (Int => Int) => (Int => Int)) => {
      val lambdaXFxx = ((x: Any) => f(x.asInstanceOf[Any => (Int => Int)](x)))
      f(lambdaXFxx(lambdaXFxx))
  }

There lies the proof. Can you see that?


// `yCombinator1` says the following:

y f = (lambdaXfxx)((lambdaXfxx))


// `yCombinator2` says the following

y f = f ((lambdaXfxx)((lambdaXfxx)))
y f = f (y f)

// Hence, we proved our `def yCombinator2(f) = <expr>` is same as `def y(f) = f(y(f))`

In summary, yCombinator2 is our real y combinator

Remove stack overflow from y combinator

May be we can apply the lambda technique we used before i.e,


{ val x: A => A = f(z) } is same as {val x : A => A = a => f(z)(a)}

All thats done here is, apply an extra lambbda, wherever possible.


// Stack safe
def yCombinator = 
    (f: (Int => Int) => (Int => Int)) => {
      val lambdaXFxx = ((x: Any) => f((y: Int) => x.asInstanceOf[Any => (Int => Int)](x)(y)))
      f(lambdaXFxx(lambdaXFxx))
  }

def factorial = yCombinator(almostFactorial) // Works !!

Generalise y combinator


 def y[A, B] = 
  (f: (A => B) => (A => B)) => {
    val lambdaXFxx = ((x: Any) => f((y: A) => x.asInstanceOf[Any => (A => B)](x)(y)))
    f(lambdaXFxx(lambdaXFxx))
  }

// In scala3, you can also write something like this if you want. 
// It removes `Any`, but it doesn't really matter :D

def yScala3_v0[A, B] = 
  (f: (A => B) => (A => B)) => {
    val lambdaXFxx:[Z] => Z => (A => B) = ([Z] => (z: Z) => f((y: A) => z.asInstanceOf[Z => (A => B)](z)(y)))
    f(lambdaXFxx(lambdaXFxx))
  }

// Well, why do we need an asInstanceOf. If you think about it, the above code is equivalent to

def yScala3[A, B] = 
  (f: (A => B) => (A => B)) => {
    lazy val lambda:[Z] => Z => (A => B) = ([Z] => (z: Z) => f((y: A) => lambda(z)(y)))
    f(lambda(lambda))
  }

// I think I liked that one
def y[A, B] = 
  (f: (A => B) => (A => B)) => {
    lazy val lambda:[Z] => Z => (A => B) = 
      ([Z] => (z: Z) => f((y: A) => lambda(z)(y)))
    f(lambda(lambda))
  }
  
def factorial = y(almostFactorial)

Ah! That was a long loop. I know, but not only you learned fix-points, you learned its implementation in scala through y f = f (y f) and proved that there exists a combinator, that is devoid of free variables that can achieve the same result in both strict and lazy languages.

Thanks, and Well done for reading such a long blog. If you are interested to read explanations in Lisp or Scheme language, go on and read this: https://mvanier.livejournal.com/2897.html