Talk:Fixed-point combinator

Klop combinator

Did anybody notice that the fixed point combinator by Klop as given here is wrong? Did anybody actually try it? I used it to test my lambda-calculus interpreter and I was thinking of a bug in it, until I found the correct definition somewhere on the web: [1] (look for $). There should be 26 L's, not 28 as given here. The problem is that many web pages directly copy from the Wikipedia text, and give the same (wrong) definition. I don't know whether the page was vandalized long ago, or it was a genuine transcription error. Fixed. --positron 10:14, 7 March 2006 (UTC)[reply]

I don't think anybody did try it. Should've just removed it when I did a big cleanup a while back, I suppose. Thanks for the fix. —donhalcon^╤ 14:52, 7 March 2006 (UTC)[reply]

Dumbing Down

Could you dumb it down a shade? --Mike Schiraldi 01:53, 27 Jun 2005 (UTC)

I think the first paragraoh is misleading the reader into thinking about fixpoints as real values, whereas the following paragraph is talking about a fixpoint in function space. It takes a bit of a conceptual leap to understand the latter, and the first paragraph doesn't particularly help...

I've submitted a rewrite that should be a lot easier to understand. --bmills 18:00, 21 October 2005 (UTC)[reply]

I suspect that some of that stuff is graffiti, but I'm not expert enough to say for sure. Will someone please check on it? --unknown

Y Combinator

It seems like the Y Combinator should have its own page.

Example

Why does the example mix (a b (c d)) and a(b)(c(d)) notation? It would be a lot clearer, I think, if it stuck to (a b (c d)), and put ( ) on the lambdas as well. It would also be nice to state the final result (fact = (fix ...)). Shinobu 06:57, 8 November 2006 (UTC)[reply]

The example also appears to be wrong. It uses just part of the church numeral, and confusingly uses f to mean two different things. Can anyone confirm this? (New guy, reluctant to change/break anything) CarpeCerevisi 11:46, 8 February 2007 (UTC)[reply]

Huh?

Note that the Y combinator is intended for the call-by-name evaluation strategy, since (Y g) diverges (for any g) in call-by-value settings

Can somebody explain this? What does call-by-name versus call-by-value even mean in the context of lambda calculus? Isn't call-by-name always the case in lambda calculus? Why does Y g diverge in call-by-value? What does 'diverge' mean in this context? All these things are totally non-obvious. JulesH 19:12, 11 November 2007 (UTC)[reply]

Also, the "Example" section refers to something described as the "fix" operator, which hasn't been defined. JulesH 19:25, 11 November 2007 (UTC)[reply]

I don't get it

I've read this definition a zillion times and it still makes no sense to me.

A fixed point of a function f is a value x such that f(x) = x.

If you've got an arbitrary function f, why should there be *any* guarantee at all that it will have a fixed point in the first place? If my function is: 'f(x) = x+1', then it's never going to have a value such that f(x) = x for any integer x. If I have a higher-order function 'f(x) = x x', then that's still no guarantee that x x == x for all x's.

It seems like nonsense. What am I misunderstanding here?

I can understand a function which *creates* a higher-order function which is guaranteed to have a known fixed point -- but not one that takes an arbitrary Turing-complete function, somehow analyses it (how do you look inside a lambda abstraction in the first place when the only operation you have is application? And wouldn't working out what value it returns for all arguments involve solving the halting problem?), determines that it has a fixed point, and returns the *fixed point itself*.

Obviously this is a hugely fundamental result in basic computer science, so it must be right, and I thought I vaguely understood lambda calculus, but I can't make head or tail of this definition as written. --Natecull (talk) 23:12, 17 November 2008 (UTC)[reply]

As is explained in the section Fixed point combinator#Existence of fixed point combinators, fixed point combinators need not exist for all settings, and need not be total, i.e. they may diverge for some (even almost all) inputs. However, there are important settings such as CPO, the cartesian closed category of complete partial orders with Scott continuous maps, where fix points always exist. — Tobias Bergemann (talk) 12:25, 18 November 2008 (UTC)[reply]

f is a little too simple, it doesn't have an iterative structure. Let

plus x 0  = x
plus x y  = plus (suc x) (dec y)

where suc(x) is essentially x+1 and dec y is essentially y -1. Your f is just f = (flip plus 1).

OK now the problem is plus is defined recursively. So lets make it a function of 3 variables:

plus' g x 0  = x
plus' g x y  = g (suc x) (dec y)

and if we had a working plus obviously plus' plus x y = plus x y. But we don't. On the other hand we can keep feeding plus' more copies of plus' and actually get a plus:

plus x y = (fix plus') x y

and then you can define your f as

f' x = (fix plus') x 1

jbolden1517^Talk 22:41, 27 March 2009 (UTC)[reply]

Hmmmm. So, if I read you right, you're basically saying what I was figuring at first: that fix (by which I assume you mean Y) can only be defined on functions like plus' which are specially written in such a way as to receive a (fix whatever) function as a first argument? And not on functions like plus which are not?

So how do you prove that all functions in the system are the plus' kind and not the plus kind? Or am I still asking the wrong questions here?

I'm still not seeing what (fix f') should produce here, which was my original question.

