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 =
if (n == 0) 1 else n * factorial(n - 1)
n =>
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 =
if (n == 0) 1 else n * f(n - 1)
n =>
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 =
if (n == 0) 1 else n * f(n - 1)
n =>
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 // that works
almostFactorial(factorial0)
=
val factorial2 // that works too.
almostFactorial(factorial1)
=
val factorial2_ // that works too.
almostFactorial(almostFactorial(almostFactorial(identity)))
: Int => Int =
val factorialInfinity.............almostFactorial(.........))) // forever
almostFactorial(almostFactorial(almostFactorial
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 =
if (n == 0) 1 else n * self.asInstanceOf[Any => (Int => Int)](self)(n - 1)
n =>
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 =
if (n == 0) 1 else n * f(n-1)
n =>
def partFactorialv1(self: Any): Int => Int = {
val f = self.asInstanceOf[Any => (Int => Int)](self) // val f = self(self)
if (n == 0) 1 else n * f(n - 1) // almost n factorial
n =>
}
// 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)
if (n == 0) 1 else n * f(n - 1) // almost n factorial
n =>
}
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) = {
almostFactorial(self.asInstanceOf[Any => (Int => Int)](self)) // almostFactorial self self
(self: Any) =>
}
// Moved inside our factorial implementation now.
def factorialV4: Int => Int = {
val partFactorial =
almostFactorial(self.asInstanceOf[Any => (Int => Int)](self)) // almostFactorial self self
(self: Any) =>
partFactorial(partFactorial)
}
// Well, lets rename this partFactorial to x
def factorialV5: Int => Int = {
val x =
almostFactorial(self.asInstanceOf[Any => (Int => Int)](self)) // almostFactorial self self
(self: Any) =>
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(x))(
((x: Any => (Int => Int)) => almostFactorial(self.asInstanceOf[Any => (Int => Int)](self))
(self: Any) =>
)
}
// 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(x))(
((x: Any => (Int => Int)) => almostFactorial(x.asInstanceOf[Any => (Int => Int)](x))
(x: Any) =>
)
}
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(x))(
((x: Any => (Int => Int)) => f(x.asInstanceOf[Any => (Int => Int)](x))
(x: Any) =>
)
}
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(x))(
((x: Any => (Int => Int)) => f(x.asInstanceOf[Any => (Int => Int)](x))
(x: Any) =>
)
}
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)) => {
(f(x.asInstanceOf[Any => (Int => Int)](x))
(x: Any) =>
)(f(x.asInstanceOf[Any => (Int => Int)](x))
(x: Any) =>
)
}
// 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
f ((lambdaXfxx)((lambdaXfxx)))
y f = f (y 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) =
f((y: A) => lambda(z)(y)))
([Z] => (z: Z) => 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