Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

The Y Combinator (no, not that one) – A Crash Course on Lambda Calculus

medium.com

Post reply on HN
Print view View original

31–40 of 51 posts

Re: The Y Combinator (no, not that one) – A Crash Course on Lambda Calculus

#31

Post by anatoly »

tel wrote: post #23
anatoly wrote: post #8

Has the Y combinator been useful to anything? Has it been used in any software in a role other than pedagogic? It's a beautiful way to make a recursive call without binding the function to an identifier, but has it actually proven useful? It would seem that languages that allow that make it easy to use the Y combinator also typically make it easy to use named recursion with a permanent or a temporary name.

Well, in 1936 Church invented the LC in order to serve as a foundational logic for mathematics. This was around the time that Hilbert's Program was attempting to totally mechanize reasoning through rich logical languages and Church wanted to use LC to define the notion of "efficiently computable" which was part of Hilbert's specification. The Y-combinator was discovered originally as a flaw in the LC. It meant that y…

> (λ x . (x x)) (λ x . (x x))

This shows an infinite loop in lambda calculus evaluation. It can be arrived at independently (and I'd be surprised if it hadn't been) just by trying to build the simplest expression that doesn't reduce. Why do you need the Y combinator for this?

Re: The Y Combinator (no, not that one) – A Crash Course on Lambda Calculus

#32

Post by ayanonagon »

drdeca wrote: post #28

