6 ms·

It's a shame that I like Y Combinator the organization so much, because I find the y combinator as a programming concept to be aesthetically displeasing. It on

by lacker 2y ago

It's a shame that I like Y Combinator the organization so much, because I find the y combinator as a programming concept to be aesthetically displeasing. It only makes sense in the untyped lambda calculus, where types are all conflated and errors are forbidden. It relies on the fact that you can take any x and "apply x to itself". These properties are essentially gimmicks of the untyped lambda calculus. It's like the saying "Everything should be made as simple as possible, but not simpler." The untyped lambda calculus, they made it even simpler. Yes, you can reduce everything to a very tiny number of combinators, but at the cost of making everything ugly. It is much cleaner to use Lisp and reduce everything to a slightly larger set of primitives. Ironically (?) one of the best explanations of this is PG's own The Roots Of Lisp - https://languagelog.ldc.upenn.edu/myl/llog/jmc.pdf https://languagelog.ldc.upenn.edu/myl/llog/jmc.pdf

hollerith 2y ago
>It only makes sense in the untyped lambda calculus Is that really true? ISTR you can impose the type (A -> A) -> A on the Y combinator.
- hollerith 2y ago
  Here is Haskell code in which the Y combinator (named "fix" in the code) is given the type (a -> a) -> a: https://play.haskell.org/saved/ndm83XBr https://play.haskell.org/saved/ndm83XBr This next a very simple Haskell program that just prints the first 8 non-negative integers: main = putStrLn $ show $ take 8 $ iterate (+ 1) 0 The linked code is just an elaboration of that where instead of using the built-in "iterate" we define an equivalent "iterate2". Usually to define iterate2 a Haskell programmer would use recursion (i.e., call iterate2 inside the definition of iterate2) but today we avoid the need for a recursive call by using the Y combinator. This disproves the assertion that the Y combinator "only makes sense in the untyped lambda calculus" because the Haskell compiler gives a type to every entity in the linked code.
  - lacker 2y ago
    I would not call that the Y combinator. As traditionally defined the Y combinator is Y = lambda f: (lambda x: f(x(x)))(lambda x: f(x(x))) so it involves applying x to x. So clearly as shown here you can express in Python. The language has to not enforce sane types. But I would say it only makes sense in the untyped lambda calculus because in any other language there would be a more reasonable way to achieve the same effect. As you show in your example, because you achieve the same effect of finding a fixed point, by not using the Y combinator.
    - hollerith 2y ago
      You can say that "fix" is not the Y combinator, but I've demonstrated in Haskell code that "fix" does the thing the Y combinator is famous for doing: namely, to eliminate the need for recursive calls. (In fact, I repeat the Haskell code in this comment.) Just because your definition is syntactically different from mine does not mean the definitions are not equivalent. My guess as to why Python programmers define the Y combinator the way you is that in Python a function's arguments are evaluated eagerly whereas in Haskell they are evaluated lazily with the result that my definition would tend to enter an infinite loop in Python (but even in a language with eager evaluation, I suspect a simpler definition than yours is possible, so I'm not sure what is going on with your definition, which is not surprising since I'm no Python expert). That is all I will to say in reply to you, but I do want to take this opportunity to fix a problem with my previous comment, namely, the fact that although HN comments tend to persist forever, links to sites other than HN rot fairly quickly: I will now repeat here on HN the tiny Haskell program that in my previously comment I put behind a link. I'll also avoid the unnecessary use of "$", "putStrLn" and "show" to make the code easier to read by Haskell newbies. Because the convention in Haskell is to reserve single-character variable names for local variables, we name the Y combinator "fix": fix :: (a -> a) -> a fix f = f (fix f) Now to demonstrate the use of "fix". My go-to toy Haskell program is this next which prints the first 8 non-negative integers. main = print (take 8 (iterate (+1) 0)) Unfortunately that is too much of a toy for our purpose here because I does not contain a recursive call, so we will pretend that the function "iterate" is not pre-defined in Haskell with the result that we would need to define it ourselves (and call it iterate2 because of course the name "iterate" is already taken). All the code in this comment has been tested; all four versions (the one above and the three below) of our toy program produce the same output. main = print (take 8 (iterate2 (+1) 0)) iterate2 :: (a -> a) -> a -> [a] iterate2 f x = x : iterate2 f (f x) The final mention of "iterate2" above is a recursive call. We replace it with a (non-recursive) call to "fix" as follows: main = print (take 8 (iterate2 (+1) 0)) iterate2 :: (a -> a) -> a -> [a] iterate2 f = fix (\self -> \x -> x : self (f x)) And here is an intermediate form of our toy program that might help the reader understand how the form that uses "fix" was derived from the original form: main = print (take 8 (iterate2 (+1) 0)) iterate2 :: (a -> a) -> a -> [a] iterate2 f = loop where loop x = x : loop (f x)
