44:["$","title",null,{"children":"Mindshift: Part 11 | Chris Whealy | Observable"}] 4c:T909,md`# Mindshift: Part 11 Republished on Feb 5th, 2018 # Deriving The Y-Combinator In the previous [Mindshift blog](https://beta.observablehq.com/@chriswhealy/mindshift-part-10), we looked at creating a recursive function using only anonymous functions. However, that function was only capable of performing a single task (calculating numbers in the Fibonacci Series). What we need however is a general purpose iterator. We have now arrived at the point where we can derive the Y-Combinator. Please remember that wherever you see the name "Y-Combinator", we could also use the name "Fixed Point Combinator". Please read [Mindshift: Part 9](https://beta.observablehq.com/@chriswhealy/mindshift-part-9#part2) for an explanation of the fixed point of a function. ## But Before We Start... It is important to understand that there is no *single* version of the Y-Combinator; rather, it is a set of functions where any member Y satisfies the criteria Y(f) === f(Y(f)) for some function f. So, strictly speaking, there are infinitely many Y-Combinators. What we're going to deal with here however, is the version of the Y-Combinator derived by Haskell Curry. This is because his version is both the most widely cited and is possibly also the least intuitive! Haskell Curry's Y-Combinator is often quoted in the following form (using Lambda Calculus notation):

Y = λf·(λx·f(x x))
       (λx·f(x x))

This expression is perfectly correct and has both an inherent beauty and, due to its symmetry, no small amount of mystery. However, it is nothing more than a description of the finished expression, and as such, is ***completely useless*** as the starting point for helping people understand the Y-Combinator! Therefore, I will not refer to this expression any more. However, by the end of this blog, we will have derived this combinator using the recursive functions defined in the previous blog to calculate the Fibonacci series. Also, I will not use any Lambda Calculus notation since this is of little help when working with the JavaScript implementation. If we translate the above expression into JavaScript arrow functions we get... `4d:T462,md`And... rats! Its still broken. The problem is call to U(fib_next) generates the next step along the Fibonacci series, and up until now, we have only ever called it ***after*** we tested that n is not less than one. So this test was acting as a safeguard to prevent runaway recursion. Unfortunately, we have now moved the call to U(fib_next) outside the safety of our termination condition. No wonder it blows up in our face! ### Step 4: Stopping the Runaway Recursion What we need is a way to delay the call to U(fib_next) so that it is only called when needed... Ah yes, we can use function wrapping. We must be careful here though. Look at where U(fib_next) is used inside the Fibonacci function. **Q:** The call to U(fib_next) generates a partial function that takes how many parameters?
**A:** Three Therefore, when we wrap the call to U(fib_next), the wrapper function must also take three parameters. For simplicity, we'll use the same names as before: n, a and b.`4e:T4b7,md`### Step 5: Just A Minute, Aren't We Going Round In Circles Here? Look at this block of code embedded into the centre of function fib_x - haven't we seen this somewhere before?

(fib_next => (n,a,b) => n < 1 ? a : fib_next(n-1,b,a+b))

Yup, this is the Fibonacci function we started with... (Look back at the coding at the start of this blog if you're not sure). The only difference is that the call to fib_next(fib_next) has been moved outside the function and is passed in as the parameter fib_next. Now let's see if we can extract the actual Fibonacci function itself from this whole mess. To do this, we'll follow exactly the same principle as before; we'll apply Tennent's Correspondence Principle on the entire function. We will extract the code block shown above by doing three things all at once. We will: 1. Cut out the code block shown above and make it the parameter to a new wrapper function 2. Give this parameter the name rec_fn meaning "recursive function" 3. Replace the code block with the parameter name rec_fn `4f:T463,md`Excellent!! ## But Is This Function Really The Y-Combinator? We've got ourselves a cool function here that can take any other recursive function (taking up to three parameters), and it will work nicely. But is it really the Y-Combinator? Well, we can check this by looking again at the discussion of [Fixed Points](https://beta.observablehq.com/@chriswhealy/mindshift-part-9#part2). A function is said to have a "fixed point" if, when you put in a particular value, you get exactly the same value out again. In the case of the cosine function (working in radians), the fixed point is 0.7390851332151607 because cos(0.7390851332151607) = 0.7390851332151607. However, there is no reason why the fixed point of a function should be a simple number such as 0.7390851332151607. It could just as easily be another function. The Y-Combinator is also known as the fixed-point combinator; therefore, we need to test whether we can supply it with a function, and then get out exactly the same function. If we can, then we know that we have successfully created the Y-Combinator. `50:T4a8,{ // The Y-Combinator var Y = (rec_fn => (gen_rec => U(gen_rec)) (gen_rec => rec_fn((n,a,b) => U(gen_rec)(n,a,b))) ) // Define functions to calculate the Fibonacci series and factorial // We can also tidy up the useability of the do_fib function so that the user does not need // to pass 0 and 1 as the sequence start values. Again, this is done by function wrapping var do_fib = fib_next => n => ((n,a,b) => n < 1 ? a : fib_next(n-1,b,a+b))(n,0,1); var do_fact = fact_next => n => n < 2 ? 1 : n * fact_next(n-1); // If we really have derived the Y-Combinator, then the following // assignments should give exactly the same results. // Y(f) === f(Y(f)); var fact1 = Y(do_fact); // fact_next => n < 2 ? 1 : n * fact_next(n-1) var fact2 = do_fact(Y(do_fact)); // fact_next => n < 2 ? 1 : n * fact_next(n-1) var fib1 = Y(do_fib); // fib_next => (n,a,b) < 1 ? a : fib_next(n-1,b,a+b) var fib2 = do_fib(Y(do_fib)); // fib_next => (n,a,b) < 1 ? a : fib_next(n-1,b,a+b) return { y_combinator_test_1_satisfied : fact1(5) === fact2(5), y_combinator_test_2_satisfied : fib1(20) === fib2(20) } } 51:T5fe,md`As can be seen, calling Y(do_fib) or Y(do_fact) gives exactly the same function as calling do_fib(Y(do_fib)) or do_fact(Y(do_fact)). So we can see that our function satisfies the criteria for being a valid Y-Combinator. Therefore function fact1 is the fixed point of function do_fact, and likewise, function fib1 is the fixed point of function do_fib. ## But This Y-Combinator Doesn't Look Like Haskell Curry's Y-Combinator That's true, and fortunately for me, there are infinitely many valid Y-Combinators so in that sense, it doesn't matter. However, at the start of this blog I promised to derive Haskell Curry's Y-Combinator. I guess this means we need to do a little more refactoring... However, for reasons that defy rational explanation, mathematicians seem to have a strong dislike for giving variables meaningful names. They seem to delight in concealing the meaning of variables by giving them intention-hiding names such as a or x, or the letters from the Greek or Hebrew alphabets, or characters written upside down or in strange type faces... So, let's follow mathematical convention and translate the meaningful variable names in our Y-Combinator into utterly meaningless, single character names. > At this point, it is very important that you suspend any desire to ask for rational explanations and just accept that rec_fn should now be called f. `52:T591,md`The next point to understand is that since JavaScript is a strict evaluation language, all expressions are evaluated before they are passed as parameters to other functions. This is why we hit the recursion limit when we tried to pass U(fib_next) as a parameter value back in step 3. However, other languages such as Haskell perform lazy evaluation. This means that expressions are not evaluated until their value is actually needed; consequently, such languages do not require the use of this workaround to avoid hitting the runtime recursion limit. Since we are using JavaScript however, we had to account for this problem by creating a wrapper function around the call to U(fib_next) to delay its execution. But by doing this, we transformed the combinator from a ***"normal order"*** combinator to an ***"applicative order"*** combinator. Normal order combinators can only be implemented in languages that perform lazy evaluation; whereas, for languages that perform strict evaluation, the applicative order combinator is required. (The applicative order combinator is also known as the Z-Combinator). However, if we pretend that JavaScript has suddenly become a lazy evaluation language, then the wrapper function (n,a,b) => x(x)(n,a,b) used to delay the execution of x(x) can be removed leaving a naked x(x) as the parameter to f:`53:T4ea,md`Et voilá! The Y-Combinator, as shown in [Wikipedia](https://en.wikipedia.org/wiki/Fixed-point_combinator#Derivation_of_the_Y_combinator). However, its fair to say that this, the most frequently cited version of the Y-Combinator, is far from intuitive - and its taken me several weeks to understand, and then a further three whole blogs to build up its derivation from first principles! I trust however, that in spite of number and length of these blogs, these explanations have been clear enough for you to follow and understand. Now that we know how the Y-Combinator works, we can proceed to define other mathematical functions such as DIVIDE and MODulus. Chris W

Previous Blog

Next Blog

#### Disclosure The content of my Mindshift blogs 9, 10 and 11 were based on a [YouTube video](https://www.youtube.com/watch?v=FITJMJjASUs) by the late (great) Jim Weirich in which he derives the Y-Combinator. In the video, Jim uses Ruby as his demonstration language, and I have translated his coding steps into JavaScript. `54:[] 48:{"id":"256e0b7678e40350","slug":"mindshift-part-11","title":"Mindshift: Part 11","thumbnail":"1c22b5b51e985a17f4338cd45120c07f322a445cd4af686265b4b6ba436e114b","access_level":"public","create_time":"$D2018-02-05T21:02:02.008Z","update_time":"$D2020-01-10T18:27:15.496Z","view_time":null,"first_public_time":"$D2018-02-05T22:26:41.330Z","has_unpublished_edits":null,"fork":false,"stars":0,"starred":false,"owner":{"type":"team","id":"224d52e60cffa1e1","login":"chriswhealy","name":"Chris Whealy","avatar_url":"https://avatars-next.observableusercontent.com/fe4f3dea84e903c1f07bbfa1cc8292304033a736d3ab9d0e5c009d1340bfefb8","tier":"starter_2024","bio":"","followed_by_you":false,"follows_you":false},"version":183,"publish_version":183,"role":null,"authored":false,"authors":[{"type":"individual","id":"c2414676c206a65f","login":"chriswhealy","name":"Chris Whealy","avatar_url":"https://avatars-next.observableusercontent.com/fe4f3dea84e903c1f07bbfa1cc8292304033a736d3ab9d0e5c009d1340bfefb8","tier":null,"bio":"","followed_by_you":false,"follows_you":false}],"members":[{"type":"individual","id":"c2414676c206a65f","login":"chriswhealy","name":"Chris Whealy","avatar_url":"https://avatars-next.observableusercontent.com/fe4f3dea84e903c1f07bbfa1cc8292304033a736d3ab9d0e5c009d1340bfefb8","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":1,"collection":null,"type":"notebook","body":{"titling":"auto","title":"Mindshift: Part 11","cells":[{"id":0,"value":"$4c","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":6,"value":"Y_Combinator = f => (x => f(x(x)))\n (x => f(x(x)))","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":10,"value":"md`BTW, ***do not*** try running the above JavaScript implementation shown above - it will blow up in your face for reasons that will soon be explained.\n\n## So, Where Did We Get Up To?\n\nBy the end of the previous blog, we had successfully calculated the Fibonacci sequence using nothing more than a recursive arrangement of anonymous functions.\n\nThe conceptual breakthrough came when we were able to get a function to call itself recursively without it needing to know its own name.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":15,"value":"{\n var fib_x = (fib_next => fib_next(fib_next))\n (fib_next => (n,a,b) => n < 1 ? a : fib_next(fib_next)(n-1,b,a+b));\n\n // Let's try calculating different numbers in the Fibonacci series...\n return {\n fib0 : fib_x(0,0,1),\n fib1 : fib_x(1,0,1),\n fib2 : fib_x(2,0,1),\n fib5 : fib_x(5,0,1),\n fib20 : fib_x(20,0,1),\n fib50 : fib_x(50,0,1),\n fib100 : fib_x(100,0,1),\n fib1474 : fib_x(1476,0,1)\n }\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":23,"value":"md`Our task here is to turn this function from one that implements the specific recursive function fib_next, into one that can handle _**any**_ recursive function.\n\nSo more refactoring is needed.\n\n\n## The Most Basic Combinators\n\nIn the simplest sense, a combinator is any function that takes some number of functions as parameters and combines them in some way.\n\nThe simplest of all combinators is known as the IDENTITY function - and it does nothing more than return its parameter completely unmodified.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":25,"value":"// The IDENTITY function returns its parameter without modification\nIDENTITY = val => val","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":28,"value":"md`Now that is a pretty dumb function!\n\nIn fact, [Dave Keenan](http://dkeenan.com/Lambda/) has rather humorously renamed it the IDIOT function - because it is too dumb to perform any processing on its parameter.\n\nAlthough we don't need to use it here, the IDENTITY function is not as useless as it might at first appear (for instance when you need to stop recursion, this function is very handy!)\n\nWe have however, already met two other very simple combinators; the TRUE and FALSE functions.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":30,"value":"// Combinator functions representing TRUE and FALSE\nTRUE = true_part => false_part => true_part","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":33,"value":"FALSE = true_part => false_part => false_part","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":36,"value":"md`Admittedly, we are stretching the definition of the verb *\"to combine\"* to its breaking point here because neither TRUE nor FALSE actually _**combine**_ their parameter values. They simply ignore one and return the other - but second only to the IDENTITY function, these are the simplest (dumbest?) of all combinators.\n\n### Recursive Combinators\n\nAs far as recursion is concerned, the recursive equivalent of the IDENTITY function is the Universal, or U-Combinator. This is a higher-order function that does nothing more than take a single function as a parameter and return whatever value is created by passing that function to itself. Under such circumstances, it is usual to expect a partial function as the return value.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":38,"value":"// The universal combinator\nU = fn => fn(fn)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":41,"value":"// Passing U to itself is a really bad idea because JavaScript will\n// promptly disappear down the rabbit hole of infinite recursion!\nU(U)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":44,"value":"md`As with IDENTITY, TRUE and FALSE, the universal combinator is not as useless as it looks; in fact, we've already been using it.\n\n\n## Deriving the Y-Combinator\n### Step 1: Apply the Universal Combinator\n\nNow that we know about the universal combinator, we can optimise our code (slightly). This particular step is not a requirement and can be omitted if desired - since right at the very end, we will remove this step anyway.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":46,"value":"{\n // Anytime a function calls itself as the only parameter, replace\n // this with a call to the universal combinator. So\n // var fib_x = (fib_next => fib_next(fib_next))\n // (fib_next => (n,a,b) => n < 1 ? a : fib_next(fib_next)(n-1,b,a+b));\n // becomes:\n var fib_x = (fib_next => U(fib_next))\n (fib_next => (n,a,b) => n < 1 ? a : U(fib_next)(n-1,b,a+b))\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":52,"value":"md`### Step 2: Encapsulate the Fibonacci Function\n\nWe know that the calculation of the Fibonacci series follows a step-wise execution pattern, so it would be good if we could isolate the parts of the function that encapsulate a single step of the calculation, then treat this in isolation from the parts that handle recursion.\n\nSo looking at our code, the Fibonacci function is where the actual calculation is performed, so lets isolate this code by applying Tennent's Correspondence Principle. This is where firstly, we take an expression and wrap it inside an anonymous function, then secondly, immediately call that function.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":54,"value":"{\n // Apply TCP to the Fibonacci function and add some indentation so\n // var fib_x = (fib_next => U(fib_next))\n // (fib_next => (n,a,b) => n < 1 ? a : U(fib_next)(n-1,b,a+b));\n // becomes:\n var fib_x = (fib_next => U(fib_next))\n (fib_next =>\n (() => (n,a,b) => n < 1 ? a : U(fib_next)(n-1,b,a+b))()\n );\n \n // As expected, TCP refactoring has no effect on the end result\n return fib_x(5,0,1);\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":57,"value":"md`Now that we have encapsulated the Fibonacci function inside a wrapper function, what value should we pass this wrapper?\n\n\n\n### Step 3: Separate the Calculation Code from the Recursion Code\n\nWe said above that we would like to separate those parts of the code that handle the actual calculation, from those parts that handle recursion. Further to this, we know that the unit of code that takes us another step along the Fibonacci series is the call to fib_next(fib_next) (which we've also identified as an example of the universal combinator U(fib_next)).\n\nSo, we can extract this recursive part of the code and make it a parameter to the new wrapper function. To achieve this, we need to do three things:\n\nFirstly, the partial function created by calling U(fib_next) becomes the parameter to our new wrapper function.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":59,"value":"{\n // First, pass U(fib_next) as a parameter to the wrapped Fibonacci function\n var fib_x = (fib_next => U(fib_next))\n (fib_next =>\n (() => (n,a,b) => n < 1 ? a : U(fib_next)(n-1,b,a+b))(U(fib_next))\n );\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":62,"value":"md`This has temporarily made the code unexecutable, but don't worry - we're taking things one step at a time.\n\nSecondly, we must create a variable name to identify the value of this parameter within the function. Since we know its going to be a partial function that takes the next step down the series, we can call it fib_next\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":67,"value":"{\n // Second, use fib_next as the parameter name for this value\n var fib_x = (fib_next => U(fib_next))\n (fib_next =>\n (fib_next => (n,a,b) => n < 1 ? a : U(fib_next)(n-1,b,a+b))(U(fib_next))\n );\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":71,"value":"md`Lastly, where we previously had the call to U(fib_next), we can replace this with the parameter name fib_next.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":74,"value":"{\n // Replace occurrences of U(fib_next) with the parameter name fib_next\n var fib_x = (fib_next => U(fib_next))\n (fib_next =>\n (fib_next => (n,a,b) => n < 1 ? a : fib_next(n-1,b,a+b))(U(fib_next))\n );\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":76,"value":"$4d","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":81,"value":"{\n // Wrap the call to U(fib_next) in a function to delay its invocation\n // This function must receive the three parameters used to calculate\n // the fibonacci series\n var fib_x = (fib_next => U(fib_next))\n (fib_next =>\n (fib_next => (n,a,b) => n < 1 ? a : fib_next(n-1,b,a+b))\n ((n,a,b) => U(fib_next)(n,a,b))\n );\n\n // Ah, that's better\n return fib_x(20,0,1);\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":86,"value":"$4e","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":92,"value":"{\n // Make the Fibonacci function a parameter to the recursion function\n var fib_x = (rec_fn =>\n (fib_next => U(fib_next))\n (fib_next => rec_fn((n,a,b) => U(fib_next)(n,a,b)))\n )(fib_next => (n,a,b) => n < 1 ? a : fib_next(n-1,b,a+b));\n\n // Check that everything still works as before...\n return fib_x(10,0,1);\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":94,"value":"md`### Step 6: Tidy Up The Pieces\n\nNow that the function to be called recursively has been isolated from the coding that performs the recursion, we can start to pull out the various pieces and give them reasonable names.\n\nFirst, the inline function passed to the recursion function does not need to be a hard-coded parameter; it can be extracted and given a name. Let's call it do_fib.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":96,"value":"{\n // Define a do_fib function that can calculate any number in the Fibonacci series\n var do_fib = fib_next => (n,a,b) => n < 1 ? a : fib_next(n-1,b,a+b);\n\n var fib_x = (rec_fn =>\n (fib_next => U(fib_next))\n (fib_next => rec_fn((n,a,b) => U(fib_next)(n,a,b)))\n )(do_fib);\n\n // Again, check that everything still works as before...\n return fib_x(10,0,1);\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":101,"value":"md`Next, it is no longer appropriate to use the internal variable name fib_next since we can now handle ***any*** recursive function. So let's rename fib_next to gen_rec, because this unit of code can \"generate recursive\" functions calls.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":103,"value":"{\n // Define a do_fib function that can calculate any number in the Fibonacci series\n var do_fib = fib_next => (n,a,b) => n < 1 ? a : fib_next(n-1,b,a+b);\n\n var fib_x = (rec_fn =>\n (gen_rec => U(gen_rec))\n (gen_rec => rec_fn((n,a,b) => U(gen_rec)(n,a,b)))\n )(do_fib);\n\n // Have we broken it?\n return fib_x(10,0,1);\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":107,"value":"md`Now that we have transformed our Fibonacci recursive function into a generic recursive function, we must do two further things: first, the name fib_x can be changed to Y (as in the Y-Combinator), and second, we can drop the (do_fib) parameter at the end of the definition of fib_x.\n\nThese two changes will now (finally) give us a general purpose Y-Combinator function.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":110,"value":"{\n // Define a do_fib function that can calculate any number in the Fibonacci series\n var do_fib = fib_next => (n,a,b) => n < 1 ? a : fib_next(n-1,b,a+b);\n\n // We now have a definition of the Y-Combinator\n var Y = (rec_fn =>\n (gen_rec => U(gen_rec))\n (gen_rec => rec_fn((n,a,b) => U(gen_rec)(n,a,b)))\n )\n\n // Now use the Y-Combinator as the framework within which any\n // function can be called recursively\n var fib = Y(do_fib);\n\n // Everything still works as before...\n return fib(10,0,1);\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":113,"value":"md`The only remnant left in this coding that betrays its prior usage for calculating the Fibonacci series is the fact that rec_fn is passed a function in three parameters. But this won't cause anything to break.\n\nIn fact, since we've derived our Y-combinator from a recursive function that requires three parameters, this solution will work with any recursive function that requires up to three parameters.\n\n\n## But Is This Really a General Purpose Recursive Function?\n\nUp till now, we've been working exclusively with the Fibonacci function. This was largely because everybody else who discusses recursion uses the Factorial function, and I just wanted to be different!\n\nNonetheless, let's create a factorial function and see how that works with our Y-Combinator.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":116,"value":"{\n // Define a do_fact function that calculates the factorial of a number\n var do_fact = fact_next => n => n < 2 ? 1 : n * fact_next(n-1);\n\n // We now have a definition of the Y-Combinator\n var Y = (rec_fn =>\n (gen_rec => U(gen_rec))\n (gen_rec => rec_fn((n,a,b) => U(gen_rec)(n,a,b)))\n )\n\n // Use the Y-Combinator to create a factorial function\n var fact = Y(do_fact);\n\n // The factorial of 5 should be 120...\n return fact(5);\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":121,"value":"$4f","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":128,"value":"md`

\n  // In order for a function to be a fixed-point combinator, it must satisfy the following requirement\n  Y(f) === f(Y(f));\n

\n\nSo using the relationship above, we already have a function called Y, and the function called f would be either the do_fib or do_fact functions.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":133,"value":"$50","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":143,"value":"$51","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":146,"value":"{\n // Change all meaningful variable names to meaningless ones\n // Rename rec_fn to f\n var Y = (f =>\n (gen_rec => U(gen_rec))\n (gen_rec => f((n,a,b) => U(gen_rec)(n,a,b)))\n )\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":149,"value":"md`Now gen_rec becomes x.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":151,"value":"{\n // Change all meaningful variable names to meaningless ones\n // Rename gen_rec to x\n var Y = (f =>\n (x => U(x))\n (x => f((n,a,b) => U(x)(n,a,b)))\n )\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":154,"value":"md`Now remove the use of the universal combinator U, and replace it with inline calls.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":156,"value":"{\n // Change all meaningful variable names to meaningless ones\n // U(x) changes back to x(x)\n var Y = (f =>\n (x => x(x))\n (x => f((n,a,b) => x(x)(n,a,b)))\n )\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":159,"value":"$52","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":163,"value":"{\n // Change all meaningful variable names to meaningless ones\n // Remove the wrapper function around x(x)\n var Y = (f =>\n (x => x(x))\n (x => f(x(x)))\n )\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":166,"value":"md`We must now understand that the above code can no longer be executed in JavaScript...\n\nLastly, the preferred mathematical style is to pass the results of the first call to x(x) to the recursive function f. As it happens, this turns out in this case to be a no-op.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":169,"value":"{\n // Change all meaningful variable names to meaningless ones\n // Wrap the first x(x) call in a call to f - which happens in this case to be a no-op.\n // Adjust the carriage returns and indentation to make it look pretty (mysterious)\n var Y = (f => (x => f(x(x)))\n (x => f(x(x))))\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":173,"value":"$53","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W54","stdlib":"1"}} 24:null