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.
- 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 ?