- codethief 2y ago
  At least in simply-typed lambda calculus it's not possible, see also https://crypto.stanford.edu/~blynn/lambda/simply.html https://crypto.stanford.edu/~blynn/lambda/simply.html : > This implies the Y combinator and omega combinator cannot be expressed in this system. […] In other words, programs always halt. I assume the reason you can still write down the type in Haskell (as in your example further down) is that Haskell types include the bottom?
tromp 2y ago
Between lambda calculus and LISP, I find LISP to be the ugly one, not only because of its far greater complexity, but also its lack of referential transparency. David Turner / Ben Lynn make some good observations about LISP in section "History versus myth" of [1]. If lack of types is what you dislike of the plain lambda calculus, then Haskell is a much better solution than LISP. [1] https://crypto.stanford.edu/~blynn/lambda/lisp.html https://crypto.stanford.edu/~blynn/lambda/lisp.html
- notpushkin 2y ago
  And IIRC, the fixed-point combinator can be defined in Haskell in a way not dissimilar to lambda’s Y combinator itself: fix :: (a -> a) -> a fix f = f (fix f) (I’d say it’s even more aesthetically pleasing, even if a bit way too simple.)
- lispm 2y ago
  Lisp and Haskell are programming languages. Lambda Calculus not.
  - tromp 2y ago
    If you consider it lacking in I/O, then it takes very little to add conventions for those. E.g. the Binary Lambda Calculus is a programming language [1]. [1] https://www.ioccc.org/2012/tromp/hint.htm https://www.ioccc.org/2012/tromp/hint.htm
- cryptonector 2y ago
  Lambda calculus isn't practical for real-world programming. You have to add various types to make it practical. By then you have a LISP.
  - kazinator 2y ago
    You don't have a Lisp until you add to lambda calculus a representation of its syntax using nested lists of symbols, with APIs to manipulate the lists, a way to intercept and transform the lists that are being processed as code and an eval function.
tkz1312 2y ago
I have very similar feelings but in the exact opposite direction :) The y combinator is a beautiful and satisfying thing that brings much joy when studied, the org is a bunch of cringe silicon valley vc types intent on owning the world…
- jvalencia 2y ago
  And yet you're here?
cryptonector 2y ago
> It only makes sense in the untyped lambda calculus, You can use it in any language that has closures but doesn't have recursion to begin with. Granted, there's no reason to have a language like that, but fixing is a very common idiom in Haskell.
jedwards1211 2y ago
Hacker News is one of the most simple, unaesthetic sites out there so the untyped lambda calculus seems like a fitting metaphor to me

by lacker 2y ago

hollerith 2y ago

>It only makes sense in the untyped lambda calculus Is that really true? ISTR you can impose the type (A -> A) -> A on the Y combinator.

