On Tuesday, August 30, 2005 3:44 PM Jens Axel Søgaard wrote: > > > > > > loop : INT -> INT > > > > > > loop (n) == loop (n) > > > > > > loop (1) > > > > > > >> System error: > > > Invocation history stack overflow. > >
> Martin Rubey wrote: > > 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? > > 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. > I think the example at: http://www.axiom-developer.org/zope/mathaction/SandBoxTailRecursion shows that something more subtle is happening here than just tail-recursion elimination (or not). For one thing, the call to summa(1000000) did not fail with a "Invocation history stack overflow" as Jens predicted above but summa2(1000000,0) did fail. The definition:: summa(n) == if n=0 then 0 else n + summa(n-1) is apparently treated specially by Axiom as a "recurrence relation" and so does not produce a stack overflow. Similarly a stack overflow does occur in this simpler case: \begin{axiom} loop : INT -> INT loop (n) == loop (n) \end{axiom} \begin{axiom} loop (1) \end{axiom} Now let's see what happens if we tell Axiom to compile the function (see web page above): \begin{axiom} )set functions compile on \end{axiom} \begin{axiom} -- a stands for accumulator summa3(n, a) == if n=0 then a else summa3(n-1, n+a) \end{axiom} \begin{axiom} summa3(1000000,0) \end{axiom} Now this function returns a correct value without the stack overflow. And similarly \begin{axiom} loop : INT -> INT loop (n) == loop (n) \end{axiom} if called here with 'loop(1)' becomes an infinite loop. So it seems that perhaps the tail recursion elimination only works when the function is compiled unless it is recognized as special case of a recurrence relation. The message "Invocation history stack overflow" is actually generated by gcl (gcl 2.6.6 is the lisp compiler used to build Axiom on MathAction). Although the examples above seem to suggest that tail recursion elimination is working as expected in the case where the Axiom interpreter functions are compiled, a search of the web returned the following hits which suggest that some previous versions of gcl may have had some problems with tail recursion: - https://savannah.gnu.org/task/?func=detailitem&item_id=788 - http://lists.gnu.org/archive/html/gcl-devel/2002-03/msg00032.html - http://www.mail-archive.com/[email protected]/msg00287.html So maybe there is still a problem lurking out there? Regards, Bill Page. _______________________________________________ Axiom-developer mailing list [email protected] http://lists.nongnu.org/mailman/listinfo/axiom-developer
