OpenEuphoria

Re: Translated w/ 2.4 CRASH

• Posted by Robert Craig <rds at RapidEuphoria.com> Jun 27, 2003
• 366 views

Andy Serpa wrote:
> Ackermann's function crashes when translated!
> 
> function ack(integer m, integer n)
>   if m = 0 then
>     return n+1
>   end if
> 
>   if n = 0 then
>     return ack(m-1,1)
>   end if
>   return ack(m-1,ack(m,n-1))
> end function
> 
> object x
> 
> x = ack(3,8)
> 
> 
> Works fine in the interpreter -- x = 2045.  But translated and it 
> crashes on my system with both Watcom & Borland (2.4 beta translator).  
> It crashes outright -- no ex.err at all.  It doesn't crash with a lower 
> argument, like (3,7).
> 
> I assume something to do with excession recursion?  I am no longer 
> set-up for translating with 2.3 so I don't know if it is a 2.4 thing, 
> but it seems likely.

Ackermann is *the* classic example of a simple function that
uses an enormous number of levels of recursion.
 From what I just read on the Web somewhere, the number of levels
of recursion goes up as 2 to the power n. Your example uses a couple
of thousand levels of calls. The Euphoria interpreter
automatically grows the call stack (until all memory is used up).
Compiled languages, like C, normally have a fixed-size call stack,
although I thought that Windows could grow the stack. On my XP
machine this example works fine, but on ME it crashes.
With WATCOM, I can make it work on ME too, by editing
"objfiles.lnk" and adding the directive:
     OPTION STACK=100000
With Borland, it works for me on ME without adding
any stack directive.

> By the way, regarding the last problem I reported with a slowdown when 
> recycling a lot of memory -- I discovered a few of my other programs are 
> victim to that as well, especially when using recursive algorithms -- 
> they take longer and longer every time they recurse.  Maybe it is part 
> of the same problem here?

I don't think recursion has much to do with it.
Your examples seem to all use hundreds of thousands,
if not millions of floating-point numbers. They also
do lots of appends and concatenations to sequences
of many different sizes. This results in a system heap
that is huge and fragmented. I believe the poor performance
stems from that. I don't see any obvious bug
in Euphoria, in terms of correctness or performance.

In the future I'll take another look at all this,
to see if there is a better overall algorithm for
handling extreme cases like yours.

Regards,
    Rob Craig
    Rapid Deployment Software
    http://www.RapidEuphoria.com