No Let, No Rec, No Problem: A Gentler Introduction to the Y and Z Combinators
1–10 of 11 posts
Re: No Let, No Rec, No Problem: A Gentler Introduction to the Y and Z Combinators
#2Here's a funny Z combinator in typescript in pure SKI form for lambda calculus purist:
const K = (a: A) => (_b: B) => a;
const S = (a: (x: C) => (y: B) => A) => (b: (x: C) => B) => (c: C) => a(c)(b(c));
const Z = S(K(S(S(K)(K))(S(K)(K))))(S(S(K(S))(K))(K(S(K(S(S)(S(K))))(S(S(K(S))(K))(K)))));
Re: No Let, No Rec, No Problem: A Gentler Introduction to the Y and Z Combinators
#3Good to see this in the second chance pool. Unfortunately I don't think most commenters know what the article is about and thus we may end up with this submission leaving the front page quickly, a shame though as the YC namesake is from similar articles as these, a company that produces other companies, as Paul Graham had said.
Re: No Let, No Rec, No Problem: A Gentler Introduction to the Y and Z Combinators
#4I feel like introducing lambda calculus (using JS syntax) would be less cumbersome and convoluted than referring to "the challenge" without really justifying it and deferring to respect the rules for so long. But maybe some people entirely unfamiliar with these concepts find this approach easier?
Re: No Let, No Rec, No Problem: A Gentler Introduction to the Y and Z Combinators
#5I feel like introducing lambda calculus (using JS syntax) would be less cumbersome and convoluted than referring to "the challenge" without really justifying it and deferring to respect the rules for so long. But maybe some people entirely unfamiliar with these concepts find this approach easier?
I found it extremely confusing.
It sets a challenge as a rhetorical tool, but then completely fails to honour the challenge through the bulk of the explanation.
- don’t use recursion: spends multiple paragraphs implying that a function calling itself isn’t recursion
- don’t use declaration: ignoring that defining arguments to a function is declaration
I’m not saying the article is “wrong”. But I thunk I’d have preferred a plain intro to lambda calculus.
(Writing this as someone who has struggled to learn “real” functional programming the few times I’ve tried over the past 20+ years, but who very much likes using RxJS and the functional flavour of lodash and wishes I could see deeper into that black hole.)
Re: No Let, No Rec, No Problem: A Gentler Introduction to the Y and Z Combinators
#6I feel like introducing lambda calculus (using JS syntax) would be less cumbersome and convoluted than referring to "the challenge" without really justifying it and deferring to respect the rules for so long. But maybe some people entirely unfamiliar with these concepts find this approach easier?
I found it extremely confusing. It sets a challenge as a rhetorical tool, but then completely fails to honour the challenge through the bulk of the explanation. - don’t use recursion: spends multiple paragraphs implying that a function calling itself isn’t recursion - don’t use declaration: ignoring that defining arguments to a function is declaration I’m not saying the article is “wrong”. But I thunk I’d have prefer…
So it's as confusing as I thought to do it that way. I wasn't sure if I thought so because I'm already familiar with all these concepts or because this introduction is indeed convoluted. Thanks for taking the time to reply!
Re: No Let, No Rec, No Problem: A Gentler Introduction to the Y and Z Combinators
#7I feel like introducing lambda calculus (using JS syntax) would be less cumbersome and convoluted than referring to "the challenge" without really justifying it and deferring to respect the rules for so long. But maybe some people entirely unfamiliar with these concepts find this approach easier?
I found it extremely confusing. It sets a challenge as a rhetorical tool, but then completely fails to honour the challenge through the bulk of the explanation. - don’t use recursion: spends multiple paragraphs implying that a function calling itself isn’t recursion - don’t use declaration: ignoring that defining arguments to a function is declaration I’m not saying the article is “wrong”. But I thunk I’d have prefer…
> don’t use recursion: spends multiple paragraphs implying that a function calling itself isn’t recursion
It did the opposite. It wrote many paragraphs of code and threw each one out as soon as recursion showed up.
Re: No Let, No Rec, No Problem: A Gentler Introduction to the Y and Z Combinators
#8I feel like introducing lambda calculus (using JS syntax) would be less cumbersome and convoluted than referring to "the challenge" without really justifying it and deferring to respect the rules for so long. But maybe some people entirely unfamiliar with these concepts find this approach easier?
I found this to be the most accessible introduction to the Y combinator I've yet read.
Re: No Let, No Rec, No Problem: A Gentler Introduction to the Y and Z Combinators
#9Earlier quoted context omitted.
I found it extremely confusing. It sets a challenge as a rhetorical tool, but then completely fails to honour the challenge through the bulk of the explanation. - don’t use recursion: spends multiple paragraphs implying that a function calling itself isn’t recursion - don’t use declaration: ignoring that defining arguments to a function is declaration I’m not saying the article is “wrong”. But I thunk I’d have prefer…
> don’t use recursion: spends multiple paragraphs implying that a function calling itself isn’t recursion It did the opposite. It wrote many paragraphs of code and threw each one out as soon as recursion showed up.
I’ll re-read it, because clearly I don’t get it. And I’d like to.
My first two attempts made it seem like it was building on a function calling itself, with itself as an argument (so that it can call itself). I’m not sure how that isn’t recursion, and I didn’t read it as throwing away those approaches. But, as I say, I’ll re-read it…
Re: No Let, No Rec, No Problem: A Gentler Introduction to the Y and Z Combinators
#10Earlier quoted context omitted.
> don’t use recursion: spends multiple paragraphs implying that a function calling itself isn’t recursion It did the opposite. It wrote many paragraphs of code and threw each one out as soon as recursion showed up.
I’ll re-read it, because clearly I don’t get it. And I’d like to. My first two attempts made it seem like it was building on a function calling itself, with itself as an argument (so that it can call itself). I’m not sure how that isn’t recursion, and I didn’t read it as throwing away those approaches. But, as I say, I’ll re-read it…
author here. the idea is to see how the Y and Z combinators come out relatively naturally given an extremely constrained context with no loops, no recursion, no bindings. the article is intentionally structured as a sequence of failed attempts that progressively reveal which phenomenon is still responsible for the recursive behaviour.
in the article, i define recursion narrowly as "... call the function `fact` from inside the definition of the function `fact`".
you're right that `factgen` is also not recursive but it is also rejected, but for a different reason: self-reference. declarations are banned precisely because they give a function a "name" that can be referenced later.
please note that the solution which uses Z combinator (given at the end) grows from `(x => x(x))(x => x(x))`, which is NOT self-referential. it achieves self-replication by literally rewriting the content of the function twice, which is different from self-referential recursion of `factgen`.
hope that clears some of the confusion.