If the answer is 'Y can only be defined over recursive functions like plus', don't attempt to take the fixpoint using Y of a non-recursive one like f' then it makes sense to me. But that means it's not actually a generalised fixpoint combinator, is it? It's only the fixpoint for a very small subset of all possible functions which play by the rules.

--Natecull (talk) 06:16, 13 June 2009 (UTC)[reply]

Further examples

Both examples for the Y combinator use functional languages, which support Currying. This means that the given examples can not simply be translated to other languages which support first-class functions, but no currying/partial exaluation.

Here is an example in Ruby of the y combinator and its use with factorial. It explicitly uses an additional function which takes the arguments for our original function, apart from that, it is a direct translation of the y combinator's definition. Maybe we could try to improve it a little / make it more readable (at least add proper indendation) and then incorporate it into the article.

y = lambda { |f| (lambda { |x| lambda { |*args| (f.call(x.call(x))).call(*args) }}).call(lambda { |x| lambda { |*args| (f.call(x.call(x))).call(*args) }})}
b = y.call(lambda { |f| lambda {|i| if i == 0 then 1 else i * (f.call(i-1)) end }})
puts(b.call 5) # 120

Subwy (talk) 10:58, 10 December 2008 (UTC)[reply]

Some material

One really good demonstration of how the Y combinator works (it has enough hand waving to make the general principles accessible to the layman), is this:

      let Y = (lambda (f)
                ((lambda (g) (f (g g)))
                 (lambda (g) (f (g g)))))
      let H = (lambda (g) (f (g g))) for convenience
  
      let fact = (Y fact-h)  
  
         fact 
      => (Y fact-h)
      => (H H)      ; with f = fact-h
      => (fact-h (g g))
      => (fact-h (H H))
      =  (fact-h (Y fact-h))
      =  (fact-h fact)
  
      ;; => indicates a substitution step, while = indicates an equivalence
      ;; which is not actually a substitution

Unfortunately, this uses a lispy syntax, which most people are not familiar with. We should work this into something that could go into the article. — Edward Z. Yang^(Talk) 06:23, 29 January 2009 (UTC)[reply]

Why is the Haskell Y the Y combinator?

Technically the Haskell definition is the equation that defines any fixed point combinator no? So why is it Y? Pcap ping 04:51, 21 August 2009 (UTC)[reply]

Well, that was incorrect, so I've fixed it. Pcap ping 21:33, 21 August 2009 (UTC)[reply]

"Fixed point combinators allow the definition of anonymous recursive functions"

Functions in lambda calculus don't have a name, so that statement is nonsensical in the context of lambda calculus. To make some sense you need to specify some formal language where you can/must have names for some functions. But the example that is supposed to clarify the meaning of "anonymous" (as opposed to named) is in lambda calculus, where all functions are anonymous! The anonymous (like all other!) function returned by Y (i.e. factorial) is indeed a primitive recursive function, but all μ-recursive functions are lambda definable (see a theory book for proof, e.g. [2]), so what are you trying to say here? Pcap ping 05:38, 21 August 2009 (UTC)[reply]

I think I've clarified the matter. Pcap ping 07:22, 21 August 2009 (UTC)[reply]