There appears to by a typo in one of the lines. The line 6 * (if 3 == 0 then 1 else 1 * (YF)(1–1)) The previous line is 6 * (λx.(if x == 0 then 1 else x * (YF)(x–1)) 1) When replacing the x s with 1s, it replaces one of the x s with 1, but replaces the first one with 3. My guess was that this was copied from the first version, and they just forgot to change one of the threes to a 1. (that is, unless I misunderstood s…

Nice catch, thank you. I've fixed it now. :)

Re: The Y Combinator (no, not that one) – A Crash Course on Lambda Calculus

#33

Post by [deleted] »

tel wrote: post #22
im3w1l wrote: post #16

tl;dr A fixed point p for a function f, is a value so that f(p)=p. A semi-recursive function f is a like a recursive function, except that instead of invoking itself, it invokes some other function provided as an argument to f. The y-combinator (aka fixed-point-combinator) is a function, that for a function f, finds a fixed point for f. We can turn a semi-recursive function f into the corresponding recursive function…

Also, and a big also, the Y-combinator exists in (untyped) lambda calculus---e.g. all you need is abstraction and application. This came as a shock to Church when he invented it as he wanted to use LC as a language for mathematical logic and fixed point combinators spell out doom for logical purposes. He thus invented the simply typed lambda calculus to banish such constructions.

[deleted]

Re: The Y Combinator (no, not that one) – A Crash Course on Lambda Calculus

#35

Post by sklogic »

anatoly wrote: post #8

Has the Y combinator been useful to anything? Has it been used in any software in a role other than pedagogic? It's a beautiful way to make a recursive call without binding the function to an identifier, but has it actually proven useful? It would seem that languages that allow that make it easy to use the Y combinator also typically make it easy to use named recursion with a permanent or a temporary name.

Yes, it is useful. For example, if you want to bootstrap a language implementation from the smallest possible subset, with a very trivial interpreter, then using Y-combinator as a way to implement recursion is reasonable (after all, performance does not matter for the bootstrap phase). See an example of such a use in https://github.com/combinatorylogic/mbase/blob/master/src/l/...

Re: The Y Combinator (no, not that one) – A Crash Course on Lambda Calculus

#36

Post by JimmyM »

agumonkey wrote: post #26
derengel wrote: post #11

From The Little Schemer - http://www.ccs.neu.edu/home/matthias/BTLS/sample.pdf That chapter made me grok the Y Combinator.

Still wishing more people read that book. It is not overrated.

I love Racket, and thus Schemes of many kinds, but that chapter is really difficult for me to read compared to more academic or technical approaches - and I am really not an academic or technical person!

I find the use of some sort of Socratique dialogue to be deeply confusing, distracting and frustrating. Creepy, SCP-foundation or Welcome-to-Nightvale-like asides such as "We did not expect you to know this." only add to my confusion. It makes simple concepts like recursion look like some sort of House of Leaves nightmare world.

Re: The Y Combinator (no, not that one) – A Crash Course on Lambda Calculus

#37

Post by jng »

anatoly wrote: post #29
jng wrote: post #12

Earlier quoted context omitted.

Hey. You're completely missing it. The Y combinator shows that full general computation, including recursion and iteration, derives automatically and inevitably from just basic rewrite rules. Obviously it is too raw to be used directly. But if you design/implement any system with rewrite rules, you have provided indefinite power for recursions, and you have opened the Pandora box of undecidable-termination. This mean…

>derives automatically and inevitably from just basic rewrite rules. Sorry, I don't understand what that means. Also, (lambda x: x(x))(lambda x: x(x)) already gives you an infinite loop, so why do you need a Y combinator to show non-termination? Once you have functions as first-class citizens that you can copy around, you've lost control of termination. Seems pretty intuitive. What's the specific contribution of the…

">derives automatically and inevitably from just basic rewrite rules."

I said "full general computation, including recursion and iteration, derives automatically and inevitably from just basic rewrite rules". You can't cut a sentence wherever you want and still think you're responding to the original thought.

There is an imprecision in my original comment, but it's not there. If you can stop nitpicking long enough, you may be able to see something that's pretty powerful.

Re: The Y Combinator (no, not that one) – A Crash Course on Lambda Calculus

#38

Post by vertex-four »

jng wrote: post #37
anatoly wrote: post #29

Earlier quoted context omitted.

>derives automatically and inevitably from just basic rewrite rules. Sorry, I don't understand what that means. Also, (lambda x: x(x))(lambda x: x(x)) already gives you an infinite loop, so why do you need a Y combinator to show non-termination? Once you have functions as first-class citizens that you can copy around, you've lost control of termination. Seems pretty intuitive. What's the specific contribution of the…

">derives automatically and inevitably from just basic rewrite rules." I said "full general computation, including recursion and iteration, derives automatically and inevitably from just basic rewrite rules". You can't cut a sentence wherever you want and still think you're responding to the original thought. There is an imprecision in my original comment, but it's not there. If you can stop nitpicking long enough, y…

Thanks for the assertion that everybody can understand you when you use terms without defining them. Not everybody here is so lucky as to have the same educational background as you.

What is a rewrite rule? To me, it's something you put in a web server configuration.

Re: The Y Combinator (no, not that one) – A Crash Course on Lambda Calculus

#39

Post by chriswarbo »

anatoly wrote: post #8

Has the Y combinator been useful to anything? Has it been used in any software in a role other than pedagogic? It's a beautiful way to make a recursive call without binding the function to an identifier, but has it actually proven useful? It would seem that languages that allow that make it easy to use the Y combinator also typically make it easy to use named recursion with a permanent or a temporary name.

Named recursion requires a notion of time, which is clear from your distinction between "permanent" and "temporary" names. This can add unnecessary complexity.

Let's use an analogy: is it ever useful to call a function with another function's return value?

    p = \q. f (g q)
We can implement the same thing using named arguments with permanent or temporary names, for example:

    p = \q. let g_of_q = g q
             in f g_of_q
That forces us to write the same boilerplate every time. We can do better by encapsulating it in a function (DRY):

    compose = \a. \b. \c. let b_of_c = b c
                           in a b_of_c
    p = compose f g
The Y/Z combinators do exactly the same job as compose, except for self-application rather than chained application. They let us write down what we mean, directly, without having to break it up into artificial chunks and chain them back together. Notice that the final definition of "p" doesn't even need a lambda abstraction, since the function is being calculated automatically rather than defined manually.

For example, I've used the Z combinator when defining arrays of functions in PHP. Without it, I'd have to define the functions separately, using brand-new function abstractions to inherit the self-reference (which is horribly verbose in PHP), then combine them into an array; or I'd have to define them separately, using brand-new function abstractions to inherit the array, then combine them into the array. Either way, it would add a bunch of complexity and boilerplate.

Re: The Y Combinator (no, not that one) – A Crash Course on Lambda Calculus

#40

Post by tel »

anatoly wrote: post #31
tel wrote: post #23

Earlier quoted context omitted.

Well, in 1936 Church invented the LC in order to serve as a foundational logic for mathematics. This was around the time that Hilbert's Program was attempting to totally mechanize reasoning through rich logical languages and Church wanted to use LC to define the notion of "efficiently computable" which was part of Hilbert's specification. The Y-combinator was discovered originally as a flaw in the LC. It meant that y…

> (λ x . (x x)) (λ x . (x x)) This shows an infinite loop in lambda calculus evaluation. It can be arrived at independently (and I'd be surprised if it hadn't been) just by trying to build the simplest expression that doesn't reduce. Why do you need the Y combinator for this?

It had been. Everyone was just talking about the Y-combinator so I derived from there, but Omega was first.

Once you have any fixed-point, though, deriving the others is trivial. The explosive self-referential nature of your system has been uncovered.

Post reply on HN