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

Deriving the Y Combinator in JavaScript

enlight.nyc

Post reply on HN
Print view View original

11–20 of 23 posts

Re: Deriving the Y Combinator in JavaScript

#11

Post by rs86 »

18nleung wrote: post #3

Hi! Author here, and glad to see my writeup on HN. I’m a JS developer by trade, but I’ve recently started exploring FP/Haskell and came across the Y Combinator. The Y writeups currently online that I read were wonderful for a seasoned Haskell programmer, but I thought it would be great to explore the concept from a more FP beginner-friendly lens, and through a more familiar language - JavaScript. I hope this explorat…

Nice article but you can't write the Y-combinator in Haskell (or in simply typed lambda calculus). You can write it in the untyped lambda calculus.

"y = \f -> (\x -> f (x x)) (\x -> f (x x))" will fail to type check in haskell.

Also it would be cool to show that what the Y-combinator does is find a fixed point for a function. When you define fact as "function fact(f, n) {...}" you are actually defining it as "function fact(f) { n => ... }" and the Y-combinator finds a fixed point for fact. A fixed point is x such that f(x) = x. so fact(fact) = fact.

In lambda calculus _every_ function has a fixed point; In a simply typed lambda calculus it does not. This gives a way to define recursion as fixed points and not as circular references.

Re: Deriving the Y Combinator in JavaScript

#12

Post by rs86 »

jacobwilliamroy wrote: post #5
18nleung wrote: post #3

Hi! Author here, and glad to see my writeup on HN. I’m a JS developer by trade, but I’ve recently started exploring FP/Haskell and came across the Y Combinator. The Y writeups currently online that I read were wonderful for a seasoned Haskell programmer, but I thought it would be great to explore the concept from a more FP beginner-friendly lens, and through a more familiar language - JavaScript. I hope this explorat…

Is it impossible to write a y-combinator with space complexity O(1)? I'm in the very early stages of a comp/sci education and have not yet learned how to prove that something is impossible.

Space complexity will depend on the computational model you choose.

Re: Deriving the Y Combinator in JavaScript

#13

Post by lsiebert »

Retra wrote: post #4

Of course, if your language doesn't support recursion it probably doesn't have first-class functions either. It's pretty trivial to implement recursion if you can pass a function pointer around.

I mean, recursion is just a way of saving state on the program's call stack implicitly instead of explicitly in a stack data structure.

fundamentally recursion is syntactical sugar over loops and stacks, as assembly can show you.

C can do recursion. It can't do first class functions, though it can pass function pointers. It just can't create new functions dynamically based on non local variables, at least not without shenanigans.

Re: Deriving the Y Combinator in JavaScript

#14

Post by pitched »

lsiebert wrote: post #13
Retra wrote: post #4

Of course, if your language doesn't support recursion it probably doesn't have first-class functions either. It's pretty trivial to implement recursion if you can pass a function pointer around.

I mean, recursion is just a way of saving state on the program's call stack implicitly instead of explicitly in a stack data structure. fundamentally recursion is syntactical sugar over loops and stacks, as assembly can show you. C can do recursion. It can't do first class functions, though it can pass function pointers. It just can't create new functions dynamically based on non local variables, at least not without…

Functions are syntactic sugar on calls and calls are syntactic sugar on jumps so those dynamic shenanigans would be messing with calling conventions? That might not be too ridiculous.

Re: Deriving the Y Combinator in JavaScript

#17

Post by aappleby »

18nleung wrote: post #3

Hi! Author here, and glad to see my writeup on HN. I’m a JS developer by trade, but I’ve recently started exploring FP/Haskell and came across the Y Combinator. The Y writeups currently online that I read were wonderful for a seasoned Haskell programmer, but I thought it would be great to explore the concept from a more FP beginner-friendly lens, and through a more familiar language - JavaScript. I hope this explorat…

Some uncanny similarities to my version - https://medium.com/@tanjent/refactoring-out-a-y-combinator-9...

Re: Deriving the Y Combinator in JavaScript

#18

Post by anothergoogler »

aappleby wrote: post #17
18nleung wrote: post #3

Hi! Author here, and glad to see my writeup on HN. I’m a JS developer by trade, but I’ve recently started exploring FP/Haskell and came across the Y Combinator. The Y writeups currently online that I read were wonderful for a seasoned Haskell programmer, but I thought it would be great to explore the concept from a more FP beginner-friendly lens, and through a more familiar language - JavaScript. I hope this explorat…

Some uncanny similarities to my version - https://medium.com/@tanjent/refactoring-out-a-y-combinator-9...

What similarities are you talking about? I'm not seeing it.

Re: Deriving the Y Combinator in JavaScript

#19

Post by rustler »

lsiebert wrote: post #13
Retra wrote: post #4

Of course, if your language doesn't support recursion it probably doesn't have first-class functions either. It's pretty trivial to implement recursion if you can pass a function pointer around.

I mean, recursion is just a way of saving state on the program's call stack implicitly instead of explicitly in a stack data structure. fundamentally recursion is syntactical sugar over loops and stacks, as assembly can show you. C can do recursion. It can't do first class functions, though it can pass function pointers. It just can't create new functions dynamically based on non local variables, at least not without…

> fundamentally recursion is syntactical sugar over loops and stacks, as assembly can show you.

That's one possible implementation of recursion on commodity hardware. Recursion itself is a mathematical method for defining a function which may not even be computable, or may be computable using other primitives.

Post reply on HN