[clean-list] Recursive array algorithms - continued

[Ronny Wichers Schreur]

Mike Rainey writes (to the Clean discussion list):

> After making the following change, stack size remains constant.
> 
> mm::*{#Real} !MortonIx !MortonIx !MortonIx !Int -> *{#Real}
> 
> ---> mm::!*{#Real} !MortonIx !MortonIx !MortonIx !Int -> *{#Real}
> 
> Does this mean Clean is clever enough to make mm tail-recursive?

No. With or without the extra strictness annotation, the
recursion depth of mm is lg2 n (not constant as you say). Of
course lg2 n is a small value.

Your original program builds a large closure of the form
(update (update (update ...))). It's during the evaluation of
this closure that the stack overflows. The strictness annotation
accomplishes that the update to the array is done immediately
for every base case.

It's unfortunate that you have to specify this strictness
annotation. The function mm *is* strict in its array argument,
but the algorithm we use for strictness analysis can't figure
that out. In particular, it can't handle the nested calls to mm.


Cheers,

Ronny Wichers Schreur