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

21–30 of 73 posts

Re: Understanding the Y Combinator

#21

Post by jerf »

quibono wrote: post #9
tromp wrote: post #5

Note that with the standard representation of natural numbers in lambda calculus, the Church numerals [1], you don't even need the Y combinator to implement factorial: fac = λn.λf.n(λf.λn.n(f(λf.λx.n f(f x))))(λx.f)(λx.x) For example, applied to Church numeral 3 this gives (with F=(λf.λn.n(f(λf.λx.n f(f x))))): 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)))…

Hey tromp, do you have any recommendations for grokking Lambda calculus properly? I've read a few tutorials and introductions, and I understand the notions of alpha- and beta-reductions, abstractions vs application, but I still have issues with practical examples like the above. Am I missing something here or should I just go back to the basics?

Have you tried actually implementing things with it? You're obviously not going to implement a web browser, but basic math, some sort of basic strings, lots of other things with a focus on "basic" because even with functions you're working at an awfully low level here?

You can read definitions and commentary on those definitions until the cows come home but until you actually use it you're not going to get it. Like most math.

Re: Understanding the Y Combinator

#22

Post by dotancohen »

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.

  > 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.
What gave it away for me was the define article "the". The "the" would have been absent had the article been about the company.

That was very difficult to write while avoiding puns!

Re: Understanding the Y Combinator

#23

Post by Joker_vD »

marvinborner wrote: post #19
Joker_vD wrote: post #15

Earlier quoted context omitted.

let odd'(n, odd, even) = if n == 0 then False else even(n-1, odd, even) let even'(n, odd, even) = if n == 0 then True else odd(n-1, odd, even) let odd(n) = odd'(n, odd', even') let even(n) = even'(n, odd', even') Look ma, no hands! Well, actually, it is explicit closure-conversion done by hand so... anyhow, there are more straightforward and performant ways to get recursion in practice.

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 tedious and error-prone, — and don't have a sufficiently ergonomic term-rewrite system at hand that would do this for you.

Re: Understanding the Y Combinator

#24

Post by jerf »

mikewarot wrote: post #3

I'd really like to understand why my brain screams NO when I try to grok lisp and especially the Y combinator. It's like it's anti-interesting to me or something. I know it's cool, and useful to know, but I just can't get there. Maybe it's a stack overflow in my head? Is it just me? [Edit] Re:082349872349872 - I grew up in a world of assembler programming, BASIC and Pascal. It wasn't unusual to have all sorts of self…

To the other fine replies, I'd add what I posted elsewhere: Have you actually tried to implement things in lambda calculus? Until you do it won't ever really click.

That said, to be clear, I haven't and I don't plan to, so don't read this as a moralistic claim that you "should" do this. To the extent that I care about lambda calculus itself at all, it is that I accept it as yet another Turing-complete representation, and then move on, because it's only marginally more useful to write things in lambda calculus than in Turing machines directly. This is a true logical if-then statement: If you want to understand this, then you'll need to actually work with it for a bit. But I have no comment as to whether you should want that.

Re: Understanding the Y Combinator

#25

Post by [deleted] »

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.

[deleted]

Re: Understanding the Y Combinator

#27

Post by louthy »

quibono wrote: post #9
tromp wrote: post #5

Note that with the standard representation of natural numbers in lambda calculus, the Church numerals [1], you don't even need the Y combinator to implement factorial: fac = λn.λf.n(λf.λn.n(f(λf.λx.n f(f x))))(λx.f)(λx.x) For example, applied to Church numeral 3 this gives (with F=(λf.λn.n(f(λf.λx.n f(f x))))): 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)))…

Hey tromp, do you have any recommendations for grokking Lambda calculus properly? I've read a few tutorials and introductions, and I understand the notions of alpha- and beta-reductions, abstractions vs application, but I still have issues with practical examples like the above. Am I missing something here or should I just go back to the basics?

For a visual representation, the classic "To Dissect a Mockingbird" is always good:

https://dkeenan.com/Lambda/

Re: Understanding the Y Combinator

#29

Post by sva_ »

mikewarot wrote: post #3

I'd really like to understand why my brain screams NO when I try to grok lisp and especially the Y combinator. It's like it's anti-interesting to me or something. I know it's cool, and useful to know, but I just can't get there. Maybe it's a stack overflow in my head? Is it just me? [Edit] Re:082349872349872 - I grew up in a world of assembler programming, BASIC and Pascal. It wasn't unusual to have all sorts of self…

This talk by Jim Weirich made me grok it and was entertaining enough to follow through:

https://m.youtube.com/watch?v=FITJMJjASUs

It's from rubyconf but it isn't about ruby really.

Re: Understanding the Y Combinator

#30

Post by seanhunter »

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!

I'll take one of these.

> In "... a value that is mapped to itself by the function.", what do "mapped to itself", and, more specifically, "mapped" mean?

A mathematical function is something more general than a function in programming. In maths, a function consists of two sets known as the domain and codomain and a rule which "maps" things in the domain into the associated things in the codomain[1]. You can think about the domain as all the possible inputs to the function and the codomain being a set which at least contains all the possible outputs from the function.

So say the rule of my function is f(x) = sin(x) and for simplicity I say the domain is real numbers greater than or equal to zero but less than 2pi, then the function "maps" any value in that domain to a value in its codomain (which in this case will be real numbers from -1 to 1).

And what it's actually doing when it maps a number is it applies "sin" to that number to find the value in the codomain (which in computer science we would call the return value of the function).

So when the author talks about fixed points being values which are mapped onto themselves by the function they are values in the domain where you apply the rule of the function and you get back the same value. So for f(x) = sin(x), 0 would be such a value because sin(0) = 0. Say my function is f(x) = x^3, then 0, 1 and -1 are fixed points, because f(-1) = (-1)^3 = -1, and you can see the same applies to f(0) and f(1).

As a bonus, if my rule is f(x) = sin(x), then "x" is a "parameter" or "argument" to the function, because it is the name I give to a value that is passed into the rule of my function. It is also a variable because it's a name for a thing which varies but not all variables get used as parameters to functions. For example if I write y = f(x), then y is a variable which is not any kind of parameter for example.

Hope that helps.

[1] I suppose technically into the "image set" of the function, which is a subset of the codomain comprising the actual output values of the function only.

Post reply on HN