4 ms·

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 somethi

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-interacting code, and deliberate use of the same half of a routine in more than one function. I get why Lambda is useful, why bother naming a function you're only going to use once. But it seemed like infinite pedantry to go about using it to do recursion... thanks! [Edit2] Re:082349872349872 - I once came upon old code that lived in a S-100 disk controller, it seemed really weird until I realized they couldn't call a subroutine because they couldn't assume there was a properly set stack. It used one of the 8080 registers as a return pointer.

sph 2y ago
It might be you. But your profile says you have been programming since 1979, so I humbly defer to your experience. If you have made it this far without Lisp, I guess you don't need it, friend :-) Take it from a younger programmer, you don't have to grok lambda calculus to understand Lisp. I like Lisp, but I only have a vague notion of lambda calculus and all that academic gobbledygook. I still do not understand the Y combinator, nor I very much care to. CS theory is good and all, but it's importance is often overstated. Physicists are not engineers and engineers are not physicists; you can be a very effective programmer without knowing about Peano numbers and what monads are.
082349872349872 2y ago
If you grew up programming in a world where self-reference is (due to linking pass or interpretation) trivial, the Y combinator is nearly useless: why should a function not be able to call itself, like we do every day? However, if you're a pedant, and only accept definitions that are in terms of things other than themselves, then you'll need something like the Y combinator to even define, let alone invoke, recursive functions. (there was a period* of a decade or two where systems people wrote recursive functions and theory people said "yes, it works in practice, but does it work in theory?", but now even theorists have a pedantic way to both describe functions in terms of themselves [syntactically] and agree that such a description denotes a unique function [semantically], so now we have our cake and eat it: a toolchain will go right ahead and generate fixups for the object that point back into itself, while a thesis will drop names like Tarski or Brouwer and maybe typeset another greek character or two) * which may have overlapped with the period where people preferred one-pass to two-pass tools because manually stuffing paper tape back into the reader between passes was a pain? EDIT: extreme pedantry: it surprises me that there was also a decade or so between LABEL and LABELS; going from single recursion to mutual recursion is a very small change in the underlying interpreters, yet even lispers were too pragmatic to have bothered to do so. EDIT2: upon reflection, this was also the period of time where having a stack was viewed as a complexity which was certainly convenient but not exactly necessary. With the benefit of hindsight, I'd argue that mutual tail recursion is useful even without a stack, but can see that at the time that might've been viewed as architecture astronaut talk.
laszlokorte 2y ago
You might find my write-up on lambda calculus and combinatory logic in javascript syntax insightful: https://static.laszlokorte.de/combinators/ https://static.laszlokorte.de/combinators/
Joker_vD 2y ago
No, you're probably not alone. I myself enjoy functional programming quite a lot but Y combinator always stood out to me as a particularly uninteresting trick. Sure, it's nice to have it around when you try to prove some theoretical stuff but for practical work letrec is just better. I mostly feel the same about the Church encoding of e.g. lists: yeah, it's a nice theoretical trick that you can equate a list xs with a function that gives your its fold but... that's just so inconvenient to actually use! Why not equate it with either a nil or a tuple of head and tail instead? def empty_list(onEmpty, onNonEmpty): return onEmpty() def make_a_non_empty_list(head, tail): def non_empty_list(onEmpty, onNonEmpty): return onNonEmpty(head, tail) return non_empty_list
jerf 2y ago
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.
sva_ 2y ago
This talk by Jim Weirich made me grok it and was entertaining enough to follow through: https://m.youtube.com/watch?v=FITJMJjASUs https://m.youtube.com/watch?v=FITJMJjASUs It's from rubyconf but it isn't about ruby really.
lacker 2y ago
The Y combinator is not really a "lisp thing", it's more of a "functional programming" thing. In Lisp, symbols and binding values to a symbol are basic elements of the language, so it usually wouldn't be natural to use the Y combinator.

sph 2y ago

It might be you. But your profile says you have been programming since 1979, so I humbly defer to your experience. If you have made it this far without Lisp, I guess you don't need it, friend :-) Take it from a younger programmer, you don't have to grok lambda calculus to understand Lisp. I like Lisp, but I only have a vague notion of lambda calculus and all that academic gobbledygook. I still do not understand the Y combinator, nor I very much care to. CS theory is good and all, but it's importance is often overstated. Physicists are not engineers and engineers are not physicists; you can be a very effective programmer without knowing about Peano numbers and what monads are.

082349872349872 2y ago

If you grew up programming in a world where self-reference is (due to linking pass or interpretation) trivial, the Y combinator is nearly useless: why should a function not be able to call itself, like we do every day? However, if you're a pedant, and only accept definitions that are in terms of things other than themselves, then you'll need something like the Y combinator to even define, let alone invoke, recursive functions. (there was a period* of a decade or two where systems people wrote recursive functions and theory people said "yes, it works in practice, but does it work in theory?", but now even theorists have a pedantic way to both describe functions in terms of themselves [syntactically] and agree that such a description denotes a unique function [semantically], so now we have our cake and eat it: a toolchain will go right ahead and generate fixups for the object that point back into itself, while a thesis will drop names like Tarski or Brouwer and maybe typeset another greek character or two) * which may have overlapped with the period where people preferred one-pass to two-pass tools because manually stuffing paper tape back into the reader between passes was a pain? EDIT: extreme pedantry: it surprises me that there was also a decade or so between LABEL and LABELS; going from single recursion to mutual recursion is a very small change in the underlying interpreters, yet even lispers were too pragmatic to have bothered to do so. EDIT2: upon reflection, this was also the period of time where having a stack was viewed as a complexity which was certainly convenient but not exactly necessary. With the benefit of hindsight, I'd argue that mutual tail recursion is useful even without a stack, but can see that at the time that might've been viewed as architecture astronaut talk.

laszlokorte 2y ago

You might find my write-up on lambda calculus and combinatory logic in javascript syntax insightful: https://static.laszlokorte.de/combinators/ https://static.laszlokorte.de/combinators/

Joker_vD 2y ago

No, you're probably not alone. I myself enjoy functional programming quite a lot but Y combinator always stood out to me as a particularly uninteresting trick. Sure, it's nice to have it around when you try to prove some theoretical stuff but for practical work letrec is just better. I mostly feel the same about the Church encoding of e.g. lists: yeah, it's a nice theoretical trick that you can equate a list xs with a function that gives your its fold but... that's just so inconvenient to actually use! Why not equate it with either a nil or a tuple of head and tail instead? def empty_list(onEmpty, onNonEmpty): return onEmpty() def make_a_non_empty_list(head, tail): def non_empty_list(onEmpty, onNonEmpty): return onNonEmpty(head, tail) return non_empty_list

jerf 2y ago

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.

sva_ 2y ago

This talk by Jim Weirich made me grok it and was entertaining enough to follow through: https://m.youtube.com/watch?v=FITJMJjASUs https://m.youtube.com/watch?v=FITJMJjASUs It's from rubyconf but it isn't about ruby really.

lacker 2y ago

The Y combinator is not really a "lisp thing", it's more of a "functional programming" thing. In Lisp, symbols and binding values to a symbol are basic elements of the language, so it usually wouldn't be natural to use the Y combinator.