Problem with lack of TCO

[Jean-Francois Poilpret]

Hi,

while programming some katas in Yeti, I developed the following function
to find primes according to sieve of Erasthothenes:

primes ps ns =
(p = head ns;
ns' = filter (_ n = (n % p != 0)) ns;
ps' = p :: ps;
if empty? ns' then ps' else primes ps' ns' fi);

primes' n = primes [] [2..n] |> reverse;

It worked fine until n = 80000, but I started to get stack overflows
with n = 85000.
I had the impression that primes ps ns was written in a way to enable
tail call optimisation, but it seems TCO is not used here.

Did I do something wrong?

Cheers, Jean-Francois

[Madis Janson]

You got this error?

java.lang.StackOverflowError
at yeti.lang.RangeIter.next(ListRange.java:46)
at yeti.lang.FilterList.filter(FilterList.java:48)
at yeti.lang.FilterList.rest(FilterList.java:54)

I tried and got this, but it's not directly a TCO bug, but a problem
with lazy list construction in filter, as it's building the following
construct:

filter (_ ) (filter (_ ) (filter (_ ) (filter (_ ) ...)))

... and then the filter implementation in library recursively calculates
the filter tail over each of the nested filtered streams. I'll try to
think some fix for that, in the mean time you could use strict arrays as
workaround:

primes ps ns =
(p = head ns;

ns' = array (filter (_ n = (n % p != 0)) ns);
ps' = p :: ps;
if empty? ns' then ps' else primes ps' (list ns') fi);

There was actually a TCO bug in versions prior to 0.9.4, but this example
shouldn't trigger it (afaik).

[Jean-Francois Poilpret]

On 26-02-2012 19:33, Madis Janson wrote:
>
> On Thu, 23 Feb 2012, Jean-Francois Poilpret wrote:
>
>> Hi,
>>
>> while programming some katas in Yeti, I developed the following
>> function to find primes according to sieve of Erasthothenes:
>>
>> primes ps ns =
>> (p = head ns;
>> ns' = filter (_ n = (n % p != 0)) ns;
>> ps' = p :: ps;
>> if empty? ns' then ps' else primes ps' ns' fi);
>>
>> primes' n = primes [] [2..n] |> reverse;
>>
>> It worked fine until n = 80000, but I started to get stack overflows
>> with n = 85000.
>> I had the impression that primes ps ns was written in a way to enable
>> tail call optimisation, but it seems TCO is not used here.
>>
>> Did I do something wrong?
>
> You got this error?
>
> java.lang.StackOverflowError
> at yeti.lang.RangeIter.next(ListRange.java:46)
> at yeti.lang.FilterList.filter(FilterList.java:48)
> at yeti.lang.FilterList.rest(FilterList.java:54)

Yes, it was about this pattern, although it differed slightly, based on
the machine I ran it on (probably due to varying versions of yeti, it
could also differ based on the previous calculations I made with the REPL).

> I tried and got this, but it's not directly a TCO bug, but a problem
> with lazy list construction in filter, as it's building the following
> construct:
>
> filter (_ ) (filter (_ ) (filter (_ ) (filter (_ ) ...)))
>
> ... and then the filter implementation in library recursively
> calculates the filter tail over each of the nested filtered streams.
> I'll try to think some fix for that, in the mean time you could use
> strict arrays as workaround:
>
> primes ps ns =
> (p = head ns;
> ns' = array (filter (_ n = (n % p != 0)) ns);
> ps' = p :: ps;
> if empty? ns' then ps' else primes ps' (list ns') fi);

Yes, now it works fine (I was able to calculate all primes under
1,000,000 !)
But still, isn't this problem a bit dangerous for any developer using
filter this way (without arrays)?
Is there any way this can be fixed (without the array workaround)?

> There was actually a TCO bug in versions prior to 0.9.4, but this
> example shouldn't trigger it (afaik).

I tested only with 0.9.4+ (but different snapshots).

Jean-Fran�ois