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

Understanding the Y Combinator

8dcc.github.io

Post reply on HN
Print view View original

61–70 of 73 posts

Re: Understanding the Y Combinator

#61

Post by tromp »

lispm wrote: post #55
tromp wrote: post #47

Earlier quoted context omitted.

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…

Lisp and Haskell are programming languages. Lambda Calculus not.

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

Re: Understanding the Y Combinator

#62

Post by tromp »

cryptonector wrote: post #59
tromp wrote: post #47

Earlier quoted context omitted.

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 calculus isn't practical for real-world programming. You have to add various types to make it practical. By then you have a LISP.

By then you have a Haskell, which unlike LISP is just syntactic sugar on a typed lambda calculus.

Re: Understanding the Y Combinator

#63

Post by kazinator »

tromp wrote: post #47
lacker wrote: post #38

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…

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…

> lack of referential transparency

This is actually a kind of double negative, because referential transparency is rather the lack of something: the lack of the ability to express a program in which an identifier refers to other than an obvious definition in an enclosing scope.

In Common Lisp, or a similar dialect, we can pose this question:

  (let ((x 42))
    (mystery-macro x))
can mystery-macro be written so that the enclosed x is other than 42? The answer is yes. To have referential transparency, we have to take away this power.

Referential transparency is not a "cool feature" we can add to a language, so then we can express new kinds of things. It just refers to something we are not allowed to do.

Re: Understanding the Y Combinator

#64

Post by tromp »

kazinator wrote: post #63
tromp wrote: post #47

Earlier quoted context omitted.

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…

> lack of referential transparency This is actually a kind of double negative, because referential transparency is rather the lack of something: the lack of the ability to express a program in which an identifier refers to other than an obvious definition in an enclosing scope. In Common Lisp, or a similar dialect, we can pose this question: (let ((x 42)) (mystery-macro x)) can mystery-macro be written so that the en…

Referential transparency is a big feature in that it hugely aids in reasoning about your program. I agree that it takes away the power of making your code hard to reason about:-)

Re: Understanding the Y Combinator

#65

Post by cryptonector »

tromp wrote: post #62
cryptonector wrote: post #59

Earlier quoted context omitted.

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.

By then you have a Haskell, which unlike LISP is just syntactic sugar on a typed lambda calculus.

Fair.

Re: Understanding the Y Combinator

#66

Post by kazinator »

tromp wrote: post #64
kazinator wrote: post #63

Earlier quoted context omitted.

> lack of referential transparency This is actually a kind of double negative, because referential transparency is rather the lack of something: the lack of the ability to express a program in which an identifier refers to other than an obvious definition in an enclosing scope. In Common Lisp, or a similar dialect, we can pose this question: (let ((x 42)) (mystery-macro x)) can mystery-macro be written so that the en…

Referential transparency is a big feature in that it hugely aids in reasoning about your program. I agree that it takes away the power of making your code hard to reason about:-)

All you need is compiler diagnostics about variable shadowing to make this academic issue entirely go away:

  1> (defmacro mystery-macro (form) ^(let ((x 73)) ,form))
  mystery-macro

  2> (with-compile-opts ()
       (compile-toplevel '(let ((x 42)) (mystery-macro x))))
  ** expr-2:2: warning: let: variable x unused
  #

  3> (with-compile-opts (:warn shadow-var)
       (compile-toplevel '(let ((x 42)) (mystery-macro x))))
  ** expr-3:2: warning: let: variable x shadows local variable
  ** expr-3:2: warning: let: variable x unused
  #

  4> (with-compile-opts (:error shadow-var)
       (compile-toplevel '(let ((x 42)) (mystery-macro x))))
  ** expr-4:2: let: variable x shadows local variable
  ** during evaluation of form (compile-toplevel '(let ((x 42))
                                                    (mystery-macro
                                                      x)))
  ** ... an expansion of (progn (compile-toplevel '(let ((x 42))
                                                     (mystery-macro
                                                       x))))
  ** ... an expansion of (with-compile-opts
                           (compile-toplevel '(let ((x 42))
                                                (mystery-macro
                                                  x))))
  ** which is located at expr-4:1
Moreover, this is a problem that mainly affects densely nested code. If you write small functions that are not nested beyond a couple of lexical levels or so, referentially opaque smells have nowhere to hide.

Example with macro generating code that unhygienically relies on list, which is redefined around the macro:

  1> (defmacro mac (x) ^(list ,x))
  mac
  2> (with-compile-opts (:warn shadow-fun)
     (compile-toplevel '(labels ((list ())) (mac 1))))
  ** expr-2:2: warning: sys:lbind: redefining list, which is a built-in defun
  ** expr-2:2: warning: sys:lbind: function list shadows global function
  ** expr-2:2: warning: list: too many arguments: max 0, given 1
  #

  3> (with-compile-opts (:error shadow-fun)
     (compile-toplevel '(labels ((list ())) (mac 1))))
  ** expr-3:2: warning: sys:lbind: redefining list, which is a built-in defun
  ** expr-3:2: sys:lbind: function list shadows global function
  ** during evaluation of form (compile-toplevel '(labels ((list ()))
                                                    (mac 1)))
  ** ... an expansion of (progn (compile-toplevel '(labels ((list ()))
                                                     (mac 1))))
  ** ... an expansion of (with-compile-opts
                           (compile-toplevel '(labels ((list ()))
                                                (mac 1))))
  ** which is located at expr-3:1
The concept of referential transparency is meaningless if there is no shadowing. If an expression which refers to a certain binding is moved around in the program, it either continues to refer to that same binding, or at worst becomes a free reference (easily diagnosable). If there is no shadowing, constructs cannot surreptitiously intercept bindings.

Re: Understanding the Y Combinator

#67

Post by kazinator »

tromp wrote: post #64
kazinator wrote: post #63

Earlier quoted context omitted.

> lack of referential transparency This is actually a kind of double negative, because referential transparency is rather the lack of something: the lack of the ability to express a program in which an identifier refers to other than an obvious definition in an enclosing scope. In Common Lisp, or a similar dialect, we can pose this question: (let ((x 42)) (mystery-macro x)) can mystery-macro be written so that the en…

Referential transparency is a big feature in that it hugely aids in reasoning about your program. I agree that it takes away the power of making your code hard to reason about:-)

Ah right! The other aspect of referential transparency is the lack of side effects. If we can do x := x + 1, then the expression x isn't referentially transparent. If we relocate it from before the assignment to after, even though it refers to the same binding, it doesn't refer to the same value; the relocation doesn't changes its meaning. No imperative language can be referentially transparent, as such. But that's all the useful languages in which shit gets done.

Re: Understanding the Y Combinator

#68

Post by marcellus23 »

pdonis wrote: post #57
marcellus23 wrote: post #52

Earlier quoted context omitted.

The text color in those snippets is pure white, and the background is nearly pure black (#111111). I don't think the problem is with the website.

> The text color in those snippets is pure white Including the syntax highlighted parts? I don't think so. > I don't think the problem is with the website. I don't think you have fully considered the situation.

well no, but the syntax highlighted parts are not white, they're different colors. So complaining about them being faint white doesn't make sense.

> I don't think you have fully considered the situation.

Hard to "consider the situation" when you won't describe what the situation actually is.

Re: Understanding the Y Combinator

#69

Post by jedwards1211 »

lacker wrote: post #38

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…

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

Re: Understanding the Y Combinator

#70

Post by lacker »

hollerith wrote: post #50
hollerith wrote: post #40

Earlier quoted context omitted.

>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.

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 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". Usu…

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.
Post reply on HN