[Shootout-list] Many tests cheat

[Einar Karttunen]

On 03.11 18:16, skaller wrote:
> On Wed, 2004-11-03 at 16:58, Isaac Gouy wrote:
> > > And mine is that it doesn't, and cannot.
> > > (pure) FPL's cannot ever provide general arrays
> > > (it is believed .. though not proven yet).
> > 
> > *general* arrays - are they different than arrays?
> 
> By general arrays I mean arrays that can be used the
> same way a C array can. In Ocaml you can do this (psuedo code):
> 
> let f a x = 
> 	if x > 0 then begin
> 		a.[1] = x; 
> 		f a (x-1)
> 	end
> 	else a.[1]
> 
> f a 99

Actually a sufficiently clever compiler could optimize that.
First of recursion is transformed into a loop:

f a x = while(x > 0) { a[1] = x; x--; }; return a[1];

This is clearly legal as our read and write sets do not overlap.
Now we can drop multiple writes to the same storage location 
and do some arithmetic playing with the loop:

f a x = a[1] = 1; return a[1];

This seems to be clearly O(1).

> Then it makes no difference whether you're using Haskell
> or Clean, this code cannot work. It isn't possible.
> Either referential transparency or O(1) performance
> will be lost. There's no way around this, the language
> involved doesn't matter. As mentioned, the best known
> implementation of functional arrays is still not O(1),
> and most people believe it can be proven functional
> array do not exist -- although no proof has been produced.

But we don't want functional arrays in the tests and the languages
provide ways to use non-functional arrays, so what is the point. 
If functional arrays would be needed then C would need them too
and things would get O(log n) there too.

> That doesn't mean *all* calls are tail recursive.
> In the same way, only *some* uses of arrays admit
> a destructive update optimisation.

True. And now think about that as compared to arrays:

Functional               Imperative
=======================================
tail-recursion           loop
non-tail recursion       non-tail recursion or loop + explicit stack
mutable arrays*          normal arrays
functional arrays        trees / functional arrays 

* monadic or uniqueness typing.

- Einar Karttunen