[Shootout-list] Many tests cheat

[skaller]

On Wed, 2004-11-03 at 18:29, Einar Karttunen wrote:
> 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.

yes I know, that's why I said a bit later to please
imagine a slightly more complex example -- such that
the whole array had to be copied, and also that
the recursion wasn't tail etc.

> 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. 

The point is that when you say 'measures array access'
I am saying the specification is unclear what an array
actually is. In general, that requires random O(1) read/write
access which cannot be provided in general in an FPL.

It may be possible in some cases to use functional arrays
to get a similar looking solution and then have it optimise
so the access is O(1). It would seem Clean can even
guarrantee that.

But in general, a suitable test must fail pure FPLs
because they can't provide arrays. [I mean,
there really *should* be one test which knocks
FPLs hard]

The way to fail them isn't to argue about what an array
looks like in the language. It has to be by bounding
time and memory so that contigous storage is the only
viable solution. That makes the test truly independent
of the language, and independent of any argument about
what an array is for that language, and whether
it meets the constrains or not -- an operational constraint
simply fails the test by exceeding bounds during the
testing process.

> If functional arrays would be needed then C would need them too
> and things would get O(log n) there too.

Yes indeed, but there are circumstances where C mutable
arrays will provide a solution that cannot be coded
in a pure FPL (by which I mean suitably fast).

Obviously, any *particular* C solution has a functional
equivalent which can run at the same speed, but will not
always be possible to mechanically find that with FPL
optimiser -- if it were possible, FPLs would rule!
But I suspect its the halting problem  .. :)

It's actually good to see heavy analysis of functional
data structures in Osakis book (Purely functional
data structures) because it shows a lot more problems
can be solved efficiently with FPLs that one might think.
Never-the-less imperative languages, like Ocaml, which
combine both functional and imperative features,
seem to offer the opportunity to work around any limitation
like this with an imperative technique if necessary,
perhaps at the expense of the purely functional code
generated being less optimal (because of eager evaluation
and side effects etc).


> mutable arrays*          normal arrays
> functional arrays        trees / functional arrays 
> 
> * monadic or uniqueness typing.

Yes, and some problem will fail to have a suitable typing.

Basically this has to be the case, otherwise there
would be no point trying to get fast functional arrays,
you'd just use the functional ones that looked mutable
all the time and performed like C arrays.

So clearly you can't do this all the time.

In any case my point is that stating a specification
that the test 'must use an array' is meaningless.
[The idea is just fine as a motivation!]

That's really the point -- I don't understand the
intended constraint, any other way than it meaning
O(1) performance for random read/write .. and so that's
what really should be stated .. this has the advantage
of annoying Brent by needing extra checking on the
run time behaviour, but it eliminates any possible
way of cheating, including non-deliberate cheating.

I don't want to be extreme here -- I'm just suggesting
a move to tests more based on observables where any
program is ok if it gives the right answer within
memory and time limits, rather than arguing if 
a test is 'fair' or not. That's why the topic
'many tests cheat' .. it isn't so easy to say if 
a test cheats of not sometimes.

The example of Felix Exception test is a good one
(raised by Isaac Gouy).

I really do NOT know if that should be considered cheating
or not. But it isn't the worst offender by any means:
several Felix test just embed part or all of the C solution.
Some of the tests are supposed to measure the native language
features -- eg Python should use the Pythonic kind of arrays
(lists) and not use a C extension.

Well, Felix is designed for C embedding. So it isn't
at all clear whether the 'method call' test is a valid
solution -- my code just defines the classes in C++,
and then uses some Felix wrappers to call the C++ code.

If it were Python doing that I'd probably agree the
program is cheating. And perhaps when and if I provide
Felix with proper classes I might agree the solution
is also cheating.

But right now I just do *not* know if the test is cheating
or not, given that my advice to people wanting to do OO
with Felix at the moment is to do it in C++ and wrap it:
C++ does classes reasonable well, so I don't find a need
to provide native ones. OTOH C++ does FP really badly,
and Felix is concentrating on that instead.

There actually *is* an 'obj' construction in Felix,
which works like CLOS -- an obj is a function that
returns a structure of function closures bound
to the functions scope. Apart from the fact method
calls would be much slower using that constuction
at present <ducks>, there are some other problems with it,
so I didn't use it.

Here, the question is 'what do you mean by *native*
technique'. The answer isn't so obvious for Felix:
embedding C/C++ is definitely a native technique,
there are more constructions for doing that than 
anything else I think. Still, the requirement
for method calls test isn't for using native embedding,
and the native *felix* code is doing ordinary function
calls. .. of course Python does that too, methods are
also just functions bound to some object... no Isaac I
don't want an argument .. I'm saying you could legitimately
disagree and that is the point: it just isn't clear
given a novel solution to a problem what the meaning 
of a specification which uses terminology designed
for more conventional systems actually means.


-- 
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