[Shootout-list] Many tests cheat

[skaller]

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


In Ocaml this code isn't functional, and it returns 0.
If the notation

	a.[1] = x

were a functional update, the correct answer would be 99.

Obviously the difference is that for referential transparency,
any changes made to the array in the recursive calls
must be invisible to the caller. If you can imagine
a slightly more complex example now please ..?

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.

A purely functional language ensuring O(1) access to
arrays can certainly exist, but they're not general arrays.
Code like the above cannot be made to work. It is more
like saying you don't need loops in FPLs, you can use
recursion. In fact, it can be proven (but is obvious anyhow)
that you can always represent a loop with a tail call,
and you can always recognize tail calls, so you can show
FPLs can loop with O(1) memory overhead. 

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

The important feature of Clean is that they found a general
way to embed enough information in the type system to
determine when the destructive update optimisation was possible,
and turn that around into a guarrantee. In other systems it
was 'maybe the compiler will recognize this, and maybe not'.
In Clean, there's no such problem -- its a statically ensured
promise.

[And after looking at the docs I'd say it's dang close
to magic that they did this .. :]

IF you use arrays and the program compiles without a type
error THEN the access is O(1) [that is, it's an array!]

The difficulty is that your code might NOT compile.
In particular for the 'slightly more complex' example
given above it can't possibly do so .. I know because
I constructed it so there cannot be a solution.

By that I mean .. there is NO possible solution,
neither in Clean, Haskell, or in C. To get the right
answer you have to copy the array, because the requirement
is for the array to appear immutable except for local
updates, and copying is O(n).

It is certainly possible to get the right answer
with a 'functional array' -- obviously that can be done
in C as well. It's just that such a data structure cannot
be O(1) access, so it isn't an array.



> > Well I guess I am loathe to spend a lot of time
> > working on something which won't be accepted.
> > I'd prefer to see a consenus on principles before
> > doing any detail work.
> 
> Nothing ventured.

There's a difference between a calculated risk and 
a place even angels fear to tread :)

-- 
John Skaller, mailto:skaller@users.sf.net
voice: 061-2-9660-0850, 
snail: PO BOX 401 Glebe NSW 2037 Australia
Checkout the Felix programming language http://felix.sf.net