[ art / civ / cult / cyb / diy / drg / feels / layer / lit / λ / q / r / sci / sec / tech / w / zzz ] archive provided by lainchan.jp

lainchan archive - /λ/ - 22281

File: 1488025457199.png (16.87 KB, 300x225, d0800ccb6a2011d34dab924ac86c01f0.jpg)


For some days I've been trying to wrap my head around the Y combinator. I've tried to follow through the amazing article explaining the Y combinator in javascript, but got lost pretty quickly.
Would you like to share some articles or papers that helped you to understand the Y combinator?


File: 1488055155919.png (1.96 MB, 200x200, The_Little_Schemer.djvu)

It's in chapter 9 but you should read the whole thing. It's lots of fun.

This is roughly the same thing if you already know Scheme: ftp://ftp.cs.indiana.edu/pub/scheme-repository/doc/pubs/Y.ps.gz


Thanks a lot, The Little Schemer indeed seems to be a lot of fun. I would have really enjoyed a book like this back in high school. I also intend to look into The Little Prover and The Little MLe later.


File: 1489841130294.png (145.52 KB, 117x200, 1436253616038.jpg)

Y is a combinator satisfying the relation
Y F = F (Y F)
Y F = (λ x. (F (x x)) λ x. (F (x x)))
Then, by applying the first function λ x. (F (x x)) to λ x. (F (x x)), you get:
Y F = F (λ x. (F (x x)) (λ x. (F (x x)))
ie: Y F = F (Y F)

You can extrapolate by saying that Y F = F(F(F(...F(Y F)...)

Let's take an example of F (in pseudo-code):
F g x =
>> if x == 0 then return 1
>> else return g(x-1)*x

The intuitive meaning of (Y F) is that it is a recursive function where g is replaced by (Y F). Remember how parenthesization of lambda-terms works: F g x = (F g) x, so (Y F) x = (F (Y F)) x = F (Y F) x.

For instance (Y F) 2 = F (Y F) 2, and if we expand the definition of the first F, we get:
>> if 2 == 0 then return 1
>> else return ((Y F) (2-1))*1
which simplifies into:
((Y F) 1)*2

As ((Y F) 1)*2 = (F (Y F) 1)*2, you get:
>> (if 1 == 0 then return 1
>> else return ((Y F) (1-1))*1)*2
which simplifies into (((Y F) 0)*1)*2.

(Y F) 0 returns 1, so the whole expression simplifies to ((1)*1)*2 --> 2


I honestly don't understand how the damn thing works, I've walked through expanding it in Scheme once while reading The Little Schemer, but I don't think I got much out of that other than being like "wow, this soykaf works".
I just know it's there and it works, and I can use it when I need it. I'm probably not gonna have to implement it or something similar myself, so I'm content with that.


the Y combinator is a function that passes a function to itself as one of that function's arguments.

the passed function can be written to have looping behavior by calling the function it's passed -- which is itself. which it passes the passed function to. which, being itself, does the same thing.

this gives iterative behavior without magical iteration constructs. all you need is function application. and infinite RAM to hold all of these call stacks that you need for something that would ordinarily occupy fixed memory. but in practice tail-calls are optimized and the functions passed to the Y combinator can be written to run in fixed memory.

  : y ( ... xt -- ... )
dup execute ;

: (upto) ( n1 n2 xt xt-self -- ) locals| self xt |
2dup = if 2drop exit then
dup xt execute 1+ xt self y ;
: upto ( n xt -- )
0 swap ['] (upto) y ;

: .upto ( n -- )
['] . upto ;

  $ gforth -e 'include yc.fs 10 .upto bye'
0 1 2 3 4 5 6 7 8 9



Here's an amusing talk. The guy takes a recursive function apart and arrives at the Y combinator.