Hacker News new | ask | show | jobs
by GravityLab 1048 days ago
This is very beautiful. TIL about Y combinators. Thanks for sharing. I looked it up with ChatGPT to learn more about what it is and then compared it with versions from different languages.

JavaScript:

    const Y = f => (x => f(v => x(x)(v)))
                   (x => f(v => x(x)(v)));
Lisp:

    (define (Y f)
     ((lambda (x) (f (lambda (y) ((x x) y))))
       (lambda (x) (f (lambda (y) ((x x) y))))))
Haskell:

    y :: (a -> a) -> a
    y f = f (y f)
OCaml:

    let z f = 
      let fn = ref (fun x -> x) in
      fn := (fun x -> f (!fn x));
      !fn;;
I think I still like the Ruby the most since it's easier to grok due to the Lisp having so many parens towards the end. The Haskell is beautiful to look at too.
3 comments
TheDong 1048 days ago
> The Haskell is beautiful to look at too.

As you might expect for a moderately complicated topic, ChatGPT is hallucinating. That is beautiful because it is not the Y combinator.

That is the Fixed-point combinator. The Y combinator is used to implement recursion when you can't directly reference the function binding.

In the haskell solution, y is used recursively on the rhs, so it's not the Y combinator, and so it's defining something different and simpler, so of course it looks different and simpler.

Do not trust ChatGPT without first giving it a brief bit of thought yourself.

And also, please don't just post ChatGPT's ramblings here if you have nothing worth adding. Most of us, I think, are here for human discussions, not to talk to chatGPT indirectly. If I wanted chatgpt's ramblings, I would go to that site instead.

link
oneshtein 1048 days ago
@ChatGPT, please explain errors in snipets above.
link
kazinator 1048 days ago
TXR Lisp:

  (defun y (f)
    [(op @1 @1)
     (op f (op [@@1 @@1]))])
It looks like the Haskell one is calling itself by name: (y f) appears in the right hand side. That's against the spirit of the exercise. The Y combinator is a way of boostrapping the ability to have functions be able to call themselves in a language which doesn't have named functions as a primitive.

See here: https://mvanier.livejournal.com/2897.html starting at "Deriving the Y combinator" where it presents a lazy version of Y in Scheme, similar to the Haskell one and argues that it's not valid.

Regarding the Scheme version, there is a shorter form:

  (define (Y f) 
    ((lambda (x) (x x))
     (lambda (x) (f (lambda (y) ((x x) y))))))
This is analogous to the TXR Lisp one above which rewrites the lambda terms using op syntax.

Except, the TXR Lisp one doesn't assume that the function takes one argument: the (op [@@1 @@1]) syntax describes a function that takes any number of arguments, and passes them to the funtion produced by [@@1 @@1], so it's like this version:

  (define (Y f)
    ((lambda (x) (x x))
      (lambda (x) (f (lambda y (apply (x x) y))))))
Note that (lambda (y) ...) is now (lambda y ...). This denotes the capture of zero or more arguments into the list y, which can then be applied.

You can see the equivalence:

  3> (expand '(op [@@1 @@1]))
  (lambda (. #:arg-rest-0023)
    [sys:apply [@@1 @@1]
      #:arg-rest-0023])
In this dialect (lambda arg ...) can be written (lambda (. arg) ...) for clarity. When the printer sees (lambda atom ...) it prints it as (lambda (. atom) ...) and we see that above. Just like (lambda (a . rest) ...) means there is one required parameter a followed by zero or more others that are shored up into a list called rest, (lambda (. rest) ...) just means zero required arguments followed by zero or more trailing arguments that become the list called rest. It's a special syntax probably found in TXR Lisp only: (. y) means y, anywhere it appears.

The double @@ in @@1 means "do not refer to @1, the implicit parameter 1 of this op function: refer to parameter @1 of the next enclosing op function":

  (op f (op [@@1 @@1])
    ^        --- ---
     `-------'---'
The (op f ...) writes a function, and @@1 inside the nested op refers to that function's first argument. Whenever you mention positional arguments in op, it no longer passes the variadic arguments implicitly. The generated function is still variadic, but throws away the trailing arguments. If you want them, you have to mention @rest:

These defaults all work together to make a short Y combinator which lets the recursive function have multiple arguments.

  1> (expand '(op f @1))
  (lambda (#:arg-1-0016 . #:arg-rest-0015)
    [f #:arg-1-0016])
  2> (expand '(op f @1 @2 @3))
  (lambda (#:arg-1-0019
           #:arg-2-0020
           #:arg-3-0021 . #:arg-rest-0018)
    [f #:arg-1-0019
      #:arg-2-0020
      #:arg-3-0021])
  3> (expand '(op f @1 @2 @3 @rest))
  (lambda (#:arg-1-0024
           #:arg-2-0025
           #:arg-3-0026 . #:arg-rest-0023)
    [f #:arg-1-0024
      #:arg-2-0025
      #:arg-3-0026
      #:arg-rest-0023])
link