Tell me more ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

The definition of a Y combinator in F# is

let rec y f x = f (y f) x

f expects to have as a first argument some continuation for the recursive subproblems. Using the y f as a continuation, we see that f will be applied to successive calls as we can develop

let y f x = f (y f) x = f (f (y f)) x = f (f (f (y f))) x etc...

The problem is that, a priori, this scheme precludes using any tail call optimization : indeed, there might be some operation pending in the f's, in which case we can't just mutate the local stack frame associated with f.

So :

  • on the one end, using the Y combinator require an explicit different continuation than the function itself.
  • on the othe to apply TCO, we would like to have no operation pending in f and only call f itself.

Do you know of any way in which those two could be reconciled ? Like a Y with accumulator trick, or a Y with CPS trick ? Or an argument proving that there is no way it can be done ?

share|improve this question
Have you added the rec keywork to your y implementation? I should think it needs it from my reading.. – Jimmy Hoffa Dec 26 '12 at 18:26
indeed, thanks. – nicolas Dec 26 '12 at 18:27
Do you have proof it doesn't optimize the tail call? I should think you might want to read the IL for that function and see, I wouldn't be surprised if the compiler is smart enough to come up with something.. – Jimmy Hoffa Dec 26 '12 at 18:41
in the case of a straight untied recursion it does not : however you can rewrite it to allow for such thing subject to the fact the stack frame is reused through the y call. yeah might need to see the IL, no experience in that. – nicolas Dec 26 '12 at 18:45
1  
I made an account and got 50 points just to comment here. This question is really interesting. I think it depends entirely on f. We can see that y could tailcall f with a thunk (y f), but as you say f might have some pending operation. I think it would be interesting to know if there's a separate combinator that is more tailcall friendly. I wonder if this question would get better attention on the CS Stackexchange site? – John Cartwright Mar 8 at 4:15

Know someone who can answer? Share a link to this question via email, Google+, Twitter, or Facebook.

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.