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

Understanding the Y Combinator

8dcc.github.io

Post reply on HN
Print view View original

41–50 of 73 posts

Re: Understanding the Y Combinator

#41

Post by marvinborner »

Joker_vD wrote: post #23
marvinborner wrote: post #19

Earlier quoted context omitted.

In lambda calculus, you could use a variadic fixed point combinator to solve such recurrence relations elegantly

But you don't need to solve these, they're solved already: these four definitions are non-recursive. Yet when evaluated, they will exhibit properly recursive behaviour. The only reason to use Y combinator in practice is when you for some reason don't want to keep manually passing the function to itself like "func fact(self, n) { return (n < 1) ? 1 : n * self(self, n-1) }; print(fact(fact, 5))" — maybe because it's te…

Yes, I realize that. However, the alternative using a variadic fixed point combinator looks slightly cleaner and would (optimally) reduce to the same term. For example, using a list-based vfix:

    even' _ odd n = if n == 0 then True else (odd (n - 1)))
    odd' even _ n = if n == 0 then False else (even (n - 1))
    even = head $ vfix [even', odd']
    odd = tail $ vfix [even', odd']
Here, the functions don't need to be passed explicitly to the "recursive" calls. I prefer this a lot, it makes my lambda functions much more readable.

Re: Understanding the Y Combinator

#43

Post by photochemsyn »

ewuhic wrote: post #17

Cool article, BUT! it leaves so many terms unexplained: - What's the distinction between a "parameter`, a "variable", and an "argument"? - What is "body" as in "Body M"? - What's a "bound" variable? - What exactly is a "function call"? - In "... a value that is mapped to itself by the function.", what do "mapped to itself", and, more specifically, "mapped" mean? Would appreciate the answers!

This explains the basic structure and definition of terms pretty well, i.e. body, variable, expression, head etc. Has links to more comprehensive coverage:

https://palmstroem.blogspot.com/2012/05/lambda-calculus-for-...

Shows how to implement counting, addition, multiplication in Python:

https://www.youtube.com/watch?v=9pmI-KK4dIA

Re: Understanding the Y Combinator

#44

Post by moi2388 »

saberience wrote: post #32
tromp wrote: post #14

Earlier quoted context omitted.

> I still have issues with practical examples like the above. What issues would those be? Do you see that λf.λx.n f(f x)) is the Church numeral n+1 ? I think there's few better ways to grok lambda calculus than working through examples like these step-by-step.

What's a church numeral?

This explains it well imo https://www.cs.rice.edu/~javaplt/311/Readings/supplemental.p...

Re: Understanding the Y Combinator

#46

Post by pdonis »

marcellus23 wrote: post #36
pdonis wrote: post #35

Note to article writers: (1) Black on white is much easier to read than white on black. That includes code snippets in blocks. (2) If you insist on ignoring (1), at least make your white text bright enough that it can be read without serious eye strain. Particularly if the white on black is code snippets surrounded by black on white article text.

The article is black on white for me. Are you sure you don't have an extension enabled or something?

As the last sentence of my (2) shows, the article itself is black on white for me too, but the code snippets are white (very faint white that I can't read without serious eyestrain) on black.

Re: Understanding the Y Combinator

#47

Post by tromp »

lacker wrote: post #38

It'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. 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 "apply x to itself". These properties are essentially gimmicks of the untyped lambda calculus. It's like the…

Between lambda calculus and LISP, I find LISP to be the ugly one, not only because of its far greater complexity, but also its lack of referential transparency. David Turner / Ben Lynn make some good observations about LISP in section "History versus myth" of [1]. If lack of types is what you dislike of the plain lambda calculus, then Haskell is a much better solution than LISP.

[1] https://crypto.stanford.edu/~blynn/lambda/lisp.html

Re: Understanding the Y Combinator

#48

Post by notpushkin »

tromp wrote: post #47
lacker wrote: post #38

It'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. 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 "apply x to itself". These properties are essentially gimmicks of the untyped lambda calculus. It's like the…

Between lambda calculus and LISP, I find LISP to be the ugly one, not only because of its far greater complexity, but also its lack of referential transparency. David Turner / Ben Lynn make some good observations about LISP in section "History versus myth" of [1]. If lack of types is what you dislike of the plain lambda calculus, then Haskell is a much better solution than LISP. [1] https://crypto.stanford.edu/~blynn…

And IIRC, the fixed-point combinator can be defined in Haskell in a way not dissimilar to lambda’s Y combinator itself:

  fix :: (a -> a) -> a
  fix f = f (fix f)
(I’d say it’s even more aesthetically pleasing, even if a bit way too simple.)

Re: Understanding the Y Combinator

#49

Post by kazinator »

nextaccountic wrote: post #16
redbell wrote: post #4

Well, I have to confess I was misled by the title! I was under the impression that the article was about YC, but it turned out to be about mathematics. Ironically, the below quote is still relevant to YC, I believe: > 8. Applications of the Y combinator > You might be wondering what makes the Y combinator so special.

The name Y Combinator is a metaphor: startup growth is "recursive" in a sense and Y Combinator builds such "recursive" companies out of a non-recursive input (the founders themselves) Also Paul Graham is a Lisp nerd (Note, I tried to find an authoritative source on how the name was chosen - the only thing I found was https://paulgraham.com/ycstart.html that lists when, but not how the name came to be; but I think thi…

To me, the "combinator" part is quite obviously an earcorn pun on "incubator".

Re: Understanding the Y Combinator

#50

Post by hollerith »

hollerith wrote: post #40
lacker wrote: post #38

It'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. 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 "apply x to itself". These properties are essentially gimmicks of the untyped lambda calculus. It's like the…

>It only makes sense in the untyped lambda calculus Is that really true? ISTR you can impose the type (A -> A) -> A on the Y combinator.

Here is Haskell code in which the Y combinator (named "fix" in the code) is given the type (a -> a) -> a:

https://play.haskell.org/saved/ndm83XBr

This next a very simple Haskell program that just prints the first 8 non-negative integers:

  main = putStrLn $ show $ take 8 $ iterate (+ 1) 0
The linked code is just an elaboration of that where instead of using the built-in "iterate" we define an equivalent "iterate2".

Usually to define iterate2 a Haskell programmer would use recursion (i.e., call iterate2 inside the definition of iterate2) but today we avoid the need for a recursive call by using the Y combinator.

This disproves the assertion that the Y combinator "only makes sense in the untyped lambda calculus" because the Haskell compiler gives a type to every entity in the linked code.

Post reply on HN