The Y Combinator in Go with generics

Re:The Y Combinator in Go with generics by grumpyprole on Sunday June 12, 2022 @10:20AM (#31714690)

Knowledge of the Y-combinator helps avoid making your language divergent (sometimes desirable), disallowing explicit recursion is not enough! The typed lambda calculus uses static types to prevent the Y-combinator and give a sound logic for proofs.

[ Parent | on HN ]

Re:The Y Combinator in Go with generics by dataangel on Sunday June 12, 2022 @10:27AM (#31714743)

Static types doesn't seem sufficient? Typed languages have no problem expressing passing functions as parameters. Where does it break when you apply static types?

[ Parent | on HN ]

Re:The Y Combinator in Go with generics by saghm on Sunday June 12, 2022 @10:40AM (#31714850)

I think it's because the y-combinator needs to be passed to itself as an argument, and it's hard to come up with a static type for a function where one of the parameters is the type itself.

[ Parent | on HN ]

Re:The Y Combinator in Go with generics by octachron on Sunday June 12, 2022 @11:04AM (#31715016)

The Y-combinator require (equi)recursive types for the intermediary step `x x` where `x` has type `('a -> 'b as 'a) -> 'b` using OCaml notation.

[ Parent | on HN ]