hollerith 2y ago
Here is Haskell code in which the Y combinator (named "fix" in the code) is given the type (a -> a) -> a: https://play.haskell.org/saved/ndm83XBr https://play.haskell.org/saved/ndm83XBr This next a very simple Haskell program that just prints the first 8 non-negative integers: main = putStrLn $ show $ take 8 $ iterate (+ 1) 0 The linked code is just an elaboration of that where instead of using the built-in "iterate" we define an equivalent "iterate2". Usually to define iterate2 a Haskell programmer would use recursion (i.e., call iterate2 inside the definition of iterate2) but today we avoid the need for a recursive call by using the Y combinator. This disproves the assertion that the Y combinator "only makes sense in the untyped lambda calculus" because the Haskell compiler gives a type to every entity in the linked code.
- lacker 2y ago
  I would not call that the Y combinator. As traditionally defined the Y combinator is Y = lambda f: (lambda x: f(x(x)))(lambda x: f(x(x))) so it involves applying x to x. So clearly as shown here you can express in Python. The language has to not enforce sane types. But I would say it only makes sense in the untyped lambda calculus because in any other language there would be a more reasonable way to achieve the same effect. As you show in your example, because you achieve the same effect of finding a fixed point, by not using the Y combinator.
  - hollerith 2y ago
    You can say that "fix" is not the Y combinator, but I've demonstrated in Haskell code that "fix" does the thing the Y combinator is famous for doing: namely, to eliminate the need for recursive calls. (In fact, I repeat the Haskell code in this comment.) Just because your definition is syntactically different from mine does not mean the definitions are not equivalent. My guess as to why Python programmers define the Y combinator the way you is that in Python a function's arguments are evaluated eagerly whereas in Haskell they are evaluated lazily with the result that my definition would tend to enter an infinite loop in Python (but even in a language with eager evaluation, I suspect a simpler definition than yours is possible, so I'm not sure what is going on with your definition, which is not surprising since I'm no Python expert). That is all I will to say in reply to you, but I do want to take this opportunity to fix a problem with my previous comment, namely, the fact that although HN comments tend to persist forever, links to sites other than HN rot fairly quickly: I will now repeat here on HN the tiny Haskell program that in my previously comment I put behind a link. I'll also avoid the unnecessary use of "$", "putStrLn" and "show" to make the code easier to read by Haskell newbies. Because the convention in Haskell is to reserve single-character variable names for local variables, we name the Y combinator "fix": fix :: (a -> a) -> a fix f = f (fix f) Now to demonstrate the use of "fix". My go-to toy Haskell program is this next which prints the first 8 non-negative integers. main = print (take 8 (iterate (+1) 0)) Unfortunately that is too much of a toy for our purpose here because I does not contain a recursive call, so we will pretend that the function "iterate" is not pre-defined in Haskell with the result that we would need to define it ourselves (and call it iterate2 because of course the name "iterate" is already taken). All the code in this comment has been tested; all four versions (the one above and the three below) of our toy program produce the same output. main = print (take 8 (iterate2 (+1) 0)) iterate2 :: (a -> a) -> a -> [a] iterate2 f x = x : iterate2 f (f x) The final mention of "iterate2" above is a recursive call. We replace it with a (non-recursive) call to "fix" as follows: main = print (take 8 (iterate2 (+1) 0)) iterate2 :: (a -> a) -> a -> [a] iterate2 f = fix (\self -> \x -> x : self (f x)) And here is an intermediate form of our toy program that might help the reader understand how the form that uses "fix" was derived from the original form: main = print (take 8 (iterate2 (+1) 0)) iterate2 :: (a -> a) -> a -> [a] iterate2 f = loop where loop x = x : loop (f x)
codethief 2y ago
At least in simply-typed lambda calculus it's not possible, see also https://crypto.stanford.edu/~blynn/lambda/simply.html https://crypto.stanford.edu/~blynn/lambda/simply.html : > This implies the Y combinator and omega combinator cannot be expressed in this system. […] In other words, programs always halt. I assume the reason you can still write down the type in Haskell (as in your example further down) is that Haskell types include the bottom?

tromp 2y ago

Between lambda calculus and LISP, I find LISP to be the ugly one, not only because of its far greater complexity, but also its lack of referential transparency. David Turner / Ben Lynn make some good observations about LISP in section "History versus myth" of [1]. If lack of types is what you dislike of the plain lambda calculus, then Haskell is a much better solution than LISP. [1] https://crypto.stanford.edu/~blynn/lambda/lisp.html https://crypto.stanford.edu/~blynn/lambda/lisp.html

notpushkin 2y ago
And IIRC, the fixed-point combinator can be defined in Haskell in a way not dissimilar to lambda’s Y combinator itself: fix :: (a -> a) -> a fix f = f (fix f) (I’d say it’s even more aesthetically pleasing, even if a bit way too simple.)
lispm 2y ago
Lisp and Haskell are programming languages. Lambda Calculus not.
- tromp 2y ago
  If you consider it lacking in I/O, then it takes very little to add conventions for those. E.g. the Binary Lambda Calculus is a programming language [1]. [1] https://www.ioccc.org/2012/tromp/hint.htm https://www.ioccc.org/2012/tromp/hint.htm
cryptonector 2y ago
Lambda calculus isn't practical for real-world programming. You have to add various types to make it practical. By then you have a LISP.
- kazinator 2y ago
  You don't have a Lisp until you add to lambda calculus a representation of its syntax using nested lists of symbols, with APIs to manipulate the lists, a way to intercept and transform the lists that are being processed as code and an eval function.

tkz1312 2y ago

I have very similar feelings but in the exact opposite direction :) The y combinator is a beautiful and satisfying thing that brings much joy when studied, the org is a bunch of cringe silicon valley vc types intent on owning the world…

jvalencia 2y ago
And yet you're here?

cryptonector 2y ago

> It only makes sense in the untyped lambda calculus, You can use it in any language that has closures but doesn't have recursion to begin with. Granted, there's no reason to have a language like that, but fixing is a very common idiom in Haskell.

jedwards1211 2y ago

Hacker News is one of the most simple, unaesthetic sites out there so the untyped lambda calculus seems like a fitting metaphor to me