Last call generalised (was Re: tail recursion, (was Re: Need some help please))
Yo,
copyList (x:xs) = x : copyList xs
is surely not tail-recursive in the traditional sense, but I think that most Haskell programmers take it for granted that it runs in constant stack space.
Not sure how this is a continuation of the safetail problem, and there are others who know a lot more about the specific guts of GHC and HUGS, but in that vein, I've got a general comment on what I see as the principle going on here. I brought up the same issue some time back about >>. That is in func = f x >> func, we have the problem that >> is a function so func is not a last call. (David Bergman emphasised that it is better viewed as "last call" than "tail recursion). But if this was C, then the function is func = {f x ; func}, in which func is then the last call. But the Haskell version of this is func = do { f x ; func}, which is just syntactic sugar for the first option, so again, no "last call". Haskell compilers do have optimisations related to this, but I just want to make a generic comment. In procedural programming, the idea of the last call is that there is an operator ; that is often thought of as separating statements. I would argue that it is rather joining commands, with a transfer of state. That is in C, {cmdA ; cmdB ; } means do cmdA with the current machine state, and then cmdB, passing the resulting state from cmdA. Thus the Haskell interpretation of ; as >> or >>= in monad terms is really just a natural statement of what is going on. Viva Haskell! But the point is that this means that "last call" is actually relative to the composition operation. So, traditional procedural last call optimisation is just last-call-wrt-join, or something like that. Thus, the situation for optimisation is f x = joinOp(x, f (g x)) were joinOp has the characteristic that it does not really need to know what the second argument is in order to proceed with the first part of the computation. Eg, using >>=, we can finish with the LHS completely before going to the RHS, and likewise with copyList (x:xs) = x : copyList xs, we can deal with the (x :) completely, and never have to come back to it. Again, I expect my comments are unorthodox, but I certainly feel that there is a point here to be made. The situation for "last call" optimisation is a bit more general than simply that case of temporal-catenation of commands. It has much more to do with the logical relation between the arguments to a function. Regards, Bruce.
Dnia czw 28. sierpnia 2003 23:04, b.i.mills@massey.ac.nz napisał:
copyList (x:xs) = x : copyList xs
is surely not tail-recursive in the traditional sense, but I think that most Haskell programmers take it for granted that it runs in constant stack space.
The problem lies in the fact that the execution of a Haskell "function" can be interleaved with the execution of the code which calls it. Counting total stack space ever consumed by parts consisting of a function is meaningless because between these parts the stack is usually unwound. If you implemented this in a strict language, you would probably attribute only building of the cons cell to the invocation of the function. The cell points to a thunk in its tail, so when the tail is evaluated, an anonymous function is called - the original function is long finished.
I brought up the same issue some time back about >>. That is in func = f x >> func, we have the problem that >> is a function so func is not a last call.
It's an easy problem: although func is not a tail call, >> is a tail call and >> itself in most monads enters its second argument in a tail position. I would name it an indirect tail call.
In procedural programming, the idea of the last call is that there is an operator ; that is often thought of as separating statements.
In Scheme not only sequencing generates tail calls; e.g. branches of 'if' are in a tail position wrt. the 'if' itself, the body of 'let' wrt. the whole 'let' etc. If these constructs were implemented as plain functions taking closures as parameters, you would derive whether they tail call some of their parameters from their implementation. A Scheme definition, which describes the semantics and not a concrete implementation, would probably specify which functions on which conditions are required to tail call which of their parameters. But Scheme prefers macros, so I think the language definition doesn't talk about tail call properties of standard functions - because there aren't any interesting functions to talk about. OTOH Haskell uses more functions instead of built-in syntactic constructs, because passing a parameterless closure is very easy - you just write the expression consisting of the body. This makes meaningful to ask which functions on which conditions enter some of their parameters in a tail position. For example && does this with its second parameter if it's entered at all. -- __("< Marcin Kowalczyk \__/ qrczak@knm.org.pl ^^ http://qrnik.knm.org.pl/~qrczak/
participants (2)
-
b.i.mills＠massey.ac.nz -
Marcin 'Qrczak' Kowalczyk