[Shootout-list] Rule 30

[John Skaller]

On Thu, 2005-05-19 at 16:30 -0700, Isaac Gouy wrote:
> --- Jon Harrop <jon@ffconsultancy.com> wrote:
> -snip-
> > Some implementations may precompute it without the reader's
> > knowledge. More worryingly, some language implementations may
> > precompute it without the author's knowledge.
> 
> Which do?

ALL compilers do constant folding which is a trivial
example of this. Some language like Haskell using
Lazy evaluation form closures which cache the result
of a computation for a function, so the function
is not called if the result isn't used, and only
called once if it is. Ocaml can do this too,
but you have to specifically annotate the code.

Felix certainly does some optimisations which
eliminate useless computations systematically,
though not the same kind as Haskell does,
which lead to it trashing everyone on two of the
original tests (exception handling and the chain
of messages). 

In both these cases *I* was surprised
and had to have a close look to see what was happening.

I think the point is *ALL* high level language translators
operate by transforming sugary source code into complex
low level terms, and then reducing the terms, before
finally generating code, and the authors of such
term rewriting systems rarely understand fully any
particular compilation: they're lucky to understand
the theory, or what happens in one or two heavily
studied cases -- there a lots of papers both on
the theory, and making measurements on practical
reduction systems (because the semantics doesn't tell
you the performance).

Some such systems are surprising: for example the Ocaml
type inference engine turns out to be unable to
to compute some simple types in a reasonable time:
turns out HM-polymorphism is NP-complete .. the big
surprise is that it works reasonably well in practice.

The bottom line is that it isn't just a matter
of 'pre-computing' the result, that is just a special
case of partial evaluation: the point is that ALL 
compilers are partial evaluators, so it is necessary
to set problems where the extent of the possible evaluation
is limited by leaving enough variables of the problem
open until 'run time'.

Alternatively -- count compile time as part of the problem,
to penalise partial evaluators (and in general slow compilers
like gcc with optimisation flags on) when the inputs are
small, but reward them when the inputs are large: that,
after all, is a real world tradeoff between using a compiler
like gcc versus an interpreter like Python.

I'd really like to see a graph of Python vs C, where Python
wins easily for small N .. and C wins for large N,
and actually find the N where they're equal!

Even better -- count developer time for the code as well:

The annual Functional Programming Competition does just that
(and quite a few FPLers were undoubtedly peeved when one
year C++ won the competition :)

-- 
John Skaller, skaller at users.sf.net
PO Box 401 Glebe, NSW 2037, Australia Ph:61-2-96600850 
Download Felix here: http://felix.sf.net