Last call generalised

[Marcin 'Qrczak' Kowalczyk]

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/