[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [Axiom-developer] Re: [Axiom-mail] [Axiom-mail] Lexicographic order
From: |
Jens Axel Søgaard |
Subject: |
Re: [Axiom-developer] Re: [Axiom-mail] [Axiom-mail] Lexicographic order |
Date: |
Tue, 30 Aug 2005 21:44:29 +0200 |
User-agent: |
Mozilla Thunderbird 1.0.2 (Windows/20050317) |
Martin Rubey wrote:
> I tried the following and ran out of stack space:
>
> loop : INT -> INT
>
> loop (n) == loop (n)
>
> loop (1)
>
> >> System error:
> Invocation history stack overflow.
Although this is not a nice way for Axiom to fail, two questions:
* is this an instance of tail-recursion?
* what result would you expect?
Hi Martin,
Yes - if tail recursion were supported, then the above would be
an infinite loop. I haven't got any complaints over the wording
of the error message.
If tail recursion is supported, the above will result in an infinite
loop.
A loose definition of a tail call is: If in the body of f, a call
to g is made in a position, where the result of the call, is to
be returned by f, then the call to g is a /tail call/.
In
summa(n) ==
if n=0
then 0
else n + summa(n-1)
> summa(10)
55
the call to summa is not a tail cail, since the result of calling
summa(n-1) needs to be added to n before a value can be returned.
On the other hand in:
-- a stands for accumulator
summa2(n, a) ==
if n=0
then a
else summa2(n-1, n+a)
> summa(10,0)
55
the result of calling summa2(n-1,n+a) is returned immediately
as the result of summa2(n,a) and is thus a tail call.
A call is /active/ if the function called hasn't returned yet.
Proper[1] tail recursion is supported, if an unbounded number
of active tail calls only use a bounded amount of stack space.
In Scheme a call summa(10000) would cause a stack overflow, just
as in Axiom, but a call summa2(10000,0) would work withput any
problems. However, in some Scheme implementations one can
turn the stack history on and off - so perhaps there is
magic switch somewhere?
See
<http://www.schemers.org/Documents/Standards/R5RS/HTML/r5rs-Z-H-6.html#%_sec_3.5>
for a more formal definition.
[1] Here "Proper Tail Recursion" is a technical term, and doesn't
mean "tail recursion done right".
--
Jens Axel Søgaard