Re: How does Scheme know if a func is tail-recursive or not?

ssecorp wrote:
> Scheme requires tail-call-optimization.

Scheme actually requires implementations to be properly
tail recursive, which is stronger than most optimizations
that people generally refer to as tail call optimization [1].

> But how does Scheme know or react?

Implementations of Scheme must treat tail contexts
differently from non-tail contexts.  That is easy,
although it involves breaking with some old ways
of thinking about procedure calls.

> Because when I use tree-recursion DrScheme never complains.

Nor should it.  Tree recursion is legal in Scheme.

> According to :
>
http://www.biglist.com/lists/lists.mulberrytech.com/dssslist/archives/199907/msg00389.html
> it s aslo undecidable if unerstood it correctly.

You are conflating at least two distinct concepts.

Whether a program you write will run in a bounded
amount of space is undecidable.

Whether an arbitrary implementation is properly tail
recursive is also undecidable, but nobody cares
about arbitrarily stupid implementations.

With a well-designed implementation of Scheme,
it should be easy to see that the implementation
is properly tail recursive in the mandated sense.

Will

[1] William D Clinger.  Proper tail recursion and space
efficiency.  In the Proceedings of the 1998 ACM Conference
on Programming Language Design and Implementation,
June 1998, pages 174-185.  Online at
ftp://ftp.ccs.neu.edu/pub/people/will/tail.ps.gz