Y-Combinator Practical Example

Question

I've been reading a bit lately about functional programming and I am trying to grok the Y-Combinator. I understand that you can use the Y-Combinator to effectively implement recursion in a language that doesn't support recursion directly. However, every language that I'm likely to use already supports recursion so I'm not sure how useful it would be to use the Y-Combinator for that.

Is there a better practical example of Y-Combinator usage that I'm missing? Has anyone actually used one in real production code? Or is using the Y-Combinator really just a mind-bending academic exercise (albeit a pretty cool one).

Dannie

Answer 1

I'm going to disagree with other answers: The fixed-point (Y) combinator does have practical applications, but it takes a very imaginative mind to find them. Like Bruce McAdam. Here's the abstract from his paper That About Wraps it Up:

The Y combinator for computing fixed points can be expressed in Standard ML. It is frequently used as an example of the power of higher-order functions, but is not generally regarded as a useful programming construction. Here, we look at how a programming technique based on the Y combinator and wrappers can give programmers a level of control over the internal workings of functions not otherwise possible without rewriting and recompiling code. As an experiment, the type-inference algorithm W is implemented using this technique, so that error messages are produced with minimum interference to the algorithm. The code for this example program illustrates the genuine usefulness of the concepts and the ease with which they can be applied. A number of other implementation techniques and possible applications are also discussed, including the use of higher-order functions to simulate the use of exceptions and continuations.

It's a great paper; anyone interested in functional programming will probably enjoy reading it.

Barbwire

Could you give one of the examples. I get "The requested resource () is not available." when I try to download it. – Worcester

I've replaced the link with a link to the Edinburgh web site; the version of the paper may be older, but I have verified that you can download PDF. – Barbwire

Thanks! I will definitely take a look at this. – Dannie

Answer 2

You could check out this nifty post on implementing the Y Combinator in C#: Recursive Lambda Expressions, it might help you understand the idea better.

You may want to check out some nice articles on Wikipedia: Fixed point combinator and Fixed point theorems

As Nathan says, many functional techniques are related to the Y combinator and are useful, so keep at it! Y really is useful because it lets you understand your code better, but I don't think that's a particularly helpful to describe how it helps.

Emersonemery

Answer 3

Others can correct me if I'm wrong, but I'm pretty sure the Y combinator is strictly academic. Think about it: to implement it your language needs to support higher-order functions but not recursion. There's only one language I know like that: lambda calculus.

So until our machines switch from Turing machines to running on lambda calculus, the Y combinator will be strictly academic.

Note: other functional techniques related to the Y combinator are useful, so keep at it. Understanding the Y combinator will help you understand continuations, lazy evaluation, etc.

Kat

Nathan, I think you are wrong, so I have tried to correct you :-) – Barbwire

C# doesn't support recursion within lambda expressions - so the Y combinator can be used to implement it. – Bulwark

"So until our machines switch from Turing machines to running on lambda calculus, the Y combinator will be strictly academic." Lambda calculus IS actually Turing complete. See en.wikipedia.org/wiki/Turing_completeness – Hord

@JPCosta: Yes, but this is an academic point. Turing machines and the lambda calculus are equivalent, but the computers we have today are Turing machines. Knowledge of the Y-combinator suddenly becomes practically important if you need to implement recursion on lambda calculus. (Of course, Norman Ramsey's examples are also useful, and applicable to today's computers to boot.) – Kat

Answer 4

You can think of the combinator as the virtual machine which runs your function, which you describe by a non-recursive functional (= higher-order function).

Sometimes it would be nice to have this combinator under program control, to do similar things as aspect oriented programming (memoizing, tracing, ...), but no programming language I know of allows it. Probably it would be too cumbersome most of the time and/or too hard to learn.

Slippery

Answer 5

let sprite = pipe4 sprite_start blanks (manyTill attribute newline) blanks (fun a b c _ -> Sprite(a,c))

let sprites = 
    let rec y f x = f (y f) x // The Y Combinator
    //let rec sprites_up = many1Indents sprite sprites_up |>> (fun x -> SubSprites x) // Does not work.
    let sprites_up = y (fun f -> many1Indents sprite f |>> (fun x -> SubSprites x))
    many1Indents sprite sprites_up

Here is an example from the compiler for a smallish game library I am making in F#. More specifically, in the above I need to have the sprites_up recursively call itself otherwise the indentation parser would not work correctly.

Without the Y Combinator, I could not have done the parser properly and would have had to resort to writing something like this:

let sprites_up4 = many1Indents sprite error |>> (fun x -> SubSprites x) 
let sprites_up3 = many1Indents sprite sprites_up4 |>> (fun x -> SubSprites x) 
let sprites_up2 = many1Indents sprite sprites_up3 |>> (fun x -> SubSprites x) 
let sprites_up1 = many1Indents sprite sprites_up2 |>> (fun x -> SubSprites x) 
let sprites_up = many1Indents sprite sprites_up1 |>> (fun x -> SubSprites x) 

Would not have been a great solution, the Y Combinator really saved me there. It was certainly not the first thing that came to mind though.

Duane