6 ms·

The Y combinator only works in languages with either a lazy or call-by-name evaluation strategy. If you run it in a language with an eager evaluation strategy t

The Y combinator only works in languages with either a lazy or call-by-name evaluation strategy. If you run it in a language with an eager evaluation strategy then it actually would result in an infinite loop. For those languages you would have to use the Z combinator or an equivalent. The z-combinator is just the Y combinator with the argument wrapped in a thunk to prevent premature evaluation.

jacquesm 17y ago
Apologies for ignorant questions, but I don't understand how lazy or call-by-name evaluation would solve that. After all lazy is just another way of saying 'deferred', and call-by-name is a way to identify what it is that you are calling, in either case you'd sooner or later have to do the evaluation and then you're back to that loop again. So, what am I missing ?
- procrastitron 17y ago
  Lazy doesn't just mean deferred; an unnecessary computation might never be performed at all. Take for example a function where the recursive argument is never called: sample = (\this->(\x->x)) Then, (Y sample) can reduce as follows: 1: (Y sample) 2: (sample (Y sample)) 3: ((\this->(\x->x)) (Y sample)) 4: (\x->x) Now, if your evaluation strategy required evaluating arguments to final form before applying an operator to them, then line 2 would expand forever: 2: (sample (Y sample)) 3: (sample (sample (Y sample))) 4: (sample (sample (sample (Y sample)))) ... And so on. However, neither call-by-need (lazy) nor call-by-name evaluation strategies require evaluating an argument before applying some operator to it. Thus, in languages that support either of those evaluation strategies, the operator can be evaluated to the point where it throws away the argument, and the argument need never be evaluated. This is a contrived example but real world recursion works for the same reason; at some point in the evaluation of the function, it no longer needs to be applied recursively, and once it reaches that base case, the recursive function can be discarded.
  - jacquesm 17y ago
    Thank you! Ok, I think I see a glimmer of understanding here, it doesn't quite 'click' yet but it is a lot clearer now. I get the 'never needed' bit, that's like in many other languages where you say for instance if x and y then And x = false, then y is never evaluated. Not quite the same, but it's a case where you can optimize out the evaluation of something because it's result will be discarded anyway. The last part of your explanation still has me going around about what makes the decision to discard, it can't be the function itself, so it has to be some criterion outside the function causing that. For instance, maybe if work is no longer done, or if some arbitrary precision level has been reached. Interesting stuff this! In 'pure' functional programming you'd not have an 'if' statement to make the decision with, or is that allowed to be used to end recursion ? I just can't see that working using functions alone.
    - Darmani 17y ago
      There is very much an "if-statement" in lambda calculus. The basic idea is, in the Church Booleans, we think of true as a function which takes a then clause and an else clause, and returns the then clause (T=\lambda xy.x), and false as a function which takes a then clause and an else clause and returns the else clause (F=\lambda x y.y). Then we get our if statement just by applying a predicate (which returns F or T) to a then clause and an else clause. Indeed, that is very much a way to get recursion to step -- the typical Church-numeral definition of the factorial function works that way. By the way, one sure-fire way to get evaluation of a lambda expression to terminate if possible is leftmost-reduction -- that is, reducing the leftmost redex first. Intuitively, the leftmost redex is the "outermost," and any other reduction preserves it, so it must be reduced at some point.
    - btilly 17y ago
      Why wouldn't a pure functional language allow you to have an if statement? Haskell certainly has one! The key is that given the same input you need to produce the same output every time. Which is great as long as you're not doing I/O. (Haskell addresses that with monads - even though it looks like you're giving the same input, you're really giving a different input each time!)

jacquesm 17y ago

Apologies for ignorant questions, but I don't understand how lazy or call-by-name evaluation would solve that. After all lazy is just another way of saying 'deferred', and call-by-name is a way to identify what it is that you are calling, in either case you'd sooner or later have to do the evaluation and then you're back to that loop again. So, what am I missing ?

procrastitron 17y ago
Lazy doesn't just mean deferred; an unnecessary computation might never be performed at all. Take for example a function where the recursive argument is never called: sample = (\this->(\x->x)) Then, (Y sample) can reduce as follows: 1: (Y sample) 2: (sample (Y sample)) 3: ((\this->(\x->x)) (Y sample)) 4: (\x->x) Now, if your evaluation strategy required evaluating arguments to final form before applying an operator to them, then line 2 would expand forever: 2: (sample (Y sample)) 3: (sample (sample (Y sample))) 4: (sample (sample (sample (Y sample)))) ... And so on. However, neither call-by-need (lazy) nor call-by-name evaluation strategies require evaluating an argument before applying some operator to it. Thus, in languages that support either of those evaluation strategies, the operator can be evaluated to the point where it throws away the argument, and the argument need never be evaluated. This is a contrived example but real world recursion works for the same reason; at some point in the evaluation of the function, it no longer needs to be applied recursively, and once it reaches that base case, the recursive function can be discarded.
- jacquesm 17y ago
  Thank you! Ok, I think I see a glimmer of understanding here, it doesn't quite 'click' yet but it is a lot clearer now. I get the 'never needed' bit, that's like in many other languages where you say for instance if x and y then And x = false, then y is never evaluated. Not quite the same, but it's a case where you can optimize out the evaluation of something because it's result will be discarded anyway. The last part of your explanation still has me going around about what makes the decision to discard, it can't be the function itself, so it has to be some criterion outside the function causing that. For instance, maybe if work is no longer done, or if some arbitrary precision level has been reached. Interesting stuff this! In 'pure' functional programming you'd not have an 'if' statement to make the decision with, or is that allowed to be used to end recursion ? I just can't see that working using functions alone.
  - Darmani 17y ago
    There is very much an "if-statement" in lambda calculus. The basic idea is, in the Church Booleans, we think of true as a function which takes a then clause and an else clause, and returns the then clause (T=\lambda xy.x), and false as a function which takes a then clause and an else clause and returns the else clause (F=\lambda x y.y). Then we get our if statement just by applying a predicate (which returns F or T) to a then clause and an else clause. Indeed, that is very much a way to get recursion to step -- the typical Church-numeral definition of the factorial function works that way. By the way, one sure-fire way to get evaluation of a lambda expression to terminate if possible is leftmost-reduction -- that is, reducing the leftmost redex first. Intuitively, the leftmost redex is the "outermost," and any other reduction preserves it, so it must be reduced at some point.
  - btilly 17y ago
    Why wouldn't a pure functional language allow you to have an if statement? Haskell certainly has one! The key is that given the same input you need to produce the same output every time. Which is great as long as you're not doing I/O. (Haskell addresses that with monads - even though it looks like you're giving the same input, you're really giving a different input each time!)