<story><title>Understanding the Y Combinator</title><url>https://8dcc.github.io/programming/understanding-y-combinator.html</url></story><parent_chain></parent_chain><comment><author>lacker</author><text>It&amp;#x27;s a shame that I like Y Combinator the organization so much, because I find the y combinator as a programming concept to be aesthetically displeasing.&lt;p&gt;It only makes sense in the untyped lambda calculus, where types are all conflated and errors are forbidden. It relies on the fact that you can take any x and &amp;quot;apply x to itself&amp;quot;. These properties are essentially gimmicks of the untyped lambda calculus. It&amp;#x27;s like the saying &amp;quot;Everything should be made as simple as possible, but not simpler.&amp;quot; The untyped lambda calculus, they made it even simpler.&lt;p&gt;Yes, you can reduce everything to a very tiny number of combinators, but at the cost of making everything ugly. It is much cleaner to use Lisp and reduce everything to a slightly larger set of primitives. Ironically (?) one of the best explanations of this is PG&amp;#x27;s own The Roots Of Lisp - &lt;a href=&quot;https:&amp;#x2F;&amp;#x2F;languagelog.ldc.upenn.edu&amp;#x2F;myl&amp;#x2F;llog&amp;#x2F;jmc.pdf&quot; rel=&quot;nofollow&quot;&gt;https:&amp;#x2F;&amp;#x2F;languagelog.ldc.upenn.edu&amp;#x2F;myl&amp;#x2F;llog&amp;#x2F;jmc.pdf&lt;/a&gt;</text></comment>
<story><title>Understanding the Y Combinator</title><url>https://8dcc.github.io/programming/understanding-y-combinator.html</url></story><parent_chain></parent_chain><comment><author>tromp</author><text>Note that with the standard representation of natural numbers in lambda calculus, the Church numerals [1], you don&amp;#x27;t even need the Y combinator to implement factorial:&lt;p&gt;&lt;pre&gt;&lt;code&gt;    fac = λn.λf.n(λf.λn.n(f(λf.λx.n f(f x))))(λx.f)(λx.x)
&lt;/code&gt;&lt;/pre&gt;
For example, applied to Church numeral 3 this gives (with F=(λf.λn.n(f(λf.λx.n f(f x))))):&lt;p&gt;&lt;pre&gt;&lt;code&gt;    fac 3 = \f. F (F (F (\x.f))) 1
          = \f. 1 (F (F (\x.f))  2)
          = \f. 1 (2 (F (\x.f)   3))
          = \f. 1 (2 (3 ((\x.f)  4)))
          = \f. 1 (2 (3 f))
&lt;/code&gt;&lt;/pre&gt;
which is the Church numeral for 1*2*3 = 6.&lt;p&gt;[1] &lt;a href=&quot;https:&amp;#x2F;&amp;#x2F;en.wikipedia.org&amp;#x2F;wiki&amp;#x2F;Church_encoding&quot; rel=&quot;nofollow&quot;&gt;https:&amp;#x2F;&amp;#x2F;en.wikipedia.org&amp;#x2F;wiki&amp;#x2F;Church_encoding&lt;/a&gt;</text></comment>