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

[ Return /
Go to bottom ]

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?

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

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

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

Y is a combinator satisfying the relation

Y F = F (Y F)

Indeed,

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

end

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

Y F = F (Y F)

Indeed,

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

end

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.

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.

>>22571

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.

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

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

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

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