How do I define y-combinator without "let rec"?

Question

In almost all examples, a y-combinator in ML-type languages is written like this:

let rec y f x = f (y f) x let factorial = y (fun f -> function 0 -> 1 | n -> n * f(n - 1)) 

This works as expected, but it feels like cheating to define the y-combinator using let rec ....

I want to define this combinator without using recursion, using the standard definition:

Y = λf·(λx·f (x x)) (λx·f (x x)) 

A direct translation is as follows:

let y = fun f -> (fun x -> f (x x)) (fun x -> f (x x));; 

However, F# complains that it can't figure out the types:

  let y = fun f -> (fun x -> f (x x)) (fun x -> f (x x));;   --------------------------------^  C:\Users\Juliet\AppData\Local\Temp\stdin(6,33): error FS0001: Type mismatch. Expecting a     'a     but given a     'a -> 'b     The resulting type would be infinite when unifying ''a' and ''a -> 'b' 

How do I write the y-combinator in F# without using let rec ...?

Answer 1

As the compiler points out, there is no type that can be assigned to x so that the expression (x x) is well-typed (this isn't strictly true; you can explicitly type x as obj->_ - see my last paragraph). You can work around this issue by declaring a recursive type so that a very similar expression will work:

type 'a Rec = Rec of ('a Rec -> 'a) 

Now the Y-combinator can be written as:

let y f =   let f' (Rec x as rx) = f (x rx)   f' (Rec f') 

Unfortunately, you'll find that this isn't very useful because F# is a strict language, so any function that you try to define using this combinator will cause a stack overflow. Instead, you need to use the applicative-order version of the Y-combinator (\f.(\x.f(\y.(x x)y))(\x.f(\y.(x x)y))):

let y f =   let f' (Rec x as rx) = f (fun y -> x rx y)   f' (Rec f') 

Another option would be to use explicit laziness to define the normal-order Y-combinator:

type 'a Rec = Rec of ('a Rec -> 'a Lazy) let y f =   let f' (Rec x as rx) = lazy f (x rx)   (f' (Rec f')).Value 

This has the disadvantage that recursive function definitions now need an explicit force of the lazy value (using the Value property):

let factorial = y (fun f -> function | 0 -> 1 | n -> n * (f.Value (n - 1))) 

However, it has the advantage that you can define non-function recursive values, just as you could in a lazy language:

let ones = y (fun ones -> LazyList.consf 1 (fun () -> ones.Value)) 

As a final alternative, you can try to better approximate the untyped lambda calculus by using boxing and downcasting. This would give you (again using the applicative-order version of the Y-combinator):

let y f =   let f' (x:obj -> _) = f (fun y -> x x y)   f' (fun x -> f' (x :?> _)) 

This has the obvious disadvantage that it will cause unneeded boxing and unboxing, but at least this is entirely internal to the implementation and will never actually lead to failure at runtime.

Answer 2

I would say it's impossible, and asked why, I would handwave and invoke the fact that simply typed lambda calculus has the normalization property. In short, all terms of the simply typed lambda calculus terminate (consequently Y can not be defined in the simply typed lambda calculus).

F#'s type system is not exactly the type system of simply typed lambda calculus, but it's close enough. F# without let rec comes really close to the simply typed lambda calculus -- and, to reiterate, in that language you cannot define a term that does not terminate, and that excludes defining Y too.

In other words, in F#, "let rec" needs to be a language primitive at the very least because even if you were able to define it from the other primitives, you would not be able to type this definition. Having it as a primitive allows you, among other things, to give a special type to that primitive.

EDIT: kvb shows in his answer that type definitions (one of the features absent from the simply typed lambda-calculus but present in let-rec-less F#) allow to get some sort of recursion. Very clever.