Re: [Caml-list] tail rec

[skaller <skaller@users.sourceforge.net>]

On Sat, 2007-05-19 at 07:28 +0200, Basile STARYNKEVITCH wrote:
> skaller wrote:
> > I have a silly idea. Introduce a new construction:
> > 
> > let tailrec f .. 
> > 
> > This is the same as let rec except it checks every direct call to f
> > is in tail position (and bombs out the compiler if not).
> 
> 
> While I also want a similar construct or help, I believe your proposal 
> is wrong. What would be needed is a tailrec operator keyword that makes 
> the compiler check that a given call is in tail position. It is not a 
> function which is tail recursive, it is a call which is.
> 
> In that way, the classical factorial does not have any tail call, so
> 
>    let rec fact n = if n <= 0 then 1 else n * tailrec fact (n - 1)

Felix actually implements this for procedure calls: instead of

	f x;

or

	call f x;

you can write:

	jump f x;

In that context, it is not a compiler *check* but sugar for

	call f x;
	return;

which forces the call to be tail. This is only for procedure
calls though, not function applications.

For Ocaml, it would seem your suggestion should use the
keyword 'return':

let rec fact n = if n <= 0 then 1 else n * return fact (n-1)

is pretty obviously an error, and a C/C++ programmer would
understand this.

The problem with your idea is that it doesn't allow the
programmer to do this:

let rec fact n = ....

Hum. Is this tail rec? I'm a GOOD programmer => I'm LAZY.
With my suggestion I could just write:

let tailrec fact n = ..

to check a claim that 'fact' isn't gratuitously non-tail rec.

The point is, I'm trying to establish a property of the function
implementation: ALL direct recursion is tailed.

In a longer chain of let rec .. and .. and this is only a single
keyword change.

Your suggestion would require writing 'tailrec' or 'return'
in advance for every call .. and no GOOD programmer would
do that because good programmers are lazy.

It would be the other way. First you write 

	let tailrec  ....

and now you get an error because there is a real and essential
non-tail call .. so you annotated that call:

	else x::(f y)

is an error because f isn't tailed but this is right so:

	else x::(rec f y)

has to be written to disable the check on that f.

In fact, I could go a step further and suggest ALL let rec
should be forced to be tailrec, so the ONLY way to do
a non tail call is write

	rec f y

The compiler then issues a warning when 'rec' is used
but the call actually is in tail position.

Unfortunately this breaks existing code so it would have
to be enabled by a compiler switch.

In summary then: what you (Basile) suggest is technically
sound, and could ALSO be implemented!

However the two features address the same issue from
opposite angles. My proposal assures a whole function
or list of function is directly tail rec, whereas
yours is extremely local and checks individual explicitly
annotated calls.

So from a software engineering/development viewpoint
they have quite different utility .. and they're not
exclusive!

-- 
John Skaller <skaller at users dot sf dot net>
Felix, successor to C++: http://felix.sf.net