# The Y (Fixed-Point) Combinator in PHP

A combinator is a type of higher-order function that can be used to express functions without the explicit use of variables. A fixed point is a value that is unchanged by a function, satisfying the equation which can be found here. Using the Y-combinator allows us to essentially convert non-recursive code into a recursive counterpart (without directly using named recursion or iteration). To work it’s magic the recursive function is computed as the fixed point of the non-recursive function.

You may be asking yourself why is this at all relevant in an imperative language such as PHP? Well, with the introduction of Closures (since PHP 5.3) the language has slowly started to embrace many functional concepts. One such concept however, still requires some work to correctly implement in-practice, that being recursive closures. In a previous memorization post I highlighted a factorial implementation using such an approach, requiring some PHP reference hackery to pass in the closure variable, as this would not typically be available in the function scope. With a little research I stumbled upon the concept of Haskell’s ‘fix’ function which is generally known by the name ‘Y-combinator’. I was keen to provide a thought-experiment into how this could be implemented in the PHP language along with some interesting example use-cases.

## Basic Implementation

Below is my first attempt at implementing the Y combinator in PHP, cheating a little by temporarily storing the fix-point function in a variable to remove code duplication.

This function can be then be applied to solve the Fibonacci sequence, as shown below. As you can see the implementation provides us with the ability to reference the function by parameter instead of name (call-by-name), which in (typed) lambda calculus is not possible.