Last call generalised

[b.i.mills@massey.ac.nz]

"Marcin 'Qrczak' Kowalczyk" produced ....

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

I'll take it for the moment that Marcin is not deliberately 
being obtuse and just emphasise what the word "problem" means.
If I say to a primary school student that in arithmetic the
problem is to work out such things as "what is 2+2" the student
might respond with "that's not a problem, 2+2=4, even I know that".
But, they missed the point they we were not saying that 2+2 was
a difficult problem whose resolution was the aim of arithmetic,
we are simply pointing out the nature of the problems that 
arithmetic is aimed at solving.

To paraphrase my earlier comment, I start by taking it that the 
definition of "last call" is essentially when a function returns 
the return value from another function call. In this situation we 
can validly destroy the context of the caller, thus, for example, 
evaluating a tail recursive routine with constant resource usage, 
ceteris paribus.

In something like fact n t = if n==0 then 1 else fact (n-1) (t*n)
this is clearly the case.  But in a traditional procedural code, we 
might say fact(n,t){if(!n) return 0; t=t*n; n=n-1; return fact(n,t);}.
This is taken within the meaning of tail recursion, but a direct 
transliteration into Haskell means that the ; becomes >>=, which means
that strictly the factorial is not a "last call". Nevertheless, the
concept of last call optimisation still stands, due to the nature
of the >>= operator. It stands here in a way that does not apply to 
fact(n){if(!n) return 1; return n * fact(n-1);}. (Of course other
automated optimisations apply here, Marcin).

> in a tail position. I would name it an indirect tail call.

To quote Spock ... I believe I just said that, Doctor.

Regards,

Bruce.

ps: If Marcin wants to play anymore semantic games I promise
    he can do so on his lonesome.